Yugoslav Journal of Operations Research (Jan 2017)

On solving Travelling Salesman Problem with Vertex Requisitions

  • Eremeev Anton V.,
  • Kovalenko Yulia V.

DOI
https://doi.org/10.2298/YJOR161012003E
Journal volume & issue
Vol. 27, no. 4
pp. 415 – 426

Abstract

Read online

We consider the Travelling Salesman Problem with Vertex Requisitions where, for each position of the tour, at most two possible vertices are given. It is known that the problem is strongly NP-hard. The algorithm, we propose for this problem, has less time complexity compared to the previously known one. In particular, almost all feasible instances of the problem are solvable in O(n) time using the new algorithm, where n is the number of vertices. The developed approach also helps in fast enumeration of a neighborhood in the local search and yields an integer programming model with O(n) binary variables for the problem.

Keywords