The Time-varying Road Networks Traveling Salesman Problem With Multiple Drones

During the COVID-19,all industries suffered a huge impact,and the logistics industry could not be left alone.But at the same time,logistics became more indispensable,not only to play the role of distribution of materials,but also to ensure the normal operation of the social economy,to ensure the basic needs of people’s "stabilizer".With the rapid development of society and the rapid growth of people’s needs,the traditional logistics distribution method has been difficult to meet the growing needs of people,and it is imperative to change the traditional distribution method.Therefore,based on the traditional truck distribution method,this paper adds drones to the truck distribution network to take up part of the parcel distribution to meet the social demand.This paper explores the time-varying road networks Traveling Salesman Problem with multiple drones(The Time-varying Road Networks Traveling Salesman Problem with Multiple Drones,TVRNTSP-MD),by which a truck and multiple heterogeneous UAVs work together to A segmentation function of the passage time is designed to reflect the traffic congestion,and a mixed integer programming model(MILP)with the objective of minimizing the delivery completion time is developed to solve the optimal delivery path for the truck and the UAV.In terms of the algorithm for solving the problem,the TVRNTSP-MD heuristic algorithm is designed in this paper.The TVRNTSP-MD heuristic algorithm is divided into three stages:(1)the customers are assigned into truck customers and UAV customers to generate the initial truck TSP routes;(2)the flight sorties of each UAV are determined;and(3)a new model is built.The detailed schedule of truck and drone activities,including the sequence of drone launch,recovery,and execution of service activities on the truck,is determined by solving for the truck and drone delivery times.Finally,the solutions obtained by Gurobi and TVRNTSP-MD heuristic algorithms are compared through case experiments,and it is verified that the TVRNTSP-MD heuristic algorithm has good solving effect.At the same time,this paper makes a sensitivity analysis of the main factors such as the distribution mode,the relevant parameters of the UAV,and the time-varying road network.Finally,the following conclusions are drawn:(1)truck-carrying drone delivery can save a lot of delivery time than the traditional mode of delivery by truck alone,and the percentage of delivery completion time improvement increases with the increase of customer size;(2)the number of drones is negatively correlated with the total delivery time,i.e.,the more the number of drones,the less the total delivery time,which is consistent with common sense,but with the further(3)Considering the time-varying nature can better reflect the current traffic conditions than using the average speed,which makes the final actual delivery completion time better optimized.Figures 27;Tables 18;References 70...