A Bilevel Ant Colony Optimization Algorithm for Capacitated Electric Vehicle Routing Problem

The development of electric vehicle (EV) techniques has led to a new vehicle routing problem (VRP) called the capacitated EV routing problem (CEVRP). Because of the limited number of charging stations and the limited cruising range of EVs, not only the service order of customers but also the recharging schedules of EVs should be considered. However, solving these two aspects of the problem together is very difficult. To address the above issue, we treat CEVRP as a bilevel optimization problem and propose a novel bilevel ant colony optimization algorithm in this article, which divides CEVRP into two levels of subproblem: 1) capacitated VRP and 2) fixed route vehicle charging problem. For the upper level subproblem, the electricity constraint is ignored and an order-first split-second max-min ant system algorithm is designed to generate routes that fulfill the demands of customers. For the lower level subproblem, a new effective heuristic is designed to decide the charging schedule in the generated routes to satisfy the electricity constraint. The objective values of the resultant solutions are used to update the pheromone information for the ant system algorithm in the upper level. Through good orchestration of the two components, the proposed algorithm can significantly outperform state-of-the-art algorithms on a wide range of benchmark instances.