Article

Received 27.02.2024

Revised 01.04.2024

Accepted 29.06.2024

Retrieved from Vol. 28, No. 1 2024

Pages 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

Methods of adaptive optimization of routes of the dynamic traveling salesman problem using a modified ant algorithm

Viktor Danchuk Oleksandr Hutarevych

The article proposes an adaptive route optimization method for solving dynamic traveling salesman problem using a modified ant colony algorithm. The method involves finding the optimal route on a 66 bidirectional weighted graph, where the edge weights are defined by relative discrete values according to the optimization criterion. Relevant information obtained from modern geographic information systems (GIS) is utilized to construct such a graph based on input data regarding cargo delivery points. Additionally, information from motion detectors located on road network sections and GIS software interfaces is used for dynamic graph updates. To perform discrete route optimization within the solution of the asymmetric dynamic traveling salesman problem (DTSP), a modification of the ant colony algorithm has been developed. This modification implements automatic updating of the graph's weights based on changes in dynamic characteristics on sections of the road network, upon fixation of the optimal configuration of the partially traversed route prior to its update. To validate the proposed method, a comprehensive set of simulation studies on routing processes under various optimization conditions was conducted. Specifically, to assess the adequacy and reliability of the proposed modification of the ant colony algorithm, corresponding test studies were conducted using a set of well-known static traveling salesman problems with distance optimization criteria in comparison with the most common AI methods of discrete optimization. The research results demonstrate an acceptable level of accuracy (with deviations up to 4% in the worst-case scenarios), which can be considered satisfactory for application in many practical cases. Furthermore, simulation studies of solving the asymmetric DTSP using the proposed adaptive route optimization method with dynamic route updates during cargo transportation revealed several effects associated with route reconstruction. Thus, based on the analysis of simulation results, the fundamental feasibility of using the developed method for solving urban transport logistics problems in real-time considering the actual configuration of the road network and the dynamics of traffic flows on its segments has been demonstrated

intelligent transportation system; intelligent optimization methods; traveling salesman problem; ant colony algorithm; information technologies; geographic information systems; transport logistics; road network; traffic flow
  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