OPTIMIZATION MODEL FOR MULTI-DEPOT ELECTRIC VEHICLE ROUTING PROBLEM WITH SOFT TIME WINDOWS WITH SCENARIO-BASED ANALYSIS

  • Elfina Tan Undergraduate Mathematics Study Program, School of Data Science, Mathematics, and Informatics, IPB University, Indonesia https://orcid.org/0009-0001-6673-0589
  • Toni Bakhtiar Undergraduate Mathematics Study Program, School of Data Science, Mathematics, and Informatics, IPB University, Indonesia https://orcid.org/0000-0002-7426-1620
  • Jaharuddin Jaharuddin Undergraduate Mathematics Study Program, School of Data Science, Mathematics, and Informatics, IPB University, Indonesia https://orcid.org/0000-0003-1732-9809
Keywords: Electric Vehicle, Integer Linear Programming, Multi-Depot, Time Windows, Vehicle Routing Optimization

Abstract

The adoption of electric vehicles has increased due to their cost-efficiency and environmental impact. However, limited battery capacity requires careful route planning to ensure vehicles complete deliveries efficiently. This study focuses on the Multi-Depot Electric Vehicle Routing Problem with Soft Time Windows (MDEVRPSTW), where electric vehicles can depart from and return to multiple depots, while serving customers within predefined time windows that allow limited violations with penalty costs. The model is formulated using Mixed Integer Linear Programming (MILP) and solved using the exact branch-and-bound method in Lingo 20.0. Two operational scenarios are considered: (1) vehicles must return to their original depot, and (2) vehicles are allowed to return to any depot. Hypothetical data is used to simulate delivery routes with varied time windows and battery capacity constraints. Results show that both scenarios produce feasible, cost-minimizing solutions. Allowing flexible depot return (scenario 2) consistently reduces total travel cost, highlighting the practical benefit of depot flexibility in real-world logistics. This model contributes to the EV routing literature by integrating multiple depots—both fixed and flexible return options—soft time windows, and battery constraints into a single formulation. However, it assumes constant travel speeds and does not account for charging durations, which presents an opportunity for future research.

Downloads

Download data is not yet available.

References

J. A. Sanguesa, V. Torres-Sanz, P. Garrido, F. J. Martinez, and J. M. Marquez-Barja, “A REVIEW ON ELECTRIC VEHICLES: TECHNOLOGIES AND CHALLENGES,” Smart Cities, vol. 4, no. 1, 2021, doi: https://doi.org/10.3390/smartcities4010022.

R. Irle, “GLOBAL EV SALES FOR 2023 H1,” https://ev-volumes.com/topic/world/. Accessed: Oct. 14, 2023. [Online]. Available: https://www.ev-volumes.com/country/total-world-plug-in-vehicle-volumes/

S. E. Pranata and Y. S. Tjahjaningsih, “ANALISIS PERBANDINGAN NILAI EKONOMIS MOBIL LISTRIK DAN MOBIL KONVENSIONAL DENGAN PENDEKATAN TOTAL COST OF OWNERSHIP (TCO),” JISE, vol. 2, no. 2, pp. 22–33, 2023.

C. Sudjoko, “STRATEGI PEMANFAATAN KENDARAAN LISTRIK BERKELANJUTAN SEBAGAI SOLUSI UNTUK MENGURANGI EMISI KARBON,” Jurnal Paradigma: Jurnal Multidisipliner Mahasiswa Pascasarjana Indonesia, vol. 2, no. 2, pp. 54–68, 2021, doi: 10.22146/jpmmpi.v2i2.70354.

R. Lahyani, M. Khemakhem, and F. Semet, “RICH VEHICLE ROUTING PROBLEMS: FROM A TAXONOMY TO A DEFINITION,” Eur J Oper Res, vol. 241, no. 1, pp. 1–14, 2015, doi: https://doi.org/10.1016/j.ejor.2014.07.048.

R. Nurlailawati, T. Bakhtiar, and P. T. Supriyo, “MASALAH ANTAR-JEMPUT BARANG MENGGUNAKAN ARMADA KENDARAAN LISTRIK DENGAN KAPASITAS ANGKUT DAN KAPASITAS BATERAI BERBEDA,” Jurnal Matematika Integratif, vol. 19, no. 2, p. 173, Dec. 2023, doi: https://doi.org/10.24198/jmi.v19.n2.48627.173-182.

K. Salsabilla, T. Bakhtiar, and F. Hanum, “OPTIMALITAS RUTE PADA PENGIRIMAN MULTIPERJALANAN DENGAN ARMADA KENDARAAN LISTRIK HETEROGEN,” Jambura Journal of Mathematics, vol. 6, no. 1, pp. 85–91, Feb. 2024, doi: https://doi.org/10.37905/jjom.v6i1.23993.

M. Schiffer and G. Walther, “THE ELECTRIC LOCATION ROUTING PROBLEM WITH TIME WINDOWS AND PARTIAL RECHARGING,” Eur J Oper Res, vol. 260, no. 3, 2017, doi: https://doi.org/10.1016/j.ejor.2017.01.011.

Y. A. A. Kinanti, T. Bakhtiar, and F. Hanum, “A HETEROGENEOUS FLEET ELECTRIC VEHICLE ROUTING MODEL WITH SOFT TIME WINDOWS,” IJIO, vol. 5, no. 2, pp. 93–105, Sep. 2024, doi: https://doi.org/10.12928/ijio.v5i2.9014.

D. M. Miranda and S. V. Conceição, “THE VEHICLE ROUTING PROBLEM WITH HARD TIME WINDOWS AND STOCHASTIC TRAVEL AND SERVICE TIME,” Expert Syst Appl, vol. 64, pp. 104–116, 2016, doi: https://doi.org/10.1016/j.eswa.2016.07.022.

T. R. P. Ramos, M. I. Gomes, and A. P. B. Póvoa, “MULTI-DEPOT VEHICLE ROUTING PROBLEM: A COMPARATIVE STUDY OF ALTERNATIVE FORMULATIONS,” International Journal of Logistics Research and Applications, vol. 23, no. 2, 2020, doi: https://doi.org/10.1080/13675567.2019.1630374.

S. Salhi, A. Imran, and N. A. Wassan, “THE MULTI-DEPOT VEHICLE ROUTING PROBLEM WITH HETEROGENEOUS VEHICLE FLEET: FORMULATION AND A VARIABLE NEIGHBORHOOD SEARCH IMPLEMENTATION,” Comput Oper Res, vol. 52, pp. 315–325, Dec. 2014, doi: https://doi.org/10.1016/j.cor.2013.05.011.

Y. Wang, Q. Li, X. Guan, J. Fan, M. Xu, and H. Wang, “COLLABORATIVE MULTI-DEPOT PICKUP AND DELIVERY VEHICLE ROUTING PROBLEM WITH SPLIT LOADS AND TIME WINDOWS,” Knowl Based Syst, vol. 231, Nov. 2021, doi: https://doi.org/10.1016/j.knosys.2021.107412.

H. Bae and I. Moon, “MULTI-DEPOT VEHICLE ROUTING PROBLEM WITH TIME WINDOWS CONSIDERING DELIVERY AND INSTALLATION VEHICLES,” Appl Math Model, vol. 40, no. 13–14, 2016, doi: https://doi.org/10.1016/j.apm.2016.01.059.

A. Ghobadi, R. Tavakkoli-Moghaddam, M. Fallah, and H. Kazemipoor, “MULTI-DEPOT ELECTRIC VEHICLE ROUTING PROBLEM WITH FUZZY TIME WINDOWS AND PICKUP/DELIVERY CONSTRAINTS,” Journal of Applied Research on Industrial Engineering, vol. 8, no. 1, 2021, doi: 10.22105/jarie.2021.231764.1165.

L. Fan, “A TWO-STAGE HYBRID ANT COLONY ALGORITHM FOR MULTI-DEPOT HALF-OPEN TIME-DEPENDENT ELECTRIC VEHICLE ROUTING PROBLEM,” Complex and Intelligent Systems, vol. 10, no. 2, pp. 2107–2128, Apr. 2024, doi: https://doi.org/10.1007/s40747-023-01259-1.

P. Chen and Y. Wang, “AN ADAPTIVE LARGE NEIGHBORHOOD SEARCH FOR MULTI-DEPOT ELECTRIC VEHICLE ROUTING PROBLEM WITH TIME WINDOWS,” European J. of Industrial Engineering, vol. 18, no. 4, 2024, doi: https://doi.org/10.1504/EJIE.2024.10057555.

J. Lin, W. Zhou, and O. Wolfson, “ELECTRIC VEHICLE ROUTING PROBLEM,” Transportation Research Procedia, vol. 12, 2016, doi: https://doi.org/10.1016/j.trpro.2016.02.007.

J. Li, F. Wang, and Y. He, “ELECTRIC VEHICLE ROUTING PROBLEM WITH BATTERY SWAPPING CONSIDERING ENERGY CONSUMPTION AND CARBON EMISSIONS,” Sustainability (Switzerland), vol. 12, no. 24, pp. 1–20, Dec. 2020, doi: https://doi.org/10.3390/su122410537.

M. F. N. Maghfiroh, A. H. Pandyaswargo, and H. Onoda, “CURRENT READINESS STATUS OF ELECTRIC VEHICLES IN INDONESIA: MULTISTAKEHOLDER PERCEPTIONS,” Dec. 01, 2021, MDPI. doi: https://doi.org/10.3390/su132313177.

Published
2025-09-01
How to Cite
[1]
E. Tan, T. Bakhtiar, and J. Jaharuddin, “OPTIMIZATION MODEL FOR MULTI-DEPOT ELECTRIC VEHICLE ROUTING PROBLEM WITH SOFT TIME WINDOWS WITH SCENARIO-BASED ANALYSIS”, BAREKENG: J. Math. & App., vol. 19, no. 4, pp. 2751-2764, Sep. 2025.