利用破坏重建算法进行物流车辆动态调度

A Dynamic Scheduling Method of Logistics Vehicles Based on Ruin and Recreate Algorithm

随着中国经济的快速发展,物流配送对车辆调度的实时性与应急情况处理能力提出了更高的要求,使用传统车辆调度算法难以满足突发事件实时处理需求。针对紧急情况如车辆故障或新增任务点等,在传统启发式算法——破坏重建算法的基础上提出了一种动态调度方法:局部搜索方法,实现了物流车辆的动态调度,有效提升了车辆调度中应对紧急情况的实时性与动态性。与多目标混合蚁群优化算法进行实验对比,结果验证了破坏重建算法的优势;利用公开数据和真实数据,与全局方式破坏重建车辆调度方法进行对比实验,结果验证了局部搜索动态调度方法的有效性。

Objectives:With the rapid development of the Chinese economy,logistics distribution has put forward higher requirements on the real-time performance of vehicle scheduling and the ability to deal with emergencies.As traditional vehicle scheduling algorithms usually consider static scheduling tasks,it is difficult to deal with emergencies such as vehicle failure or adding new tasks in real-time.A local search of the dynamic scheduling method is proposed based on the ruin and recreate algorithm.Methods:When some vehicle breaks down or a new task is added,the location of the added task node or broken vehicle is obtained and all the nodes are found within a certain range around the location.Based on the initial solution,all the unfinished nodes are searched that are outside the range and on the same path with the nodes mentioned above.The two sets of nodes compose a collection of removal task nodes,which act as the input of the ruin and recreate algorithm to generate new vehicle routes.Results:To demonstrate the performance of the proposed method,three experiments are designed and conducted:(1)The data in the Solomon benchmark examples are used in the static scheduling experiment,which is divided into 9 C-type(clustered customers)and 8 R-type(uniformly distributed customers)datasets.The multi-objective hybrid ant colony optimization algorithm is employed as the reference method.Results on the Solomon benchmark datasets show that ruin and recreate algorithm outperforms the reference method with respect to distance cost and the number of vehicles in 14 of 17 datasets.(2)The second experiment is a dynamic scheduling test,and it uses Lackner.s benchmark datasets that can be used to demonstrate five different dynamic degrees of 10%,30%,50%,70%,and 90%.The test data contains 240 sub-datasets and is divided into four groups:C1,C2,R1,and R2.In this experiment,the ruin and recreate algorithm is employed as the reference method.Results show that the local search algorithm proposed in this paper outperforms the ruin and recreate algorithm in terms of vehicle usage and driving distance on C2 and R1 datasets,but the ruin and recreate algorithm performs better than the proposed method on C1 dataset.For the R2 dataset,the proposed method reduces the number of vehicles but increases the driving distance.(3)The third experiment is conducted on a real scheduling scenario dataset that contains 35 vehicles and 307 task nodes.Ruin and recreate algorithm is also employed as the reference method in this experiment.In the case of vehicle breakdowns,the proposed method changes 37.5%of vehicle routes while the reference method changes all the routes,and the performance of the proposed method is much better than that of the ruin and recreate algorithm with respect to program running time and driving distance cost.In the case of adding new tasks,the proposed method adjusts only 8.3%vehicle routes while the reference method changes 87.5%of routes.Conclusions:The proposed method performs much better than the reference method in terms of running time,but the proposed method costs an additional 0.5%driving distance than the reference method.From the above three experiments,it can be concluded that the ruin and recreate algorithm has advantages in terms of vehicle usages and driving distance for the static scheduling tasks,and for the dynamic scheduling scenario that has a lot of distribution task nodes,the proposed method can solve small-scale dynamic vehicle routing problem within a very short time and with minor route adjustments.