The Undirectedm-Peripatetic Salesman Problem: Polyhedral Results and New Algorithms
Éric Duchenne, Gilbert Laporte, Frédéric Semet
Operations Research · 2007 · Volume 55 · Issue 5
Abstract
In the m -peripatetic salesman problem ( m -PSP), the aim is to determine m edge disjoint Hamiltonian cycles of minimum total cost on a graph. This article introduces new valid inequalities and polyhedral results for the m -PSP. An improved 2-index branch-and-cut algorithm is developed. Tests performed on randomly generated and TSPLIB Euclidean instances indicate that this algorithm can solve instances with more than double the size of what was previously achievable.
Keywords
mathematics, combinatorics, networks/graphs, traveling salesman, programming, integer
Enable JavaScript for citation tools and additional paper interactions.