Generalized online routing: New competitive ratios, resource augmentation, and asymptotic analyses

• 成果类型: Article
• 署名作者: Jaillet, Patrick; Wagner, Michael R.
• 署名单位: Massachusetts Institute of Technology (MIT); California State University System; California State University East Bay
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1070.0450
• 发表日期: 2008
• 页码: 745-757

摘要

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.