Approximation algorithms for the traveling repairman and speeding deliveryman problems. (English) Zbl 1277.68297

Summary: Constant-factor, polynomial-time approximation algorithms are presented for two variations of the traveling salesman problem with time windows. In the first variation, the traveling repairman problem, the goal is to find a path that visits the maximum possible number of locations during their time windows. In the second variation, the speeding deliveryman problem, the goal is to find a path that uses the minimum possible speedup to visit all locations during their time windows. For both variations, the time windows are of unit length, and the distance metric is based on a weighted, undirected graph. Algorithms with improved approximation ratios are given for the case when the input is defined on a tree rather than a general graph. The algorithms are also extended to handle time windows whose lengths fall in any bounded range.


68W25 Approximation algorithms
05C85 Graph algorithms (graph-theoretic aspects)
90C27 Combinatorial optimization


Full Text: DOI


[1] Arkin, E.M., Mitchell, J.S.B., Narasimhan, G.: Resource-constrained geometric network optimization. In: Proc. 14th Symp. on Computational Geometry, pp. 307–316. ACM, New York (1998)
[2] Awerbuch, B., Azar, Y., Blum, A., Vempala, S.: New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM J. Comput. 28(1), 254–262 (1998) · Zbl 0916.90256
[3] Bansal, N., Blum, A., Chawla, S., Meyerson, A.: Approximation algorithms for deadline-TSP and vehicle routing with time-windows. In: Proc. 36th ACM Symp. on Theory of Computing, pp. 166–174 (2004) · Zbl 1192.90216
[4] Bar-Yehuda, R., Even, G., Shahar, S.: On approximating a geometric prize-collecting traveling salesman problem with time windows. J. Algorithms 55(1), 76–92 (2005) · Zbl 1066.90098
[5] Blum, A., Chawla, S., Karger, D.R., Lane, T., Meyerson, A., Minkoff, M.: Approximation algorithms for orienteering and discounted-reward TSP. SIAM J. Comput. 37(2), 653–670 (2007) · Zbl 1137.90687
[6] Chawla, S.: Graph algorithms for planning and partitioning. PhD thesis, Carnegie Mellon University (2005)
[7] Chekuri, C., Korula, N.: Approximation algorithms for orienteering with time windows (2007). arXiv:0711.4825
[8] Chekuri, C., Kumar, A.: Maximum coverage problem with group budget constraints and applications. In: 7th Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems. LNCS, vol. 3122, pp. 72–83. Springer, Berlin (2004) · Zbl 1106.90062
[9] Chekuri, C., Korula, N., Pál, M.: Improved algorithms for orienteering and related problems. In: Proc. 19th ACM-SIAM Symp. on Discrete Algorithms, pp. 661–670. Society for Industrial and Applied Mathematics, Philadelphia (2008) · Zbl 1192.90162
[10] Chen, K., Har-Peled, S.: The orienteering problem in the plane revisited. In: Proc. 22nd Symp. on Computational Geometry, pp. 247–254. ACM, New York (2006) · Zbl 1153.65319
[11] Focacci, F., Lodi, A., Milano, M.: Solving TSP with time windows with constraints. In: Proc. 1999 Int. Conf. on Logic Programming, pp. 515–529. MIT Press, Cambridge (1999)
[12] Focacci, F., Lodi, A., Milano, M.: Embedding relaxations in global constraints for solving TSP and TSPTW. Ann. Math. Artif. Intell. 34(4), 291–311 (2002) · Zbl 1002.68159
[13] Frederickson, G.N., Wittman, B.: Approximation algorithms for the traveling repairman and speeding deliveryman problems with unit-time windows. In: APPROX-RANDOM. LNCS, vol. 4627, pp. 119–133. Springer, Berlin (2007) · Zbl 1171.90508
[14] Frederickson, G.N., Wittman, B.: Speedup in the traveling repairman problem with unit time windows (2009). arXiv:0907.5372
[15] Frederickson, G.N., Wittman, B.: Speedup in the traveling repairman problem with constrained time windows (2011). arXiv:1101.3960
[16] Frederickson, G.N., Wittman, B.: Two multivehicle routing problems with unit-time windows (2011). arXiv:1101.3953
[17] Hoogeveen, J.: Analysis of Christofides’ heuristic: some paths are more difficult than cycles. Oper. Res. Lett. 10(5), 291–295 (1991) · Zbl 0748.90071
[18] Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)
[19] Karuno, Y., Nagamochi, H., Ibaraki, T.: Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks. Networks 39(4), 203–209 (2002) · Zbl 1024.90008
[20] Knuth, D.E.: The Art of Computer Programming, 1st edn. Seminumerical Algorithms, vol. 2. Addison-Wesley, Reading (1969) · Zbl 0191.18001
[21] Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Schmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)
[22] Nagarajan, V., Ravi, R.: Poly-logarithmic approximation algorithms for directed vehicle routing problems. In: APPROX-RANDOM. LNCS, vol. 4627, pp. 257–270. Springer, Berlin (2007) · Zbl 1171.90511
[23] Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1–11 (1993) · Zbl 0778.90057
[24] Tsitsiklis, J.N.: Special cases of traveling salesman and repairman problems with time windows. Networks 22, 263–282 (1992) · Zbl 0819.90124
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.