IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v41y2007i3p366-381.html
   My bibliography  Save this article

The Robust Traveling Salesman Problem with Interval Data

Author

Listed:
  • R. Montemanni

    (Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, Galleria 2, CH-6928 Lugano-Manno, Switzerland)

  • J. Barta

    (Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, Galleria 2, CH-6928 Lugano-Manno, Switzerland)

  • M. Mastrolilli

    (Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, Galleria 2, CH-6928 Lugano-Manno, Switzerland)

  • L. M. Gambardella

    (Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, Galleria 2, CH-6928 Lugano-Manno, Switzerland)

Abstract

The traveling salesman problem is one of the most famous combinatorial optimization problems and has been intensively studied. Many extensions to the basic problem have also been proposed, with the aim of making the resulting mathematical models as realistic as possible. We present a new extension to the basic problem, where travel times are specified as a range of possible values. This model reflects the intrinsic difficulties of estimating travel times in reality. We apply the robust deviation criterion to drive optimization over the interval data problem so obtained. Some interesting theoretical properties of the new optimization problems are identified and discussed, together with a new mathematical formulation and some exact and heuristic algorithms. Computational experiments are finally presented.

Suggested Citation

  • R. Montemanni & J. Barta & M. Mastrolilli & L. M. Gambardella, 2007. "The Robust Traveling Salesman Problem with Interval Data," Transportation Science, INFORMS, vol. 41(3), pages 366-381, August.
    • Handle: RePEc:inm:ortrsc:v:41:y:2007:i:3:p:366-381
    DOI: 10.1287/trsc.1060.0181
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1060.0181
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1060.0181?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
    ---><---

    References listed on IDEAS

    as
    1. Gilbert Laporte & François Louveaux & Hélène Mercure, 1992. "The Vehicle Routing Problem with Stochastic Travel Times," Transportation Science, INFORMS, vol. 26(3), pages 161-170, August.
    2. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    3. Richard L. Daniels & Panagiotis Kouvelis, 1995. "Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production," Management Science, INFORMS, vol. 41(2), pages 363-376, February.
    4. Helsgaun, Keld, 2000. "An effective implementation of the Lin-Kernighan traveling salesman heuristic," European Journal of Operational Research, Elsevier, vol. 126(1), pages 106-130, October.
    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. Liang, Jinpeng & Wu, Jianjun & Qu, Yunchao & Yin, Haodong & Qu, Xiaobo & Gao, Ziyou, 2019. "Robust bus bridging service design under rail transit system disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 132(C), pages 97-116.
    2. Alireza Amirteimoori & Simin Masrouri, 2021. "DEA-based competition strategy in the presence of undesirable products: An application to paper mills," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 31(2), pages 5-21.
    3. Bock, Stefan, 2020. "Optimally solving a versatile Traveling Salesman Problem on tree networks with soft due dates and multiple congestion scenarios," European Journal of Operational Research, Elsevier, vol. 283(3), pages 863-882.
    4. Mengshi Lu & Zuo‐Jun Max Shen, 2021. "A Review of Robust Operations Management under Model Uncertainty," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1927-1943, June.
    5. Amadeu A. Coco & Andréa Cynthia Santos & Thiago F. Noronha, 2022. "Robust min-max regret covering problems," Computational Optimization and Applications, Springer, vol. 83(1), pages 111-141, September.
    6. Gabrel, Virginie & Murat, Cécile & Thiele, Aurélie, 2014. "Recent advances in robust optimization: An overview," European Journal of Operational Research, Elsevier, vol. 235(3), pages 471-483.
    7. Yossiri Adulyasak & Patrick Jaillet, 2016. "Models and Algorithms for Stochastic and Robust Vehicle Routing with Deadlines," Transportation Science, INFORMS, vol. 50(2), pages 608-626, May.
    8. Mohammad Javad Feizollahi & Igor Averbakh, 2014. "The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 321-335, May.
    9. Jordi Pereira & Igor Averbakh, 2013. "The Robust Set Covering Problem with interval data," Annals of Operations Research, Springer, vol. 207(1), pages 217-235, August.
    10. Groß, Patrick-Oliver & Ehmke, Jan Fabian & Mattfeld, Dirk Christian, 2020. "Interval travel times for robust synchronization in city logistics vehicle routing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    11. Jean-François Cordeau & Gianpaolo Ghiani & Emanuela Guerriero, 2014. "Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem," Transportation Science, INFORMS, vol. 48(1), pages 46-58, February.
    12. Wei Wu & Manuel Iori & Silvano Martello & Mutsunori Yagiura, 2022. "An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2523-2539, September.
    13. Yin, Yunqiang & Luo, Zunhao & Wang, Dujuan & Cheng, T.C.E., 2023. "Wasserstein distance‐based distributionally robust parallel‐machine scheduling," Omega, Elsevier, vol. 120(C).
    14. Patrick Jaillet & Jin Qi & Melvyn Sim, 2016. "Routing Optimization Under Uncertainty," Operations Research, INFORMS, vol. 64(1), pages 186-200, February.
    15. Fabio Furini & Manuel Iori & Silvano Martello & Mutsunori Yagiura, 2015. "Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 392-405, May.
    16. János Barta & Valeria Leggieri & Roberto Montemanni & Paolo Nobili & Chefi Triki, 2011. "Minimum power multicasting in wireless networks under probabilistic node failures," Computational Optimization and Applications, Springer, vol. 49(1), pages 193-212, May.
    17. Ivana Semanjski & Sidharta Gautama, 2024. "Sustainable Time-Dependent Cheapest Path Problem with Integrated Collaborative Stakeholders’ Perspectives," Sustainability, MDPI, vol. 16(9), pages 1-19, April.
    18. Li, Xiang & Zhou, Jiandong & Zhao, Xiande, 2016. "Travel itinerary problem," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 332-343.
    19. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2009. "Min-max and min-max regret versions of combinatorial optimization problems: A survey," European Journal of Operational Research, Elsevier, vol. 197(2), pages 427-438, 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. Gary R. Waissi & Pragya Kaushal, 2020. "A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP," OPSEARCH, Springer;Operational Research Society of India, vol. 57(1), pages 73-87, March.
    2. G Laporte, 2010. "A concise guide to the Traveling Salesman Problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(1), pages 35-40, January.
    3. William Cook & Daniel G. Espinoza & Marcos Goycoolea, 2007. "Computing with Domino-Parity Inequalities for the Traveling Salesman Problem (TSP)," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 356-365, August.
    4. Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
    5. Bruce Golden & Zahra Naji-Azimi & S. Raghavan & Majid Salari & Paolo Toth, 2012. "The Generalized Covering Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 534-553, November.
    6. G Babin & S Deneault & G Laporte, 2007. "Improvements to the Or-opt heuristic for the symmetric travelling salesman problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 402-407, March.
    7. Burger, M. & Su, Z. & De Schutter, B., 2018. "A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 265(2), pages 463-477.
    8. Anurag Agarwal, 2009. "Theoretical insights into the augmented-neural-network approach for combinatorial optimization," Annals of Operations Research, Springer, vol. 168(1), pages 101-117, April.
    9. Lisa K. Fleischer & Adam N. Letchford & Andrea Lodi, 2006. "Polynomial-Time Separation of a Superclass of Simple Comb Inequalities," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 696-713, November.
    10. Bernardino, Raquel & Paias, Ana, 2018. "Solving the family traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 267(2), pages 453-466.
    11. Siyun Zhang & Kameng Nip & Zhenbo Wang, 0. "Related machine scheduling with machine speeds satisfying linear constraints," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-17.
    12. A. Scholz & G. Wäscher, 2017. "Order Batching and Picker Routing in manual order picking systems: the benefits of integrated routing," 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. 25(2), pages 491-520, June.
    13. Chiang, Wen-Chyuan & Russell, Robert & Xu, Xiaojing & Zepeda, David, 2009. "A simulation/metaheuristic approach to newspaper production and distribution supply chain problems," International Journal of Production Economics, Elsevier, vol. 121(2), pages 752-767, October.
    14. Mathias A. Klapp & Alan L. Erera & Alejandro Toriello, 2018. "The One-Dimensional Dynamic Dispatch Waves Problem," Transportation Science, INFORMS, vol. 52(2), pages 402-415, March.
    15. Olcay Polat & Duygu Topaloğlu, 2022. "Collection of different types of milk with multi-tank tankers under uncertainty: a real case study," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 1-33, April.
    16. Rostami, Borzou & Malucelli, Federico & Belotti, Pietro & Gualandi, Stefano, 2016. "Lower bounding procedure for the asymmetric quadratic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 253(3), pages 584-592.
    17. Neves-Moreira, Fábio & Almada-Lobo, Bernardo & Guimarães, Luís & Amorim, Pedro, 2022. "The multi-product inventory-routing problem with pickups and deliveries: Mitigating fluctuating demand via rolling horizon heuristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    18. Stock-Williams, Clym & Swamy, Siddharth Krishna, 2019. "Automated daily maintenance planning for offshore wind farms," Renewable Energy, Elsevier, vol. 133(C), pages 1393-1403.
    19. Furini, Fabio & Persiani, Carlo Alfredo & Toth, Paolo, 2016. "The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace," Transportation Research Part B: Methodological, Elsevier, vol. 90(C), pages 38-55.
    20. Lang, Jan Christian & Shen, Zuo-Jun Max, 2011. "Fix-and-optimize heuristics for capacitated lot-sizing with sequence-dependent setups and substitutions," European Journal of Operational Research, Elsevier, vol. 214(3), pages 595-605, November.

    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:inm:ortrsc:v:41:y:2007:i:3:p:366-381. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.