IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v49y2025i5d10.1007_s10878-025-01288-1.html
   My bibliography  Save this article

The multiple steiner TSP with cyclic order on terminals: valid inequalities and polyhedra

Author

Listed:
  • A. Ridha Mahjoub

    (Kuwait University
    Université Paris-Dauphine PSL)

  • Raouia Taktak

    (ISIMS, Université de Sfax
    Sm@rts, Centre de Recherche en Numérique de Sfax)

  • Eduardo Uchoa

    (Universidade Federal Fluminense)

Abstract

This paper deals with a variant of the Traveling Salesman Problem (TSP), called the Multiple Steiner TSP with Order Constraints (MSTSPOC). Consider an undirected graph with nonnegative weights on the edges, and a set of salesmen such that with each salesman is associated a set of ordered terminals. The MSTSPOC consists in finding a minimum-weight subgraph containing for each salesman a tour going in order through its terminals. We study the polytope associated with the Integer Linear Programming (ILP) formulation proposed in Borne et al. (2013). We characterize when the basic inequalities define facets. We also describe new valid inequalities along with necessary conditions and sufficient conditions for these inequalities to be facet-defining. Further families of valid inequalities, coming from closely related problems, are also discussed. The theoretical results presented in this paper are computationally tested in a companion paper (Taktak 2024).

Suggested Citation

  • A. Ridha Mahjoub & Raouia Taktak & Eduardo Uchoa, 2025. "The multiple steiner TSP with cyclic order on terminals: valid inequalities and polyhedra," Journal of Combinatorial Optimization, Springer, vol. 49(5), pages 1-51, July.
    • Handle: RePEc:spr:jcomop:v:49:y:2025:i:5:d:10.1007_s10878-025-01288-1
    DOI: 10.1007/s10878-025-01288-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-025-01288-1
    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-025-01288-1?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

    for a different version of it.

    References listed on IDEAS

    as
    1. Mourad Baïou & Francisco Barahona & Ali Ridha Mahjoub, 2000. "Separation of Partition Inequalities," Mathematics of Operations Research, INFORMS, vol. 25(2), pages 243-254, May.
    2. 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.
    3. Khachai, Daniil & Sadykov, Ruslan & Battaia, Olga & Khachay, Michael, 2023. "Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm," European Journal of Operational Research, Elsevier, vol. 309(2), pages 488-505.
    4. Éric Duchenne & Gilbert Laporte & Frédéric Semet, 2007. "The Undirected m -Peripatetic Salesman Problem: Polyhedral Results and New Algorithms," Operations Research, INFORMS, vol. 55(5), pages 949-965, October.
    5. Bektas, Tolga, 2006. "The multiple traveling salesman problem: an overview of formulations and solution procedures," Omega, Elsevier, vol. 34(3), pages 209-219, June.
    6. Xianghu Meng & Jun Li & MengChu Zhou & Shi Cheng, 2021. "A Colored Traveling Salesman Problem with Varying City Colors," Discrete Dynamics in Nature and Society, Hindawi, vol. 2021, pages 1-14, December.
    7. Letchford, Adam N. & Nasiri, Saeideh D. & Theis, Dirk Oliver, 2013. "Compact formulations of the Steiner Traveling Salesman Problem and related problems," European Journal of Operational Research, Elsevier, vol. 228(1), pages 83-92.
    8. José Alejandro Cornejo-Acosta & Jesús García-Díaz & Julio César Pérez-Sansalvador & Carlos Segura, 2023. "Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems," Mathematics, MDPI, vol. 11(13), pages 1-25, July.
    9. Duchenne, Éric & Laporte, Gilbert & Semet, Frédéric, 2012. "The undirected m-Capacitated Peripatetic Salesman Problem," European Journal of Operational Research, Elsevier, vol. 223(3), pages 637-643.
    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. Davood Shiri & Vahid Akbari & F. Sibel Salman, 2020. "Online routing and scheduling of search-and-rescue teams," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(3), pages 755-784, September.
    2. Wex, Felix & Schryen, Guido & Feuerriegel, Stefan & Neumann, Dirk, 2014. "Emergency response in natural disaster management: Allocation and scheduling of rescue units," European Journal of Operational Research, Elsevier, vol. 235(3), pages 697-708.
    3. Zhang, Ruijuan & Dai, Ying & Yang, Fei & Ma, Zujun, 2024. "A cooperative vehicle routing problem with delivery options for simultaneous pickup and delivery services in rural areas," Socio-Economic Planning Sciences, Elsevier, vol. 93(C).
    4. CASTRO, Marco & SÖRENSEN, Kenneth & VANSTEENWEGEN, Pieter & GOOS, Peter, 2012. "A simple GRASP+VND for the travelling salesperson problem with hotel selection," Working Papers 2012024, University of Antwerp, Faculty of Business and Economics.
    5. Sebastian Henn & André Scholz & Meike Stuhlmann & Gerhard Wäscher, 2015. "A New Mathematical Programming Formulation for the Single-Picker Routing Problem in a Single-Block Layout," FEMM Working Papers 150005, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    6. Andrzej Grzybowski, 2009. "A Note On A Single Vehicle And One Destination Routing Problem And Its Game-Theoretic Models," Advanced Logistic systems, University of Miskolc, Department of Material Handling and Logistics, vol. 3(1), pages 71-76, December.
    7. Du, Mingyang & Cheng, Lin & Li, Xuefeng & Tang, Fang, 2020. "Static rebalancing optimization with considering the collection of malfunctioning bikes in free-floating bike sharing system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    8. Fischer, Vera & Pacheco Paneque, Meritxell & Legrain, Antoine & Bürgy, Reinhard, 2024. "A capacitated multi-vehicle covering tour problem on a road network and its application to waste collection," European Journal of Operational Research, Elsevier, vol. 315(1), pages 338-353.
    9. Nourinejad, Mehdi & Zhu, Sirui & Bahrami, Sina & Roorda, Matthew J., 2015. "Vehicle relocation and staff rebalancing in one-way carsharing systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 81(C), pages 98-113.
    10. F. Angel-Bello & Y. Cardona-Valdés & A. Álvarez, 2019. "Mixed integer formulations for the multiple minimum latency problem," Operational Research, Springer, vol. 19(2), pages 369-398, June.
    11. Peter Reiter & Walter Gutjahr, 2012. "Exact hybrid algorithms for solving a bi-objective vehicle routing problem," 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. 20(1), pages 19-43, March.
    12. Bakker, Steffen J. & Wang, Akang & Gounaris, Chrysanthos E., 2021. "Vehicle routing with endogenous learning: Application to offshore plug and abandonment campaign planning," European Journal of Operational Research, Elsevier, vol. 289(1), pages 93-106.
    13. N. A. Arellano-Arriaga & J. Molina & S. E. Schaeffer & A. M. Álvarez-Socarrás & I. A. Martínez-Salazar, 2019. "A bi-objective study of the minimum latency problem," Journal of Heuristics, Springer, vol. 25(3), pages 431-454, June.
    14. Day, Jamison M. & Daniel Wright, P. & Schoenherr, Tobias & Venkataramanan, Munirpallam & Gaudette, Kevin, 2009. "Improving routing and scheduling decisions at a distributor of industrial gasses," Omega, Elsevier, vol. 37(1), pages 227-237, February.
    15. Zhang, Ruiyou & Lu, Jye-Chyi & Wang, Dingwei, 2014. "Container drayage problem with flexible orders and its near real-time solution strategies," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 235-251.
    16. Malladi, Krishna Teja & Quirion-Blais, Olivier & Sowlati, Taraneh, 2018. "Development of a decision support tool for optimizing the short-term logistics of forest-based biomass," Applied Energy, Elsevier, vol. 216(C), pages 662-677.
    17. Luigi Di Puglia Pugliese & Francesca Guerriero, 2016. "On the shortest path problem with negative cost cycles," Computational Optimization and Applications, Springer, vol. 63(2), pages 559-583, March.
    18. John S. F. Lyons & Peter C. Bell & Mehmet A. Begen, 2018. "Solving the Whistler-Blackcomb Mega Day Challenge," Interfaces, INFORMS, vol. 48(4), pages 323-339, August.
    19. Wang, Congke & Liu, Yankui & Yang, Guoqing, 2023. "Adaptive distributionally robust hub location and routing problem with a third-party logistics strategy," Socio-Economic Planning Sciences, Elsevier, vol. 87(PA).
    20. Enrique Benavent & Antonio Martínez, 2013. "Multi-depot Multiple TSP: a polyhedral study and computational results," Annals of Operations Research, Springer, vol. 207(1), pages 7-25, August.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:49:y:2025:i:5:d:10.1007_s10878-025-01288-1. 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.