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. 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.
    3. 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.
    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. 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.
    2. 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.
    3. 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).
    4. Patrick Jaillet & Jin Qi & Melvyn Sim, 2016. "Routing Optimization Under Uncertainty," Operations Research, INFORMS, vol. 64(1), pages 186-200, February.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Li, Xiang & Zhou, Jiandong & Zhao, Xiande, 2016. "Travel itinerary problem," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 332-343.
    12. 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.
    13. 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.
    14. Yin, Yunqiang & Luo, Zunhao & Wang, Dujuan & Cheng, T.C.E., 2023. "Wasserstein distance‐based distributionally robust parallel‐machine scheduling," Omega, Elsevier, vol. 120(C).
    15. 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.
    16. 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.
    17. 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.
    18. 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.

    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. 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.
    2. Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Sascha Wörz, 2017. "On global integer extrema of real-valued box-constrained multivariate quadratic functions," Journal of Combinatorial Optimization, Springer, vol. 34(3), pages 964-986, October.
    9. 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.
    10. Jian Yang & Gang Yu, 2002. "On the Robust Single Machine Scheduling Problem," Journal of Combinatorial Optimization, Springer, vol. 6(1), pages 17-33, March.
    11. Roel G. van Anholt & Leandro C. Coelho & Gilbert Laporte & Iris F. A. Vis, 2016. "An Inventory-Routing Problem with Pickups and Deliveries Arising in the Replenishment of Automated Teller Machines," Transportation Science, INFORMS, vol. 50(3), pages 1077-1091, August.
    12. Balma, Ali & Salem, Safa Ben & Mrad, Mehdi & Ladhari, Talel, 2018. "Strong multi-commodity flow formulations for the asymmetric traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 271(1), pages 72-79.
    13. 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.
    14. Vairaktarakis, George L., 2000. "Robust multi-item newsboy models with a budget constraint," International Journal of Production Economics, Elsevier, vol. 66(3), pages 213-226, July.
    15. Koç, Çağrı & Bektaş, Tolga & Jabali, Ola & Laporte, Gilbert, 2016. "The fleet size and mix location-routing problem with time windows: Formulations and a heuristic algorithm," European Journal of Operational Research, Elsevier, vol. 248(1), pages 33-51.
    16. 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.
    17. Avraham, Edison & Raviv, Tal, 2020. "The data-driven time-dependent traveling salesperson problem," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 25-40.
    18. Briant, Olivier & Cambazard, Hadrien & Cattaruzza, Diego & Catusse, Nicolas & Ladier, Anne-Laure & Ogier, Maxime, 2020. "An efficient and general approach for the joint order batching and picker routing problem," European Journal of Operational Research, Elsevier, vol. 285(2), pages 497-512.
    19. Theys, Christophe & Bräysy, Olli & Dullaert, Wout & Raa, Birger, 2010. "Using a TSP heuristic for routing order pickers in warehouses," European Journal of Operational Research, Elsevier, vol. 200(3), pages 755-763, February.
    20. Dahlbeck, Mirko & Fischer, Anja & Fischer, Frank, 2020. "Decorous combinatorial lower bounds for row layout problems," European Journal of Operational Research, Elsevier, vol. 286(3), pages 929-944.

    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.