Algorithms for the on-line travelling salesman
In this paper the problem of efficiently serving a sequence of requests presented in an on-line fashion located at points of a metric space is considered. We call this problem the On-Line Travelling Salesman Problem (OLTSP). It has a variety of relevant applications in logistics and robotics. We con...
Guardado en:
| Publicado: |
2001
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v29_n4_p560_Ausiello http://hdl.handle.net/20.500.12110/paper_01784617_v29_n4_p560_Ausiello |
| Aporte de: |
| id |
paper:paper_01784617_v29_n4_p560_Ausiello |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_01784617_v29_n4_p560_Ausiello2023-06-08T15:19:16Z Algorithms for the on-line travelling salesman Competitive analysis On-line algorithms Travelling salesman problem Vehicle routing Logistics Problem solving Robotics Traveling salesman problem On-line algorithms Algorithms In this paper the problem of efficiently serving a sequence of requests presented in an on-line fashion located at points of a metric space is considered. We call this problem the On-Line Travelling Salesman Problem (OLTSP). It has a variety of relevant applications in logistics and robotics. We consider two versions of the problem. In the first one the server is not required to return to the departure point after all presented requests have been served. For this problem we derive a lower bound on the competitive ratio of 2 on the real line. Besides, a 2.5-competitive algorithm for a wide class of metric spaces, and a 7/3-competitive algorithm for the real line are provided. For the other version of the problem, in which returning to the departure point is required, we present an optimal 2-competitive algorithm for the above-mentioned general class of metric spaces. If in this case the metric space is the real line we present a 1.75-competitive algorithm that compares with a ≈1.64 lower bound. 2001 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v29_n4_p560_Ausiello http://hdl.handle.net/20.500.12110/paper_01784617_v29_n4_p560_Ausiello |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Competitive analysis On-line algorithms Travelling salesman problem Vehicle routing Logistics Problem solving Robotics Traveling salesman problem On-line algorithms Algorithms |
| spellingShingle |
Competitive analysis On-line algorithms Travelling salesman problem Vehicle routing Logistics Problem solving Robotics Traveling salesman problem On-line algorithms Algorithms Algorithms for the on-line travelling salesman |
| topic_facet |
Competitive analysis On-line algorithms Travelling salesman problem Vehicle routing Logistics Problem solving Robotics Traveling salesman problem On-line algorithms Algorithms |
| description |
In this paper the problem of efficiently serving a sequence of requests presented in an on-line fashion located at points of a metric space is considered. We call this problem the On-Line Travelling Salesman Problem (OLTSP). It has a variety of relevant applications in logistics and robotics. We consider two versions of the problem. In the first one the server is not required to return to the departure point after all presented requests have been served. For this problem we derive a lower bound on the competitive ratio of 2 on the real line. Besides, a 2.5-competitive algorithm for a wide class of metric spaces, and a 7/3-competitive algorithm for the real line are provided. For the other version of the problem, in which returning to the departure point is required, we present an optimal 2-competitive algorithm for the above-mentioned general class of metric spaces. If in this case the metric space is the real line we present a 1.75-competitive algorithm that compares with a ≈1.64 lower bound. |
| title |
Algorithms for the on-line travelling salesman |
| title_short |
Algorithms for the on-line travelling salesman |
| title_full |
Algorithms for the on-line travelling salesman |
| title_fullStr |
Algorithms for the on-line travelling salesman |
| title_full_unstemmed |
Algorithms for the on-line travelling salesman |
| title_sort |
algorithms for the on-line travelling salesman |
| publishDate |
2001 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v29_n4_p560_Ausiello http://hdl.handle.net/20.500.12110/paper_01784617_v29_n4_p560_Ausiello |
| _version_ |
1768543654736035840 |