This Article Full Text (PDF) e-companion 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 Google Scholar Google Scholar Articles by Jaillet, P. Articles by Wagner, M. R. Search for Related Content

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

Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Department of Management, California State University East Bay, Hayward, California 94542
jaillet{at}mit.edu
michael.wagner{at}csueastbay.edu

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.

Subject classifications: online optimization; transportation; analysis of algorithms.
History: Received May 2006; revision received February 2007; accepted April 2007.