Informacionnye TehnologiiInformacionnye TehnologiiИнформационные технологии1684-6400New Technologies Publishing House70236510.17587/it.30.607-615Modeling and optimizationМоделирование и оптимизацияResearch ArticleResults of computational experiment for solving the minimum traveling salesman problem by the cycle merging algorithmРезультаты вычислительного эксперимента для решения задачи коммивояжера на минимум алгоритмом соединения цикловLeonovaI. F.ЛеоноваЮ. Ф.
Russian Federation

Postgraduate Student

аспирант

yuliya.igosheva@gmail.comSouth Ural State UniversityЮжно-Уральский государственный университет1512202430126076150802202608022026Copyright ©; 2024, Informacionnye TehnologiiCopyright ©; 2024, Информационные технологии2024Informacionnye TehnologiiИнформационные технологииhttps://journals.eco-vector.com/1684-6400/article/view/702365

The traveling salesman problem is an important combinatorial optimization problem, which consists in finding the shortest path that passes through each city exactly once and ends at the starting point. Despite its simple formulation, this problem turns out to be computationally complex, and its exact solution requires significant computational resources. In this regard, the search for efficient algorithms to solve the traveling salesman problem remains an urgent task in the context of modern technological challenges. In this paper we present the results of a computational experiment that gives an insight into the quality of the cycle merging algorithm for the minimum traveling salesman problem. The quality of the cycle merging algorithm is investigated on seven sets of instances of the traveling salesman problem. The results obtained are compared with the results of computational experiments for some known heuristics. The analysis allows us to say that the cycle merging algorithm shows relatively good results for all tested sets and can be used for a wide range of instances of the traveling salesman problem as a relatively fast heuristic of good enough quality.

Приведены результаты вычислительного эксперимента, дающего представление о качестве алгоритма соединения циклов для задачи коммивояжера на минимум в сравнении с результатами вычислительных экспериментов для некоторых известных эвристик. Проведенный анализ позволяет говорить, что алгоритм соединения циклов может использоваться для широкого спектра экземпляров задачи коммивояжера в качестве относительно быстрой эвристики достаточно хорошего качества.

traveling salesman problemheuristic algorithmconstruction algorithmcomputational experimentзадача коммивояжераэвристический алгоритмалгоритм построения туравычислительный экспериментTurkensteen M., Ghosh D., Goldengorin B., Sierksma G. Tolerance-based branch and bound algorithms, A EURO conference for young OR researches and practitioners, ORP3 2005, 6—10 September 2005, Valencia, Spain. Proceedings Edited by C. Maroto et al., ESMAP SL, 2005, pp. 171—182.Turkensteen M., Ghosh D., Goldengorin B., Sierksma G. Tolerance-based branch and bound algorithms. A EURO conference for young OR researches and practitioners, ORP3 2005, 6—10 September 2005, Valencia, Spain // Proceedings Edited by C. Maroto et al., ESMAP SL. 2005. P. 171—182.Johnson D. S., Gutin G., McGeoch L. A., Yeo A., Zhang W., Zverovitch A. Experimental analysis of heuristics for the ATSP. The traveling salesman problem and its variations, Combinatorial Optimization, vol 12, Springer, Boston, MA, 2007, pp. 445—487, doi: 10.1007/0-306-48213-4_1O.Johnson D. S., Gutin G., McGeoch L. A., Yeo A., Zhang W., Zverovitch A. Experimental analysis of heuristics for the ATSP // The traveling salesman problem and its variations. Combinatorial Optimization, Vol. 12. Springer, Boston, MA. 2007. P. 445—487. DOI: 10.1007/0-306-48213-4_10.Glover F., Gutin G., Yeo A., Zverovich A. Construction heuristics for the asymmetric TSP, European Journal of Operational Research, 2001, vol. 129, no. 3, pp. 555—568, doi: 1O.1016/s0377- 2217(99)00468-3.Glover F., Gutin G., Yeo A., Zverovich A. Construction heuristics for the asymmetric TSP //European Journal of Operational Research. 2001. Vol. 129, N. 3. P. 555—568. DOI: 10.1016/ s0377-2217(99)00468-3.Gutin G., Yeo A., Zverovich A. Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP, Discrete Applied Mathematics, 2002, vol. 117, no. 1—3, pp. 81—86, doi: 10.1016/s0166-218x(01)00195-0.Gutin G., Yeo A., Zverovich A. Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP // Discrete Applied Mathematics. 2002. Vol. 117, N. 1—3. P. 81—86. DOI: 10.1016/s0166-218x(01)00195-0.Panyukov A. V., Leonova Yu. F. Cycle merging algorithm for the metric problem of the traveling salesman at maximum, Bulletin of the South Ural State University. Series: Computational Mathematics and Informatics, 2021, vol. 10, no. 4, pp. 26—36 (in Russian), doi: 10.14529/cmse210402.Панюков А. В., Леонова Ю. Ф. Алгоритм соединения циклов для метрической задачи коммивояжера на максимум // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 4. С. 26—36. DOI: 10.14529/cmse210402.Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem, Operations Research Forum, Cham, Springer International Publishing, 2022, vol. 3, no. 1, p. 20.Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem // Operations Research Forum. Cham: Springer International Publishing. 2022. Vol. 3, N. 1. P. 20.Google. 2015. OR-tools: Google’s Operations Research tools, available at: https://developers.google.com/optimization?hl=ru (date of access: 01.03.24).Google. 2015. OR-tools: Google’s Operations Research tools. URL: https://developers.google.com/optimization?hl=ru (дата обращения: 01.03.24).Johnson D. S., McGeoch L. A. The Travelling Saleman Problem: A case study in Local Optimization, AT&T Labs, Florham Park, Department of Mathematics and Computer Science, Amherst College, 1995.Johnson D. S., McGeoch L. A. The Travelling Saleman Problem: A case study in Local Optimization // AT&T Labs, Florham Park, Department of Mathematics and Computer Science, Amherst College, 1995.Helsgaun K. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems, Roskilde, Roskilde University, 2017, vol. 12, pp. 966—980.Helsgaun K. An extension of the Lin-Kernighan-Hels-gaun TSP solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017. Vol. 12. P. 966—980.Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling-salesman problem, Operations research, 1973, vol. 21, no. 2, pp. 498—516.Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling-salesman problem // Operations research. 1973. Vol. 21, N. 2. P. 498—516.Helsgaun K. An effective implementation of the Lin—Ker- nighan traveling salesman heuristic, European journal of operational research, 2000, vol. 126, no. 1, pp. 106—130.Helsgaun K. An effective implementation of the Lin— Kernighan traveling salesman heuristic // European journal of operational research. 2000. Vol. 126, N. 1. P. 106—130.Johnson D. S. A case study in local optimization, Local search in combinatorial optimization, 1997, pp. 215—310, DOI: 10.2307/j.ctv346t9c.Johnson D. S. A case study in local optimization // Local search in combinatorial optimization. 1997. P. 215—310. DOI: 10.2307/j.ctv346t9c.Reinelt G. The traveling salesman: Computational solutions for TSP applications, Springer, 1994.Reinelt G. The traveling salesman: Computational solutions for TSP applications. Springer, 1994.Karp R. M. A patching algorithm for the nonsymmetric traveling-salesman problem, SIAM Journal on Computing, 1979, vol. 8, no. 4, pp. 561—573, doi: 10.1137/0208045.Karp R. M. A patching algorithm for the nonsymmetric traveling-salesman problem // SIAM Journal on Computing. 1979. Vol. 8, N. 4. P. 561—573. DOI: 10.1137/0208045.Karp R. M., Steele J. M. Probabilistic analysis of heuristics, The traveling salesman problem, 1985, pp. 181—205.Karp R. M., Steele J. M. Probabilistic analysis of heuristics // The traveling salesman problem. 1985. P. 181—205.Yeo A. Large exponential neighbourhoods for the TSP, Preprint, Odense, Denmark, Dept of Maths and CS, Odense University, 1997.Yeo A. Large exponential neighbourhoods for the TSP. Preprint. Odense, Denmark: Dept of Maths and CS, Odense University, 1997.Deineko V. G., Woeginger G. J. A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem, Mathematical programming, 2000, vol. 87, pp. 519—542, doi: 1O.1OO7/S1O1O7OO5O01O.Deineko V. G., Woeginger G. J. A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem // Mathematical programming. 2000. Vol. 87. P. 519—542. DOI: 10.1007/s101070050010.Glover F., Punnen A. P. The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms, Journal of the Operational Research Society, 1997, vol. 48, pp. 502—510, doi: 10.1038/sj.jors.2600392.Glover F., Punnen A. P. The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms // Journal of the Operational Research Society. 1997. Vol. 48. P. 502—510. DOI: 10.1038/sj.jors.2600392.Gutin G. Exponential neighbourhood local search for the traveling salesman problem, Computers & Operations Research , 1999, vol. 26, no. 4, pp. 313—320, doi: 10.1016/s0305- 0548(98)00064-1.Gutin G. Exponential neighbourhood local search for the traveling salesman problem // Computers & Operations Research. 1999. Vol. 26, N. 4. P. 313—320. DOI: 10.1016/s0305- 0548(98)00064-1.Gutin G., Yeo A. Small diameter neighbourhood graphs for the traveling salesman problem: at most four moves from tour to tour, Computers & Operations Research, 1999, vol. 26, no. 4, pp. 321—327, doi: 10.1016/s0305-0548(98)00065-3.Gutin G., Yeo A. Small diameter neighbourhood graphs for the traveling salesman problem: at most four moves from tour to tour // Computers & Operations Research. 1999. Vol. 26, N. 4. P. 321—327. DOI: 10.1016/s0305-0548(98)00065-3.Balas E., Simonetti N. Linear time dynamic programming algorithms for some new classes of restricted TSP’s, Proc. IPCO V, LNCS, 1996, vol. 1084, pp. 316—329, doi: 10.1287/ijoc.13.1.56.9748.Balas E., Simonetti N. Linear time dynamic programming algorithms for some new classes of restricted TSP’s // Proc. IPCO V, LNCS. 1996. Vol. 1084. P. 316—329. DOI: 10.1287/ ijoc.13.1.56.9748.Carlier J., Villon P. A new heuristic for the traveling salesman problem, RAIRO-Operations Research, 1990, vol. 24, no. 3, pp. 245—253, ' doi: 10.1051/ro/1990240302451.Carlier J., Villon P. A new heuristic for the traveling salesman problem // RAIRO-Operations Research. 1990. Vol. 24, N. 3. P. 245—253. DOI: 10.1051/ro/1990240302451.Sigal I. H., Ivanova A. P. Introduction to Applied Discrete Programming. Models and computational algorithms, Moscow, FIZMATLIT, 2007, 304 p. (in Russian).Сигал И. Х., Иванова А. П. Введение в прикладное дискретное программирование. Модели и вычислительные алгоритмы. М.: Физматлит, 2007. 304 с.Reinelt G. TSPLIB—A traveling salesman problem library, ORSA journal on computing, 1991, vol. 3 (INFORMS), pp. 376—384, doi: 10.1287/ijoc.3.4.376.Reinelt G. TSPLIB—A traveling salesman problem library // ORSA journal on computing. Vol. 3 (INFORMS). 1991. P. 376—384. DOI: 10.1287/ijoc.3.4.376.Leonova Yu. F. Investigation of the quality of the cycle merging algorithm on examples from the TSPLIB library, Actual problems of applied mathematics, computer science and mechanics: proceedings of the International Scientific Conference, Voronezh, 13—15 December 2021, Voronezh, 2022, pp. 573—579 (in Russian).Леонова Ю. Ф. Исследование качества алгоритма соединения циклов на примерах из библиотеки TSPLIB // Актуальные проблемы прикладной математики, информатики и механики: сб. тр. Междунар. науч. конф., Воронеж, 13—15 декабря 2021 г. Воронеж, 2022. С. 573—579.Balas E., Thoth P. Branch and bound methods. Ghaptcr 10, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, New York, 1985, pp. 80—147, doi: 10.21236/ada126957.Balas E., Thoth P. Branch and bound methods. Chapter 10 // The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. New York: John Wiley & Sons, 1985. P. 80—147. DOI: 10.21236/ada126957.Held M., Karp R. M. The traveling-salesman problem and minimum spanning trees, Operations research, 1970, vol. 18, no. 6, pp. 1138—1162, doi: 10.1287/opre.18.6.1138.Held M., Karp R. M. The traveling-salesman problem and minimum spanning trees // Operations research. 1970. Vol. 18, N. 6. P. 1138—1162. DOI: 10.1287/opre.18.6.1138.Held M., Karp R. M. The traveling-salesman problem and minimum spanning trees: Part II, Mathematical programming, 1971, vol. 1, no. 1, pp. 6—25, doi: 10.1007/bf01584070.Held M., Karp R. M. The traveling-salesman problem and minimum spanning trees: Part II // Mathematical programming. 1971. Vol. 1, N. 1. P. 6—25. DOI: 10.1007/bf01584070.Zverovitch A. E. Construction Heuristics for Hard Combinatorial Optimisation Problems, Diss. University of London, 2003.Zverovitch A. E. Construction Heuristics for Hard Combinatorial Optimisation Problems. Дисс. University of London, 2003.