Article

Received 14.08.2021

Revised 05.01.2022

Accepted 15.02.2022

Retrieved from Vol. 26, No. 1, 2022

Pages 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

Dynamic routing of cargo delivery processes in cities base on synergetic approach

Viktor Danchuk Vitaly Svatko N. Rudoman

The paper proposes synergetic approach for simulation the processes of optimization of routes for the delivery of goods taking into account the non-stationary dynamics of traffic flows on sections of the urban road network. Within the framework of synergetic Lorentz model, the analytical dependences of the change in the speed of the traffic flow on the characteristic time of the change in the dynamics of the traffic flow and the density of the traffic flow in the network sections are determined. Further, based on the obtained dependence of the traffic flow speed on its density by using a modified self-organization algorithm of the ant colony, the route on the network is optimized. Here the urban road network is represented as a bidirectional weighted graph. The main element of the modification is that it implements the possibility of asynchronous movement of the each ant colony agent at a certain speed. In addition, it is also possible to fix the results of optimization of a partially traveled path for calculating a further route when the edge weight (length) of the graph changes during the movement. This allows you to management the route optimization process, taking into account the dynamic state of the network, which depends on the speed of movement of vehicles on certain sections of the network. These changes in speed can be caused by an increase in the congestion of network sections, the occurrence of traffic jams, emergency situations, etc. To test the proposed method, simulation of route optimization processes was carried out within the framework of the traveling salesman problem, taking into account the real dynamics of traffic flows on the example of the road network of Kyiv city. Here, when conducting research on some selected sections of the network, the average density of traffic flows at certain points in time during the day was experimentally determined. Based on the simulation results, a number of effects were identified. These effects are associated with the rebuilding of optimal routes when the average speeds of vehicles on the model sections of the network decrease to certain boundary values corresponding to certain modes of traffic flow. The paper discusses the possibility of using the proposed method in intelligent transportation systems. In particular, this method can be used to solve dynamic vehicle routing problems using information about traffic prediction.

 

traffic flow; urban road network; synergetic Lorentz model; synergetic approach; ant algorithm
  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