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 approximate to1.64 lower bound.

Algorithms for the on-line travelling salesman / Ausiello, Giorgio; E., Feuerstein; Leonardi, Stefano; L., Stougie; M., Talamo. - In: ALGORITHMICA. - ISSN 0178-4617. - 29:4(2001), pp. 560-581. [10.1007/s004530010071]

Algorithms for the on-line travelling salesman

AUSIELLO, Giorgio;LEONARDI, Stefano;
2001

Abstract

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 approximate to1.64 lower bound.
2001
competitive analysis; on-line algorithms; travelling salesman problem; vehicle routing
01 Pubblicazione su rivista::01a Articolo in rivista
Algorithms for the on-line travelling salesman / Ausiello, Giorgio; E., Feuerstein; Leonardi, Stefano; L., Stougie; M., Talamo. - In: ALGORITHMICA. - ISSN 0178-4617. - 29:4(2001), pp. 560-581. [10.1007/s004530010071]
File allegati a questo prodotto
File Dimensione Formato  
VE_2001_11573-255261.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 146.82 kB
Formato Adobe PDF
146.82 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/255261
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 136
  • ???jsp.display-item.citation.isi??? 109
social impact