A Canceling Heuristic for the Directed Traveling Salesman Problem
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
The Traveling Salesman Problem (TSP) is one of the classic and hard problems in combinatorial optimization. We develop a new heuristic that uses a connection between Minimum Cost Flow Problems and the TSP to improve on a given suboptimal tour, such as a local optimum found using a classic heuristic. Minimum Cost Flow Problems can be solved efficiently through linear programming or combinatorial algorithms based on cycle canceling. We investigate the potential of flow-canceling in the context of the TSP. Through a restriction of the search space to cycles and circulations that alternate between arcs in- and outside of the tour, practical results exhibit that only a low number of subtours is created, and a lightweight patching step suffices for a high success rate and gap closure towards an optimum.
Fields of Study & Subjects
Vehicle Routing Optimization Methods
Complexity and Algorithms in Graphs
Metaheuristic Optimization Algorithms Research
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 27 March 2026
- Language
- EN
- Document type
- Preprint