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

Patrick Jaillet () and Michael R. Wagner ()
Additional contact information
Patrick Jaillet: Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Michael R. Wagner: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Transportation Science, 2006, vol. 40, issue 2, 200-210

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

Keywords: online routing problems; advanced information; competitive ratio (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (26)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1060.0147 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:40:y:2006:i:2:p:200-210

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().