A Memetic Algorithm With Competition for the Capacitated Green Vehicle Routing Problem

作     者：Ling Wang Jiawen Lu 

作者机构：the Department of Automation Tsinghua University 

出 版 物：《IEEE/CAA Journal of Automatica Sinica》 (自动化学报（英文版）)

年 卷 期：2019年第6卷第2期

页      面：516-526页

核心收录：

学科分类：083305[工学-城乡生态环境与基础设施规划] 08[工学] 09[农学] 0903[农学-农业资源与环境] 0833[工学-城乡规划学] 

基　　金：supported by the National Science Fund for Distinguished Young Scholars of China(61525304) the National Natural Science Foundation of China(61873328) 

主　　题：Capacitated green vehicle routing problem(CGVRP) competition k-nearest neighbor(kNN) local intensification memetic algorithm 

摘      要：In this paper, a memetic algorithm with competition(MAC) is proposed to solve the capacitated green vehicle routing problem(CGVRP). Firstly, the permutation array called traveling salesman problem(TSP) route is used to encode the solution, and an effective decoding method to construct the CGVRP route is presented accordingly. Secondly, the k-nearest neighbor(k NN) based initialization is presented to take use of the location information of the customers. Thirdly, according to the characteristics of the CGVRP, the search operators in the variable neighborhood search(VNS) framework and the simulated annealing(SA) strategy are executed on the TSP route for all solutions. Moreover, the customer adjustment operator and the alternative fuel station(AFS) adjustment operator on the CGVRP route are executed for the elite solutions after competition. In addition, the crossover operator is employed to share information among different solutions. The effect of parameter setting is investigated using the Taguchi method of design-ofexperiment to suggest suitable values. Via numerical tests, it demonstrates the effectiveness of both the competitive search and the decoding method. Moreover, extensive comparative results show that the proposed algorithm is more effective and efficient than the existing methods in solving the CGVRP.