Statistical Study of the Quality of the Cycle Merging Algorithm for Solving the Traveling Salesman Problem at Minimum

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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

References

  1. Zhang C., Sun P. Heuristic Methods for Solving the Traveling Salesman Problem (TSP): A Comparative Study // 2023 IEEE 34th Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC). 2023. P. 1–6. https://doi.org/10.1109/PIMRC56721.2023.10293957
  2. Toaza B., Eszterg´ar-Kiss D. A review of metaheuristic algorithms for solving TSPbased scheduling optimization problems // Appl. Soft Comput. 2023. V. 148. 110908 p. https://doi.org/10.1016/j.asoc.2023.110908
  3. Reingold E.M., Nievergelt J., Deo N. Combinatorial algorithms: theory and practice. Prentice Hall College Div, 1977. https://doi.org/10.2307/2987917
  4. Авдошин С.М., Береснева Е.Н. Метрическая задача коммивояжера: экспериментальное исследование Парето-оптимальных алгоритмов // Труды Института системного программирования РАН. 2017. 29(4). С. 123–138. https://doi.org/10.15514/ISPRAS-2017-29(4)-8
  5. Flood M.M. The traveling-salesman problem // Oper. res. 1956. V. 4. P. 61–75. https://doi.org/10.1287/opre.4.1.61
  6. Rosenkrantz D., Stearns R., Lewis II P. An analysis of several heuristics for the traveling salesman problem // SIAM J. Comput. 1977. V. 6. P. 563–581. https://doi.org/10.1137/0206041
  7. Hahsler M., Hornik K. TSP – Infrastructure for the traveling salesperson problem // J. Statist. Softwar. 2007. V. 23. No. 2. https://doi.org/10.18637/jss.v023.i02
  8. Kay E., Christofides N. Graph Theory: An Algorithmic Approach // Oper. Res. Quarterly. 1976. V. 27. No. 4. P. 1027. https://doi.org/10.2307/3009122
  9. Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem // Graduat. School Industr. Administrat. CMU. 1976. https://doi.org/10.1007/s43069-021-00101-z
  10. Buchin K. Space-filling curves. Organizing points sets: space-filling curves, delaunay tessellations of random point sets, and flow complexes. Berlin, Free University of Berlin, 2007. P. 5–30.
  11. Bartholdi J., Platzman L., Collins R., Warden W. A minimal technology routing system for meals on wheels // Interfaces. 1983. V. 13. No. 3. P. 1–8. https://doi.org/10.1287/inte.13.3.1
  12. Aarts E., Lenstra J. Local search in combinatorial optimization, Princeton, New Jersey: Princeton University Press, 2003. https://doi.org/10.1515/9780691187563
  13. Панюков А.В., Леонова Ю.Ф. Алгоритм соединения циклов для метрической задачи коммивояжера на максимум // Вест. Южно-Урал. гос. ун-та. Сер. Вычисл. мат. и информатика. 2021. Т. 10. No. 4. С. 26–36. https://doi.org/10.14529/cmse210402
  14. Reinelt G. TSPLIB—A traveling salesman problem library // ORSA J. Comput. 1991. V. 3. P. 376–384. https://doi.org/10.1287/ijoc.3.4.376.
  15. Леонова Ю.Ф. Исследование качества алгоритма соединения циклов на примерах из библиотеки TSPLIB / Ю.Ф. Леонова // Актуальные проблемы прикладной математики, информатики и механики : сборник трудов Международной научной конференции, Воронеж, 13–15 декабря 2021 г. Воронеж, 2022. С. 573–579.
  16. Heins J., Bossek J., Pohl J., et. al. A study on the effects of normalized TSP features for automated algorithm selection // Theoretical Computer Science. 2023. V. 940. P. 123–145. https://doi.org/10.1016/j.tcs.2023.01.045

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 The Russian Academy of Sciences

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).