Skip to main content
SpringerLink
Log in

A hybrid genetic algorithm for the electric vehicle routing problem with time windows

  • Research Article
  • Published:
Control Theory and Technology Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. Toth, P., & Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications. Philadelphia: SIAM.

    Book  MATH  Google Scholar 

  2. 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

    Article  MathSciNet  MATH  Google Scholar 

  3. 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

    Article  MathSciNet  MATH  Google Scholar 

  4. 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

    Article  MATH  Google Scholar 

  5. 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.

  6. 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

    Article  Google Scholar 

  7. 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

    Article  Google Scholar 

  8. 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

    Article  Google Scholar 

  9. 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

    Article  Google Scholar 

  10. 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

    Article  Google Scholar 

  11. 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.

  12. 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

    Article  Google Scholar 

  13. 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

  14. 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

  15. 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

    Article  MathSciNet  MATH  Google Scholar 

  16. 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

    Article  MathSciNet  MATH  Google Scholar 

  17. Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Michigan: MIT press.

  18. 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

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors would like to acknowledge the Toyota Motor Corporation for supports in this work.

Author information

Author notes

  1. Qixing Liu, Peng Xu and Tielong Shen contributed equally to this work.

Authors and Affiliations

  1. School of Control Science and Engineering, Dalian University of Technology, Dalian, 116024, China

    Qixing Liu, Peng Xu & Yuhu Wu

  2. Department of Mechanical Engineering, Sophia University, Tokyo, 102-8554, Japan

    Tielong Shen

Authors
  1. Qixing Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peng Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yuhu Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tielong Shen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yuhu Wu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11768-022-00091-1

Keywords

Search

Navigation