Abstract
In the m-Capacitated Peripatetic Salesman Problem (m-CPSP) the aim is to determine m Hamiltonian cycles of minimal total cost on a graph, such that all the edges are traversed less than the value of their capacity. This article introduces three formulations for the m-CPSP. Two branch-and-cut algorithms and one branch-and-price algorithm are developed. Tests performed on randomly generated and on TSPLIB Euclidean instances indicate that the branch-and-price algorithm can solve instances with more than twice the size of what is achievable with the branch-and-cut algorithms.
| Original language | English |
|---|---|
| Pages (from-to) | 637-643 |
| Number of pages | 7 |
| Journal | European Journal of Operational Research |
| Volume | 223 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 16 Dec 2012 |
Funding
This work was partially supported by the International Campus on Safety and Intermodality in Transportation, the Nord–Pas-de-Calais Region, the European Community, the Regional Delegation for Research and Technology, the French Ministry of Higher Education and Research, the National Center for Scientific Research, and the Canadian Natural Sciences and Engineering Research Council under grant 39682-10. This support is gratefully acknowledged. Thanks are due to the referees for their valuable comments.
Keywords
- Branch-and-cut
- Branch-and-price
- Capacity
- Peripatetic Salesman Problem
- Traveling Salesman Problem
ASJC Scopus subject areas
- General Computer Science
- Modelling and Simulation
- Management Science and Operations Research
- Information Systems and Management