Algorithm Design And System Implementation For Dynamic Vehicle Routing Problem

Vehicle routing problem is a combinatorial optimization problem of organizing appropriate routes for a series of nodes, and it is widely used in logistics areas. With the development of technology and the improvement of people’s living standard, the logistics distribution in real life requires that it can receive and deal with the new customers, and the delivery drivers have fixed working time interval. Therefore, the study of the dynamic vehicle routing problem with time deadline is a real need.For the actual situation of current logistics distribution, this subject studies the dynamic vehicle routing problem with time deadline, and designs a selecting strategy for starting nodes and a hybrid large neighborhood searching algorithm.This algorithm introduces the periodic optimization strategy to divide the working time interval into multiple equal time slices, and at the end of each time slice, it uses an insert algorithm which is based on neighborhood analysis to deal with the new customers. Meanwhile, it selects the effective starting nodes to form the current static sub-problems. For them, it establishes a mathematical model for the optimization of the total distances of vehicles, and uses a large neighborhood searching algorithm for optimization which is based on three removal strategies and random greedy re-insertion strategy. This subject runs the static and the dynamic simulation experiments on 22 data sets ranging from 50 up to 385 customers respectively. And in the 10 static experiments, the average relative errors of all the data sets’ target values obtained by this algorithm are 3.11% by comparing with the current optimal results, and there are more than 80% data sets whose relative errors of target values are lower than 5%. By combining the position distribution of customers, it concludes that this algorithm has a good performance on solving the customers with aggregation distribution. In the 5 dynamic experiments, the optimal results, the average results and the variances obtained by this algorithm are compared with the optimal ones, the average ones and the variances obtained by genetic algorithm GA, respectively. There are 13 data sets whose optimal results are better than GA, 10 data sets whose average results are better than GA, and 11 data sets whose variances are lower than GA. By comprehensive comparison of the sum of the optimal values, the average values and the variances of 22 results, it can be drawn that the algorithm designed by this subject has an effective competitiveness in obtaining the optimal value and stability of algorithm.This subject also designs a logistics distribution system based on the hybrid large neighborhood searching algorithm. It realizes the function of PC client and android client by combining with Web GIS technology, Baidu map API, Java Script,PHP and Java. The PC client is mainly used to collect customers’ information,receive feedback, plan distribution routes and display them on Baidu map; the android client is mainly used to provide the distribution scheme and feedback operation for the drivers.