On solving Travelling Salesman Problem with Vertex Requisitions

Authors

  • Anton V. Eremeev Omsk State University n.a. F.M. Dostoevsky, Omsk Branch of Sobolev Institute of Mathematics SB RAS, Omsk, Russia
  • Yulia V. Kovalenko Omsk State University n.a. F.M. Dostoevsky, Omsk Branch of Sobolev Institute of Mathematics SB RAS, Omsk, Russia

DOI:

https://doi.org/10.2298/YJOR161012003E

Keywords:

Combinatorial optimization, System of vertex requisitions, Local search, Integer programming

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.

References

Chvatal, V., “Probabilistic methods in graph theory”, Annals of Operations Research, 1 (1984) 171-182.

Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C., Introduction to Algorithms, 2nd edition, MIT Press, 2001.

Eremeev, A., and Kovalenko, J., “Optimal recombination in genetic algorithms for combinatorial optimization problems: Part II”, Yugoslav Journal of Operations Research, 24 (2) (2014) 165-186.

Feller, W., An Introduction to Probability Theory and Its Applications, Vol. 1, John Wiley & Sons, New York, NY, 1968.

Garey, M.R., and Johnson, D.S., “Strong NP-completeness results: Motivation, examples, and implications”, Journal of the ACM, 25 (1978) 499-508.

Garey, M.R., and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, San Francisco, CA, 1979.

Kochetov, Yu. A., “Computational bounds for local search in combinatorial optimization”, Computational Mathematics and Mathematical Physics, 48 (5) (2008) 747-763.

Reingold, E.M., Nievergelt, J., and Deo, N., Combinatorial Algorithms: Theory and Practice, Englewood Cliffs, Prentice-Hall, 1977.

Riordan, J., An Introduction to Combinatorial Analysis, John Wiley & Sons, New York, NY, 1958.

Serdyukov, A.I., “On travelling salesman problem with prohibitions”, Upravlyaemye Sistemy, 17 (1978) 80-86. (In Russian)

Serdyukov, A.I., “On finding Hamilton cycle (circuit) problem with prohibitions”, Upravlyaemye Sistemy, 19 (1979) 57-64. (In Russian)

Serdyukov, A.I., “Complexity of solving the travelling salesman problem with requisitions on graphs with small degree of vertices”, Upravlyaemye Sistemy, 26 (1985) 73-82. (In Russian)

Downloads

Published

2017-11-01

Issue

Vol. 27 No. 4 (2017)

Section

Research Articles

License

Copyright (c) 2017 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.