СТАТИСТИЧЕСКОЕ ИССЛЕДОВАНИЕ КАЧЕСТВА АЛГОРИТМА СОЕДИНЕНИЯ ЦИКЛОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА НА МИНИМУМ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

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

Об авторах

Ю. Ф ЛЕОНОВА

Южно-Уральский государственный университет

Email: yuliya.igosheva@gmail.com
Челябинск

А. В ПАНЮКОВ

Южно-Уральский государственный университет

Email: paniukovav@susu.ru
д-р физ.-мат. наук Челябинск

Список литературы

  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

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2025

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

 

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