Document Open Access Logo

A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of Depots

Authors Max Deppert , Matthias Kaul , Matthias Mnich

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.39.pdf
  • Filesize: 0.82 MB
  • 15 pages

Document Identifiers

Author Details

Max Deppert
  • Institute for Algorithms and Complexity, Hamburg University of Technology, Germany
Matthias Kaul
  • Institute for Algorithms and Complexity, Hamburg University of Technology, Germany
Matthias Mnich
  • Institute for Algorithms and Complexity, Hamburg University of Technology, Germany

Funding

Partially supported by DFG project MN 59/4-1.

Acknowledgements

The third author thanks L{á}szló Végh for inspiring discussions on multi-depot TSP and feedback on an earlier version.

Cite AsGet BibTex

Max Deppert, Matthias Kaul, and Matthias Mnich. A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of Depots. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.39

Abstract

One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is the Multiple TSP: a set of m ≥ 1 salespersons collectively traverses a set of n cities by m non-trivial tours, to minimize the total length of their tours. This problem can also be considered to be a variant of Uncapacitated Vehicle Routing, where the objective is to minimize the sum of all tour lengths. When all m tours start from and end at a single common depot v₀, then the metric Multiple TSP can be approximated equally well as the standard metric TSP, as shown by Frieze (1983). The metric Multiple TSP becomes significantly harder to approximate when there is a set D of d ≥ 1 depots that form the starting and end points of the m tours. For this case, only a (2-1/d)-approximation in polynomial time is known, as well as a 3/2-approximation for constant d which requires a prohibitive run time of n^Θ(d) (Xu and Rodrigues, INFORMS J. Comput., 2015). A recent work of Traub, Vygen and Zenklusen (STOC 2020) gives another approximation algorithm for metric Multiple TSP with run time n^Θ(d), which reduces the problem to approximating metric TSP. In this paper we overcome the n^Θ(d) time barrier: we give the first efficient approximation algorithm for Multiple TSP with a variable number d of depots that yields a better-than-2 approximation. Our algorithm runs in time (1/ε)^O(dlog d) ⋅ n^O(1), and produces a (3/2+ε)-approximation with constant probability. For the graphic case, we obtain a deterministic 3/2-approximation in time 2^d ⋅ n^O(1).

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Traveling salesperson problem
  • rural postperson problem
  • multiple TSP
  • vehicle routing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Tolga Bektaş. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3):209-219, 2006. URL: https://doi.org/10.1016/j.omega.2004.10.004.
  2. Tolga Bektaş. Formulations and benders decomposition algorithms for multidepot salesmen problems with load balancing. European J. Oper. Res., 216(1):83-93, 2012. URL: https://doi.org/10.1016/j.ejor.2011.07.020.
  3. Enrique Benavent and Antonio Martínez. Multi-depot multiple TSP: a polyhedral study and computational results. Annals Oper. Res., 207:7-25, 2013. URL: https://doi.org/10.1007/s10479-011-1024-y.
  4. Kristóf Bérczi, Matthias Mnich, and Roland Vincze. A 3/2-approximation for the metric many-visits path TSP. SIAM J. Discrete Math., 36(4):2995-3030, 2022. URL: https://doi.org/10.1137/22M1483414.
  5. Kristóf Bérczi, Matthias Mnich, and Roland Vincze. Approximations for many-visits multiple traveling salesman problems. Omega, 116:102816, 2023. URL: https://doi.org/10.1016/j.omega.2022.102816.
  6. M. Burger, Z. Su, and B. De Schutter. A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem. European J. Oper. Res., 265(2):463-477, 2018. URL: https://doi.org/10.1016/j.ejor.2017.07.056.
  7. Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Carnegie-Mellon University, Management Sciences Research Group, 1976. URL: https://doi.org/10.1007/s43069-021-00101-z.
  8. Greg N. Frederickson. Approximation algorithms for some postman problems. J. ACM, 26(3):538-554, 1979. URL: https://doi.org/10.1145/322139.322150.
  9. Greg N. Frederickson, Matthew S. Hecht, and Chul E. Kim. Approximation algorithms for some routing problems. SIAM J. Comput., 7(2):178-193, 1978. URL: https://doi.org/10.1137/0207017.
  10. A.M. Frieze. An extension of Christofides heuristic to the k-person travelling salesman problem. Discrete Appl. Math., 6(1):79-83, 1983. URL: https://doi.org/10.1016/0166-218X(83)90102-6.
  11. Gregory Gutin, Magnus Wahlström, and Anders Yeo. Rural postman parameterized by the number of components of required edges. J. Comput. Syst. Sci., 83(1):121-131, 2017. URL: https://doi.org/10.1016/j.jcss.2016.06.001.
  12. Klaus Jansen. An approximation algorithm for the general routing problem. Inf. Process. Lett., 41(6):333-339, 1992. URL: https://doi.org/10.1016/0020-0190(92)90161-N.
  13. Imdat Kara and Tolga Bektaş. Integer linear programming formulations of multiple salesman problems and its variations. European J. Oper. Res., 174(3):1449-1458, 2006. URL: https://doi.org/10.1016/j.ejor.2005.03.008.
  14. Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric TSP. In Proc. STOC 2021, pages 32-45, 2021. URL: https://doi.org/10.1145/3406325.3451009.
  15. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85-103. Plenum, 1972. Google Scholar
  16. Gilbert Laporte, Yves Nobert, and Serge Taillefer. Solving a family of multi-depot vehicle routing and location-routing problems. Transport. Sci., 22(3):161-172, 1988. URL: https://doi.org/10.1287/trsc.22.3.161.
  17. Waqar Malik, Sivakumar Rathinam, and Swaroop Darbha. An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem. Oper. Res. Lett, 35(6):747-753, 2007. URL: https://doi.org/10.1016/j.orl.2007.02.001.
  18. Tobias Mömke and Ola Svensson. Approximating graphic TSP by matchings. In Proc. FOCS 2011, pages 560-569, 2011. URL: https://doi.org/10.1109/FOCS.2011.56.
  19. Paul Oberlin, Sivakumar Rathinam, and Swaroop Darbha. A transformation for a heterogeneous, multiple depot, multiple traveling salesman problem. In Proc. ACC 2009, pages 1292-1297, 2009. URL: https://doi.org/10.1109/ACC.2009.5160666.
  20. SN Parragh. Solving a real-world service technician routing and scheduling problem. In Proc. TRISTAN VII, 2010. Google Scholar
  21. Sivakumar Rathinam, Raja Sengupta, and Swaroop Darbha. A resource allocation algorithm for multivehicle systems with nonholonomic constraints. IEEE Trans. Automat. Sci. Engin., 4(1):98-104, 2007. URL: https://doi.org/10.1109/TASE.2006.872110.
  22. Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, 1980. URL: https://doi.org/10.1145/322217.322225.
  23. András Sebő and Jens Vygen. Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica, 34(5):597-629, 2014. URL: https://doi.org/10.1007/s00493-014-2960-3.
  24. Anatoliy I. Serdyukov. On some extremal walks in graphs. Upravlyaemye Sistemy, 17:76-79, 1978. (in Russian). Google Scholar
  25. Kaarthik Sundar and Sivakumar Rathinam. An exact algorithm for a heterogeneous, multiple depot, multiple traveling salesman problem. In Proc. ICUAS 2015, pages 366-371, 2015. URL: https://doi.org/10.1109/ICUAS.2015.7152311.
  26. Vera Traub, Jens Vygen, and Rico Zenklusen. Reducing path TSP to TSP. In Proc. STOC 2020, pages 14-27, 2020. URL: https://doi.org/10.1137/20M135594X.
  27. René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko. On approximate data reduction for the rural postman problem: Theory and experiments. Networks, 76(4):485-508, 2020. URL: https://doi.org/10.1002/net.21985.
  28. Zhou Xu and Brian Rodrigues. A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots. INFORMS J. Comput., 27(4):636-645, 2015. URL: https://doi.org/10.1287/ijoc.2015.0650.
  29. Zhou Xu and Brian Rodrigues. An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem. European J. Oper. Res., 257(3):735-745, 2017. URL: https://doi.org/10.1016/j.ejor.2016.08.054.
  30. Zhou Xu, Liang Xu, and Brian Rodrigues. An analysis of the extended Christofides heuristic for the k-depot TSP. Oper. Res. Lett., 39(3):218-223, 2011. URL: https://doi.org/10.1016/j.orl.2011.03.002.
  31. S. Yadlapalli, W.A. Malik, S. Darbha, and M. Pachter. A lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem. Nonlinear Analysis: Real World Applications, 10(4):1990-1999, 2009. URL: https://doi.org/10.1016/j.nonrwa.2008.03.014.
  32. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Edward W. Ng, editor, Proc. EUROSAM 1979, volume 72 of Lecture Notes Comput. Sci., pages 216-226, 1979. URL: https://doi.org/10.1007/3-540-09519-5_73.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact