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.
