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. | Yugoslav Journal of Operations Research 27 (2017), Number 4, 415–426 DOI: ON SOLVING TRAVELLING SALESMAN PROBLEM WITH VERTEX REQUISITIONS Anton V. EREMEEV Sobolev Institute of Mathematics SB RAS, Omsk State University . . Dostoevsky eremeev@ Yulia V. KOVALENKO Sobolev Institute of Mathematics SB RAS, Received: October 2016 / Accepted: March 2017 Abstract: 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: Combinatorial Optimization, System of Vertex Requisitions, Local Search, Integer Programming. MSC: 90C59, 90C10. 1. INTRODUCTION The Travelling Salesman Problem (TSP) is one of the well-known NP-hard combinatorial optimization problems [6]: given a complete arc-weighted digraph This research of the authors is supported by the Russian Science Foundation Grant (project no. 1511-10009). 416 A. V. Eremeev, Y. V. Kovalenko / On Solving Travelling Salesman Problem with n vertices, find a shortest travelling salesman tour (Hamiltonian circuit) in it. The TSP with Vertex Requisitions (TSPVR) was formulated by . Serdyukov in [12]: find a shortest travelling salesman tour, passing at ith position a vertex from a given subset Xi , i = 1, . . . , n. A special case where |Xi | = n, i = 1, . . . , n, is equivalent to the TSP. This problem can be interpreted in terms of scheduling theory. Consider a single machine that .
