Abstract
Driven by the new legislation on greenhouse gas emissions, carriers began to use electric vehicles (EVs) for logistics transportation. This paper addresses an electric vehicle routing problem with time windows (EVRPTW). The electricity consumption of EVs is expressed by the battery state-of-charge (SoC). To make it more realistic, we take into account the terrain grades of roads, which affect the travel process of EVs. Within our work, the battery SoC dynamics of EVs are used to describe this situation. We aim to minimize the total electricity consumption while serving a set of customers. To tackle this problem, we formulate the problem as a mixed integer programming model. Furthermore, we develop a hybrid genetic algorithm (GA) that combines the 2-opt algorithm with GA. In simulation results, by the comparison of the simulated annealing (SA) algorithm and GA, the proposed approach indicates that it can provide better solutions in a short time.
Similar content being viewed by others
References
Toth, P., & Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications. Philadelphia: SIAM.
Lysgaard, J., Letchford, A. N., & Eglese, R. W. (2004). A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, 100(2), 423–445. https://doi.org/10.1007/s10107-003-0481-8
Desrochers, M., Desrosiers, J., & Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2), 342–354. https://doi.org/10.1287/opre.40.2.342
Kim, B.-I., Kim, S., & Sahoo, S. (2006). Waste collection vehicle routing problem with time windows. Computers & Operations Research, 33(12), 3624–3642. https://doi.org/10.1016/j.cor.2005.02.045
Liu, Q., Xu, P., Wu, Y., & Shen, T. (2012). A two-stage algorithm for vehicle routing problem with timed-path in disaster response. In: 2021 60th Annual Conference of the Society of Instrument and Control Engineers of Japan (SICE), pp. 36–41. Tokyo, Japan.
Dekker, R., Bloemhof, J., & Mallidis, I. (2012). Operations research for green logistics-an overview of aspects, issues, contributions and challenges. European Journal of Operational Research, 219(3), 671–679. https://doi.org/10.1016/j.ejor.2011.11.010
Lin, J., Zhou, W., & Wolfson, O. (2016). Electric vehicle routing problem. Transportation Research Procedia, 12, 508–521. https://doi.org/10.1016/j.trpro.2016.02.007
Pelletier, S., Jabali, O., & Laporte, G. (2019). The electric vehicle routing problem with energy consumption uncertainty. Transportation Research Part B: Methodological, 126, 225–255. https://doi.org/10.1016/j.trb.2019.06.006
Liao, C.-S., Lu, S.-H., & Shen, Z.-J.M. (2016). The electric vehicle touring problem. Transportation Research Part B: Methodological, 86, 163–180. https://doi.org/10.1016/j.trb.2016.02.002
Kucukoglu, I., Dewil, R., & Cattrysse, D. (2021). The electric vehicle routing problem and its variations: A literature review. Computers & Industrial Engineering, 161, 107650. https://doi.org/10.1016/j.cie.2021.107650
Zhenfeng, G., Yang, L., Xiaodan, J., & Sheng, G. The electric vehicle routing problem with time windows using genetic algorithm. In: 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), pp. 635–639 (2017). https://doi.org/10.1109/IAEAC.2017.8054093. Chongqing, China.
Schneider, M., Stenger, A., & Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 48(4), 500–520. https://doi.org/10.1287/trsc.2013.0490
Shao, S., Guan, W., & Bi, J. (2018). Electric vehicle-routing problem with charging demands and energy consumption. IET Intelligent Transport Systems, 12(3), 202–212. https://doi.org/10.1049/iet-its.2017.0008www.ietdl.org
Froger, A., Jabali, O., Mendoza, J. E., & Laporte, G. (2021). The electric vehicle routing problem with capacitated charging stations. Transportation Science. https://doi.org/10.1287/trsc.2021.1111
Keskin, M., & Çatay, B. (2018). A matheuristic method for the electric vehicle routing problem with time windows and fast chargers. Computers & Operations Research, 100, 172–188. https://doi.org/10.1016/j.cor.2018.06.019
Bruglieri, M., Pezzella, F., Pisacane, O., & Suraci, S. (2015). A variable neighborhood search branching for the electric vehicle routing problem with time windows. Electronic Notes in Discrete Mathematics, 47, 221–228. https://doi.org/10.1016/j.endm.2014.11.029
Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Michigan: MIT press.
Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations Research, 6(6), 791–812. https://doi.org/10.1287/opre.6.6.791
Acknowledgements
The authors would like to acknowledge the Toyota Motor Corporation for supports in this work.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Liu, Q., Xu, P., Wu, Y. et al. A hybrid genetic algorithm for the electric vehicle routing problem with time windows. Control Theory Technol. 20, 279–286 (2022). https://doi.org/10.1007/s11768-022-00091-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11768-022-00091-1