Geodesic
On Solving Travelling Salesman Problem With Vertex Requisitions
Yugoslav journal of operations research, Tome 27 (2017) no. 4, p. 415 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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.
Classification : 90C59, 90C10
Keywords: Combinatorial Optimization, System of Vertex Requisitions, Local Search, Integer Programming 
@article{YJOR_2017_27_4_a1,
     author = {Anton V. Eremeev and Yulia V. Kovalenko},
     title = {On {Solving} {Travelling} {Salesman} {Problem} {With} {Vertex} {Requisitions}},
     journal = {Yugoslav journal of operations research},
     pages = {415 },
     publisher = {mathdoc},
     volume = {27},
     number = {4},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2017_27_4_a1/}
}
TY  - JOUR
AU  - Anton V. Eremeev
AU  - Yulia V. Kovalenko
TI  - On Solving Travelling Salesman Problem With Vertex Requisitions
JO  - Yugoslav journal of operations research
PY  - 2017
SP  - 415 
VL  - 27
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_2017_27_4_a1/
LA  - en
ID  - YJOR_2017_27_4_a1
ER  - 
%0 Journal Article
%A Anton V. Eremeev
%A Yulia V. Kovalenko
%T On Solving Travelling Salesman Problem With Vertex Requisitions
%J Yugoslav journal of operations research
%D 2017
%P 415 
%V 27
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_2017_27_4_a1/
%G en
%F YJOR_2017_27_4_a1
Anton V. Eremeev; Yulia V. Kovalenko. On Solving Travelling Salesman Problem With Vertex Requisitions. Yugoslav journal of operations research, Tome 27 (2017) no. 4, p. 415 . http://geodesic.mathdoc.fr/item/YJOR_2017_27_4_a1/