A Canceling Heuristic for the Directed Traveling Salesman Problem

Read full text Summarise with VIRAT
Authors: Steffen Borgwardt, Zachary Sorenson
Cited by: 0
References: 17

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