ИССЛЕДОВАНИЕ ВЛИЯНИЯ АСИММЕТРИИ НА СЛОЖНОСТЬ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ
Аннотация
Одной из самых известных задач комбинаторной оптимизации является задача коммивояжера. Эта задача является важной и вместе с тем трудноразрешимой, что связано с экспоненциальной сложностью точных методов решения. Она возникает в обширном классе приложений: в построении оптимальных схем движения, распознавании траекторий и образов. Однако, целый ряд научных исследований, в частности, вопросы генетики и биоинформатики, требуют получения точного решения. На основе классической реализации метода ветвей и границ в работе проводится исследование влияния асимметрии на сложность решения. Поскольку проводимое исследование требует анализа большого числа экспериментально полученных данных, возникает необходимость повышения скорости проведения расчетов. Выбранный для работы метод ветвей и границ допускает получение большей скорости перебора решений за счет хранения в памяти состояний активных листовых вершин дерева решений. На эффективность реализации алгоритма влияет также выбор структур данных для быстрого нахождения следующей рассматриваемой вершины. На основании полученных результатов и проведенного анализа установлена зависимость сложности решения задачи от асимметричности матрицы. Некоторые из вариантов внесения асимметрии приводят к сокращению сложности решения. Изучение влияния асимметрии на сложность задачи коммивояжера на примере классического алгоритма решения – метода ветвей и границ – представляет интерес для дальнейшего предиктивного анализа сложности индивидуальных задач.
Литература
[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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
