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.