DOI:
https://doi.org/10.64539/sjer.v2i4.2026.568Keywords:
Autonomous electric vehicles, Dynamic vehicle routing, Heterogeneous fleet, Time-dependent network, Battery charging, Bi-objective optimizationAbstract
Dynamic routing is operationally fragile when autonomous electric vehicles differ in capacity and energy use, traffic changes mid-arc, and charging delays redispatch. We formulate a bi-objective problem minimizing operating cost and customer response without time windows. The model combines FIFO-consistent piecewise traffic, load- and speed-sensitive energy, autonomy auxiliary power, SOC reserve, charging loss and duration, and three vehicle classes. Real-world light-duty data and VECTO heavy-duty simulations calibrate four speeds (18.12–40.60 km/h) and three energy intensities (0.146–1.365 kWh/km). We introduce causal charge-aware regret insertion with exchange (CCARI-EX), combining adaptive batching, heterogeneous insertion, relocation, and cross-class exchange. A route-set mixed-integer model proves supported optima for 63 scalarized solves over 21 dispatch epochs. A frozen-seed holdout contains 480 request streams and 4,800 policy executions across four sizes, four release processes, and 30 seeds per cell. An independently implemented validator recorded no rejected dispatch. CCARI-EX (0.75) averaged USD 405.18 and 88.96 min response, improving cost-greedy by USD 6.53 and 4.71 min (paired Holm-adjusted p < .001); it was nondominated in 69.0% of streams. The exact formulation validation confirmed consistency between the route-set model and heuristic evaluation on tractable dispatch epochs. A 12-run SUMO transfer reproduced ordered traffic regimes but exposed severe congestion censoring. The results support charging-continuous replanning while delimiting what aggregate traffic calibration can establish.
References
[1] C. Archetti, L. C. Coelho, M. G. Speranza, and P. Vansteenwegen, “Beyond fifty years of vehicle routing: Insights into the history and the future,” European Journal of Operational Research, vol. 330, no. 2, pp. 355–372, 2026. https://doi.org/10.1016/j.ejor.2025.06.014.
[2] K. Rajashekara, “Energy impacts of autonomous vehicles—Present and the future,” iEnergy, vol. 3, no. 2, pp. 73–74, 2024, https://doi.org/10.23919/IEN.2024.0012.
[3] G. Lera-Romero, J. J. Miranda Bront, and F. J. Soulignac, “A branch-cut-and-price algorithm for the time-dependent electric vehicle routing problem with time windows,” European Journal of Operational Research, vol. 312, no. 3, pp. 978–995, 2024. https://doi.org/10.1016/j.ejor.2023.06.037.
[4] S. Zhou, D. Zhang, B. Ji, S. Zhou, S. Li, and L. Zhou, “A MILP model and heuristic method for the time-dependent electric vehicle routing and scheduling problem with time windows,” Journal of Cleaner Production, vol. 434, Art. no. 140188, 2024, https://doi.org/10.1016/j.jclepro.2023.140188.
[5] N. Soeffker, M. W. Ulmer, and D. C. Mattfeld, “Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review,” European Journal of Operational Research, vol. 298, no. 3, pp. 801–820, 2022. https://doi.org/10.1016/j.ejor.2021.07.014.
[6] J. Zhang, K. Luo, A. M. Florio, and T. Van Woensel, “Solving large-scale dynamic vehicle routing problems with stochastic requests,” European Journal of Operational Research, vol. 306, no. 2, pp. 596–614, 2023. https://doi.org/10.1016/j.ejor.2022.07.015.
[7] W. Wu, Y. Lin, R. Liu, and W. Jin, “The multi-depot electric vehicle scheduling problem with power grid characteristics,” Transportation Research Part B: Methodological, vol. 155, pp. 322–347. https://doi.org/10.1016/j.trb.2021.11.007.
[8] M. H. de Vos, R. N. van Lieshout, and T. Dollevoet, “Electric vehicle scheduling in public transit with capacitated charging stations,” Transportation Science, vol. 58, no. 2, pp. 279–294, 2024. https://doi.org/10.1287/trsc.2022.0253.
[9] A. Tansini, J. Suarez Corujo, A. Laverde Marin, M. Otura Garcia, and G. Fontaras, Real-world driving data—BEV (Darwin) [Dataset]. European Commission, Joint Research Centre, 2025. https://doi.org/10.2905/JRC.A754JZ8.
[10] A. Hanif, M. Abid, M. Tabaa, H. Bensag, and M. Youssfi, “Electric vehicle routing with time windows and heterogeneous charging-station attribute dataset,” Data, vol. 11, no. 4, Art. no. 83, 2026. https://doi.org/10.3390/data11040083.
[11] O. Rainio, J. Teuho, and R. Klén, “Evaluation metrics and statistical tests for machine learning,” Scientific Reports, vol. 14, Art. no. 6086, 2024. https://doi.org/10.1038/s41598-024-56706-x.
[12] İ. Küçükoğlu, R. Dewil, and D. Cattrysse, “The electric vehicle routing problem and its variations: A literature review,” Computers & Industrial Engineering, vol. 161, Art. no. 107650, 2021. https://doi.org/10.1016/j.cie.2021.107650.
[13] Y. Xiao, Y. Zhang, I. Kaku, R. Kang, and X. Pan, “Electric vehicle routing problem: A systematic review and a new comprehensive model with nonlinear energy recharging and consumption,” Renewable and Sustainable Energy Reviews, vol. 151, Art. no. 111567, 2021, doi: 10.1016/j.rser.2021.111567. https://doi.org/10.1016/j.rser.2021.111567.
[14] E. Lam, G. Desaulniers, and P. J. Stuckey, “Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise-linear recharging and capacitated recharging stations,” Computers & Operations Research, vol. 145, Art. no. 105870, 2022. https://doi.org/10.1016/j.cor.2022.105870.
[15] R. Raeesi and K. G. Zografos, “Coordinated routing of electric commercial vehicles with intra-route recharging and en-route battery swapping,” European Journal of Operational Research, vol. 301, no. 1, pp. 82–109, 2022. https://doi.org/10.1016/j.ejor.2021.09.037.
[16] M. Seyfi, M. Alinaghian, E. Ghorbani, B. Çatay, and M. S. Sabbagh, “Multi-mode hybrid electric vehicle routing problem,” Transportation Research Part E: Logistics and Transportation Review, vol. 166, Art. no. 102882, 2022. https://doi.org/10.1016/j.tre.2022.102882.
[17] S. Dönmez, Ç. Koç, and F. Altıparmak, “The mixed fleet vehicle routing problem with partial recharging by multiple chargers: Mathematical model and adaptive large neighborhood search,” Transportation Research Part E: Logistics and Transportation Review, vol. 167, Art. no. 102917, 2022. https://doi.org/10.1016/j.tre.2022.102917.
[18] W. Wang, Y. Adulyasak, and J.-F. Cordeau, “Electric vehicle routing with heterogeneous charging stations,” Computers & Operations Research, vol. 189, Art. no. 107374, 2026. https://doi.org/10.1016/j.cor.2025.107374.
[19] M. Bruglieri, M. Paolucci, and O. Pisacane, “A matheuristic for the electric vehicle routing problem with time windows and a realistic energy consumption model,” Computers & Operations Research, vol. 157, Art. no. 106261, 2023. https://doi.org/10.1016/j.cor.2023.106261.
[20] J. Dong, H. Wang, and S. Zhang, “Dynamic electric vehicle routing problem considering mid-route recharging and new demand arrival using an improved memetic algorithm,” Sustainable Energy Technologies and Assessments, vol. 58, Art. no. 103366, 2023. https://doi.org/10.1016/j.seta.2023.103366.
[21] M. Bruglieri, R. Peruzzini, and O. Pisacane, “Efficiently routing a fleet of autonomous vehicles in a real-time ride-sharing system,” Computers & Operations Research, vol. 168, Art. no. 106668, 2024. https://doi.org/10.1016/j.cor.2024.106668.
[22] J. Zhao, Z. Zeng, and Y. Liu, “Electric vehicle routing problem considering traffic conditions and real-time loads,” Transportation Research Part C: Emerging Technologies, vol. 176, Art. no. 105150, 2025. https://doi.org/10.1016/j.trc.2025.105150.
[23] H. Gehring and J. Homberger, “Two evolutionary metaheuristics for the vehicle routing problem with time windows,” INFOR: Information Systems and Operational Research, vol. 37, no. 3, pp. 297–318, 1999. https://doi.org/10.1080/03155986.1999.11732386.
[24] G. Oh, D. J. LeBlanc, and H. Peng, “Vehicle Energy Dataset (VED), a large-scale dataset for vehicle energy consumption research,” IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 4, pp. 3302–3312, 2022. https://doi.org/10.1109/TITS.2020.3035596.
[25] W. Wang and J. Zhao, “Partial linear recharging strategy for the electric fleet size and mix vehicle routing problem with time windows and recharging stations,” European Journal of Operational Research, vol. 308, no. 2, pp. 929–948, 2023. https://doi.org/10.1016/j.ejor.2022.12.011.
[26] Y. Jiang, W. Hu, W. Gu, Y. Yu, and M. Xu, “A multi-mode hybrid electric vehicle routing problem with time windows,” Transportation Research Part E: Logistics and Transportation Review, vol. 195, Art. no. 103976, 2025. https://doi.org/10.1016/j.tre.2025.103976.
[27] A. Parmentier, R. Martinelli, and T. Vidal, “Electric vehicle fleets: Scalable route and recharge scheduling through column generation,” Transportation Science, vol. 57, no. 3, pp. 631–646, 2023. https://doi.org/10.1287/trsc.2023.1199.
[28] Y. Zang, M. Wang, and M. Qi, “A column generation tailored to electric vehicle routing problem with nonlinear battery depreciation,” Computers & Operations Research, vol. 137, Art. no. 105527, 2022. https://doi.org/10.1016/j.cor.2021.105527.
[29] R. Basso, B. Kulcsár, I. Sánchez-Díaz, and X. Qu, “Dynamic stochastic electric vehicle routing with safe reinforcement learning,” Transportation Research Part E: Logistics and Transportation Review, vol. 157, Art. no. 102496, 2022. https://doi.org/10.1016/j.tre.2021.102496.
[30] B. Lin, B. Ghaddar, and J. Nathwani, “Electric vehicle routing with charging/discharging under time-variant electricity prices,” Transportation Research Part C: Emerging Technologies, vol. 130, Art. no. 103285, 2021. https://doi.org/10.1016/j.trc.2021.103285.
[31] A. Froger, O. Jabali, J. E. Mendoza, and G. Laporte, “The electric vehicle routing problem with capacitated charging stations,” Transportation Science, vol. 56, no. 2, pp. 460–482, 2022. https://doi.org/10.1287/trsc.2021.1111.
[32] M. Dastpak, F. Errico, O. Jabali, and F. Malucelli, “Dynamic routing for the electric vehicle shortest path problem with charging station occupancy information,” Transportation Research Part C: Emerging Technologies, vol. 158, Art. no. 104411, 2024. https://doi.org/10.1016/j.trc.2023.104411.
[33] G. M. Nafstad, G. Desaulniers, and M. Stålhane, “Branch-price-and-cut for the electric vehicle routing problem with heterogeneous recharging technologies and nonlinear recharging functions,” Transportation Science, vol. 59, no. 3, pp. 628–646, 2025. https://doi.org/10.1287/trsc.2024.0725.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Kashif Bashir, Rumaisa Rafiq, Muhammad Afzal Shah, Marzia Niazi, Nouman Bashir, Sara Khan, Haseeb ur Rehman
This work is licensed under a Creative Commons Attribution 4.0 International License.
