| Article ID: | iaor20083407 |
| Country: | United States |
| Volume: | 55 |
| Issue: | 5 |
| Start Page Number: | 949 |
| End Page Number: | 965 |
| Publication Date: | Sep 2007 |
| Journal: | Operations Research |
| Authors: | Laporte Gilbert, Semet Frdric, Duchenne ric |
| Keywords: | combinatorial optimization, programming: integer |
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.