Research On TSP-D Optimization Algorithm Based On Drone And Distribution Vehicle

In the field of logistics delivery,traditional single delivery vehicle delivery has high delivery costs,low efficiency,high delays,environmental pollution and other problems.As drones receive more and more attention in the logistics field,a new delivery concept has been proposed--drones combined with delivery vehicles to collaboratively deliver parcels,which has led to the discussion of the “Travelling Salesman Problem with Drone(TSP-D)”.In this paper,we study the joint path planning of drone and delivery vehicle and the path optimization algorithm problem with the problem objective of minimizing delivery time for this new delivery method.Firstly,the joint delivery problem model of drone delivery vehicles was developed by studying the traditional Travelling Salesman Problem(TSP)model,on which the joint delivery problem model was developed.The problem hypothesis is formulated and a mathematical model for mixed integer programming is developed,taking into account the drone and system constraints;secondly,a new optimal iterative algorithm is proposed to plan the joint path for the synergistic characteristics between the drone and the delivery vehicle in the problem and the constraints.The algorithm idea is to divide the problem into two steps,the first step determines the distribution vehicle path and customer node assignment,the second step fixes the distribution vehicle path and drone node,and determines the convergence node of the two to generate the drone distribution path.The drone paths and the corresponding delivery vehicle paths that satisfy the constraints are retained,and the total joint delivery time is solved.In this way,the problem is solved by updating the global upper bound starting from the least delivery vehicle node iteratively;then,the solution is improved by using the simulated annealing algorithm;finally,The problem of 10 and 11 node size was experimented in both uniform and aggregated cases,and the results showed that the optimal solution of the problem of 10 to 11 node size could be obtained within a reasonable time frame of about 20 min,and the proposed algorithm reduced the search size and the running time of the program to some extent.The analysis of the experimental results shows that the solution quality is better in the aggregation case,that means that the algorithm is more advantageous when the customer nodes are more densely distributed;increasing the speed of the drone can improve the solution quality and efficiency;there is no positive relationship between the number of nodes assigned to the drone and the solution quality;by comparing the TSP solution with the TSP-D solution under the same problem size,it is proved that the integration of the drone into the traditional single-delivery vehicle delivery model can improve the solution quality and efficiency.By comparing the TSP solution with the TSP-D solution for the same problem size,it is proved that the integration of drone into the traditional single-truck distribution mode can improve the distribution efficiency and save the overall cost of the traditional logistics system to a certain extent,and has practical application value.