Document Open Access Logo

Primal-Dual 2-Approximation Algorithm for the Monotonic Multiple Depot Heterogeneous Traveling Salesman Problem

Authors S. Rathinam, R. Ravi, J. Bae, K. Sundar

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.33.pdf
  • Filesize: 0.76 MB
  • 13 pages

Document Identifiers

Author Details

S. Rathinam
  • Texas A & M University, College Station, TX 77843, USA
R. Ravi
  • Carnegie Mellon University, Pittsburgh, PA 15213, USA
J. Bae
  • Michigan Technological University, Houghton, MI 49931, USA
K. Sundar
  • Los Alamos Laboratory, NM 87545, USA

Funding

  • Ravi, R.: This material is based upon work supported in part by the U. S. Office of Naval Research under award number N00014-18-1-2099.

Cite AsGet BibTex

S. Rathinam, R. Ravi, J. Bae, and K. Sundar. Primal-Dual 2-Approximation Algorithm for the Monotonic Multiple Depot Heterogeneous Traveling Salesman Problem. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 33:1-33:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SWAT.2020.33

Abstract

We study a Multiple Depot Heterogeneous Traveling Salesman Problem (MDHTSP) where the cost of the traveling between any two targets depends on the type of the vehicle. The travel costs are assumed to be symmetric, satisfy the triangle inequality, and are monotonic, i.e., the travel costs between any two targets monotonically increases with the index of the vehicles. Exploiting the monotonic structure of the travel costs, we present a 2-approximation algorithm based on the primal-dual method.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
Keywords
  • Approximation Algorithm
  • Heterogeneous Traveling Salesman Problem
  • Primal-dual Method

Metrics

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

References

  1. Ajit Agrawal, Philip Klein, and Ramamoorthi Ravi. When trees collide: An approximation algorithm for the generalized steiner problem on networks. SIAM journal on Computing, 24(3):440-456, 1995. Google Scholar
  2. Jung Yun Bae and Sivakumar Rathinam. A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem. Optimization Letters, 10, 2015. URL: https://doi.org/10.1007/s11590-015-0924-1.
  3. Jungyun Bae and Sivakumar Rathinam. Approximation algorithms for multiple terminal, hamiltonian path problems. Optimization Letters, 6(1):69-85, 2012. URL: https://doi.org/10.1007/s11590-010-0252-4.
  4. Bruno N. Coelho, Vitor N. Coelho, Igor M. Coelho, Luiz S. Ochi, Roozbeh Haghnazar K., Demetrius Zuidema, Milton S.F. Lima, and Adilson R. da Costa. A multi-objective green uav routing problem. Comput. Oper. Res., 88(C):306-315, December 2017. URL: https://doi.org/10.1016/j.cor.2017.04.011.
  5. R. Doshi, S. Yadlapalli, S. Rathinam, and S. Darbha. Approximation algorithms and heuristics for a 2-depot, heterogeneous hamiltonian path problem. International Journal of Robust and Nonlinear Control, 21(12):1434-1451, 2011. URL: https://doi.org/10.1002/rnc.1701.
  6. A.M. Frieze. An extension of christofides heuristic to the k-person travelling salesman problem. Discrete Applied Mathematics, 6(1):79-83, 1983. URL: https://doi.org/10.1016/0166-218X(83)90102-6.
  7. Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24(2):296-317, April 1995. Google Scholar
  8. I. Gortz, M. Molinaro, V. Nagarajan, and R. Ravi. Capacitated Vehicle Routing with Non-uniform Speeds, volume 6655 of Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 2011. Google Scholar
  9. Samir Khuller, Azarakhsh Malekian, and Julián Mestre. To fill or not to fill: The gas station problem. ACM Trans. Algorithms, 7(3):36:1-36:16, July 2011. URL: https://doi.org/10.1145/1978782.1978791.
  10. David Levy, Kaarthik Sundar, and Sivakumar Rathinam. Heuristics for routing heterogeneous unmanned vehicles with fuel constraints. Mathematical Problems in Engineering, 2014, 2014. Google Scholar
  11. Parikshit Maini and P.B. Sujit. On cooperation between a fuel constrained uav and a refueling ugv for large scale mapping applications. In 2015 International Conference on Unmanned Aircraft Systems, 2015. URL: https://doi.org/10.1109/ICUAS.2015.7152432.
  12. W. Malik, S. Rathinam, and S. Darbha. An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem. Operations Research Letters, 35:747-753, 2007. Google Scholar
  13. P. Oberlin, S. Rathinam, and S. Darbha. Today’s traveling salesman problem. IEEE Robotics and Automation Magazine, 17(4):70-77, December 2010. Google Scholar
  14. Alena Otto, Niels A. H. Agatz, James F. Campbell, Bruce L. Golden, and Erwin Pesch. Optimization approaches for civil applications of unmanned aerial vehicles (uavs) or aerial drones: A survey. Networks, 72(4):411-458, 2018. URL: https://doi.org/10.1002/net.21818.
  15. Stefan Poikonen, Xingyin Wang, and Bruce Golden. The vehicle routing problem with drones: Extended models and connections. Networks, 70(1):34-43, 2017. URL: https://doi.org/10.1002/net.21746.
  16. Amritha Prasad, Shreyas Sundaram, and Han-Lim Choi. Min-max tours for task allocation to heterogeneous agents. In 2018 IEEE Conference on Decision and Control (CDC), pages 1706-1711, 2018. URL: https://doi.org/10.1109/CDC.2018.8619118.
  17. S. Rathinam, R. Sengupta, and S. Darbha. A resource allocation algorithm for multivehicle systems with nonholonomic constraints. IEEE Transactions Automation Science and Engineering, 4:98-104, 2007. URL: https://doi.org/10.1109/TASE.2006.872110.
  18. Sivakumar Rathinam and Raja Sengupta. 3/2-approximation algorithm for two variants of a 2-depot hamiltonian path problem. Operations Research Letters, 38(1):63-68, 2010. URL: https://doi.org/10.1016/j.orl.2009.10.001.
  19. J. A. Reeds and L. A. Shepp. Optimal paths for a car that goes both forwards and backwards. Pacific J. Math., 145(2):367-393, 1990. Google Scholar
  20. Kaarthik Sundar and Sivakumar Rathinam. An exact algorithm for a heterogeneous, multiple depot, multiple traveling salesman problem. In Unmanned Aircraft Systems (ICUAS), 2015 International Conference on, pages 366-371. IEEE, 2015. Google Scholar
  21. Zhou Xu and Brian Rodrigues. An extension of the christofides heuristic for the generalized multiple depot multiple traveling salesmen problem. European Journal of Operational Research, 257(3):735-745, 2017. URL: https://doi.org/10.1016/j.ejor.2016.08.054.
  22. S. Yadlapalli, S. Rathinam, and S. Darbha. 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem. Optimization Letters, pages 1-12, 2010. Google Scholar
  23. Miao Yu, Viswanath Nagarajan, and Siqian Shen. An approximation algorithm for vehicle routing with compatibility constraints. Operations Research Letters, 46(6):579-584, 2018. URL: https://doi.org/10.1016/j.orl.2018.10.002.
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