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 (VRP) called capacitated electric VRP. Since charging is not as convenient as refueling, both the service of customers and the recharging of vehicles should be considered. In this article, we propose a confidence-based bilevel ant colony optimization (ACO) algorithm to solve the problem. It divides the whole problem into the upper level subproblem capacitated VRP and the lower level subproblem fixed routing vehicle charging problem. For the upper level subproblem, an ACO 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 subproblem, a new heuristic called simple enumeration is proposed to generate recharging schedules for vehicles. Between the two subproblems, 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. The experiments show that the proposed algorithm has reached the state-of-the-art level and updated eight best known solutions of the benchmark.