A Dual-Population-Based Co-Evolutionary Algorithm for Capacitated Electric Vehicle Routing Problems

The capacitated electric vehicle routing problem is a challenging non-deterministic polynomial hard (NP-hard) problem consisting of two interdependent sub-problems, the routing optimization problem and the charging decision problem. The routing optimization for electric vehicles with limited driving range is dependent on the available charging stations, while the charging decision is based on the charging demand that is estimated on the fixed route in return. Taking this coupling relationship into consideration, this paper proposes a dual-population based co-evolutionary algorithm that uses two evolution populations to collaboratively optimize these two sub-problems. In routing population, the charging station is regarded as a kind of customer with no demand, and an improved ant colony optimization algorithm is designed to generate routes that involve the position information of charging stations. In charging population, a binary genetic algorithm is used to generate a population of charging schemes whose qualities are evaluated based on the best ant obtained from the routing population, and then the resultant solution by inserting the best charging scheme is used to update the pheromone for the routing generation. Through the information interaction during the evolution, these two populations collaboratively search for the optimal solution of the problem. Experimental results demonstrate that the proposed algorithm can be able to avoid falling into the local optimum and has a reduction of about 4% in route distance averaged over two test suites. Additionally, it also has a high computational efficiency, which is faster than the advanced ant colony optimization method by about 2 times.