The undirected m-Capacitated Peripatetic Salesman Problem

Éric Duchenne, Gilbert Laporte, Frédéric Semet

Research output: Contribution to journalArticlepeer-review

9 Citations (SciVal)


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 languageEnglish
Pages (from-to)637-643
Number of pages7
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 16 Dec 2012


  • 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


Dive into the research topics of 'The undirected m-Capacitated Peripatetic Salesman Problem'. Together they form a unique fingerprint.

Cite this