Confidence-based Ant Colony Optimization for Capacitated Electric Vehicle Routing Problem with Comparison of Different Encoding Schemes

The blossoming of electric vehicles gives rise to a new vehicle routing problem called capacitated electric vehicle routing problem. Since charging is not as convenient as refueling, both the service of customers and the recharging of vehicles should be considered. In this paper, we propose a confidence-based bi-level ant colony optimization algorithm to solve the problem. It divides the whole problem into the upper-level sub-problem capacitated vehicle routing problem and the lower-level sub-problem fixed routing vehicle charging problem. For the upper-level sub-problem, an ant colony optimization algorithm is used to generate customer service sequence. Both the direct encoding scheme and the order-first split-second encoding scheme are implemented to make a guideline of their applicable scenes. For the lower-level sub-problem, a new heuristic called simple enumeration is proposed to generate recharging schedules for vehicles. Between the two sub-problems, a confidence-based selection method is proposed to select promising customer service sequence to conduct local search and lower-level optimization. By setting adaptive confidence thresholds, the inferior service sequences that have little chance to become the iteration best are eliminated during the execution. Experiments show that the proposed algorithm has reached the state-of-the-art level and updated eight best known solutions of the benchmark.