×

zbMATH — the first resource for mathematics

A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots. (English) Zbl 1338.90358
Summary: We study a natural extension of the classical traveling salesman problem (TSP) in the situation where multiple salesmen are dispatched from a number of different depots. As with the TSP, this problem is motivated by a large range of applications in vehicle routing. Although it is known to have a 2-approximation algorithm, whether the problem has a 3/2-approximation algorithm, as is the case with the well-known Christofides heuristic for the TSP, remains an open question. We answer this question positively by providing a 3/2-approximation algorithm for the problem with a fixed number of depots. The algorithm uses an edge exchange strategy, and its analysis hinges on a newly discovered exchange property of matroids. In addition, the algorithm is applied to multidepot extensions of other TSP variants, and we show for the first time, to our knowledge, that for these multidepot extensions the same best constant approximation ratios can be achieved as for their respective single-depot cases.

MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arkin EM, Hassin R, Levin A (2006) Approximations for minimum and min-max vehicle routing problems. J. Algorithms 59(1): 1-18. CrossRef · Zbl 1112.68135
[2] Bae J, Rathinam S (2012) Approximation algorithms for multiple terminal, Hamiltonian path problems. Optim. Lett. 6(1):69-85. CrossRef · Zbl 1259.90106
[3] Chandler PR, Pachter M (1998) Research issues in autonomous control of tactical UAVs. Proc. Amer. Control Conf. 1998, Vol. 1 (IEEE, Piscataway, NJ), 394-398. CrossRef
[4] Chandler PR, Pachter M, Swaroop D, Fowler JM, Howlett JK, Rasmussen S, Schumacher C, Nygard K (2002) Complexity in UAV cooperative control. Proc. Amer. Control Conf. 2002, Vol. 3 (IEEE, Piscataway, NJ), 1831-1836. CrossRef
[5] Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh.
[6] Foulds LR, Wilson JM (1997) A variation of the generalized assignment problem arising in the New Zealand dairy industry. Ann. Oper. Res. 69:105-114. CrossRef · Zbl 0880.90035
[7] Frederickson GN (1979) Approximation algorithms for some postman problems. J. ACM 26(3):538-554. CrossRef · Zbl 0405.90076
[8] Giosa ID, Tansini IL, Viera IO (2002) New assignment algorithms for the multi-depot vehicle routing problem. J. Oper. Res. Soc. 53(9):977-984. CrossRef · Zbl 1079.90030
[9] Guttmann-Beck N, Hassin R, Khuller S, Raghavachari B (2000) Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 28(4):422-437. CrossRef · Zbl 0963.68226
[10] Hoogeveen JA (1991) Analysis of Christofides’ heuristic: Some paths are more difficult than cycles. Oper. Res. Lett. 10(5): 291-295. CrossRef · Zbl 0748.90071
[11] Irnich S (2008) A unified modeling and solution framework for vehicle routing and local search-based metaheuristics. INFORMS J. Comput. 20(2):270-287. Link · Zbl 1243.90225
[12] Malik W, Rathinam S, Darbha S (2007) An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem. Oper. Res. Lett. 35(6):747-753. CrossRef · Zbl 1169.90436
[13] Papadimitriou CH, Steiglitz K (1998) Approximation algorithms for the traveling salesman problem. Papadimitriou CH, Steiglitz K, eds. Combinatorial Optimization: Algorithms and Complexity (Dover Publications, Mineola, NY), 410-419.
[14] Potvin J-Y (2009) State-of-the art review–Evolutionary algorithms for vehicle routing. INFORMS J. Comput. 21(4):518-548. Link · Zbl 1243.90001
[15] Rathinam S, Sengupta R (2010) 3/2-approximation algorithm for two variants of a 2-depot Hamiltonian path problem. Oper. Res. Lett. 38(1):63-68. CrossRef · Zbl 1182.90074
[16] Rathinam S, Sengupta R, Darbha S (2007) A resource allocation algorithm for multivehicle systems with nonholonomic constraints. IEEE Trans. Automation Sci. Engrg. 4(1):98-104. CrossRef
[17] Renaud J, Laporte G, Boctor FF (1996) A tabu search heuristic for the multi-depot vehicle routing problem. Comput. Oper. Res. 23(3):229-235. CrossRef · Zbl 0855.90055
[18] Schrijver A (2003) Matroids. Schrijver A, ed. Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, Vol. 24 (Springer, Berlin), 651-687.
[19] Vygen J (2012) New approximation algorithms for the TSP. Optima: Math. Optim. Soc. Newsletter 90:1-12.
[20] Xu Z, Xu L, Rodrigues B (2011) An analysis of the extended Christofides heuristic for the k-depot TSP. Oper. Res. Lett. 39(3): 218-223. CrossRef · Zbl 1219.90149
[21] Yadlapalli S, Malik WA, Darbha S, Pachter M (2009) A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem. Nonlinear Anal.: Real World Applications 10(4): 1990-1999. CrossRef · Zbl 1163.90722
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.