On the high multiplicity traveling salesman problem

Alexander Grigoriev, Joris Van De Klundert

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


This paper considers a version of the traveling salesman problem where the cities are to be visited multiple times. Each city has its own required number of visits. We investigate how the optimal solution and its objective value change when the numbers of visits are increased by a common multiplicator. In addition, we derive lower bounds on values of the multiplicator beyond which further increase does not improve the average tour length. Moreover, we show how and when the structure of an optimal tour length can be derived from tours with smaller multiplicities.

Original languageEnglish
Pages (from-to)50-62
Number of pages13
JournalDiscrete Optimization
Issue number1
StatePublished - 1 Mar 2006
Externally publishedYes


  • High multiplicity
  • Traveling salesman problem


Dive into the research topics of 'On the high multiplicity traveling salesman problem'. Together they form a unique fingerprint.

Cite this