Research On Traveling Salesman Problem With Drones And Its Intelligent Optimization Algorithm

With the continuous development and maturity of drone technology,drones are widely used in the logistics industry,especially in the field of "last mile" logistics and distribution.With the addition of drones,truck-drone hybrid distribution has become a common form of logistics distribution.It can comprehensively utilize the characteristics of drones such as high speed and the advantages of trucks such as large load capacity,thereby greatly improving the distribution capacity and efficiency.The key to truck-drone hybrid distribution is the truck-drone hybrid path optimization problem.The traveling salesman problem with drones(TSP-D)is a typical truck-drone hybrid path optimization problem.This thesis studies the parallel drone scheduling traveling salesman problem(PDSTSP)and the flying sidekick traveling salesman problem(FSTSP).Based on the problem modeling and property analysis of these TSP-D,two intelligent optimization algorithms are designed,and the effectiveness of the algorithms is verified by computational experiments.The main contents of this thesis are listed below.(1)The research background and significance of TSP-D are introduced.The research status of PDSTSP and FSTSP at home and abroad and the application of intelligent optimization algorithms in routing problem with drones are summarized.(2)An improved variable neighborhood search(IVNS)is proposed for PDSTSP with the goal of minimizing delivery completion time.The algorithm adopts a multistring encoding method,and uses the basic variable neighborhood search(BVNS)and reduced variable neighborhood search(RVNS)to optimize truck routing and drone scheduling,respectively.Three initialization methods based on the longest processing time,BVNS and RVNS are proposed,and an adaptive RVNS is used to adjust the customer assignments between the truck and drones.Extensive computational experiments show that IVNS is very competitive in solving PDSTSP.(3)For the FSTSP with synchronization constraints of a truck and a drone,a mathematical model aiming at minimizing the total operational cost is constructed,and a hybrid immune algorithm(HIA)is proposed.In order to increase the search speed,the BVNS combined with 2-opt is used to initialize the population,and a general variable neighborhood search(GVNS)is used to improve the memory cells.Randomized variable neighborhood descent is used as the local search method for GVNS,which applies a random neighborhood order.Experimental results show that HIA outperforms existing comparison algorithms.