IDEAS home Printed from https://ideas.repec.org/a/gam/jsusta/v15y2023i5p4330-d1083591.html
   My bibliography  Save this article

A Flow-Based Formulation of the Travelling Salesman Problem with Penalties on Nodes

Author

Listed:
  • Przemysław Kowalik

    (Department of Quantitative Methods in Management, Faculty of Management, Lublin University of Technology, ul. Nadbystrzycka 38, 20-618 Lublin, Poland)

  • Grzegorz Sobecki

    (General Military Department, Military University of Technology, ul. Gen. Sylwestra Kaliskiego 2, 00-908 Warszawa, Poland)

  • Piotr Bawoł

    (General Military Department, Military University of Technology, ul. Gen. Sylwestra Kaliskiego 2, 00-908 Warszawa, Poland)

  • Paweł Muzolf

    (Faculty of Civil Engineering and Geodesy, Military University of Technology, ul. Gen. Sylwestra Kaliskiego 2, 00-908 Warszawa, Poland)

Abstract

The travelling salesman problem (TSP) is one of combinatorial optimization problems of huge importance to practical applications. However, the TSP in its “pure” form may lack some essential issues for a decision maker—e.g., time-dependent travelling conditions. Among those shortcomings, there is also a lack of possibility of not visiting some nodes in the network—e.g., thanks to the existence of some more cost-efficient means of transportation. In this article, an extension of the TSP in which some nodes can be skipped at the cost of penalties for skipping those nodes is presented under a new name and in a new mathematical formulation. Such an extension can be applied as a model for transportation cost reduction due to the possibility of outsourcing deliveries to some nodes in a TSP route. An integer linear programming formulation of such a problem based on the Gavish–Graves-flow-based TSP formulation is introduced. This formulation makes it possible to solve the considered problem by using any integer linear programming optimization software. Numerical examples and opportunities for further research are presented.

Suggested Citation

  • Przemysław Kowalik & Grzegorz Sobecki & Piotr Bawoł & Paweł Muzolf, 2023. "A Flow-Based Formulation of the Travelling Salesman Problem with Penalties on Nodes," Sustainability, MDPI, vol. 15(5), pages 1-28, February.
    • Handle: RePEc:gam:jsusta:v:15:y:2023:i:5:p:4330-:d:1083591
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2071-1050/15/5/4330/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2071-1050/15/5/4330/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Jarosław Ziółkowski & Józef Żurek & Jerzy Małachowski & Mateusz Oszczypała & Joanna Szkutnik-Rogoż, 2022. "Method for Calculating the Required Number of Transport Vehicles Supplying Aviation Fuel to Aircraft during Combat Tasks," Sustainability, MDPI, vol. 14(3), pages 1-18, January.
    2. Rusul Abduljabbar & Hussein Dia & Sohani Liyanage & Saeed Asadi Bagloee, 2019. "Applications of Artificial Intelligence in Transport: An Overview," Sustainability, MDPI, vol. 11(1), pages 1-24, January.
    3. Jean-Claude Picard & Maurice Queyranne, 1978. "The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling," Operations Research, INFORMS, vol. 26(1), pages 86-110, February.
    4. Bektas, Tolga, 2006. "The multiple traveling salesman problem: an overview of formulations and solution procedures," Omega, Elsevier, vol. 34(3), pages 209-219, June.
    5. Jarosław Ziółkowski & Aleksandra Lęgas & Elżbieta Szymczyk & Jerzy Małachowski & Mateusz Oszczypała & Joanna Szkutnik-Rogoż, 2022. "Optimization of the Delivery Time within the Distribution Network, Taking into Account Fuel Consumption and the Level of Carbon Dioxide Emissions into the Atmosphere," Energies, MDPI, vol. 15(14), pages 1-22, July.
    6. Niclas Hoffmann & Robert Stahlbock & Stefan Voß, 2020. "A decision model on the repair and maintenance of shipping containers," Journal of Shipping and Trade, Springer, vol. 5(1), pages 1-21, December.
    7. Zhou, Jianli & Wu, Yunna & Tao, Yao & Gao, Jianwei & Zhong, Zhiming & Xu, Chuanbo, 2021. "Geographic information big data-driven two-stage optimization model for location decision of hydrogen refueling stations: An empirical study in China," Energy, Elsevier, vol. 225(C).
    8. Yvan Dumas & Jacques Desrosiers & Eric Gelinas & Marius M. Solomon, 1995. "An Optimal Algorithm for the Traveling Salesman Problem with Time Windows," Operations Research, INFORMS, vol. 43(2), pages 367-371, April.
    9. Merrill M. Flood, 1956. "The Traveling-Salesman Problem," Operations Research, INFORMS, vol. 4(1), pages 61-75, February.
    10. 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.
    11. Russ J. Vander Wiel & Nikolaos V. Sahinidis, 1996. "An exact solution approach for the time‐dependent traveling‐salesman problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(6), pages 797-820, September.
    12. Michael F. Dacey, 1960. "Letter to the Editor---Selection of an Initial Solution for the Traveling-Salesman Problem," Operations Research, INFORMS, vol. 8(1), pages 133-134, February.
    13. Song, Malin & Fisher, Ron & Kwoh, Yusen, 2019. "Technological challenges of green innovation and sustainable resource management with large scale data," Technological Forecasting and Social Change, Elsevier, vol. 144(C), pages 361-368.
    14. Sanjeeb Dash & Oktay Günlük & Andrea Lodi & Andrea Tramontani, 2012. "A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 132-147, February.
    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. Vu, Duc Minh & Hewitt, Mike & Vu, Duc D., 2022. "Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery," European Journal of Operational Research, Elsevier, vol. 302(3), pages 831-846.
    2. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2012. "New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 356-371, August.
    3. Rui Chen & Xinglu Liu & Lixin Miao & Peng Yang, 2020. "Electric Vehicle Tour Planning Considering Range Anxiety," Sustainability, MDPI, vol. 12(9), pages 1-17, May.
    4. 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.
    5. Haluk Yapicioglu, 2018. "Multiperiod Multi Traveling Salesmen Problem Considering Time Window Constraints with an Application to a Real World Case," Networks and Spatial Economics, Springer, vol. 18(4), pages 773-801, December.
    6. Fontaine, Romain & Dibangoye, Jilles & Solnon, Christine, 2023. "Exact and anytime approach for solving the time dependent traveling salesman problem with time windows," European Journal of Operational Research, Elsevier, vol. 311(3), pages 833-844.
    7. Tamás Kalmár-Nagy & Giovanni Giardini & Bendegúz Dezső Bak, 2017. "The Multiagent Planning Problem," Complexity, Hindawi, vol. 2017, pages 1-12, February.
    8. 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.
    9. Christian Tilk & Stefan Irnich, 2014. "Dynamic Programming for the Minimum Tour Duration Problem," Working Papers 1408, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 04 Aug 2014.
    10. 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.
    11. Sonela Stillo & Gentisa Furxhi, 2016. "The Retention of the Employees as Long as Possible in the Organization, Through Finding the Right Factors of Motivation. Albania as a Case of Study," European Journal of Economics and Business Studies Articles, Revistia Research and Publishing, vol. 2, May - Aug.
    12. Natashia L. Boland & Martin W. P. Savelsbergh, 2019. "Perspectives on integer programming for time-dependent models," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(2), pages 147-173, July.
    13. Bruck, Bruno P. & Cordeau, Jean-François & Iori, Manuel, 2018. "A practical time slot management and routing problem for attended home services," Omega, Elsevier, vol. 81(C), pages 208-219.
    14. 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.
    15. Dieter, Peter & Caron, Matthew & Schryen, Guido, 2023. "Integrating driver behavior into last-mile delivery routing: Combining machine learning and optimization in a hybrid decision support framework," European Journal of Operational Research, Elsevier, vol. 311(1), pages 283-300.
    16. Roberto Roberti & Aristide Mingozzi, 2014. "Dynamic ng-Path Relaxation for the Delivery Man Problem," Transportation Science, INFORMS, vol. 48(3), pages 413-424, August.
    17. Christian Tilk & Stefan Irnich, 2017. "Dynamic Programming for the Minimum Tour Duration Problem," Transportation Science, INFORMS, vol. 51(2), pages 549-565, May.
    18. Zang, Xiaoning & Jiang, Li & Liang, Changyong & Fang, Xiang, 2023. "Coordinated home and locker deliveries: An exact approach for the urban delivery problem with conflicting time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    19. Khalid Mekamcha & Mehdi Souier & Hakim Nadhir Bessenouci & Mohammed Bennekrouf, 2021. "Two metaheuristics approaches for solving the traveling salesman problem: an Algerian waste collection case," Operational Research, Springer, vol. 21(3), pages 1641-1661, September.
    20. Vahid Akbari & İhsan Sadati & F. Sibel Salman & Davood Shiri, 2023. "Minimizing total weighted latency in home healthcare routing and scheduling with patient prioritization," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 45(3), pages 807-852, September.

    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:gam:jsusta:v:15:y:2023:i:5:p:4330-:d:1083591. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.