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.
- 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