Online routing problems: value of advanced information as improved competitive ratios

Online routing problems: value of advanced information as improved competitive ratios

0.00 Avg rating0 Votes
Article ID: iaor20072490
Country: United States
Volume: 40
Issue: 2
Start Page Number: 200
End Page Number: 210
Publication Date: May 2006
Journal: Transportation Science
Authors: ,
Keywords: optimization
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.

Reviews

Required fields are marked *. Your email address will not be published.