Approximation algorithms for deadline-TSP and vehicle routing with time-windows

ABSTRACT

Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v, we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible by their deadlines. We also consider the more general Vehicle Routing with Time-Windows problem, in which each node v also has a release-time R(v) and the goal is to visit as many nodes as possible within their "time-windows" [R(v),D(v)]. No good approximations were known previously for these problems on general metric spaces. We give an O(logn) approximation algorithm for Deadline-TSP, and extend this algorithm to an O(log²n) approximation for the Time-Window problem. We also give a bicriteria approximation algorithm for both problems: Given an ε>0, our algorithm produces a (1/ε) approximation, while exceeding the deadlines by a factor of 1+ε. We use as a subroutine for these results a constant-factor approximation that we develop for a generalization of the orienteering problem in which both the start and the end nodes of the path are fixed. In the process, we give a 3-approximation to the orienteering problem, improving on the previously best known 4-approximation of [6].

REFERENCES

• 1: Bibliography on vehicle routing, http://people. freenet. de/Emden-Weinert/VRP. html.
• 2: A. Allahverdi, J. Gupta, and T. Aldowaisan. A review of scheduling research involving setup considerations. Omega, Int. Journal of Management Science 27:219--239, 1999.
• 3: Esther M. Arkin , Joseph S. B. Mitchell , Giri Narasimhan, Resource-constrained geometric network optimization, Proceedings of the fourteenth annual symposium on Computational geometry, p.307-316, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276919]
• 4: Baruch Awerbuch , Yossi Azar , Avrim Blum , Santosh Vempala, New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen, SIAM Journal on Computing, v.28 n.1, p.254-262, Feb. 1999 [doi>10.1137/S009753979528826X]
• 5: R. Bar-Yehuda, G. Even, and S. Shahar. On approximating a geometric prize-collecting traveling salesman. In Proceedings of the European Symposium on Algorithms 2003.
• 6: Avrim Blum , Shuchi Chawla , David R. Karger , Terran Lane , Adam Meyerson , Maria Minkoff, Approximation Algorithms for Orienteering and Discounted-Reward TSP, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.46, October 11-14, 2003
• 7: J. Brun and P. Downey. Complexity of task sequencing with deadlines, set-up times and changeover costs. SIAM Journal on Computing 7(4):393--404, 1978.
• 8: C. Chekuri and A. Kumar. Maximum coverage problem with group budget constraints and applications, Manuscript, 2004.
• 9: Martin Desrochers , Jacques Desrosiers , Marius Solomon, A new optimization algorithm for the vehicle routing problem with time windows, Operations Research, v.40 n.2, p.342-354, March–April 1992 [doi>10.1287/opre.40.2.342]
• 10: M. Desrochers, J. Lenstra, M. Savelsbergh, and F. Soumis. Vehicle routing with time windows: optimization and appr ximation. In B. L. Golden, A. A. Assad (eds. ). Vehicle Routing: Methods and Studies, North-Holland, Amsterdam pages 65--84, 1988.
• 11: B. Golden, L. Levy, and R. Vohra. The orienteering problem. Naval Research Logistics 34:307--318, 1987.
• 12: M. Gravel, W. Price, and C. Gagn. Scheduling jobs in a alcan aluminium factory using a genetic algorithm. International Journal of Production Research 38(13):3031--3041, 2000.
• 13: C. Jordan. A two-phase genetic algorithm to solve variants of the batch sequencing problem. International Journal of Production Research (UK) 36(3):745--760, 1998.
• 14: M. Kantor and M. Rosenwein. The orienteering problem with time windows. Journal of the Operational Research Society 43:629--635,1992.
• 15: Yoshiyuki Karuno , Hiroshi Nagamochi, A 2-Approximation Algorithm for the Multi-vehicle Scheduling Problem on a Path with Release and Handling Times, Proceedings of the 9th Annual European Symposium on Algorithms, p.218-229, August 28-31, 2001
• 16: A. W. J. Kolen , A. H. G. R. Kan , H. W. J. M. Trienekens, Vehicle routing with time windows, Operations Research, v.35 n.2, p.266-273, March-April 1987 [doi>10.1287/opre.35.2.266]
• 17: M. Savelsbergh. Local search for routing problems with time windows. Annals of Operations Research 4: 285--305, 1985.
• 18: K. Tan, L. Lee, and K. Zhu. Heuristic methods for vehicle routing problem with time windows. In Proceedings of the 6th AI and Math 2000.
• 19: S. Thangiah. Vehicle Routing with Time Windows using Genetic Algorithms, Application Handbook of Genetic Algorithms: New Frontiers, Volume II. Lance Chambers (Ed. ) CRC Press, 1995.
• 20: Sam R. Thangiah , Ibrahim H. Osman , Rajini Vinayagamoorthy , Tong Sun, Algorithms for the vehicle routing problems with time deadlines, American Journal of Mathematical and Management Sciences, v.13 n.3-4, p.323-355, 1993
• 21: J. Tsitsiklis. Special cases of traveling salesman and repairman problems with time windows. Networks 22: 263--282, 1992.
• 22: J. Wisner and S. Siferd. A survey of u. s. manufacturing practices in make-to-order machine shops. Production and Inventory Management Journal 1:1--7, 1995.
• 23: W. Yang and C. Liao. Survey of scheduling research involving setup times. International Journal of Systems Science 30(2): 143--155, 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, orienteering, traveling salesman problem, vehicle routing