Abstract
In the classical Travelling Salesman Problem (TSP), the objective function sums the costs for travelling from one city to the next city along the tour. In the q-stripe TSP with q≥1, the objective function sums the costs for travelling from one city to each of the next q cities in the tour. The resulting q-stripe TSP generalizes the TSP and forms a special case of the quadratic assignment problem. We analyze the computational complexity of the q-stripe TSP for various classes of specially structured distance matrices. We derive NP-hardness results as well as polynomially solvable cases. One of our main results generalizes a well-known theorem of Kalmanson from the classical TSP to the q-stripe TSP.
Originalsprache | englisch |
---|---|
Seiten (von - bis) | 21-34 |
Seitenumfang | 14 |
Fachzeitschrift | Annals of Operations Research |
Jahrgang | 259 |
Ausgabenummer | 1-2 |
DOIs | |
Publikationsstatus | Veröffentlicht - 2017 |
ASJC Scopus subject areas
- Allgemeine Mathematik
Fields of Expertise
- Information, Communication & Computing
Treatment code (Nähere Zuordnung)
- Basic - Fundamental (Grundlagenforschung)