Statistical Study of the Quality of the Cycle Merging Algorithm for Solving the Traveling Salesman Problem at Minimum
- Authors: Leonova Y.F1, Panyukov A.V1
-
Affiliations:
- Issue: No 5 (2025)
- Pages: 98-113
- Section: Optimization, system analysis, and operations research
- URL: https://journals.rcsi.science/0005-2310/article/view/294471
- DOI: https://doi.org/10.31857/S0005231025050065
- EDN: https://elibrary.ru/AXACAX
- ID: 294471
Cite item
Abstract
About the authors
Yu. F Leonova
Email: yuliya.igosheva@gmail.com
A. V Panyukov
Email: paniukovav@susu.ru
References
- 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
- 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
- Reingold E.M., Nievergelt J., Deo N. Combinatorial algorithms: theory and practice. Prentice Hall College Div, 1977. https://doi.org/10.2307/2987917
- Авдошин С.М., Береснева Е.Н. Метрическая задача коммивояжера: экспериментальное исследование Парето-оптимальных алгоритмов // Труды Института системного программирования РАН. 2017. 29(4). С. 123–138. https://doi.org/10.15514/ISPRAS-2017-29(4)-8
- Flood M.M. The traveling-salesman problem // Oper. res. 1956. V. 4. P. 61–75. https://doi.org/10.1287/opre.4.1.61
- 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
- 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
- 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
- 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
- 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.
- 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
- Aarts E., Lenstra J. Local search in combinatorial optimization, Princeton, New Jersey: Princeton University Press, 2003. https://doi.org/10.1515/9780691187563
- Панюков А.В., Леонова Ю.Ф. Алгоритм соединения циклов для метрической задачи коммивояжера на максимум // Вест. Южно-Урал. гос. ун-та. Сер. Вычисл. мат. и информатика. 2021. Т. 10. No. 4. С. 26–36. https://doi.org/10.14529/cmse210402
- 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.
- Леонова Ю.Ф. Исследование качества алгоритма соединения циклов на примерах из библиотеки TSPLIB / Ю.Ф. Леонова // Актуальные проблемы прикладной математики, информатики и механики : сборник трудов Международной научной конференции, Воронеж, 13–15 декабря 2021 г. Воронеж, 2022. С. 573–579.
- 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
