IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v45y2023i4d10.1007_s10878-023-01029-2.html
   My bibliography  Save this article

An approximation algorithm for the clustered path travelling salesman problem

Author

Listed:
  • Jiaxuan Zhang

    (Hebei Normal University)

  • Suogang Gao

    (Hebei Normal University)

  • Bo Hou

    (Hebei Normal University)

  • Wen Liu

    (Hebei Normal University)

Abstract

In this paper, we consider the clustered path travelling salesman problem. In this problem, we are given a complete graph $$G=(V,E)$$ G = ( V , E ) with an edge weight function w satisfying the triangle inequality. In addition, the vertex set V is partitioned into clusters $$V_1,\ldots ,V_k$$ V 1 , … , V k and s, t are two given vertices of G with $$s\in V_1$$ s ∈ V 1 and $$t\in V_k$$ t ∈ V k . The objective of the problem is to find a minimum Hamiltonian path of G from s to t, where all vertices of each cluster are visited consecutively. In this paper, we deal with the case that the start-vertex and the end-vertex of the path on each cluster are both specified, and for it we provide a polynomial-time approximation algorithm.

Suggested Citation

  • Jiaxuan Zhang & Suogang Gao & Bo Hou & Wen Liu, 2023. "An approximation algorithm for the clustered path travelling salesman problem," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-12, May.
    • Handle: RePEc:spr:jcomop:v:45:y:2023:i:4:d:10.1007_s10878-023-01029-2
    DOI: 10.1007/s10878-023-01029-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-023-01029-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-023-01029-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Li Zhu & Yeming Gong & Yishui Xu & Jun Gu, 2019. "Emergency relief routing models for injured victims considering equity and priority," Annals of Operations Research, Springer, vol. 283(1), pages 1573-1606, December.
    2. Evin Uzun Jacobson & Nilay Tanık Argon & Serhan Ziya, 2012. "Priority Assignment in Emergency Response," Operations Research, INFORMS, vol. 60(4), pages 813-832, August.
    3. Li Zhu & Yeming Gong & Yishui Xu & Jun Gu, 2019. "Emergency Relief Routing Models for Injured Victims Considering Equity and Priority," Post-Print hal-02879681, HAL.
    4. Jongens, Kees & Volgenant, Ton, 1985. "The symmetric clustered traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 19(1), pages 68-75, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Farahani, Reza Zanjirani & Lotfi, M.M. & Baghaian, Atefe & Ruiz, Rubén & Rezapour, Shabnam, 2020. "Mass casualty management in disaster scene: A systematic review of OR&MS research in humanitarian operations," European Journal of Operational Research, Elsevier, vol. 287(3), pages 787-819.
    2. Rabin K. Jana & Dinesh K. Sharma & Peeyush Mehta, 2022. "A probabilistic fuzzy goal programming model for managing the supply of emergency relief materials," Annals of Operations Research, Springer, vol. 319(1), pages 149-172, December.
    3. Roberto Aringhieri & Sara Bigharaz & Davide Duma & Alberto Guastalla, 2022. "Fairness in ambulance routing for post disaster management," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 30(1), pages 189-211, March.
    4. Jiaxin Geng & Hanping Hou & Shaoqing Geng, 2021. "Optimization of Warehouse Location and Supplies Allocation for Emergency Rescue under Joint Government–Enterprise Cooperation Considering Disaster Victims’ Distress Perception," Sustainability, MDPI, vol. 13(19), pages 1-14, September.
    5. Sun, Huali & Li, Jiamei & Wang, Tingsong & Xue, Yaofeng, 2022. "A novel scenario-based robust bi-objective optimization model for humanitarian logistics network under risk of disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).
    6. Yongling Zhang & Xin Li & Nana Kong & Miao Zhou & Xiaobing Zhou, 2022. "Spatial Accessibility Assessment of Emergency Response of Urban Public Services in the Context of Pluvial Flooding Scenarios: The Case of Jiaozuo Urban Area, China," Sustainability, MDPI, vol. 14(24), pages 1-15, December.
    7. Hasti Seraji & Reza Tavakkoli-Moghaddam & Sobhan Asian & Harpreet Kaur, 2022. "An integrative location-allocation model for humanitarian logistics with distributive injustice and dissatisfaction under uncertainty," Annals of Operations Research, Springer, vol. 319(1), pages 211-257, December.
    8. Morin, Michael & Abi-Zeid, Irène & Quimper, Claude-Guy, 2023. "Ant colony optimization for path planning in search and rescue operations," European Journal of Operational Research, Elsevier, vol. 305(1), pages 53-63.
    9. Maliheh Khorsi & Seyed Kamal Chaharsooghi & Ali Husseinzadeh Kashan & Ali Bozorgi-Amiri, 2022. "Solving the humanitarian multi-trip cumulative capacitated routing problem via a grouping metaheuristic algorithm," Annals of Operations Research, Springer, vol. 319(1), pages 173-210, December.
    10. Diehlmann, Florian & Hiemsch, Patrick S. & Wiens, Marcus & Lüttenberg, Markus & Schultmann, Frank, 2020. "A novel approach to include social costs in humanitarian objective functions," Working Paper Series in Production and Energy 52, Karlsruhe Institute of Technology (KIT), Institute for Industrial Production (IIP).
    11. Guo Fuli & Cyril Foropon & Ma Xin, 2022. "Reducing carbon emissions in humanitarian supply chain: the role of decision making and coordination," Annals of Operations Research, Springer, vol. 319(1), pages 355-377, December.
    12. Wang, Jing & Cai, Jianping & Yue, Xiaohang & Suresh, Nallan C., 2021. "Pre-positioning and real-time disaster response operations: Optimization with mobile phone location data," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 150(C).
    13. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    14. Kamali, Behrooz & Bish, Douglas & Glick, Roger, 2017. "Optimal service order for mass-casualty incident response," European Journal of Operational Research, Elsevier, vol. 261(1), pages 355-367.
    15. Francisca Santana-Robles & Eva Selene Hernández-Gress & Ricardo Martínez-López & Isidro Jesús González-Hernández, 2024. "Quick-Response Model for Pre- and Post-Disaster Evacuation and Aid Distribution: The Case of the Tula River Flood Event," Logistics, MDPI, vol. 8(1), pages 1-21, January.
    16. Emmett J. Lodree & Nezih Altay & Robert A. Cook, 2019. "Staff assignment policies for a mass casualty event queuing network," Annals of Operations Research, Springer, vol. 283(1), pages 411-442, December.
    17. Renaud, Jacques & Boctor, Fayez F., 1998. "An efficient composite heuristic for the symmetric generalized traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 108(3), pages 571-584, August.
    18. Rezapour, Shabnam & Naderi, Nazanin & Morshedlou, Nazanin & Rezapourbehnagh, Shaghayegh, 2018. "Optimal deployment of emergency resources in sudden onset disasters," International Journal of Production Economics, Elsevier, vol. 204(C), pages 365-382.
    19. Li Zhu & Yeming Gong & Yishui Xu & Jun Gu, 2019. "Emergency Relief Routing Models for Injured Victims Considering Equity and Priority," Post-Print hal-02879681, HAL.
    20. Shuwan Zhu & Wenjuan Fan & Xueping Li & Shanlin Yang, 2023. "Ambulance dispatching and operating room scheduling considering reusable resources in mass-casualty incidents," Operational Research, Springer, vol. 23(2), pages 1-37, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:45:y:2023:i:4:d:10.1007_s10878-023-01029-2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.