Multi-Objective EV Routing with Recharging, Battery-Swapping, and K-Means Station Siting for Ride-Hailing Fleets in Medan City

Widya Afriani; Fibri Rakhmawati

doi:10.56427/jcbd.v5i3.1054

Authors

Widya Afriani Universitas Islam Negeri Sumatera Utara
Fibri Rakhmawati Universitas Islam Negeri Sumatera Utara

DOI:

https://doi.org/10.56427/jcbd.v5i3.1054

Keywords:

Electric Vehicle Routing Problem, Clarke–Wright Savings Algorithm, State of Charge, Weighted Sum, Recharging and Battery Swapping

Abstract

Electric vehicle adoption requires routing strategies that address travel efficiency and battery-energy constraints. This study develops a Multi-Objective Electric Vehicle Routing Problem (EVRP) model for two-wheeled electric ride-hailing services in Medan City, Indonesia. The model minimizes total travel distance and operational energy cost while incorporating recharging and battery-swapping strategies and identifying candidate sites for public charging stations (SPKLU) and battery-swapping stations (SPBKLU). It integrates route construction, battery-energy feasibility, recharge–swap assignment, multi-objective evaluation, and spatial clustering within one decision-support framework. Secondary data comprise one depot, 200 service points, four existing SPKLU, and nine existing SPBKLU. The Clarke–Wright Savings algorithm generates six routes, while the State of Charge (SOC) model evaluates battery feasibility. Twenty recharge–swap assignments are evaluated using the weighted sum method, and Pareto analysis identifies five non-dominated solutions. Under the cost-oriented weighting scenario, recharging is assigned to Routes 1, 4, and 6 and battery swapping to Routes 2, 3, and 5, yielding a travel distance of 327.79 km and an operational cost of IDR 39,131. This solution requires four SPKLU and three SPBKLU points, which K-Means clustering reduces to three and two candidate locations, respectively, providing guidance for battery-replenishment infrastructure planning.

Downloads

Download data is not yet available.

References

[1] V. Vieira, A. Baptista, A. Cavadas, G. F. Pinto, J. Monteiro, and L. Ribeiro, “Comparison of Battery Electrical Vehicles and Internal Combustion Engine Vehicles–Greenhouse Gas Emission Life Cycle Assessment,” Applied Sciences (Switzerland), vol. 15, no. 6, pp. 1–20, 2025, doi: 10.3390/app15063122.

[2] A. Sagwal, P. Agrawal, Randeep, and M. Bhullar, “Revolution in Electric Vehicles,” IOP Conf. Ser. Mater. Sci. Eng., vol. 1225, no. 1, p. 012015, 2022, doi: 10.1088/1757-899x/1225/1/012015.

[3] İ. Küçükoğlu, R. Dewil, and D. Cattrysse, “The electric vehicle routing problem and its variations: A literature review,” Comput. Ind. Eng., vol. 161, p. 107650, 2021, doi: 10.1016/j.cie.2021.107650.

[4] H. Qin, X. Su, T. Ren, and Z. Luo, “A review on the electric vehicle routing problems: Variants and algorithms,” Frontiers of Engineering Management, vol. 8, no. 3, pp. 370–389, 2021, doi: 10.1007/s42524-021-0157-1.

[5] M. Thymianis, A. Tzanetos, E. Osaba, G. Dounias, and J. Del Ser, “Electric Vehicle Routing Problem: Literature Review, Instances and Results with a Novel Ant Colony Optimization Method,” 2022 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8, 2022, doi: 10.1109/CEC55065.2022.9870373.

[6] E. B. Ginting, P. Gultom, and Sutarman, “Optimization Model for Electric Vehicle Routing Problem with Two Charging Options,” Sinkron : Jurnal dan Penelitian Teknik Informatika, vol. 8, no. 3, pp. 1446–1452, 2023, doi: 10.33395/sinkron.v8i3.12577.

[7] C. Ye, W. He, and H. Chen, “Electric vehicle routing models and solution algorithms in logistics distribution: A systematic review,” Environmental Science and Pollution Research, vol. 29, no. 38, pp. 57067–57090, 2022, doi: 10.1007/s11356-022-21559-2.

[8] A. H. S. Azadi, M. Khalilzadeh, J. Antucheviciene, A. Heidari, and A. Soon, “A Sustainable Multi-Objective Model for Capacitated-Electric-Vehicle-Routing-Problem Considering Hard and Soft Time Windows as Well as Partial Recharging,” Biomimetics, vol. 9, no. 4, 2024, doi: 10.3390/biomimetics9040242.

[9] Y. Hao, C. Zhao, Y. Zhang, Y. Cao, and Z. Li, “Constrained multi-objective optimization problems: Methodologies, algorithms and applications,” Knowl. Based. Syst., vol. 299, no. May, p. 111998, 2024, doi: 10.1016/j.knosys.2024.111998.

[10] G. Zhu et al., Optimizing Route Planning via the Weighted Sum Method and Multi-Criteria Decision-Making, vol. 13, no. 11. 2025. doi: 10.3390/math13111704.

[11] U. Jauharul, U. Khothibul , W. N. C. Hendro, and U. M. Ari, “Analisis Perbandingan Algoritma Dijkstra, Haversine, dan Distance Matrix API pada Penentuan Jarak Sekolah di Kota Semarang,” Jurnal Teknologi dan Manajemen Informatika, vol. 11, no. 1, pp. 58–68, 2025, doi: 10.26905/jtmi.v11i1.15544.

[12] C. Cataldo-Díaz, R. Linfati, and J. W. Escobar, Mathematical models for the electric vehicle routing problem with time windows considering different aspects of the charging process, vol. 24, no. 1. Springer Berlin Heidelberg, 2024. doi: 10.1007/s12351-023-00806-5.

[13] E. Roszkowska and T. Wachowicz, “Impact of Normalization on Entropy-Based Weights in Hellwig’s Method: A Case Study on Evaluating Sustainable Development in the Education Area,” Entropy, vol. 26, no. 5, 2024, doi: 10.3390/e26050365.

[14] M. R. Abdullahi, Q. C. Lu, A. Hussain, S. Tripura, P. C. Xu, and S. X. Wang, “Location optimization of EV charging stations: A custom K-means cluster algorithm approach,” Energy Reports, vol. 12, no. July, pp. 5367–5382, 2024, doi: 10.1016/j.egyr.2024.09.075.

[15] H. U. U. Simamora and F. Rakhmawati, “Optimization of Salak Fruit Distribution Routes With Vehicle Routing Problem (VRP) Using Clarke And Wright Saving’s,” Mathline: Jurnal Matematika dan Pendidikan Matematika, vol. 8, no. 2, pp. 691–704, 2023, doi: 10.31943/mathline.v8i2.434.