Cooperative co-evolution with adaptive decomposition schemes for large scale capacitated electric vehicle routing problem

Abstract

The capacitated electric vehicle routing problem is a complex optimization problem consisting of two types of decisions: (1) deciding the routes for the electric vehicle fleets to complete the customer service; and (2) determining when to visit the charging stations. When the problem size grows, the problem becomes particularly challenging due to the large search space. To address this issue, we develop a cooperative co-evolution algorithm, containing novel problem decomposition and charging scheduling strategies. Two adaptive schemes are adopted to divide the problem into a reasonable number of subproblems with tractable sizes and select the customers with closeness beyond the threshold degree between two routes to measure their relationship. Based on the problem decomposition strategy, a memetic algorithm is designed as an optimizer for each subproblem, and the best sub-solutions are concatenated into an entire solution. The proposed algorithm is verified by comparing it with a number of state-of-the-art algorithms on two popular benchmark datasets as well as their enhanced forms. The experimental results show that our proposed algorithm outperforms the compared algorithms on nearly all instances. In particular, it successfully updated the majority of best-known solutions to the large instances.