ЕВРИСТИЧНИЙ ПІДХІД ДО ПРОГРАМНОЇ РЕАЛІЗАЦІЇ МЕТОДУ ЛІТТЛА НА ПРИКЛАДІ ЗАДАЧІ КОМІВОЯЖЕРА
DOI:
https://doi.org/10.20998/2078-9130.2024.2.316075Ключові слова:
математична модель, задача комівояжера, метод Літтла, евристичний підхід, матриця відстаней, задача оптимізаціїАнотація
Розглянуто задачу комівояжера (комівояжер — бродячий торговець; англ. Travelling Salesman Problem, TSP) як одну з найбільш популярних оптимізаційних задач. Ця задача полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста по одному разу. В умовах даної задачі застосовуються критерій вигідності маршруту (тобто найкоротший та найдешевший) і відповідні матриці відстаней (в кілометрах). Задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів. Для можливості застосування математичного апарату для розв'язання проблеми, її представлено у вигляді математичної моделі. Проблему комівояжера подано у вигляді моделі на графі, тобто, використовуючи вершини та ребра між ними. Авторами запропоновано застосування евристичного методу до розв’язання даної задачі. Для цього вдосконалено програмну реалізацію алгоритму Літтла, який вибирає для розбиття множини з мінімальною межею з усіх можливих гілок, а не з двох отриманих в результаті останнього розбиття. При цьому використовується евристичний підхід до вибору множини з межею не більше, ніж мінімальна. Продемонстровано роботу програми на прикладі проїзду автомобілем між містами України, заданими реальної матрицею відстаней (в кілометрах). Виявлено, що швидкість роботи наведеної авторами програмної реалізації модифікованого алгоритму Літтла набагато вище, що дозволяє застосовувати останній замість методу повного перебору.
Посилання
Salii, Y. Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization. European Journal of Operational Research. 2019. 272(1). Pp. 32–42. https://doi.org/10.1016/j.ejor.2018.06.003
Inayatullah, S., Riaz, W., Jafree, H. A., Siddiqi, T. A., Imtiaz, M., Naz, S. & Hassan, S. A. A Note on Branch and Bound Algorithm for Integer Linear Programming. Current Journal of Applied Science and Technology. 2019. 34(6). Pp. 1–6. https://doi: 10.9734/cjast/2019/v34i630155
Berger, A., Kozma L., Mnich M. & Vincze R. A time- and space-optimal algorithm for the many-visits TSP. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics. 2019. Pp. 1770–1782. https://doi: 10.1137/1.9781611975482.106
Kesen, S. E. & Bektaş T. Integrated Production Scheduling and Distribution Planning with Time Windows. Cham: Springer, Lean and Green Supply Chain Management. 2019. Pp. 231–252. https://doi.org/10.1007/978-3-319-97511-5_8
Wu, J., Zhou L., Du Z. & Lv Y. Mixed steepest descent algorithm for the traveling salesman problem and application in air logistics. Transportation Research Part E: Logistics and Transportation Review. 2019. 126. Pp. 87–102. https://doi.org/10.1016/j.tre.2019.04.004
O’Neil, R. J. & Hoffman, K. Decision diagrams for solving traveling salesman problems with pickup and delivery in real time. Operations Research Letters. 2019. 47(3). Pp. 197–201. https://doi.org/10.1016/j.orl.2019.03.008.
Tawhid, M. A.& Savsani, P. Discrete sine-cosine algorithm (DSCA) with local search for solving traveling salesman problem. Arabian Journal for Science and Engineering. 2019. 44(4). Pp. 3669–3679. https://doi.org/10.1007/s13369-018-3617-0
Paul, J. A., Niels, S., Remy, K. & René, De Shared Capacity Routing Problem − An omni-channel retail study. European Journal of Operational Research. 2019. 273(2). Pp. 731–739. https://doi.org/10.1016/j.ejor.2018.08.027
Taillard, É. D. & Helsgaun, K. POPMUSIC for the travelling salesman problem. European Journal of Operational Research. 2019. 272(2). Pp. 420–429. https://doi.org/10.1016/j.ejor.2018.06.039
Karaboga, D. & Gorkemli B. Solving Traveling Salesman Problem by Using Combinatorial Artificial Bee Colony Algorithms. International Journal on Artificial Intelligence Tools. 2019. 28(01). Pp. 1950004:1–1950004:28. https://doi.org/10.1142/S0218213019500040
Dell'Amico, M., Montemanni, R. & Novellani, S. Matheuristic algorithms for the parallel drone scheduling traveling salesman problem. arXiv preprint arXiv:1906.02962. 2019. Pp. 1–18.
Juneja, S. S., Saraswat P. & Chowdhary S. K. Travelling Salesman Problem Optimization Using Genetic Algorithm. 2019 Amity International Conference on Artificial Intelligence (AICAI), IEEE. 2019. Pp. 264–268. https://doi:10.1109/aicai.2019.8701246
Varadarajan, S. & Whitley, D. The massively parallel mixing genetic algorithm for the traveling salesman problem. Proceedings of the Genetic and Evolutionary Computation Conference, ACM. 2019. Pp. 872–879. https://doi.org/10.1145/3321707.3321772
Maity, S., Roy, A. & Maiti M. A rough multi-objective genetic algorithm for uncertain constrained multi-objective solid travelling salesman problem. Granular Computing. 2019. 4(1). Pp. 125–142. https://doi.org/10.1007/s41066-018-0094-5
Singhal S., Goyal Н., Singhal P. & Grover J. Hybrid Genetic Algorithm: Traveling Salesman Problem. International Conference on E-Business and Telecommunications, Springer, Cham. 2019. Pp. 376–384. https://doi.org/10.1007/978-3-030-24322-7_48
Halim A. H. & Ismail I. Combinatorial optimization: comparison of heuristic algorithms in travelling salesman problem. Archives of Computational Methods in Engineering. 2019. 26(2). Pp. 367–380. https://doi.org/10.1007/s11831-017-9247-y
Gilbert, H. & Spanjaard, O. Optimizing a Generalized Gini Index in Stable Marriage Problems: NP-Hardness, Approximation and a Polynomial Time Special Case. Algorithmica. 2019. 81(7). Pp. 2653–2681. https://doi.org/10.1007/s00453-019-00550-3
Pelofske E., Hahn G. & Djidjev H. Solving large Maximum Clique problems on a quantum annealer. Cham: Springer, International Workshop on Quantum Technology and Optimization Problems. 2019. Pp. 123–135. https://doi.org/10.1007/978-3-030-14082-3_11
