期刊
TRANSPORTATION SCIENCE
卷 -, 期 -, 页码 -出版社
INFORMS
DOI: 10.1287/trsc.2022.1180
关键词
split delivery vehicle routing; vehicle routing; heuristics; edge assembly crossover; hybrid search
资金
- China Scholarship Council (CSC) [201906850087]
This paper presents a memetic algorithm for solving the split delivery vehicle routing problem with limited or unlimited vehicles. The algorithm generates and improves solutions using strategies such as edge assembly crossover and local search, and is enhanced by various techniques. Extensive experiments show that the algorithm achieves optimal results on multiple instances. Additional experiments are conducted to study the key components of the algorithm.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据