Abstract: To solve the Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows (VRPSPDTW),a Discrete Cuckoo Search (DCS) algorithm was presented.Based on the standard cuckoo search,the current nest was improved by using intra-route improvement method 2-opt move and inter-route improvement method swap/shift move during the process of Lévy flight position update,and a new nest was selected randomly by using intra-route improvement method relocate/exchange move and inter-route improvement method GENE move during the process of nest position update.The performance of DCS algorithm was tested and compared with genetic algorithm and parallel-simulated annealing algorithm.Computational results showed that the proposed DCS was able to achieve the Best Known Solution (BKS) as 100% of the 9 small-to-medium instances.For the large scale instances,DCS obtained better solutions for 5 instances,and equaled BKS in 17 instances.These three algorithms were compared based on Friedman test and Wilcoxon signed-rank test with Rank value method,and the result showed that DCS was an effective method for solving VRPSPDTW problem.

Key words: vehicle routing problem, simultaneous pickup and delivery, time windows, cuckoo search

摘要： 为求解带时间窗和同时取送货的车辆路径问题(VRPSPDTW),提出一种离散布谷鸟(DCS)算法,该算法在标准布谷鸟算法的基础上,在Lévy飞行位置更新过程中,使用路径内搜索2-opt法和路径间搜索swap/shift法改进当前巢穴;在寄生巢位置更新过程中,使用路径内搜索relocate/exchange法和路径间搜索GENE法,随机产生新巢穴。选取Wang和Chen测试数据集,对算法性能进行测试,并与遗传算法和并行模拟退火算法进行比较。测试结果显示,在9个中小型顾客规模算例中,DCS算法获取了所有的当前国际最优解,在56个大型顾客规模的算例中,DCS算法在5个算例中更新了当前国际最优解,在17个算例中获取了当前国际最优解。通过Rank值法对这3种算法进行Friedman检验和Wilcoxon秩检验,结果表明所提DCS算法的有效性。

关键词: 车辆路径问题, 同时取送货, 时间窗, 布谷鸟算法