General Edge Assembly Crossover-Driven Memetic Search for Split Delivery Vehicle Routing
提出一种模因算法求解拆分交付车辆路径问题，通过通用边组装交叉和局部搜索生成高质量解，在324个基准实例上更新了143个最优上界，适合研究车辆路径优化和物流配送的学者参考。
The split delivery vehicle routing problem is a variant of the well-known vehicle routing problem, where each customer can be visited by several vehicles. The problem has many practical applications, but it is computationally challenging. This paper presents an effective memetic algorithm for solving the problem with a fleet of limited or unlimited vehicles. The algorithm features a general edge assembly crossover to generate promising offspring solutions from the perspective of assembling suitable edges and an effective local search to improve each offspring solution. The algorithm is further reinforced by a feasibility-restoring procedure, a diversification-oriented mutation, and a quality-and-distance pool updating technique. Extensive experiments on 324 benchmark instances indicate that our algorithm is able to update 143 best upper bounds in the literature and match the best results for 156 other instances. Additional experiments are presented to obtain insight into the roles of the key search ingredients of the algorithm. The method was ranked second in the SDVRP track at the 12th DIMACS Implementation Challenge on Vehicle Routing Problems. Funding: Support from the China Scholarship Council (CSC) [Grant 201906850087] for the first author is acknowledged.