- Код статьи
- 10.31857/S0005231025050065-1
- DOI
- 10.31857/S0005231025050065
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 5
- Страницы
- 98-113
- Аннотация
- Задача коммивояжера является одной из наиболее изученных в комбинаторной оптимизации, однако исследование новых подходов и улучшение существующих методов остается актуальной задачей. Вда нной работе проведен анализ качества алгоритма соединения циклов для задачи коммивояжера на минимум. Представлены результаты вычислительного эксперимента на пяти семействах задач, проанализированы точность и временная сложность алгоритма. Для симметричных экземпляров задачи построена регрессионная модель, описывающая зависимость оценки относительной погрешности от числа вершин. Показано, что полиномиальная модель наилучшим образом аппроксимирует полученные данные и удовлетворяет основным статистическим предпосылкам. Полученные результаты позволяют оценить характер роста ошибки и обосновать применимость алгоритма к экземплярам задачи коммивояжера большой размерности.
- Ключевые слова
- задача коммивояжера эвристический алгоритм асимптотическая точность алгоритма статистическое исследование
- Дата публикации
- 01.05.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 12
Библиография
- 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
