ЕВРИСТИЧНИЙ ПІДХІД ДО ПРОГРАМНОЇ РЕАЛІЗАЦІЇ МЕТОДУ ЛІТТЛА НА ПРИКЛАДІ ЗАДАЧІ КОМІВОЯЖЕРА

Автор(и)

DOI:

https://doi.org/10.20998/2078-9130.2024.2.316075

Ключові слова:

математична модель, задача комівояжера, метод Літтла, евристичний підхід, матриця відстаней, задача оптимізації

Анотація

Розглянуто задачу комівояжера (комівояжер — бродячий торговець; англ. Travelling Salesman Problem, TSP) як одну з найбільш популярних оптимізаційних задач. Ця задача полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста по одному разу. В умовах даної задачі застосовуються критерій вигідності маршруту (тобто найкоротший та найдешевший) і відповідні матриці відстаней (в кілометрах). Задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів. Для можливості застосування математичного апарату для розв'язання проблеми, її представлено у вигляді математичної моделі. Проблему комівояжера подано у вигляді моделі на графі, тобто, використовуючи вершини та ребра між ними. Авторами запропоновано застосування евристичного методу до розв’язання даної задачі. Для цього вдосконалено програмну реалізацію алгоритму Літтла, який вибирає для розбиття множини з мінімальною межею з усіх можливих гілок, а не з двох отриманих в результаті останнього розбиття. При цьому використовується евристичний підхід до вибору множини з межею не більше, ніж мінімальна. Продемонстровано роботу програми на прикладі проїзду автомобілем між містами України, заданими реальної матрицею відстаней (в кілометрах). Виявлено, що швидкість роботи наведеної авторами програмної реалізації модифікованого алгоритму Літтла набагато вище, що дозволяє застосовувати останній замість методу повного перебору.

Посилання

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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.
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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.
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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

##submission.downloads##

Опубліковано

2024-12-24

Як цитувати

Місюра, Є., Місюра, С., & Сметанкіна, Н. (2024). ЕВРИСТИЧНИЙ ПІДХІД ДО ПРОГРАМНОЇ РЕАЛІЗАЦІЇ МЕТОДУ ЛІТТЛА НА ПРИКЛАДІ ЗАДАЧІ КОМІВОЯЖЕРА. Вісник Національного технічного університету «ХПІ». Серія: Динамiка та мiцнiсть машин, (2), 39–46. https://doi.org/10.20998/2078-9130.2024.2.316075

Номер

№ 2 (2024): Вісник НТУ "ХПІ" Серія: "Динаміка та міцність машин"

Розділ

Статті