Стаття

Отримано 27.02.2024

Доопрацьовано 01.04.2024

Прийнято 29.06.2024

Взято з Том 28, № 1, 2024

Сторінки 55 -66

Danchuk, V., & Hutarevych, O. (2024). Methods of adaptive optimization of routes of the dynamic traveling salesman problem using a modified ant algorithm. The National Transport University Bulletin, 28(1), 55-66. https://doi.org/10.33744/2308-6645-2024-1-58-055-066

Методи адаптивної оптимізації маршрутів динамічної задачі комівояжера з використанням модифікованого мурашиного алгоритму

Віктор Данчук Олександр Гутаревич

У статті запропоновано метод адаптивної оптимізації маршруту в динамічній задачі комівояжера з використанням модифікованого мурашиного алгоритму. Метод передбачає знаходження оптимального маршруту на двонаправлено орієнтованому зваженому графі, вага ребер якого задається відносними дискретними величинами у відповідності до критерію оптимізації. Для побудови такого графу на основі вхідних даних щодо точок доставки вантажів використовується відповідна інформація, отримана за допомогою сучасних геоінформаційних систем (ГІС). Для динамічного оновлення графу використовується інформація, яку отримують з детекторів руху, розташованих на ділянках вулично-дорожньої мережі (ВДМ) та з програмних інтерфейсів ГІС. Для проведення дискретної оптимізації маршруту в рамках розв’язку асиметричної динамічної задачі комівояжера (DTSP) розроблено модифікацію мурашиного алгоритму, в рамках якої реалізована можливість автоматичного оновлення ваг графу в залежності від змін динамічних характеристик на ділянках ВДМ при фіксації оптимальної конфігурації частково пройденого маршруту перед його оновленням. Для апробації запропонованого методу здійснено комплекс відповідних імітаційних досліджень процесів маршрутизації при різних умовах оптимізації. Так, з метою перевірки адекватності та достовірності запропонованої модифікації мурашиного алгоритму були проведені відповідні тестові дослідження на прикладі набору загальновідомих статичних TSP задач з критерієм оптимізації за відстанню у порівнянні з найбільш поширеними АІ методами дискретної оптимізації. Результати досліджень демонструють прийнятний рівень точності (з відхиленням до 4% у найгірших варіантах), що може вважатися задовільним результатом для застосування у багатьох практичних випадках. При проведенні імітаційних досліджень асиметричної DTSP за допомогою запропонованого методу адаптивної оптимізації маршруту з динамічним його оновленням під час перевезень вантажів, зокрема, було виявлено низку ефектів, пов’язаних з перебудовою маршруту. Таким чином, на підставі аналізу результатів імітаційних досліджень доведена принципова можливість використання розробленого методу для вирішення задач міської транспортної логістики в онлайн режимі з урахуванням реальної конфігурації ВДМ та динаміки ТП на її ділянках

інтелектуальна транспортна система; інтелектуальні методи оптимізації; проблема комівояжера; алгоритм мурашиної колонії; інформаційні технології; географічні інформаційні системи; транспортна логістика; дорожня мережа; транспортний потік
  1. Larsen A. (2001). The dynamic vehicle routing problem. Technical University of Denmark, LYNGBY 2001 IMM-PHD-2000-73, 209p. https://backend.orbit.dtu.dk/ws/portalfiles/portal/5261816/imm143.pdf [in English].
  2. Hernandez F., Sotelo R., & Forets M. (2024). Optimization algorithms for adaptive route sequencing on real-world last-mile deliveries. Ingenius, 2024(31), pp. 64–80. https://ingenius.ups.edu.ec/index.php/ingenius/article/view/7410 [in English].
  3. Erdogan S. (2017). An open source spreadsheet solver for vehicle routing problems. Computers & Operations Research, 84, 62–72. https://doi.org/10.1016/j.cor.2017.02.022 [in English].
  4. Thompson R.G., & Zhang L. (2018). Optimizing courier routes in central city areas. Transportation Research Part C: Emerging Technology, 93, 1–12. https://doi.org/10.1016/j.trc.2018.05.016 [in English].
  5. Jamil A., Abdallah B.N., & Leksono V.A. (2021). Firefly algorithm for multi-type vehicle routing problem. Journal of Physics: Conference Series, 1726(1), 012006. https://doi.org/10.1088/1742-6596/1726/1/012006 [in English].
  6. Wu H., Gao Y., Wang W., & Zhang Z. (2021). A hybrid ant colony algorithm based on multiple strategies for the vehicle routing problem with time windows. Complex & Intelligent Systems, 18. https://doi.org/10.1007/s40747-021-00401-1 [in English].
  7. Giuffrida N., Fajardo-Calderin J., Masegosa A.D., Werner F., Steudter M., & Pilla F. (2022). Optimization and machine learning applied to last-mile logistics: A review. Sustainability, 14(9), 5329. https://doi.org/10.3390/su14095329 [in English].
  8. RTC. (2020). The Impact of Emerging Technologies on the Transport System; Research for Tran Committee, Policy Department for Structural and Cohesion Policies, Directorate-General for Internal Policies: Brussels, Belgium. Available at: https://www.europarl.europa.eu/RegData/etudes/STUD/2020/652226/IPOL_STU(2020)652226_EN.pdf [in English].
  9. Zajkani, M.A., Rahimi Baghdorani, R., & Haeri, M. (2021). Model predictive based approach to solve DVRP with traffic congestion. IFAC-Papers On Line, 54(21), 163-167. https://doi.org/10.1016/j.ifacol.2021.12.028 [in English].
  10. Zhang, H., Zhang, Q., Ma, L., & Liu, Y. (2019). A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows. Information Sciences, 490, 166-190. https://doi.org/10.1016/j.ins.2019.03.070 [in English].
  11. Belhaiza, S., M’Hallah, R., Brahim, G.B., & Laporte, G. (2019). Three multi-start data-driven evolutionary heuristics for the vehicle routing problem with multiple time windows. Journal of Heuristics, 25(3), 485–515. https://doi.org/10.1007/s10732-019-09412-1 [in English].
  12. Hoogeboom, M., & Dullaert, W. (2019). Vehicle routing with arrival time diversification. European Journal of Operational Research, 275(1), 93–107. https://doi.org/10.1016/j.ejor.2018.11.020 [in English].
  13. Xu, Yu. (2022). Logistics distribution for path optimization using artificial neural network and decision support system. Research Square, 1–17. https://doi.org/10.21203/rs.3.rs-1249887/v1 [in English].
  14. Zhang, N. (2018). Smart logistics path for cyber-physical systems with Internet of Things. IEEE Access, 6, 70808-70819. https://doi.org/10.1109/ACCESS.2018.2879966 [in English].
  15. Sanchez-Diaz, I., Holguin-Veras, J., & Ban, X.J. (2015). A time-dependent freight tour synthesis model. Transportation Research Part B: Methodological, 78(C), 144–168. https://doi.org/10.1016/j.trb.2015.04.007 [in English].
  16. Zhang, L., & Thompson, R.G. (2019). Understanding the benefits and limitations of occupancy information systems for couriers. Transportation Research Part C: Emerging Technology, 105, 520–535. https://doi.org/10.1016/j.trc.2019.06.013 [in English].
  17. Russo, F., & Comi, A. (2021). Sustainable urban delivery: The learning process of path costs enhanced by information and communication technologies. Sustainability, 13(13103), 1–17. https://doi.org/10.3390/su132313103 [in English].
  18. Danchuk, V., Comi, A., Weiß, C., & Svatko, V. (2023). The optimization of cargo delivery processes with dynamic route updates in smart logistics. Eastern-European Journal of Enterprise Technologies, Vol. 2, No. 3 (122), pp. 64-73. https://doi.org/10.15587/1729-4061.2023.277583 [in English].
  19. Lakshmi S., Ishwarya Srikanth, & Arockiasamy M. (2019). Identification of Traffic Accident Hotspots using Geographical Information System. International Journal of Engineering and Advanced Technology (IJEAT), Vol. 9, Iss. 2. http://dx.doi.org/10.35940/ijeat.B3848.129219 [in English].
  20. Microsoft Bing Maps Documentation. Retrieved from https://learn.microsoft.com/en-us/bingmaps [in English].
  21. Dorigo, M., & Di Caro, G. (1999). The ant colony optimization meta-heuristic. In D. Corne, M. Dorigo, & F. Glover (Eds.), New Ideas in Optimization (pp. 11–32). McGraw-Hill, London [in English].
  22. Heidelberg University (2013). TSPLIB. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95 [in English].

https://doi.org/10.33744/2308-6645-2024-1-58-055-066