Development of optimization algorithms to vehicle routing problem

Authors

DOI:

https://doi.org/10.15587/1729-4061.2025.326135

Keywords:

optimization, machine learning, set cover, CVRP, cost

Abstract

The Capacitated Vehicle Routing Problem with Time-Dependent Demands (CVRPTD) is a significant optimization challenge in the logistics and transportation domain, characterized by dynamic customer demands, strict time windows, and heterogeneous vehicle fleets. This study focuses on urban parcel delivery operations as the primary object of research. The problem addressed involves the inefficiency of conventional vehicle routing strategies in adapting to time-varying customer demands and operational constraints, which often lead to increased costs and service delays. This study aims to minimize total operational costs while ensuring compliance with capacity constraints, service continuity, and demand fluctuations. A comprehensive mathematical model is developed based on a fully connected, directed acyclic graph G=(V, A), incorporating decision variables that represent vehicle routing sequences, timing, and vehicle type assignments. This study addresses the Capacitated Vehicle Routing Problem with Time-Dependent Demands (CVRPTD) in urban parcel delivery, where traditional routing methods struggle with dynamic demands and operational constraints. A mathematical model using a directed acyclic graph is developed, optimized via a gradient-based method with Hessian approximation, LU decomposition, and quasi-Newton techniques. Experiments on datasets with up to 200 customers and 20 vehicles with reductions ranging from 1.79% to 12.75%. The most significant improvement was observed in Sidorame Timur, where the optimization distance decreased by 12.75%, indicating high accuracy in route optimization. For the SCP, the proposed algorithm achieved a 6.46% improvement in solution quality over traditional greedy algorithms

Author Biographies

Muhammad Amin, Universitas Sumatera Utara

Department of Computer Science

Syahril Efendi, Universitas Sumatera Utara

Department of Computer Science

Mahyuddin K. M. Nasution, Universitas Sumatera Utara

Department of Computer Science

Marischa Elveny, Universitas Sumatera Utara

Department of Computer Science

References

  1. Anityasari, M., Rinardi, H. C., Warmadewanthi, I. D. A. A. (2024). Analysing medical waste transportation using periodic vehicle routing problem for Surabaya public health facilities. Journal of Material Cycles and Waste Management, 27 (2), 830–847. https://doi.org/10.1007/s10163-024-02124-0
  2. Rezaei, B., Gadelha Guimaraes, F., Enayatifar, R., C. Haddow, P. (2024). Exploring dynamic population Island genetic algorithm for solving the capacitated vehicle routing problem. Memetic Computing, 16 (2), 179–202. https://doi.org/10.1007/s12293-024-00412-8
  3. Ambrosino, D., Cerrone, C. (2022). A Rich Vehicle Routing Problem for a City Logistics Problem. Mathematics, 10 (2), 191. https://doi.org/10.3390/math10020191
  4. Lim, H., Lee, G. M., Singgih, I. K. (2021). Multi-Depot Split-Delivery Vehicle Routing Problem. IEEE Access, 9, 112206–112220. https://doi.org/10.1109/access.2021.3103640
  5. Wei, X., Niu, C., Zhao, L., Wang, Y. (2024). Combination of ant colony and student psychology based optimization for the multi-depot electric vehicle routing problem with time windows. Cluster Computing, 28 (2). https://doi.org/10.1007/s10586-024-04821-9
  6. Kim, G. (2024). Electric Vehicle Routing Problem with States of Charging Stations. Sustainability, 16 (8), 3439. https://doi.org/10.3390/su16083439
  7. Li, B., Wu, G., He, Y., Fan, M., Pedrycz, W. (2022). An Overview and Experimental Study of Learning-Based Optimization Algorithms for the Vehicle Routing Problem. IEEE/CAA Journal of Automatica Sinica, 9 (7), 1115–1138. https://doi.org/10.1109/jas.2022.105677
  8. Khorsi, M., Chaharsooghi, S. K., Husseinzadeh Kashan, A., Bozorgi-Amiri, A. (2022). Solving the humanitarian multi-trip cumulative capacitated routing problem via a grouping metaheuristic algorithm. Annals of Operations Research, 319 (1), 173–210. https://doi.org/10.1007/s10479-022-04757-6
  9. Yue, B., Ma, J., Shi, J., Yang, J. (2024). A Deep Reinforcement Learning-Based Adaptive Search for Solving Time-Dependent Green Vehicle Routing Problem. IEEE Access, 12, 33400–33419. https://doi.org/10.1109/access.2024.3369474
  10. Thakur, G., Pal, A., Mittal, N., Yajid, M. S. A., Gared, F. (2024). A significant exploration on meta-heuristic based approaches for optimization in the waste management route problems. Scientific Reports, 14 (1). https://doi.org/10.1038/s41598-024-64133-1
  11. Shahbazian, R., Pugliese, L. D. P., Guerriero, F., Macrina, G. (2024). Integrating Machine Learning Into Vehicle Routing Problem: Methods and Applications. IEEE Access, 12, 93087–93115. https://doi.org/10.1109/access.2024.3422479
  12. Pan, B., Zhang, Z., Lim, A. (2021). Multi-trip time-dependent vehicle routing problem with time windows. European Journal of Operational Research, 291 (1), 218–231. https://doi.org/10.1016/j.ejor.2020.09.022
  13. Azad, T., Rahman, H. F., Chakrabortty, R. K., Ryan, M. J. (2022). Optimization of integrated production scheduling and vehicle routing problem with batch delivery to multiple customers in supply chain. Memetic Computing, 14 (3), 355–376. https://doi.org/10.1007/s12293-022-00372-x
  14. Huang, G., Qi, Y., Cai, Y., Luo, Y., Huang, H. (2024). A Grey Wolf Optimizer Algorithm for Multi-Objective Cumulative Capacitated Vehicle Routing Problem Considering Operation Time. Biomimetics, 9 (6), 331. https://doi.org/10.3390/biomimetics9060331
  15. Hesam Sadati, M. E., Çatay, B., Aksen, D. (2021). An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems. Computers & Operations Research, 133, 105269. https://doi.org/10.1016/j.cor.2021.105269
  16. Akbarpour, N., Salehi-Amiri, A., Hajiaghaei-Keshteli, M., Oliva, D. (2021). An innovative waste management system in a smart city under stochastic optimization using vehicle routing problem. Soft Computing, 25 (8), 6707–6727. https://doi.org/10.1007/s00500-021-05669-6
  17. Chen, C.-M., Lv, S., Ning, J., Wu, J. M.-T. (2023). A Genetic Algorithm for the Waitable Time-Varying Multi-Depot Green Vehicle Routing Problem. Symmetry, 15 (1), 124. https://doi.org/10.3390/sym15010124
  18. Park, S., Ha, C., Seok, H. (2023). Vehicle Routing Problem Model with Practicality. Processes, 11 (3), 654. https://doi.org/10.3390/pr11030654
  19. Fernández Gil, A., Lalla-Ruiz, E., Gómez Sánchez, M., Castro, C. (2023). The cumulative vehicle routing problem with time windows: models and algorithm. Annals of Operations Research. https://doi.org/10.1007/s10479-022-05102-7
  20. Mancini, S., Gansterer, M. (2024). Bundle generation for the vehicle routing problem with occasional drivers and time windows. Flexible Services and Manufacturing Journal, 36 (4), 1189–1221. https://doi.org/10.1007/s10696-023-09529-3
Development of optimization algorithms to vehicle routing problem

Downloads

Published

2025-06-30

How to Cite

Amin, M., Efendi, S., Nasution, M. K. M., & Elveny, M. (2025). Development of optimization algorithms to vehicle routing problem. Eastern-European Journal of Enterprise Technologies, 3(3 (135), 67–77. https://doi.org/10.15587/1729-4061.2025.326135

Issue

Vol. 3 No. 3 (135) (2025): Control processes

Section

Control processes

License

Copyright (c) 2025 Muhammad Amin, Syahril Efendi, Mahyuddin K. M. Nasution, Marischa Elveny

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.