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

Przemysław Kowalik (), Grzegorz Sobecki, Piotr Bawoł and Paweł Muzolf
Additional contact information
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

Sustainability, 2023, vol. 15, issue 5, 1-28

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.

Keywords: travelling salesman problem; integer linear programming; penalties (search for similar items in EconPapers)
JEL-codes: O13 Q Q0 Q2 Q3 Q5 Q56 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2071-1050/15/5/4330/pdf (application/pdf)
https://www.mdpi.com/2071-1050/15/5/4330/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jsusta:v:15:y:2023:i:5:p:4330-:d:1083591

Access Statistics for this article

Sustainability is currently edited by Ms. Alexandra Wu

More articles in Sustainability from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().