IDEAS home Printed from https://ideas.repec.org/a/hin/complx/2826082.html
   My bibliography  Save this article

Trajectory Stability in the Traveling Salesman Problem

Author

Listed:
  • Sergio Sánchez
  • Germinal Cocho
  • Jorge Flores
  • Carlos Gershenson
  • Gerardo Iñiguez
  • Carlos Pineda

Abstract

Two generalizations of the traveling salesman problem in which sites change their position in time are presented. The way the rank of different trajectory lengths changes in time is studied using the rank diversity. We analyze the statistical properties of rank distributions and rank dynamics and give evidence that the shortest and longest trajectories are more predictable and robust to change, that is, more stable.

Suggested Citation

  • Sergio Sánchez & Germinal Cocho & Jorge Flores & Carlos Gershenson & Gerardo Iñiguez & Carlos Pineda, 2018. "Trajectory Stability in the Traveling Salesman Problem," Complexity, Hindawi, vol. 2018, pages 1-8, April.
    • Handle: RePEc:hin:complx:2826082
    DOI: 10.1155/2018/2826082
    as

    Download full text from publisher

    File URL: http://downloads.hindawi.com/journals/8503/2018/2826082.pdf
    Download Restriction: no
    File URL: http://downloads.hindawi.com/journals/8503/2018/2826082.xml
    Download Restriction: no
    File URL: https://libkey.io/10.1155/2018/2826082?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. Chryssi Malandraki & Mark S. Daskin, 1992. "Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms," Transportation Science, INFORMS, vol. 26(3), pages 185-200, August.
    2. Germinal Cocho & Jorge Flores & Carlos Gershenson & Carlos Pineda & Sergio Sánchez, 2015. "Rank Diversity of Languages: Generic Behavior in Computational Linguistics," PLOS ONE, Public Library of Science, vol. 10(4), pages 1-12, April.
    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. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    2. Kinable, Joris & Cire, Andre A. & van Hoeve, Willem-Jan, 2017. "Hybrid optimization methods for time-dependent sequencing problems," European Journal of Operational Research, Elsevier, vol. 259(3), pages 887-897.
    3. Stanisław Majer & Alicja Sołowczuk, 2023. "Traffic Calming Measures and Their Slowing Effect on the Pedestrian Refuge Approach Sections," Sustainability, MDPI, vol. 15(21), pages 1-27, October.
    4. 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.
    5. Gmira, Maha & Gendreau, Michel & Lodi, Andrea & Potvin, Jean-Yves, 2021. "Tabu search for the time-dependent vehicle routing problem with time windows on a road network," European Journal of Operational Research, Elsevier, vol. 288(1), pages 129-140.
    6. Wołoszyn, Maciej & Kułakowski, Krzysztof, 2023. "Status achieved in an organization—Rank dynamics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 610(C).
    7. Rabie Jaballah & Leandro C. Coelho & Jacques Renaud, 2025. "Time-Dependent Routing and Road Network Precision," SN Operations Research Forum, Springer, vol. 6(2), pages 1-23, June.
    8. 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.
    9. Abdelrahman E. E. Eltoukhy & Hashim A. Hashim & Mohamed Hussein & Waqar Ahmed Khan & Tarek Zayed, 2025. "Sustainable vehicle route planning under uncertainty for modular integrated construction: multi-trip time-dependent VRP with time windows and data analytics," Annals of Operations Research, Springer, vol. 348(2), pages 863-898, May.
    10. Tikani, Hamid & Setak, Mostafa & Demir, Emrah, 2021. "A risk-constrained time-dependent cash-in-transit routing problem in multigraph under uncertainty," European Journal of Operational Research, Elsevier, vol. 293(2), pages 703-730.
    11. Jinghao Sun & Yakun Meng & Guozhen Tan, 2015. "An integer programming approach for the Chinese postman problem with time-dependent travel time," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 565-588, April.
    12. Guo, Feng & Wei, Qu & Wang, Miao & Guo, Zhaoxia & Wallace, Stein W., 2023. "Deep attention models with dimension-reduction and gate mechanisms for solving practical time-dependent vehicle routing problems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 173(C).
    13. Loske, Dominic & Klumpp, Matthias, 2021. "Human-AI collaboration in route planning: An empirical efficiency-based analysis in retail logistics," International Journal of Production Economics, Elsevier, vol. 241(C).
    14. Verbeeck, C. & Sörensen, K. & Aghezzaf, E.-H. & Vansteenwegen, P., 2014. "A fast solution method for the time-dependent orienteering problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 419-432.
    15. Fang Zhao & Bingfeng Si & Zhenlin Wei & Tianwei Lu, 2023. "Time-dependent vehicle routing problem of perishable product delivery considering the differences among paths on the congested road," Operational Research, Springer, vol. 23(1), pages 1-23, March.
    16. Ebrahim Teimoury & Reza Rashid, 2024. "A hybrid variable neighborhood search heuristic for the sustainable time-dependent truck-drone routing problem with rendezvous locations," Journal of Heuristics, Springer, vol. 30(1), pages 1-41, April.
    17. Liu, Yiming & Yu, Yang & Baldacci, Roberto & Tang, Jiafu & Sun, Wei, 2025. "Optimizing carbon emissions in green logistics for time-dependent routing," Transportation Research Part B: Methodological, Elsevier, vol. 192(C).
    18. Cristián E. Cortés & Doris Sáez & Alfredo Núñez & Diego Muñoz-Carpintero, 2009. "Hybrid Adaptive Predictive Control for a Dynamic Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 43(1), pages 27-42, February.
    19. Tiwari, Anurag & Chang, Pei-Chann, 2015. "A block recombination approach to solve green vehicle routing problem," International Journal of Production Economics, Elsevier, vol. 164(C), pages 379-387.
    20. Abdelkader Sbihi & Richard Eglese, 2010. "Combinatorial optimization and Green Logistics," Annals of Operations Research, Springer, vol. 175(1), pages 159-175, March.

    More about this item

    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:hin:complx:2826082. 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: Mohamed Abdelhakeem (email available below). General contact details of provider: https://www.hindawi.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.