Optimalitas Rute pada Pengiriman Multiperjalanan dengan Armada Kendaraan Listrik Heterogen

Kamilia Salsabilla, Toni Bakhtiar, Farida Hanum


Electric vehicles are emerging as a key trend in sustainable mobility, mitigating emissions, and reducing dependence on fossil fuels. The challenge in optimizing route modeling lies in some limitations, such as battery range, charging time, and the diversity of electric vehicle types. This article explores the optimality of routes in a multiple-trip distribution system using a heterogeneous fleet of electric vehicles. The electric vehicle routing problem is formulated as a mixed-integer linear programming aiming to find the most cost-efficient optimal route. A notable feature of the model allows electric vehicle fleets to undertake additional travel to complete distribution tasks, i.e., multiple trips. The model is implemented in two illustrative examples involving the delivery of goods using homogeneous and heterogeneous electric vehicle fleets characterized by loading and battery capacities. Each case includes one depot, 8 and 10 customers, and 2 battery swapping stations, solved using the branch-and-bound method through Lingo 18.0. Simulation results indicate that battery capacity and the presence of battery swapping stations significantly influence the routes selection.


Electric Vehicles; Vehicle Routing Problems; Multiple Trips; Optimal Route

Full Text:



G. Laporte, ”Fifty years of vehicle routing,” Transp. Sci., vol. 43, no. 4, pp. 408–416, 2009, doi: 10.1287/trsc.1090.0301.

G. B. Dantzig and J. H. Ramser, “The truck dispatching problem,” Manag. Sci., vol. 6, no. 1, pp. 80–91, 1959, doi: 10.1287/mnsc.6.1.80.

K. Young, C. Wang, L. Y. Wang, and K. Strunz, “Electric vehicle battery technologies,” in R. Garcia-Valle and J. Pecas-Lopes (eds), Electric Vehicle Integration into Modern Power Networks. Power Electronics and Power Systems, New York, NY: Springer, 2013, doi: 10.1007/978-1-4614-0134-6_2.

J. van Duin, L. Tavasszy, and H. Quak, “Towards e(lectric)-urban freight: First promising steps in the electronic vehicle revolution,” Eur. Transp. Trasp. Eur., no. 54, pp. 1–19, 2013.

C. Liao, S. Lu, and Z. M. Shen, “The electric vehicle touring problem,” Transp. Res. B Methodol., vol. 86, pp. 163–180, 2016, doi: 10.1016/j.trb.2016.02.002.

D. Margaritis, A. Anagnostopoulou, A. Tromaras, and M. Boile, “Electric commercial vehicles: practical perspectives and future research directions,” Res. Transp. Bus. Manag., vol. 18, pp. 4–10, 2016, doi: 10.1016/j.rtbm.2016.01.005.

A. Juan, C. Mendez, J. Faulin, J. de Armas, and S. Grasman, “Electric vehicles in logistics and transportation: a survey on emerging environmental, strategic, and operational challenges,” Energies, vol. 9, no. 2, pp. 86, 2016, doi: 10.3390/en9020086.

G. Macrina, L. D. P. Pugliese, and F. Guerriero, “The green-vehicle routing problem: a survey.” In H. Derbel, B. Jarboui, and P. Siarry (eds), Modeling and optimization in green logistics, pp. 1–26, 2020, Springer, Cham, doi: 10.1007/978-3-030-45308-4_1.

I. E. A., “Global EV outlook 2023: catching up with climate ambitions,” International Energy Agency, 2023.

F. A. Padhilah, P. Aji, and I. R. F. Surya, “Indonesia Electric Vehicle Outlook (IEVO) 2023,” Institute for Essential Services Reform (IESR), 2023.

P. Martin, “Weak emission standards and Australia’slow takeup of electric vehicles,” Econ. Papers, vol. 41, no. 4, pp. 390–395, 2022, doi: 10.1111/1759-3441.12371.

L. Li, H. K. Lo, F. Xiao, and X. Cen, “Mixed bus fleet management strategy forminimizing overall and emissions external costs,” Transp. Res. D Transp. Environ., vol. 60, pp. 104–118, 2018, doi: 10.1016/j.trd.2016.10.001.

C. C. Lu, S. Yan, and Y. W. Huang, “Optimal scheduling of a taxi fleet with mixed electric and gasoline vehicles to service advance reservations,” Transp. Res. C Emerg. Technol., vol. 93, pp. 479–500, 2018, doi: 10.1016/j.trc.2018.06.015.

P. Toth and D. Vigo, The vehicle routing problem, Philadelphia, PA: Society for Industrial and Applied Mathematics, 2002, doi: 10.1137/1.9780898718515.

T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins, “Heuristics for multi-attribute vehicle routing problems: a survey and synthesis,” Eur. J. Oper. Res., vol. 231, no. 1, pp. 1–21, 2013, doi: 10.1016/j.ejor.2013.02.053.

D. Pecin, A. Pessoa, M. Poggi, and E. Uchoa, “Improved branch-cut-and-price for capacitated vehicle routing,” Math. Prog. Comput., vol. 9, no. 1, pp. 61–100, 2017, doi: 10.1007/s12532-016-0108-8.

R. Baldacci, A. Mingozzi, and R. Roberti, “Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints,” Eur. J. Oper. Res., vol. 218, no. 1, pp. 1–6, 2012, doi: 10.1016/j.ejor.2011.07.037.

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,” Renew. Sust. Energ. Rev., vol. 151, pp. 111567, 2021, doi: 10.1016/j.rser.2021.111567.

H. Qin, X. Su, T. Ren, and Z. Luo, “A review on the electric vehicle routing problems: variants and algorithms,” Front. Eng. Manag., vol. 8, pp. 370–389, 2021, doi: 10.1007/s42524-021-0157-1.

Y. Huang, “A review on the electric vehicle routing problem and its variations,” Front. Soc. Sci. Technol., vol. 5, no. 5, pp. 85–90, 2023, doi: 10.25236/FSST.2023.050514.

K. V. Tiwari and S. K. Sharma, “An optimization model for vehicle routing problem in last-mile delivery,” Expert Syst. Appl., vol. 222, pp. 119789, 2023, doi: 10.1016/j.eswa.2023.119789.

N. Huang, J. Li, W. Zhu, and H. Qin, “The multi-trip vehicle routing problem with time windows and unloading queue at depot,” Transp. Res. E: Logist. Transp. Rev., vol. 152, pp. 102370, 2021, doi: 10.1016/j.tre.2021.102370.

L. Zhen, C. Ma, K. Wang, L. Xiao, and W. Zhang, “Multi-depot multi-trip vehicle routing problem with time windows and release dates,” Transp. Res. E: Logist. Transp. Rev., vol. 135, pp. 101866, 2020, doi: 10.1016/j.tre.2020.101866.

R. Xu, S. Li, and J. Wu, “Multi-trip vehicle routing problem with time windows and resource synchronization on heterogeneous facilities,” Systems, vol. 11, no. 8, pp. 412, 2023, doi: 10.3390/systems11080412.

P. Kabcome and T. Mouktonglang, “Vehicle routing problem for multiple product types, compartments, and trips with soft time windows,” Int. J. Math. Math. Sci., vol. 2015, article ID 126754, 2015, doi: 10.1155/2015/126754.

F. Hanum, M. R. N. Hadi, A. Aman, and T. Bakhtiar, “Vehicle routing problems in rice-for-the-poor distribution,” Decis. Sci. Lett., vol. 8, no. 3, pp. 323–338, 2019, doi: 10.5267/j.dsl.2018.11.001.

J. Zhang and X. Zhang, “A multi-trip electric bus routing model considering equity during short-notice evacuations,” Transp. Res. D: Transp. Environ., vol. 110, pp. 103397, 2022, doi: 10.1016/j.trd.2022.103397.

Z. I. Haryanto, “Multi trip electric vehicle routing problem backhaul with time window dalam pengadopsian kendaraan listrik pada jasa layanan last mile,” Institut Teknologi Sepuluh Nopember, 2023.

W. Wang, D. Ding, and S. Cao, “Hybrid variable neighborhood search algorithm for the multi-trip and heterogeneous-fleet electric vehicle routing problem, J. Syst. Simul., vol. 34, no. 4, pp. 910–919, 2022, doi: 10.16182/j.issn1004731x.joss.21-1133.

J. Lin, W. Zhou, and O. Wolfson, “Electric vehicle routing problem,” Transp. Res. Proc., vol. 12, pp. 508–521, 2016, doi: 10.1016/j.trpro.2016.02.007.

C. E. Miller, A. W. Tucker, and R. A. Zemlin, “Integer programming formulation of traveling salesman problem, J. ACM, vol. 7, no. 4, pp. 326–329, 1960, doi: 10.1145/321043.321046.

DOI: https://doi.org/10.37905/jjom.v6i1.23993

Copyright (c) 2024 Kamilia Salsabilla, Toni Bakhtiar, Farida Hanum

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

Jambura Journal of Mathematics has been indexed by

>>>More Indexing<<<

Creative Commons License

Jambura Journal of Mathematics (e-ISSN: 2656-1344) by Department of Mathematics Universitas Negeri Gorontalo is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Powered by Public Knowledge Project OJS. 

Editorial Office

Department of Mathematics, Faculty of Mathematics and Natural Science, Universitas Negeri Gorontalo
Jl. Prof. Dr. Ing. B. J. Habibie, Moutong, Tilongkabila, Kabupaten Bone Bolango, Gorontalo, Indonesia
Email: info.jjom@ung.ac.id.