A genetic algorithm to minimise number of vehicles in an electric vehicle routing problem

• Main Authors: QUECK, Kiian Leong Bertran, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2020
• Subjects: Electric Vehicle Routing Problem; Genetic algorithm; Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms; Transportation
• Online Access: https://ink.library.smu.edu.sg/sis_research/5569; https://ink.library.smu.edu.sg/context/sis_research/article/6572/viewcontent/GeneticAlgorithmToMinimise_av_2020.pdf
• Institution: Singapore Management University

Electric Vehicles (EVs) and charging infrastructure are starting to become commonplace in major cities around the world. For logistics providers to adopt an EV fleet, there are many factors up for consideration, such as route planning for EVs with limited travel range as well as long-term planning of fleet size. In this paper, we present a genetic algorithm to perform route planning that minimises the number of vehicles required. Specifically, we discuss the challenges on the violations of constraints in the EV routing problem (EVRP) arising from applying genetic algorithm operators. To overcome the challenges, techniques specific to addressing the infeasibility of solutions are discussed. We test our genetic algorithm against EVRP benchmarks and show that it outperforms them for most problem instances on both the number of vehicles as well as total time traveled.