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 |
Keywords
- Branch-and-cut
- Branch-and-price
- Capacity
- Peripatetic Salesman Problem
- Traveling Salesman Problem
ASJC Scopus subject areas
- Computer Science(all)
- Modelling and Simulation
- Management Science and Operations Research
- Information Systems and Management