Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses

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: Department of Management, California State University East Bay, Hayward, California 94542

Operations Research, 2008, vol. 56, issue 3, 745-757

Abstract: We consider online routing optimization problems where the objective is to minimize the time needed to visit a set of locations under various constraints; the problems are online because the set of locations are revealed incrementally over time. We consider two main problems: (1) the online traveling salesman problem (TSP) with precedence and capacity constraints, and (2) the online TSP with m salesmen. For both problems we propose online algorithms, each with a competitive ratio of 2; for the m -salesmen problem, we show that our result is best-possible. We also consider polynomial-time online algorithms.We then consider resource augmentation, where we give the online servers additional resources to offset the powerful offline adversary advantage. In this way, we address a main criticism of competitive analysis. We consider the cases where the online algorithm has access to faster servers, servers with larger capacities, additional servers, and/or advanced information. We derive improved competitive ratios. We also give lower bounds on the competitive ratios under resource augmentation, which in many cases are tight and lead to best-possible results.Finally, we study online algorithms from an asymptotic point of view. We show that, under general stochastic structures for the problem data, unknown and unused by the online player, the online algorithms are almost surely asymptotically optimal. Furthermore, we provide computational results that show that the convergence can be very fast.

Keywords: online optimization; transportation; analysis of algorithms (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1070.0450 (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:oropre:v:56:y:2008:i:3:p:745-757

Access Statistics for this article

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