The multi-stripe travelling salesman problem

Eranda Çela (), Vladimir G. Deineko () and Gerhard J. Woeginger ()
Additional contact information
Eranda Çela: TU Graz
Vladimir G. Deineko: The University of Warwick
Gerhard J. Woeginger: Lehrstuhl für Informatik 1, RWTH Aachen

Annals of Operations Research, 2017, vol. 259, issue 1, No 2, 34 pages

Abstract: 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\ge 1$$ 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.

Keywords: Combinatorial optimization; Computational complexity; Travelling salesman problem; Quadratic assignment problem; Tractable special case; Kalmanson conditions (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2513-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:259:y:2017:i:1:d:10.1007_s10479-017-2513-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2513-4

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().