This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Jaillet, P. Articles by Wagner, M. R. Search for Related Content

Online Routing Problems: Value of Advanced Information as Improved Competitive Ratios

Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
jaillet{at}mit.edu
mikew{at}mit.edu

We consider online versions of the traveling salesman problem (TSP) and traveling repairman problem (TRP) where instances are not known in advance. Cities (points) to be visited are revealed over time, while the server is en route serving previously released requests. These problems are known in the literature as the online TSP (TRP, respectively). The corresponding offline problems are the TSP (TRP) with release dates, problems where each point has to be visited at or after a given release date. In the current literature, the assumption is that a request becomes known at the time of its release date. In this paper we introduce the notion of a request’s disclosure date, the time when a city’s location and release date are revealed to the server. In a variety of disclosure date scenarios and metric spaces, we give new online algorithms and quantify the value of this advanced information in the form of improved competitive ratios. We also provide a general result on polynomial-time online algorithms for the online TSP.

Key Words: online routing problems; advanced information; competitive ratio
History: Received: April 2005; revised: November 2005; accepted: January 2006.

This article has been cited by other articles:

				P. Jaillet and M. R. Wagner Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses Operations Research, May 1, 2008; 56(3): 745 - 757. [Abstract] [PDF]