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

  • Nikolay Viktorovich Mamonov Московский государственный университет имени М.В. Ломоносова; ООО «Гудфокаст» http://orcid.org/0000-0002-6088-7366

Аннотация

Одной из самых известных задач комбинаторной оптимизации является задача коммивояжера. Эта задача является важной и вместе с тем трудноразрешимой, что связано с экспоненциальной сложностью точных методов решения. Она возникает в обширном классе приложений: в построении оптимальных схем движения, распознавании траекторий и образов. Однако, целый ряд научных исследований, в частности, вопросы генетики и биоинформатики, требуют получения точного решения. На основе классической реализации метода ветвей и границ в работе проводится исследование влияния асимметрии на сложность решения. Поскольку проводимое исследование требует анализа большого числа экспериментально полученных данных, возникает необходимость повышения скорости проведения расчетов. Выбранный для работы метод ветвей и границ допускает получение большей скорости перебора решений за счет хранения в памяти состояний активных листовых вершин дерева решений. На эффективность реализации алгоритма влияет также выбор структур данных для быстрого нахождения следующей рассматриваемой вершины. На основании полученных результатов и проведенного анализа установлена зависимость сложности решения задачи от асимметричности матрицы. Некоторые из вариантов внесения асимметрии приводят к сокращению сложности решения. Изучение влияния асимметрии на сложность задачи коммивояжера на примере классического алгоритма решения – метода ветвей и границ – представляет интерес для дальнейшего предиктивного анализа сложности индивидуальных задач.

Сведения об авторе

Nikolay Viktorovich Mamonov, Московский государственный университет имени М.В. Ломоносова; ООО «Гудфокаст»

магистрант, факультет вычислительной математики и кибернетики; математик-программист

Литература

[1] Ulyanov M.V. Resource-efficient computer algorithms. Development and analysis. M.: Fizmatlit, 2008. (In Russ.)
[2] Tang N.C., Chilkoti A. Combinatorial codon scrambling enables scalable gene synthesis and amplification of repetitive proteins. Nature Materials. 2016; 15(4):419-424. (In Eng.) DOI: 10.1038/nmat4521
[3] Kostevich L.S. Mathematical programming: information technologies of optimal solutions. Mn.: Novoye znaniye, 2003. (In Russ.)
[4] Goodman S.E., Hedetniemi S.T. Introduction to the Design and Analysis of Algorithms. NY: McGraw-Hill, 1977. (In Eng.)
[5] Ulyanov M.V., Fomichev M.I. Resource characteristics of ways to organize a decision tree in the branch-andbound method for the traveling salesmen problem. Business Informatics. 2015; 4(34):38-46. (In Eng.) DOI: 10.17323/1998-0663.2015.4.38.46
[6] Goloveshkin V.A., Zhukova G.N., Ulyanov M.V., Fomichev M.I. Probabilistic Prediction of the Complexity of Traveling Salesman Problems Based on Approximating the Complexity Distribution from Experimental Data. Automation and Remote Control. 2018; 79(7):1296-1310. (In Eng.) DOI: 10.1134/S0005117918070093
[7] Lobjois L., Lemaitre M. Branch and Bound Algorithm Selection by Performance Prediction. Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98). American Association for Artificial Intelligence, AAAI Press, Menlo Park, CA, 1998. Available at: https://aaai.org/Papers/AAAI/1998/AAAI98-050.pdf (accessed 13.01.2019). (In Eng.)
[8] Bektaş T., Gouveia L., Martínez-Sykora A., Salazar-González J. Balanced vehicle routing: Polyhedral analysis and branch-and-cut algorithm. European Journal of Operational Research. 2019; 273(2):452-463. (In Eng.) DOI: 10.1016/j.ejor.2018.08.034
[9] Arigliano A., Ghiani G., Grieco A., Guerriero E., Plana I. Time-dependent asymmetric traveling salesman problem with time windows: Properties and an exact algorithm. Discrete Applied Mathematics. 2019; 261:28-39. (In Eng.) DOI: 10.1016/j.dam.2018.09.017
[10] Hore S., Chatterjee A., Dewanji A. Improving variable neighborhood search to solve the traveling salesman problem. Applied Soft Computing. 2018; 68:83-91. (In Eng.) DOI: 10.1016/j.asoc.2018.03.048
[11] Gouveia L., Leitner M., Ruthmair M. Extended formulations and branch-and-cut algorithms for the Black-and-White Traveling Salesman Problem. European Journal of Operational Research. 2017; 262(3):908-928. DOI: 10.1016/j.ejor.2017.04.061
[12] Huang Y., Zhong C. Detecting list-colored graph motifs in biological networks using branch-and-bound strategy. Computers in Biology and Medicine. 2019; 107:1-9. (In Eng.) DOI: 10.1016/j.compbiomed.2019.01.025
[13] Toriello A. Optimal Toll Design: A Lower Bound Framework for the Asymmetric Traveling Salesman Problem. Mathematical Programming. 2014; 144(1-2):247-264. (In Eng.) DOI: 10.1007/s10107-013-0631-6
[14] Sergeev S. Nonlinear resolving functions for the travelling salesman problem. Automation and Remote Control. 2013; 74(6):978-994. (In Eng.) DOI: 10.1134/S0005117913060088
[15] Charikar M., Goemans M.X., Karloff H. On the Integrality Ratio for the Asymmetric Traveling Salesman Problem. Mathematics of Operations Research. 2006; 31(2):245-252. DOI: 10.1287/moor.1060.0191
[16] Subramanyam A., Gounaris C. A branch-and-cut framework for the consistent traveling salesman problem. European Journal of Operational Research. 2016; 248(2):384-395. (In Eng.) DOI: 10.1016/j.ejor.2015.07.030
[17] Goloveshkin V.A., Zhukova G.N., Ulyanov M.V., Fomichev M.I. The estimation of the complexity of solving a particular travelling salesman problem by quantile-based measures for skewness and kurtosis. International Journal of Open Information Technologies. 2016; 4(12):7-12. Available at: https://elibrary.ru/item.asp?id=27543353 (accessed 13.01.2019). . (In Russ.)
[18] Liśkiewicz M., Schuster M. A new upper bound for the traveling salesman problem in cubic graphs. Journal of Discrete Algorithms. 2014; 27:1-20. (In Eng.) DOI: 10.1016/j.jda.2014.02.001
[19] Kara I., Derya T. Formulations for Minimizing Tour Duration of the Traveling Salesman Problem with Time Windows. Procedia Economics and Finance. 2015; 26:1026-1034. (In Eng.) DOI: 10.1016/S2212-5671(15)00926-0
[20] LaRusic J., Punnen A.P. The asymmetric bottleneck traveling salesman problem: Algorithms, complexity and empirical analysis. Computers & Operations Research. 2014; 43:20-35. (In Eng.) DOI: 10.1016/j.cor.2013.08.005
Опубликована
2019-04-19
Как цитировать
MAMONOV, Nikolay Viktorovich. ИССЛЕДОВАНИЕ ВЛИЯНИЯ АСИММЕТРИИ НА СЛОЖНОСТЬ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 15, n. 1, p. 99-106, apr. 2019. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/505>. Дата доступа: 18 aug. 2019 doi: https://doi.org/10.25559/SITITO.15.201901.99-106.
Раздел
Прикладные проблемы оптимизации