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

Éric Duchenne (), Gilbert Laporte () and Frédéric Semet ()
Additional contact information
Éric Duchenne: LAMIH, Université de Valenciennes et du Hainaut-Cambresis, 59313 Valenciennes Cedex 9, France
Gilbert Laporte: Centre de Recherche sur les Transports, HEC Montréal, Montreal, Quebec, Canada H3T 2A7
Frédéric Semet: LAMIH, Université de Valenciennes et du Hainaut-Cambresis, 59313 Valenciennes Cedex 9, France

Operations Research, 2007, vol. 55, issue 5, 949-965

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 (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1070.0387 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:55:y:2007:i:5:p:949-965

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().