The multi-stripe travelling salesman problem
研究了q条带旅行商问题，其中目标函数计算从一个城市到后续q个城市的旅行成本之和，分析了不同距离矩阵结构下的计算复杂性，包括NP难和多项式可解情况。
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$$ , 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.