An Empirical Study of the Quality of the Cycle Merging Algorithm for the Maximum Traveling Salesman Problem

Задача коммивояжера на максимум - это задача комбинаторной оптимизации, заключающаяся в построении гамильтонова цикла с наибольшей суммой весов ребер. Она применяется в биоинформатике, кодировании, логистике и других областях. Несмотря на наличие теоретических границ точности приближенных алгоритмов, их реальное поведение остается недостаточно изученным. В данной работе приводится эмпирический анализ алгоритма соединения циклов (Cycle Merging Algorithm, CMA) для решения задачи коммивояжера на максимум. CMA является жадной эвристикой, основанной на последовательном объединении циклов в 2-факторе максимального веса. В ходе вычислительного эксперимента (на наборах от 100 до 3000 вершин) исследуется точность решений CMA относительно верхней границы, определяемой как решение задачи о назначении, а также вычислительная эффективность метода. Особый вклад работы заключается в построении регрессионной модели, описывающей зависимость оценки относительной погрешности от числа вершин для метрических экземпляров задачи. Модель показывает, что относительная погрешность убывает по степенному закону, а анализ подтверждает, что CMA стабильно превосходит гарантированную теоретическую границу. Полученные результаты свидетельствуют о том, что алгоритм соединения циклов является мощной эвристикой для задачи коммивояжера на максимум, обеспечивая высокое качество решений и вычислительную эффективность на практике. Перспективными направлениями дальнейшей работы являются оптимизация стратегии объединения циклов, разработка гибридных алгоритмов реализация GPU-версии для улучшения масштабируемости.

Ключевые слова

задача коммивояжера на максимум; приближенные алгоритмы; вычислительный эксперимент; регрессионный анализ; сложность алгоритма.

Литература

1. Reingold, E. M., Nievergelt, J., Deo, N. Combinatorial Algorithms: Theory and Practice. - Prentice Hall College Div, 1977.
2. Sichen Zhong. Optimizing Read Reversals for Sequence Compression / Zhong Sichen, Lu Zhao, Yiang Liang, M. Zamani, R. Patro, R. Chowdhury, E.M. Arkin, J.S. B.Mitchell, S. Skiena // International Workshop on Algorithms in Bioinformatics. - Atlanta, 2015. - P. 189-202.
3. Leonova, Y.F. Application of the Cycles Merging Algorithm to the Shortest Common Superstring Problem / Y.F. Leonova, A.V. Panyukov // 2020 Global Smart Industry Conference (GloSIC). - IEEE, 2020. - P. 342-347.
4. Gimadi, E.K. On Finding a Cyclic Tour and a Vehicle Loading Plan Yielding Maximum Profit / E.K. Gimadi, N.I. Glebov, A.I. Serdyukov // Discrete Applied Mathematics. - 2004. - Т. 135, № 1-3. - P. 105-111.
5. Kaplan, H. Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs / H. Kaplan, M. Lewenstein, N. Shafrir, M. Sviridenko // Journal of the ACM (JACM). - 2005. - Т. 52, № 4. - P. 602-626.
6. Paluch, K. A 7/9-Approximation Algorithm for the Maximum Traveling Salesman Problem / K. Paluch, M. Mucha, A. Madry // International Workshop on Approximation Algorithms for Combinatorial Optimization. - Berlin: Springer, 2009. - P. 298-311.
7. Kowalik, L. 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality / L. Kowalik, M. Mucha // Algorithmica. - 2011. - Т. 59. - P. 240-255.
8. Kowalik, L. Deterministic 7/8-Approximation for the Metric Maximum TSP / L. Kowalik, M. Mucha // Theoretical Computer Science. - 2009. - Т. 410, № 47-49. - P. 5000-5009.
9. Glover, F. Construction Heuristics for the Asymmetric TSP / F. Glover, G. Gutin, A. Zverovich, A. Yeo // European Journal of Operational Research. - 2001. - Т. 129, № 3. - P. 555-568.
10. Shenmaier V. Asymptotic Optimality of the Greedy Patching Heuristic for Max TSP in Doubling Metrics / V. Shenmaier // Data Structures and Algorithms. - 2022.
11. Леонова, Ю.Ф. Алгоритм соединения циклов для приближенного решения задачи коммивояжера / Ю.Ф. Леонова, А.В. Панюков // Тезисы XIX Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям. - 2018. - С. 28-29.
12. Панюков, А.В. Алгоритм для приближенного решения задачи коммивояжера / А.В. Панюков, Ю.Ф. Игошева // Проблемы оптимизации и их приложения. - 2018. - С. 31.
13. Panyukov, A.V. Cycle Merging Algorithm for Max TSP Problems. / A.V. Panyukov, Y.F. Leonova // XVIII International Conference Mathematical Optimization Theory and Operations Research (MOTOR 2019). - 2019. - P. 57.
14. Панюков, А.В. Алгоритм соединения циклов для метрической задачи коммивояжера на максимум / А.В. Панюков, Ю.Ф. Леонова // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. - 2021. - Т. 10, № 4. - С. 26-36.
15. Реализация алгоритма соединения циклов для задачи коммивояжера на максимум. - URL: https://github.com/YuliyaLeonova/CMA_MAX (дата обращения 06.02.2025)
12. Panyukov A.V., Leonova Y.F. Algorithm for Approximate Solution of the Traveling Salesman Problem. Optimization Problems and Their Applications (OPTA-2018), 2018, p. 31.
13. Panyukov A.V., Leonova Y.F. Cycle Merging Algorithm for Max TSP Problems. XVIII International Conference Mathematical Optimization Theory and Operations Research (MOTOR 2019), 2019, p.57.
14. Panyukov A.V., Leonova Y.F. Cycle Merging Algorithm for the Metric Maximum Traveling Salesman Problem. Bulletin of South Ural State University. Series: Computational Mathematics and Informatics, 2021, vol. 10, no. 4, pp. 26-36. DOI:10.14529/cmse210402
15. Implementation of the Cycle Merging Algorithm for the Maximum Traveling Salesman Problem (2025). Available at: https://github.com/YuliyaLeonova/CMA_MAX (accessed 6 February 2025)