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

Formulations and Branch-and-cut algorithms for the Period Travelling Salesman Problem

Author

Listed:
  • Henriques, Sofia
  • Paias, Ana

Abstract

In this work, we address two variants of the Period Travelling Salesman Problem: one where some nodes cannot be visited consecutively over the time horizon, and another one where this restriction is not imposed. A new flow-based formulation that uses specific information about the visit patterns of nodes is studied and empirical tests show that it is able to solve test instances where a flow-based formulation based on the Single Commodity Flow formulation for the Travelling Salesman Problem reached the time limit. Non-compact formulations are studied in this work as well. We propose two new sets of exponentially-sized valid inequalities that have not been studied yet in the literature. A formulation which is based on connectivity cuts per period enhanced with these sets of valid inequalities proved to be the most efficient and it was able to solve several instances.

Suggested Citation

  • Henriques, Sofia & Paias, Ana, 2025. "Formulations and Branch-and-cut algorithms for the Period Travelling Salesman Problem," European Journal of Operational Research, Elsevier, vol. 323(3), pages 739-752.
    • Handle: RePEc:eee:ejores:v:323:y:2025:i:3:p:739-752
    DOI: 10.1016/j.ejor.2025.01.015
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221725000402
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2025.01.015?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. Baptista, Susana & Oliveira, Rui Carvalho & Zuquete, Eduardo, 2002. "A period vehicle routing case study," European Journal of Operational Research, Elsevier, vol. 139(2), pages 220-229, June.
    2. Rodríguez-Martín, Inmaculada & Salazar-González, Juan-José & Yaman, Hande, 2019. "The periodic vehicle routing problem with driver consistency," European Journal of Operational Research, Elsevier, vol. 273(2), pages 575-584.
    3. Sun, Lei & Karwan, Mark H. & Diaby, Moustapha, 2018. "The indefinite period traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 270(3), pages 1171-1181.
    4. Bassetto, Tatiana & Mason, Francesco, 2011. "Heuristic algorithms for the 2-period balanced Travelling Salesman Problem in Euclidean graphs," European Journal of Operational Research, Elsevier, vol. 208(3), pages 253-262, February.
    5. Tan, C.C.R. & Beasley, J.E., 1984. "A heuristic algorithm for the period vehicle routing problem," Omega, Elsevier, vol. 12(5), pages 497-504.
    6. Kara, Imdat & Bektas, Tolga, 2006. "Integer linear programming formulations of multiple salesman problems and its variations," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1449-1458, November.
    7. Roberto Baldacci & Enrico Bartolini & Aristide Mingozzi & Andrea Valletta, 2011. "An Exact Algorithm for the Period Routing Problem," Operations Research, INFORMS, vol. 59(1), pages 228-241, February.
    8. Hemmelmayr, Vera C. & Doerner, Karl F. & Hartl, Richard F., 2009. "A variable neighborhood search heuristic for periodic routing problems," European Journal of Operational Research, Elsevier, vol. 195(3), pages 791-802, June.
    9. Mourgaya, M. & Vanderbeck, F., 2007. "Column generation based heuristic for tactical planning in multi-period vehicle routing," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1028-1041, December.
    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. Rodríguez-Martín, Inmaculada & Yaman, Hande, 2022. "Periodic Vehicle Routing Problem with Driver Consistency and service time optimization," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 468-484.
    2. Rodríguez-Martín, Inmaculada & Salazar-González, Juan-José & Yaman, Hande, 2019. "The periodic vehicle routing problem with driver consistency," European Journal of Operational Research, Elsevier, vol. 273(2), pages 575-584.
    3. Sinem Kınay Savaşer & Bahar Yetis Kara, 2022. "Mobile healthcare services in rural areas: an application with periodic location routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 875-910, September.
    4. Halvorsen-Weare, Elin E. & Fagerholt, Kjetil & Nonås, Lars Magne & Asbjørnslett, Bjørn Egil, 2012. "Optimal fleet composition and periodic routing of offshore supply vessels," European Journal of Operational Research, Elsevier, vol. 223(2), pages 508-517.
    5. Roberto Baldacci & Enrico Bartolini & Aristide Mingozzi & Andrea Valletta, 2011. "An Exact Algorithm for the Period Routing Problem," Operations Research, INFORMS, vol. 59(1), pages 228-241, February.
    6. Song, Ruidian & Zhao, Lei & Van Woensel, Tom & Fransoo, Jan C., 2019. "Coordinated delivery in urban retail," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 122-148.
    7. Campelo, Pedro & Neves-Moreira, Fábio & Amorim, Pedro & Almada-Lobo, Bernardo, 2019. "Consistent vehicle routing problem with service level agreements: A case study in the pharmaceutical distribution sector," European Journal of Operational Research, Elsevier, vol. 273(1), pages 131-145.
    8. Ann-Kathrin Rothenbächer, 2017. "Branch-and-Price-and-Cut for the Periodic Vehicle Routing Problem with Flexible Schedule Structures," Working Papers 1714, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    9. Fabien Tricoire & Nathalie Bostel & Pierre Dejax & Pierre Guez, 2013. "Exact and hybrid methods for the multiperiod field service 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. 21(2), pages 359-377, March.
    10. Liu, Ran & Xie, Xiaolan & Garaix, Thierry, 2014. "Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics," Omega, Elsevier, vol. 47(C), pages 17-32.
    11. Chen, Yujie & Cowling, Peter & Polack, Fiona & Remde, Stephen & Mourdjis, Philip, 2017. "Dynamic optimisation of preventative and corrective maintenance schedules for a large scale urban drainage system," European Journal of Operational Research, Elsevier, vol. 257(2), pages 494-510.
    12. Nair, D.J. & Grzybowska, H. & Fu, Y. & Dixit, V.V., 2018. "Scheduling and routing models for food rescue and delivery operations," Socio-Economic Planning Sciences, Elsevier, vol. 63(C), pages 18-32.
    13. Ramos, Tânia Rodrigues Pereira & Gomes, Maria Isabel & Barbosa-Póvoa, Ana Paula, 2014. "Assessing and improving management practices when planning packaging waste collection systems," Resources, Conservation & Recycling, Elsevier, vol. 85(C), pages 116-129.
    14. le Blanc, H.M. & Cruijssen, F. & Fleuren, H.A. & de Koster, M.B.M., 2006. "Factory gate pricing: An analysis of the Dutch retail distribution," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1950-1967, November.
    15. Theodore Athanasopoulos & Ioannis Minis, 2013. "Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework," Annals of Operations Research, Springer, vol. 206(1), pages 1-22, July.
    16. Aksen, Deniz & Kaya, Onur & Sibel Salman, F. & Tüncel, Özge, 2014. "An adaptive large neighborhood search algorithm for a selective and periodic inventory routing problem," European Journal of Operational Research, Elsevier, vol. 239(2), pages 413-426.
    17. Vieira, Bruno S. & Ribeiro, Glaydston M. & Bahiense, Laura & Cruz, Roberto & Mendes, André B. & Laporte, Gilbert, 2021. "Exact and heuristic algorithms for the fleet composition and periodic routing problem of offshore supply vessels with berth allocation decisions," European Journal of Operational Research, Elsevier, vol. 295(3), pages 908-923.
    18. Cruijssen, F., 2006. "Horizontal cooperation in transport and logistics," Other publications TiSEM ab6dbe68-aebc-4b03-8eea-d, Tilburg University, School of Economics and Management.
    19. Ann-Kathrin Rothenbächer, 2019. "Branch-and-Price-and-Cut for the Periodic Vehicle Routing Problem with Flexible Schedule Structures," Transportation Science, INFORMS, vol. 53(3), pages 850-866, May.
    20. D Ronen & C A Goodhart, 2008. "Tactical store delivery planning," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(8), pages 1047-1054, 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:eee:ejores:v:323:y:2025:i:3:p:739-752. 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.