OPTIMIZATION MODEL FOR MULTI-DEPOT ELECTRIC VEHICLE ROUTING PROBLEM WITH SOFT TIME WINDOWS WITH SCENARIO-BASED ANALYSIS
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
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.
Copyright (c) 2025 Elfina Tan, Toni Bakhtiar, Jaharuddin Jaharuddin

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.