Поиск точного решения задачи нескольких коммивояжеров
Main Article Content
Аннотация
В работе рассмотрена задача нескольких коммивояжеров. Она состоит в том, чтобы на графе со взвешенными дугами найти набор из заранее заданного количества непересекающихся циклов, у которого сумма весов дуг наибольшего цикла будет минимальной. Разработан точный алгоритм решения поставленной задачи, основанный на методе ветвей и границ. В построенном алгоритме, как и в известном алгоритме Балаша – Кристофидеса решения задачи одного коммивояжера, использован венгерский алгоритм решения задачи о назначениях. Представлены результаты численных экспериментов со случайными графами большой размерности.
Article Details
Библиографические ссылки
2. Balas E., Christofides N. A restricted lagrangean approach to the traveling salesman problem // Mathematical Programming. 1981. Vol. 21. No. 1. P. 19–46. https://doi.org/10.1007/BF01584228
3. Burhoveckij V.V. Optimization and Parallelization of Simplified Balas’ and Christofides’ Algorithm for the Traveling Salesman Problem. Program Systems: Theory and Applications // Program Systems: Theory and Applications. 2020. Т. 11, Vyp. 4. S. 3–16. https://doi.org/10.25209/2079-3316-2020-11-4-3-16
4. Burhoveckij V.V., Steinberg B.J. Tochnoe i priblizhennoe resheniya zadachi kommivoyazhyora bol'shogo razmera // Vychislitel'nye metody i programmirovanie. 2024. T. 25, Vyp. 4. S. 476–482. https://doi.org/10.26089/NumMet.v25r436
5. Steinberg B., Baglij A., Petrenko V., Burhovetckij V., Steinberg O., Metelica E. An Analyzer for Program parallelization and Optimization // 3-rd International Conference on Applications in Information Technologies ICAIT 2018, Tokyo, November 1–3, 2018. https://doi.org/10.1145/3274856.3274875.
6. Feautrier P. A parallelization framework for recursive tree programs / Feautrier P // EuroPar’98 Parallel Processing: 4th International Euro-Par Conference Southampton, UK, September 1–4, 1998 Proceedings 4. Springer, 1998. P. 470–479. https://doi.org/10.1007/BFb0057890
7. Kuhn H.W. The Hungarian Method for the assignment problem // Naval Research Logistics Quarterly. 1955. Vol. 2. P. 83–97. https://doi.org/10.1002/nav.3800020109
8. Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem. Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group (1976). https://doi.org/10.1007/s43069-021-00101-z
9. Kurejchik V.V., Logunova Y.A. Zadacha kommivoyazhyora. Obzor i metody eyo resheniya. Palmarium Academic Publishing, 2020.
10. Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures // Omega. 2006. Vol. 34, Issue 3. P. 209–219. https://doi.org/10.1016/j.omega.2004.10.004
11. Ali AI, Kennington JL. The asymmetric m-traveling salesmen problem: a duality based branchand-bound algorithm // Discrete Applied Mathematics 1986. Vol. 13. P. 259–276. https://doi.org/10.1016/0166-218x(86)90087-9
12. Laporte G, Nobert Y. A cutting planes algorithm for the m-salesmen problem // Journal of the Operational Research Society. 1980. Vol. 31. P. 1017–1023. https://doi.org/10.1057/jors.1980.188
13. Ahmeda Z.H., Al-Dayel I. An Exact Algorithm for the Single Depot Multiple Travelling Salesman Problem // IJCSNS International Journal of Computer Science and Network Security. 2020. Vol. 20. No. 9. https://doi.org/10.22937/IJCSNS.2020.20.09.9
14. Little J., Murty K., Sweeney D., Karel C. An Algorithm for the Traveling Salesman Problem // Operations Research. 1963. Vol. 11, No. 6. P. 972–989. https://doi.org/10.1287/opre.11.6.972
15. Böhm M., Friggstad Z., Mömke T., Spoerhase J. Approximating Traveling Salesman Problems Using a Bridge Lemma // Proceedings of the 2025 Annual ACMSIAM Symposium on Discrete Algorithms. https://doi.org/10.1137/1.9781611978322.34
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Представляя статьи для публикации в журнале «Электронные библиотеки», авторы автоматически дают согласие предоставить ограниченную лицензию на использование материалов Казанскому (Приволжскому) федеральному университету (КФУ) (разумеется, лишь в том случае, если статья будет принята к публикации). Это означает, что КФУ имеет право опубликовать статью в ближайшем выпуске журнала (на веб-сайте или в печатной форме), а также переиздавать эту статью на архивных компакт-дисках журнала или включить в ту или иную информационную систему или базу данных, производимую КФУ.
Все авторские материалы размещены в журнале «Электронные библиотеки» с ведома авторов. В случае, если у кого-либо из авторов есть возражения против публикации его материалов на данном сайте, материал может быть снят при условии уведомления редакции журнала в письменной форме.
Документы, изданные в журнале «Электронные библиотеки», защищены законодательством об авторских правах, и все авторские права сохраняются за авторами. Авторы самостоятельно следят за соблюдением своих прав на воспроизводство или перевод их работ, опубликованных в журнале. Если материал, опубликованный в журнале «Электронные библиотеки», с разрешения автора переиздается другим издателем или переводится на другой язык, то ссылка на оригинальную публикацию обязательна.
Передавая статьи для опубликования в журнале «Электронные библиотеки», авторы должны принимать в расчет, что публикации в интернете, с одной стороны, предоставляют уникальные возможности доступа к их материалам, но, с другой, являются новой формой обмена информацией в глобальном информационном обществе, где авторы и издатели пока не всегда обеспечены защитой от неправомочного копирования или иного использования материалов, защищенных авторским правом.
При использовании материалов из журнала обязательна ссылка на URL: http://rdl-journal.ru. Любые изменения, дополнения или редактирования авторского текста недопустимы. Копирование отдельных фрагментов статей из журнала разрешается для научных исследований, персонального использования, коммерческого использования до тех пор, пока есть ссылка на оригинальную статью.
Запросы на право переиздания или использования любых материалов, опубликованных в журнале «Электронные библиотеки», следует направлять главному редактору Елизарову А.М. по адресу: amelizarov@gmail.com
Издатели журнала «Электронные библиотеки» не несут ответственности за точки зрения, излагаемые в публикуемых авторских статьях.
Предлагаем авторам статей загрузить с этой страницы, подписать и выслать в адрес издателя журнала по электронной почте скан Авторского договора о передаче неисключительных прав на использование произведения.