On Solving Travelling Salesman Problem with Vertex Requisitions

  • Anton Valentinovich Eremeev Omsk Branch of Sobolev Institute of Mathematics SB RAS
  • Yulia Viktorovna Kovalenko Sobolev Institute of Mathematics SB RAS

Abstract

We consider the Travelling Salesman Problem with Vertex Requisitions, where each position of the tour is given at most two possible vertices to pass. The problem is known to be strongly NP-hard. The proposed algorithm for this problem has smaller time complexity compared to the previously known one. In particular, almost all instances of the problem are solvable in O(n) time using the new  algorithm, n being 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 under consideration.

Published
Mar 29, 2017
How to Cite
EREMEEV, Anton Valentinovich; KOVALENKO, Yulia Viktorovna. On Solving Travelling Salesman Problem with Vertex Requisitions. Yugoslav Journal of Operations Research, [S.l.], mar. 2017. ISSN 2334-6043. Available at: <http://yujor.fon.bg.ac.rs/index.php/yujor/article/view/54>. Date accessed: 23 aug. 2017.
Section
Articles