关键词: 农村物流, 卡车和无人机联合配送, 路径优化, 自适应大邻域搜索算法

Abstract: The emergence of logistics drones provides a new way to solve the problems with rural e-commerce logistics, such as scattered demand points, road network limitation, and high terminal delivery costs. However, the terminal delivery by drones is limited by the cruising range and load capacity, which restricts its wide-scale application. In order to expand the service scope of logistics drones and reduce the cost of terminal distribution, the joint distribution mode of trucks and drones is a brand new attempt. This paper studies a Travel Salesman Problem with multi-Drones (TSP-mD), in which a truck with several drones is required to visit a set of customers. The truck starts from a depot and back to the depot after all customers are visited by the truck or a drone once. This study is of great significance for reducing the cost and improving the efficiency while applying to the rural logistics scenario.
   Considering the mutual waiting cost of trucks and drones, this paper establishes a joint delivery route optimization model for single-truck and multi-drone with the goal of minimum total cost. According to the characteristics of the model, an adaptive large-neighborhood search algorithm is designed. Three damage operators and repair operators are used, and the simulated annealing acceptance criterion is used for the temporary solutions after damage and repair. Based on the proposed algorithm, two types of instances (9 under each type) including 10-100 nodes with uniform distribution and cluster distribution are solved. The comparison with the CPLEX solution results indicates that the proposed algorithm has faster speed, better accuracy and stability. Through the analysis of the joint delivery scheme of trucks carrying different numbers of drones, the results show that the delivery scheme of truck carrying 0 drones (pure truck delivery) and the joint delivery of truck carrying 1-4 drones can reduce the total rural e-commerce terminal delivery cost by 17.88%~28.89%, and can improve the delivery efficiency. Finally, the sensitivity analysis of the cruising range of the drones shows that with an increase in the cruising range, the delivery cost decreases first rapidly and then slowly or tends to be stable.
   For future research, the time window constraint would be considered, and the influence of factors such as load constraint, geographical conditions, weather impact, fixed cost of carrier and personnel cost would be taken into account. Besides, the joint distribution mode of multiple trucks and multiple drones is a promising research direction to further improve the distribution efficiency.

Key words: rural e-commerce logistics, joint delivery of trucks and drones, route optimization, adaptive large neighbourhood search algorithm