A platform for research: civil engineering, architecture and urbanism
A platform for research: civil engineering, architecture and urbanism
A Flow-Based Formulation of the Travelling Salesman Problem with Penalties on Nodes
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.
A Flow-Based Formulation of the Travelling Salesman Problem with Penalties on Nodes
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.
A Flow-Based Formulation of the Travelling Salesman Problem with Penalties on Nodes
Przemysław Kowalik (author) / Grzegorz Sobecki (author) / Piotr Bawoł (author) / Paweł Muzolf (author)
2023
Article (Journal)
Electronic Resource
Unknown
Metadata by DOAJ is licensed under CC BY-SA 1.0
Combinatorial Optimization: Comparison of Heuristic Algorithms in Travelling Salesman Problem
| Online Contents | 2017
An Improved Routing Optimization Algorithm Based on Travelling Salesman Problem for Social Networks
| DOAJ | 2017
Applications of Travelling Salesman Optimization in Construction Scheduling
| Springer Verlag | 2024
New Formulation for Traveling Salesman Problem with Separation Requirement and Cost
| British Library Online Contents | 2011