A Bilevel Hybrid Genetic Algorithm for Capacitated Electric Vehicle Routing Problem

As electric vehicles become more prevalent, a novel vehicle routing problem (VRP) has emerged, known as the capacitated electric VRP (CEVRP). CEVRP requires determining not only the service order of customers but also the charging plans for vehicles, thereby increasing the complexity of solution construction. In response to this challenge, we propose a bilevel hybrid genetic algorithm (BHGA). BHGA models CEVRP as two levels of subproblem: 1) the upper level capacitated VRP, focusing on the service order and 2) the lower level fixed route vehicle charging problem, focusing on the charging plans. In dealing with the upper level subproblem, the hybrid genetic search algorithm is adopted to construct the routes to visit customers and an advanced screening strategy is proposed to optimize the local search process and effectively guide the evolution of population. For the lower level subproblem, an efficient heuristic method called focus enumeration is designed, which is specifically used to insert charging stations into routes to ensure battery constraint. The collaboration of the advanced screening strategy and the focus enumeration assists in more unified solving of the two subproblems. The experiments show that BHGA significantly surpasses state-of-the-art algorithms on benchmark instances and has successfully updated eleven best known solutions, demonstrating its outstanding performance.