Hauptmenü
  • 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
  • ZugriffsrechteCC-BY
  • Download Statistik622
  • 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.