A heterogeneous fleet electric vehicle routing model with soft time windows

Authors

  • Yoanda Astri Ayu Kinanti IPB University
  • Toni Bakhtiar IPB University
  • Farida Hanum IPB University

Keywords:

Electric vehicles, Heterogeneous fleet, Soft time window, Vehicle routing problem

Abstract

The emergence of electric vehicles in distribution and logistics activities has brought significant benefits due to their unique characteristics, such as energy-efficient and lower carbon emissions. In the perspective of vehicle routing problem, electric vehicles pose challenging constraints regarding the limited battery capacity, and thus their traveling ranges, and the availability of charging stations. In this paper, we propose a model of the fleet electric vehicle routing problem (EVRP) with soft time windows, where a mixed integer linear programming framework is implemented in model formulation. The objective of mathematical programming is to minimize the total operational cost, which consists of a fixed cost, a traveling cost, a battery charging cost, and probably a penalty cost due to time window violation. We implement our model in two simple cases, namely homogeneous and heterogeneous fleets EVRPs, characterized by loading and battery capacities. Each case consists of one depot, five customers, two electric vehicles, and two charging stations. Optimal routes are obtained using the well-known branch-and-bound method under Lingo 17.0. It is found that the existence of charging stations may affect the routes selection and the implementation of soft time windows rather than hard time windows has been proven to increase the feasibility of routing problem.

References

I. E. A., “Global EV outlook 2023: catching up with climate ambitions,” International Energy Agency, 2023. Available: www.iea.org/reports/global-ev-outlook-2023.

F. Alanazi, “Electric vehicles: benefits, challenges, and potential solutions for widespread adaptation,” Applied Sciences, vol. 13, no. 10, pp. 6016, 2023. doi: 10.3390/app13106016.

S. Lozanova, “Electric vehicle trends for 2024: what to expect in the EV market,” Greenlancer, 2024. Available: www.greenlancer.com/post/ev-market-trends.

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.

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,” European Transport - Trasporti Europei, no. 54, pp. 1–19, 2013. Available: hdl.handle.net/10077/8875.

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

A. Montoya, C. Guéret, J. E. Mendoza, and J. G. Villegas, “The electric vehicle routing problem with nonlinear charging function,” Transportation Research Part B: Methodological, vol. 103, pp. 87–110, 2017. doi: 10.1016/j.trb.2017.02.004.

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. doi: 10.1016/j.ejor.2022.12.011.

S. Zhang, Y. Gajpal, S. S. Appadoo, and M. M. S. Abdulkader, “Electric vehicle routing problem with recharging stations for minimizing energy consumption,” International Journal of Production Economics, vol. 203, pp. 404–413, 2018. doi: 10.1016/j.ijpe.2018.07.016.

P. Jarvis, L. Climent, and A. Arbelaez, “Smart and sustainable scheduling of charging events for electric buses.” In: Henriques, C., Viseu, C. (eds) EU Cohesion Policy Implementation - Evaluation Challenges and Opportunities. Springer Proceedings in Political Science and International Relations. Cham, CH: Springer, 2023. doi: 10.1007/978-3-031-18161-0_8.

C. Cataldo-Díaz, R. Linfati, and J. W. Escobar, “Mathematical model for the electric vehicle routing problem considering the state of charge of the batteries,” Sustainability, vol. 14, no. 3, pp. 1645, 2022. doi: 10.3390/su14031645.

X. Zuo, Y. Xiao, M. You, I. Kaku, and Y. Xu, “A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function,” Journal of Cleaner Production, vol. 236, pp. 117687, 2019. doi: 10.1016/j.jclepro.2019.117687.

L. Li, H. K. Lo, F. Xiao, and X. Cen, “Mixed bus fleet management strategy forminimizing overall and emissions external costs,” Transportation Research Part D: Transport and Environment, 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,” Transportation Research Part C: Emerging Technologies, 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.

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

F. Liu, C. Lua, L. Gui, Q. Zhang, X. Tong, and M. Yuan, “Heuristics for vehicle routing problem: a survey and recent advances,” arXiv, 2303.04147, pp. 1–67, 2023. doi: 10.48550/arXiv.2303.04147.

J. P. Futalef, D. Munoz-Carpintero, H. Rozas, and M Orchard, “Evolutionary algorithm for the electric vehicle routing problem with battery degradation and capacitated charging stations.” In Proceedings of the Annual Conference of the PHM Society, Nashville, TN, USA, 9–13 November 2020, vol. 12, no. 1, pp. 1–9, 2020. doi: 10.36001/phmconf.2020.v12i1.1281.

Y. Zhang, S. Zhou, X. P. Ji, B. Chen, H. X. Liu, Y. Xiao, and W. Chang, “The mathematical model and a genetic algorithm for the two-echelon electric vehicle routing problem,” Journal of Physics: Conference Series, vol. 1813, pp. 012006, 2020. doi: 10.1088/1742-6596/1813/1/012006.

M. Bruglieri, F. Pezzella, O. Pisacane, and S. Suraci, “A variable neighborhood search branching for the electric vehicle routing problem with time windows,” Electronic Notes in Discrete Mathematics, vol. 47, pp. 221–228, 2015. doi: 10.1016/j.endm.2014.11.029.

K. Sadeghi-Velni, R. Tavakkoli-Moghaddam, and F. Jolai, “New mathematical modelling for an electric vehicle inventory-routing problem,” Quarterly Journal of Transportation Engineering, vol. 13, no. 1, pp. 1071–1090, 2021. doi: 10.22119/jte.2021.63216.

M. Setak and A. Karimpour, “A mathematical model for the electric vehicle routing with time windows considering queuing system at charging stations and alternative paths,” Journal of Industrial and Systems Engineering, vol. 12, no. 1, pp. 284–306, 2019. Available at: www.jise.ir/article_81756.html.

M. Elahi and S. A. Darestani, “Modeling a periodic electric vehicle-routing problem considering delivery due date and mixed charging rates using metaheuristic method,” Environmental Science and Pollution Research, vol. 29, no. 46, pp. 69691–69704, 2022. doi: 10.1007/s11356-022-20776-z.

S. E. Comert and H. R. Yazgan, “A new approach based on hybrid ant colony optimization-artificial bee colony algorithm for multi-objective electric vehicle routing problems,” Engineering Applications of Artificial Intelligence, vol. 123, B, pp. 106375, 2023. doi: 10.1016/j.engappai.2023.106375.

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, pp. 106261, 2023. doi: 10.1016/j.cor.2023.106261.

J. Xiao, J, Du, Z. Cao, X. Zhang, and Y. Niu, “A diversity-enhanced memetic algorithm for solving electric vehicle routing problems with time windows and mixed backhauls,” Applied Soft Computing, vol. 134, pp. 110025, 2023. doi: 10.1016/j.asoc.2023.110025.

N. Singh, Q.-V. Dang, A. Akcay, I. Adan, and T. Martagan, “A matheuristic for AGV scheduling with battery constraints,” European Journal of Operational Research, vol. 298, no. 3, pp. 855–873, 2022. doi: 10.1016/j.ejor. 2021.08.008.

G. Hiermann, J. Puchinger, S. Ropke, and R. F. Hartl, “The electric fleet size and mix vehicle routing problem with time windows and recharging stations,” European Journal of Operational Research, vol. 252, no. 3, pp. 995–1018, 2016. doi: 10.1016/j.ejor.2016.01.038.

A. Karimpour, M. Setak, and A. Hemmati, “Estimating energy consumption and charging duration of electric vehicle in multigraph,” Computers & Operations Research, vol. 155, pp. 106216, 2023. doi: 10.1016/j.cor.2023.106216.

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, 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,” Frontiers of Engineering Management, 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,” The Frontiers of Society, Science and Technology, vol. 5, no. 5, pp. 85–90, 2023. doi: 10.25236/FSST.2023.050514.

M. Schneider, A. Stenger, and D. Goeke, “The electric vehicle-routing problem with time windows and recharging stations,” Transportation Science, vol. 48, no. 4, pp. 500–520, 2014. doi: 10.1287/trsc.2013.0490.

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

X. Zhang, J. Yao, Z. Liao, J. Li, “The electric vehicle routing problem with soft time windows and recharging stations in the reverse logistics,” in J. Xu, F. Cooke, M. Gen, S. Ahmed (eds), Proceedings of the Twelfth International Conference on Management Science and Engineering Management, Lecture Notes on Multidisciplinary Industrial Engineering. Cham, CH: Springer, 2019. doi: 10.1007/978-3-319-93351-1_15.

D. Tas, N. Dellaert, T. van Woensel, and T. de Kok, “The time-dependent vehicle routing problem with soft time windows and stochastic travel times,” Transportation Research Part C: Emerging Technologies, vol. 48, pp. 66–83, 2014. doi: 10.1016/j.trc.2014.08.007.

S. Iqbal and M. S. Rahman, “Vehicle routing problems with soft time windows,” The 7th International Conference on Electrical and Computer Engineering, Dhaka, Bangladesh, pp. 634-638, 2012. doi: 10.1109/ICECE.2012.6471630.

P. Li, J. He, D. Zheng, Y. Huang, C. Fan, “Vehicle routing problem with soft time windows based on improved genetic algorithm for fruits and vegetables distribution,” Discrete Dynamics in Nature and Society, vol. 2015, article ID 483830, 8 pages, 2015. doi: 10.1155/2015/483830.

H. Mao, J. Shi, Y. Zhou, G. Zhang, “The electric routing problem with time windows and multiple recharging options,” IEEE Access, vol. 8, pp. 114864–114875, 2020. doi: 10.1109/ACCESS.2020.3003000.

A. Verma, “Electric vehicle routing problem with time windows, recharging station and battery swapping station” EURO Journal of Transportation and Logistics, vol. 7, pp. 415–451, 2018. doi: 10.1007/s13676-018-0136-9.

Downloads

Published

2024-09-03

How to Cite

Kinanti, Y. A. A., Bakhtiar, T., & Hanum, F. (2024). A heterogeneous fleet electric vehicle routing model with soft time windows. International Journal of Industrial Optimization, 5(2), 93–105. Retrieved from http://journal2.uad.ac.id/index.php/ijio/article/view/9014

Issue

Vol. 5 No. 2 (2024)

Section

Articles

License

Copyright (c) 2024 Yoanda Astri Ayu Kinanti, Toni Bakhtiar, Farida Hanum

Creative Commons License

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

License and Copyright Agreement

In submitting the manuscript to the journal, the authors certify that:

  • They are authorized by their co-authors to enter into these arrangements.
  • The work described has not been formally published before, except in the form of an abstract or as part of a published lecture, review, thesis, or overlay journal. Please also carefully read the International Journal of Industrial Optimization (IJIO) Author Guidelines at http://journal2.uad.ac.id/index.php/ijio/about/submissions#onlineSubmissions
  • That it is not under consideration for publication elsewhere,
  • That its publication has been approved by all the author(s) and by the responsible authorities tacitly or explicitly of the institutes where the work has been carried out.
  • They secure the right to reproduce any material that has already been published or copyrighted elsewhere.
  • They agree to the following license and copyright agreement.

Copyright

Authors who publish with the International Journal of Industrial Optimization (IJIO) agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.