The Time Dependent Traveling Salesman Problem With Drone

In recent years,population growth and urbanization,e-commerce growth and the desire for prompt delivery bring many opportunities and challenges to urban logistics.Moreover,the research production of drones used in logistics and distribution are constantly emerging,and the joint distribution mode of vehicles and drones is one of the most promising research directions.Therefore,it is of great theoretical and practical significance to study the urban logistics distribution problem based on the joint distribution mode of vehicles and drones.This paper studies the time dependent traveling salesman problem with drone(TDTSPD).Based on the joint distribution mode of a vehicle and a drone,this paper considers to optimally schedule the route of vehicle and drone under temporal-dependent and spatial-dependent traffic congestion level,in order to minimize distribution complete time.A mixed integer linear programming model is built for this problem.In terms of solving methods,the exact algorithm and the heuristic algorithm are used to solve the small-scale and large-scale problems respectively.For small-scale problems,four valid inequalities are proposed to strengthen the model and a branch-and-cut algorithm is developed.For large-scale problems,two heuristic algorithms are adopted.The first one is the TDTSPD-LS algorithm,which is modified based on the heuristic algorithm proposed for the TSPD problem,so that it can be applied to the problems studied in this paper.Another one is the AGVNS algorithm,which consists of initial solution construction stage and solution improvement stage,wherein the solution improvement stage is based on the AVNS algorithm.The adaptive mechanism of the AVNS algorithm can evaluate each local search strategy according to the historical information during the search process,thereby adaptively adjusting the local search strategy used in each iteration.Based on numerical experiments,the effectiveness of the branch-and-cut algorithm on small-scale problems is verified by comparing with CPLEX.Meanwhile,the impact of the joint distribution mode of vehicle and drone,the effects of changes in the parameters of drones and the influence of time-dependent are analyzed.In addition,the parameters of the two heuristic algorithms are analyzed,and the optimal parameter combinations of the two algorithms are obtained.Finally,two heuristic algorithms are used to solve both small-scale and large-scale instances,and their performance are evaluated and compared.The numerical experiments show that: 1)both heuristic algorithms can quickly find high quality feasible solution of the problem in a short time;2)the AGVNS algorithm gives higher solution quality than the TDTSPD-LS algorithm,with an average improvement of nearly 10%,and can reach the global optimal solution for small-scale problems.