This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Duchenne, E. Articles by Semet, F. Search for Related Content

The Undirected m-Peripatetic Salesman Problem: Polyhedral Results and New Algorithms

LAMIH, Université de Valenciennes et du Hainaut-Cambresis, 59313 Valenciennes Cedex 9, France
Centre de Recherche sur les Transports, HEC Montréal, Montreal, Quebec, Canada H3T 2A7
LAMIH, Université de Valenciennes et du Hainaut-Cambresis, 59313 Valenciennes Cedex 9, France
eric.duchenne{at}univ-valenciennes.fr
gilbert{at}crt.umontreal.ca
frederic.semet{at}univ-valenciennes.fr

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.

Subject classifications: mathematics; combinatorics; networks/graphs; traveling salesman; programming; integer.
History: Received March 2005; revision received September 2006; accepted December 2006.