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

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

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