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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M.
Formato:	JOUR
Materias:	Competitive analysis On-line algorithms Travelling salesman problem Vehicle routing Logistics Problem solving Robotics Traveling salesman problem Algorithms
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_01784617_v29_n4_p560_Ausiello
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_01784617_v29_n4_p560_Ausiello
record_format	dspace
spelling	todo:paper_01784617_v29_n4_p560_Ausiello2023-10-03T15:08:17Z Algorithms for the on-line travelling salesman Ausiello, G. Feuerstein, E. Leonardi, S. Stougie, L. Talamo, M. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Ausiello, G. Feuerstein, E. Leonardi, S. Stougie, L. Talamo, M. 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.
format	JOUR
author	Ausiello, G. Feuerstein, E. Leonardi, S. Stougie, L. Talamo, M.
author_facet	Ausiello, G. Feuerstein, E. Leonardi, S. Stougie, L. Talamo, M.
author_sort	Ausiello, G.
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
url	http://hdl.handle.net/20.500.12110/paper_01784617_v29_n4_p560_Ausiello
work_keys_str_mv	AT ausiellog algorithmsfortheonlinetravellingsalesman AT feuersteine algorithmsfortheonlinetravellingsalesman AT leonardis algorithmsfortheonlinetravellingsalesman AT stougiel algorithmsfortheonlinetravellingsalesman AT talamom algorithmsfortheonlinetravellingsalesman
_version_	1807314953312403456

Algorithms for the on-line travelling salesman

Ejemplares similares