Research On Routing Optimization Model And Algorithm For Collaborative Delivery Of Trucks And Drones

With the rapid development of aviation technology and continuous breakthroughs in information technology,drone technology has become increasingly mature.Drones are widely used in various fields of the national economy because they have the advantages of low manufacturing cost,no personnel manipulation,flexible deployment,and can meet the needs of enterprises to reduce costs and increase efficiency.In the field of logistics,the traditional truck delivery mode can alleviate the impact of the ground road network on logistics delivery by introducing drones,improve the delivery efficiency of logistics enterprises,reduce delivery costs,and promote the high-quality development of China’s modern logistics system.However,drones also have their limitations in the delivery process.For example,they cannot deliver goods from a long distance due to the limitation of battery capacity,and the weight of goods they can carry is small.In addition,in different delivery scenarios,the functions undertaken by trucks will change,so the collaborative delivery mode of trucks and drones is also different.The limitations of drones and the variability of delivery scenarios have brought challenges to routing optimization under the collaborative delivery mode of trucks and drones.On the one hand,for the urban terminal delivery scenario that only contains small goods,most of the existing studies are based on the constraint that drones can only deliver a single customer in a single trip,without fully exploiting the potential of drones to deliver multiple customers in a single trip.On the other hand,for the urban terminal delivery scenario that contains large goods,the existing research mainly focuses on the economy of the collaborative delivery route of trucks and drones,ignoring the impact of delivery on the urban environment.Based on the above analysis,in view of the two different delivery scenarios faced by logistics enterprises(i.e.,urban terminal delivery scenario containing small goods and urban terminal delivery scenario containing large goods),first,according to the different functions of trucks in the collaborative mode,this study constructs the routing optimization models under the two collaborative delivery modes of "drone-based-and-truck-assisted" and "truck-based-and-drone-assisted".Secondly,efficient algorithms for solving two models are proposed.The innovations of this study are as follows:(1)This study proposed a routing optimization model based on the collaborative delivery mode of "drone-based-and-truck-assisted",which considers that trucks only carry drones,and takes drones as the only means of small commodity delivery,so as to apply to the urban delivery scenario that only contains small goods.This model allows drones to serve multiple customers in a single trip to tap their delivery potential,thereby improving delivery efficiency.At the same time,the delivery routes of multiple drones and the parking routes of trucks are optimized to obtain the routing scheme with the minimum total delivery cost.On this basis,an extended Variable Neighborhood Search(VNS)Algorithm is proposed to solve the proposed model efficiently.The improvement idea of the extended algorithm is: integrating 3D route coding in the basic VNS algorithm,and introducing an improved neighborhood search operator and tabu list to improve the performance of the algorithm.(2)This study proposed a routing optimization model based on the collaborative delivery mode of "truck-based-and-drone-assisted",which considers the dual functions of trucks carrying drones and delivering large goods,so as to apply to the urban delivery scenario with large goods.Considering that the flight duration of drones is affected by the weight of goods loaded,this study optimized the collaborative route from the perspective of environmental impact and economic benefits to obtain the optimal Pareto solution.On this basis,an extended Non-dominated Sorting Genetic Algorithm-Ⅱ(NSGA-Ⅱ)is proposed in this paper to solve the proposed model more efficiently.The improvement idea of the extended algorithm is to integrate the giant route coding and novel decoding algorithm,and introduce multiple crossover and mutation operators and a multi-directional local search strategy to improve the performance of the algorithm.In summary,the research on the routing optimization model and algorithm for collaborative delivery of trucks and drones carried out in this study has important theoretical value and practical significance for enriching the application scenarios of drones in the logistics field,improving the delivery efficiency of enterprises,and promoting the transformation and upgrading of China’s logistics system towards modernization and intelligence.