A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots

References

• Arkin EM, Hassin R, Levin A (2006) Approximations for minimum and min-max vehicle routing problems. J. Algorithms 59(1): 1–18.Crossref, Google Scholar
• Bae J, Rathinam S (2012) Approximation algorithms for multiple terminal, Hamiltonian path problems. Optim. Lett. 6(1):69–85.Crossref, Google Scholar
• 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, Google Scholar
• 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, Google Scholar
• 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.Google Scholar
• 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, Google Scholar
• Frederickson GN (1979) Approximation algorithms for some postman problems. J. ACM 26(3):538–554.Crossref, Google Scholar
• 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, Google Scholar
• 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, Google Scholar
• Hoogeveen JA (1991) Analysis of Christofides’ heuristic: Some paths are more difficult than cycles. Oper. Res. Lett. 10(5): 291–295.Crossref, Google Scholar
• 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, Google Scholar
• 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, Google Scholar
• 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.Google Scholar
• Potvin J-Y (2009) State-of-the art review—Evolutionary algorithms for vehicle routing. INFORMS J. Comput. 21(4):518–548.Link, Google Scholar
• 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, Google Scholar
• 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, Google Scholar
• 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, Google Scholar
• Schrijver A (2003) Matroids. Schrijver A, ed. Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, Vol. 24 (Springer, Berlin), 651–687.Google Scholar
• Vygen J (2012) New approximation algorithms for the TSP. Optima: Math. Optim. Soc. Newsletter 90:1–12.Google Scholar
• 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, Google Scholar
• 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, Google Scholar