Стаття

Отримано 02.03.2022

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

Прийнято 22.08.2022

Взято з Том 26, № 3, 2022

Сторінки 127 -137

Danchuk, V., Svatko, V., & Bogdanets, Y. (2022). Method of optimizing the route of cargo transportation in cities using information technologies based on the modified ant algorithm. The National Transport University Bulletin, 26(3), 127-137. https://doi.org/10.33744/2308-6645-2022-3-53-127-137

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

Віктор Данчук Віталій Сватко Є. Богданець

Для вирішення проблем маршрутизації вантажних перевезень у великих містах в умовах нестаціонарної динаміки транспортних потоків на ділянках вулично-дорожньої мережі (ВДМ) запропоновано метод оптимізації маршруту на мережі у вигляді двонаправлено орієнтованого зваженого графа. Метод базується на використанні модифікованого мурашиного алгоритму. Основним елементом модифікації є те, що реалізована можливість асинхронного руху агентів мурашиної колонії з певною швидкістю. Крім цього, також можливе фіксування результатів оптимізації частково пройденого шляху для розрахунку подальшого маршруту при зміні умов руху цих агентів. Це дозволяє здійснювати управління процесом оптимізації маршруту з урахуванням динамічного стану ВДМ, що пов’язаний із суттєвими змінами швидкості руху транспортних засобів на певних ділянках цієї мережі. Ці зміни швидкості можуть бути обумовлені підвищенням завантаженості ділянок ВДМ, виникненням заторів, аварійних ситуацій тощо. Для апробації запропонованого методу здійснені з використанням розробленого програмного забезпечення імітаційні моделювання процесів оптимізації маршруту в рамках задачі комівояжера на прикладі ВДМ м. Києва. При проведенні моделювання було виявлено низку ефектів. Ці ефекти пов’язані з перебудовою оптимальних маршрутів при зменшенні середніх швидкостей руху транспортних засобів на модельних ділянках ВДМ до певних граничних значень, які відповідають певним режимам руху транспортних потоків. Аналіз виявлених ефектів дозволив сформулювати деякі методичні рекомендації щодо прийняття управлінських рішень з питань раціональної організації перевезень вантажів. На підставі аналізу результатів імітаційних досліджень доведена можливість використання методу для вирішення задач ефективного управління процесом перевезень у мегаполісах. Зокрема, застосування цього методу може бути корисним при формуванні оптимальних маршрутів доставки вантажу в онлайн режимі з урахуванням реального стану руху транспорту на ділянках ВДМ.

 

транспортний потік; вулично-дорожня мережа; інформаційні технології; програмне забезпечення; мурашиний алгоритм
  1. Statystyka tsin na vantazhni perevezennia po Ukraini [Statistics of prices for freight transportation in Ukraine]. Available at: http://degruz.com/price_statistics (Accessed 20 June 2022).
  2. Lukinskiy, V. Methods of evaluating transportation and logistics operations in supply chains / V. Lukinskiy, V. Dobromirov // Transport and Telecommunication, 2016. V. 17. P. 55–59.
  3. Balasescu, S. Optimization methods for supply chain activities / S. Balasescu, M. Balasescu // Bulletin of the Transilvania University of Brasov Series V: Economic Sciences, 2014. V. 7(56). P. 9–16.
  4. Qingyou, Y. The Optimization of Transportation Costs in Logistics Enterprises with Time-Window Constraints / Yan Qingyou, Qian Zhang // Discrete Dynamics in Nature and Society, 2015. V. 2015. P. 10–15.
  5. Prokudin G. Improvement of the Methods for Determining Optimal Characteristics of Transportation Networks / G. Prokudin, O. Chupaylenko, O. Dudnik, A. Dudnik, D. Omarov // Eastern-European Journal of Enterprise Technologies, 2016. V. 6/3 (84). P. 54–61.
  6. Knight, H. New algorithm can dramatically streamline solutions to the ‘max flow’ problem // MIT News, 2014. P. 21–26.
  7. Shtovba S.D. Murashyni alhorytmy [Ant algorithm]. Exponenta Pro. Matematyka v prylozheniiakh [Exponenta Pro. Mathematics in applications], 2003, issue 4, pp. 70–75.
  8. Zhaoyuan, W. A Modified Ant Colony Optimization Algorithm for Network Coding Resource Minimization / W. Zhaoyuan, X. Huanlai, L. Tianrui // IEEE Transactions on Evolutionary Computation, 2016. V. 20 (3). P. 325–342.
  9. Danchuk, V. An Improvement in Ant Algorithm Method for Optimizing a Transport Route with Regard to Traffic Flow / V. Danchuk, O. Bakulich, V. Svatko // Procedia Engineering, 2017. V. 187. P. 425–434.
  10. Danchuk, V.D., Svatko, V.V. Optymizatsiia poshuku shliakhiv po hrafu v dynamichnii zadachi komivoiazhera metodom modyfikovanoho murashynoho alhorytmu [Optimization of the search for paths along the graph in the dynamic problem of the traveling salesman using the method of the modified ant algorithm]. Systemni doslidzhennia ta informatsiini tekhnolohii NTUU «KPI» [System research and information technologies of NTUU "KPI"], 2012, issue 2, pp. 78–86.
  11. Nakaz Ministerstva transportu Ukrainy vid 05.02.2001 r. N 65 «Pro zatverdzhennia Metodychnykh rekomendatsii z formuvannia sobivartosti perevezen (robit, posluh) na transporti» [Order of the Ministry of Transport of Ukraine dated February 5, 2001 No. 65 "On the approval of Methodological recommendations on the formation of the cost of transportation (works, services) in transport"]. Available at: http://uazakon.com/document/spart34/inx34634.htm (Accessed 20 June 2022).
  12. Karta mista Kyieva dlia pobudovy marshrutiv po Ukraini [Map of the city of Kyiv for building routes across Ukraine]. Available at: https://www.google.com.ua/maps/ (Accessed 20 June 2022).
  13. Resurs sposterezhennia za chastynoiu dilianok VDM m. Kyieva [A resource for monitoring part of the URN sites in Kyiv]. Available at: http://videoprobki.ua (Accessed 20 June 2022).
  14. Lobanov, E.M., Sylianov, V.V., Sytnykov, Yu.M., Sapehyn, L.N. Propusknaia sposobnost avtomobylnikh doroh [Carrying capacity of highways]. M.: Transport, 1970, 152 p.
  15. Postanova Kabinetu Ministriv Ukrainy vid 10.11.2017 № 883 «Pro vnesennia zmin do Pravyl dorozhnoho rukhu» [Resolution of the Cabinet of Ministers of Ukraine dated November 10, 2017 No. 883 "On Amendments to the Traffic Rules"]. Available at: http://zakon3.rada.gov.ua/laws/show/883-2017-%D0%BF (Accessed 20 June 2022). 

https://doi.org/10.33744/2308-6645-2022-3-53-127-137