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

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