IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v257y2017i3p735-745.html
   My bibliography  Save this article

An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem

Author

Listed:
  • Xu, Zhou
  • Rodrigues, Brian

Abstract

We study a generalization of the classical traveling salesman problem, where multiple salesmen are positioned at different depots, of which only a limited number (k) can be selected to service customers. For this problem, only two 2-approximation algorithms are available in the literature. Here, we improve on these algorithms by showing that a non-trivial extension of the well-known Christofides heuristic has a tight approximation ratio of 2−1/(2k). In doing so, we develop a body of analysis which can be used to build new approximation algorithms for other vehicle routing problems.

Suggested Citation

  • Xu, Zhou & Rodrigues, Brian, 2017. "An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem," European Journal of Operational Research, Elsevier, vol. 257(3), pages 735-745.
    • Handle: RePEc:eee:ejores:v:257:y:2017:i:3:p:735-745
    DOI: 10.1016/j.ejor.2016.08.054
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716306932
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.08.054?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. Gilbert Laporte & Yves Nobert & Serge Taillefer, 1988. "Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems," Transportation Science, INFORMS, vol. 22(3), pages 161-172, August.
    2. Mina, Hokey & Jayaraman, Vaidyanathan & Srivastava, Rajesh, 1998. "Combined location-routing problems: A synthesis and future research directions," European Journal of Operational Research, Elsevier, vol. 108(1), pages 1-15, July.
    3. William Cook & André Rohe, 1999. "Computing Minimum-Weight Perfect Matchings," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 138-148, May.
    4. Prodhon, Caroline & Prins, Christian, 2014. "A survey of recent research on location-routing problems," European Journal of Operational Research, Elsevier, vol. 238(1), pages 1-17.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Henan Liu & Huili Zhang & Yi Xu, 2021. "The m-Steiner Traveling Salesman Problem with online edge blockages," Journal of Combinatorial Optimization, Springer, vol. 41(4), pages 844-860, May.
    2. Yong Wang, 2019. "Sufficient and Necessary Conditions for an Edge in the Optimal Hamiltonian Cycle Based on Frequency Quadrilaterals," Journal of Optimization Theory and Applications, Springer, vol. 181(2), pages 671-683, May.
    3. Bérczi, Kristóf & Mnich, Matthias & Vincze, Roland, 2023. "Approximations for many-visits multiple traveling salesman problems," Omega, Elsevier, vol. 116(C).
    4. Xiaofan Lai & Liang Xu & Zhou Xu & Yang Du, 2023. "An Approximation Algorithm for k -Depot Split Delivery Vehicle Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1179-1194, September.

    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. Zhu, Stuart X. & Ursavas, Evrim, 2018. "Design and analysis of a satellite network with direct delivery in the pharmaceutical industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 190-207.
    2. Alvarez, Jose A. Lopez & Buijs, Paul & Deluster, Rogier & Coelho, Leandro C. & Ursavas, Evrim, 2020. "Strategic and operational decision-making in expanding supply chains for LNG as a fuel," Omega, Elsevier, vol. 97(C).
    3. Ponboon, Sattrawut & Qureshi, Ali Gul & Taniguchi, Eiichi, 2016. "Branch-and-price algorithm for the location-routing problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 86(C), pages 1-19.
    4. Arslan, Okan, 2021. "The location-or-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 147(C), pages 1-21.
    5. Paolo Gianessi & Laurent Alfandari & Lucas Létocart & Roberto Wolfler Calvo, 2016. "The Multicommodity-Ring Location Routing Problem," Transportation Science, INFORMS, vol. 50(2), pages 541-558, May.
    6. Capelle, Thomas & Cortés, Cristián E. & Gendreau, Michel & Rey, Pablo A. & Rousseau, Louis-Martin, 2019. "A column generation approach for location-routing problems with pickup and delivery," European Journal of Operational Research, Elsevier, vol. 272(1), pages 121-131.
    7. Elena Fernández & Gilbert Laporte & Jessica Rodríguez-Pereira, 2019. "Exact Solution of Several Families of Location-Arc Routing Problems," Transportation Science, INFORMS, vol. 53(5), pages 1313-1333, September.
    8. H. Neil Geismar & Yiwei Huang & Suresh D. Pillai & Chelliah Sriskandarajah & Seokjun Youn, 2020. "Location‐Routing with Conflicting Objectives: Coordinating eBeam Phytosanitary Treatment and Distribution of Mexican Import Commodities," Production and Operations Management, Production and Operations Management Society, vol. 29(6), pages 1506-1531, June.
    9. Drexl, M. & Schneider, M., 2014. "A Survey of the Standard Location-Routing Problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65940, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    10. Michiel A. J. uit het Broek & Albert H. Schrotenboer & Bolor Jargalsaikhan & Kees Jan Roodbergen & Leandro C. Coelho, 2021. "Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm," Operations Research, INFORMS, vol. 69(2), pages 380-409, March.
    11. Albareda-Sambola, Maria & Fernandez, Elena & Laporte, Gilbert, 2007. "Heuristic and lower bound for a stochastic location-routing problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 940-955, June.
    12. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    13. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    14. Ahn, Jaemyung & de Weck, Olivier & Geng, Yue & Klabjan, Diego, 2012. "Column generation based heuristics for a generalized location routing problem with profits arising in space exploration," European Journal of Operational Research, Elsevier, vol. 223(1), pages 47-59.
    15. Daniel Negrotto & Irene Loiseau, 2021. "A Branch & Cut algorithm for the prize-collecting capacitated location routing problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 34-57, April.
    16. Kelley, Jason & Kuby, Michael & Sierra, Rodrigo, 2013. "Transportation network optimization for the movement of indigenous goods in Amazonian Ecuador," Journal of Transport Geography, Elsevier, vol. 28(C), pages 89-100.
    17. Younes Rahmani & Wahiba Ramdane Cherif-Khettaf & Ammar Oulamara, 2016. "The two-echelon multi-products location-routing problem with pickup and delivery: formulation and heuristic approaches," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 999-1019, February.
    18. Janjevic, Milena & Merchán, Daniel & Winkenbach, Matthias, 2021. "Designing multi-tier, multi-service-level, and multi-modal last-mile distribution networks for omni-channel operations," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1059-1077.
    19. Michael Schneider & Michael Drexl, 2017. "A survey of the standard location-routing problem," Annals of Operations Research, Springer, vol. 259(1), pages 389-414, December.
    20. Michael Schneider & Maximilian Löffler, 2019. "Large Composite Neighborhoods for the Capacitated Location-Routing Problem," Service Science, INFORMS, vol. 53(1), pages 301-318, February.

    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:eee:ejores:v:257:y:2017:i:3:p:735-745. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.