- Autor
- Çela, Eranda
- Deineko, Vladimir G.
- Woeginger, Gerhard J.
- TitelThe multi-stripe travelling salesman problem
- Datei
- DOI10.1007/s10479-017-2513-4
- Persistent Identifier
- Erschienen inAnnals of Operations Research
- Band259
- Erscheinungsjahr2017
- Heft1
- Seiten21-34
- ISSN1572-9338
- Download Statistik839
- Peer ReviewJa
- AbstractIn 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.
[476.31 KB]