Стаття

Отримано 14.08.2021

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

Прийнято 15.02.2022

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

Сторінки 159 -171

Danchuk, V., Svatko, V., & Rudoman, N. (2022). Dynamic routing of cargo delivery processes in cities base on synergetic approach. The National Transport University Bulletin, 26(1), 159-171. https://doi.org/10.33744/2308-6645-2022-1-51-159-171

Динамічна маршрутизація процесів доставки вантажів у містах на базі синергетичного підходу

Віктор Данчук Віталій Сватко Н. Рудоман

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

 

транспортний потік; вулично-дорожня мережа; синергетичний підхід; синергетична модель Лоренца; мурашиний алгоритм
  1. Lukinskiy, V. and Dobromirov, V.: Methods of evaluating transportation and logistics operations in supply chains. Transport and Telecommunication, 17, 55–59 (2016).
  2. Knight, H.: New algorithm can dramatically streamlinesolutions to the ‘maxflow’ problem, MIT News, 21–26 (2014).
  3. Balasescu, S. and Balasescu, M.: Optimization methods for supply chain activities. Bulletin of the Transilvania University of Brasov Series V: Economic Sciences, 7(56), 9–16 (2014).
  4. Qingyou, Y. and Zhang, Q.: The Optimization of Transportation Costs in Logistics Enterprises with Time-Window Constraints. Discrete Dynamics in Nature and Society, 2015, 10–15 (2015).
  5. Prokudin G., Chupaylenko O., Dudnik O., Oliskevych M.: Development of Vehicle Speed Forecasting Method for Intelligent Highway Transport System. Eastern-European Journal of Enterprise Technologies. N. 4/3 (100). Р. 6–14 (2019). doi:10.15587/1729-4061.2019.174255
  6. Glover, F., Kochenberger, G.: Handbook of Metaheuristics. In: International Series in Operations Research & Management Science 57, 570 (2003).
  7. McCall, J.: Genetic algorithms for modelling and optimization. Journal of Computational and Applied Mathematics, 184, 205–222 (2005).
  8. Rejer, I., Lorenz, K.: Classic genetic algorithm vs. Genetic algorithm with aggressive mutation for feature selection for a brain-computer interface. Przegląd Elektrotechniczny 91(2), 98–102 (2015). doi:10.15199/48.2015.02.24.
  9. Dorigo, M., Gambardella, L. M.: Ant colonies for the travelling salesman problem. BioSystems 43(2), 73–81 (1997). doi: 10.1016/S0303-2647(97)01708-5.
  10. Chandekar, N. and Jayachandran Pillai, M.: A Comparative Study of GA and ACO for Solving Travelling Salesman Problem. International Journal of Mechanical and Production Engineering, 5(11), 34–37 (2017).
  11. Ali, H., Haris, M., Hadi, F., Ahmadullah, Salman and Shah, Y.: Solving Traveling Salesman Problem through Optimization Techniques Using Genetic Algorithm and Ant Colony Optimization. Journal of Applied Environmental and Biological Sciences, 6(4S), 55–62 (2016).
  12. Danchuk V., Bakulich, O., Svatko V.: Building optimal routes for cargo delivery in megacities. Transport and Telecommunication, 20(2), 142–152 (2019). https://doi.org/10.2478/ttj-2019-0013
  13. Seyedali Mirjalili: Ant Colony Optimisation. Evolutionary Algorithms and Neural Networks, 33–42 (2018). doi:10.1007/978-3-319-93025-1_3.
  14. Haslina Abdullah, Rizauddin Ramli, Dzuraidah Abd Wahab: Tool path length optimisation of contour parallel milling based on modified ant colony optimisation. The International Journal of Advanced Manufacturing Technology 92, 1263–1276 (2017). doi:10.1007/s00170-017-0193-5.
  15. Chiranjit Changdar, Dr. G. S. Mahapatra, Rajat Kumar Pal.: A modified ant colony optimisation based approach to solve sub-tour constant travelling salesman problem. International Journal of Mathematics in Operational Research, Vol. 11, No. 3 (2017). doi: 10.1504/IJMOR.2017.087204
  16. Kerner B. S.: Introduction to Modern Traffic Flow Theory and Control. Berlin: Springer (2009).
  17. Haken, H.: Synergetics. Introduction and Advanced Topics. Berlin, Heidelberg: Springer, 758p (2004).
  18. Puchkovska G. O., Makarenko S. P., Danchuk V. D., Kravchuk A. P., Baran J., Kotelnikova E. N., Filatov S. K.: Dynamics of molecules and phase transitions in the crystals of pure and binary mixtures of n-paraffins. J. of Mol. Struct. 614(1), 159–166 (2002). https://doi.org/10.1016/S0022-2860(02)00237-5
  19. Olemskoi A., Khomenko A.: Synergetic theory for jamming transition in traffic flow. Physical Review E 63(3) (2001). doi: 10.1103/PhysRevE.63.036116
  20. Danchuk V., Svatko V., Kunytska O., Kush Y.: Simulation of Processes for Optimizing the Delivery Routes of Goods on Urban Road Networks by a Synergetic Approach. Lecture Notes in Networks and Systems Volume 208, 175–196 (2021).
  21. Kwangsoo Kim, Minseok Kwon, Jaegeun Park, and Yongsoon Eun.: Dynamic Vehicular Route Guidance Using Traffic Prediction Information. Hindawi Publishing Corporation. Mobile Information Systems. Volume 2016, 1–11 (2016). http://dx.doi.org/10.1155/2016/3727865

https://doi.org/10.33744/2308-6645-2022-1-51-159-171