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

摘要： 车辆和无人机联合配送模式是降低末端配送成本、提高效率的全新尝试。本文考虑卡车和无人机相互等待成本,以最小总成本为目标建立了单卡车和多无人机联合配送路径优化模型。设计了自适应大邻域搜索算法,采用三种破坏算子和修复算子,对破坏、修复后的临时解使用模拟退火接受准则。对包含10-100个节点的呈均匀分布和簇状分布的2类算例进行求解,与CPLEX求解结果对比表明提出的算法具有较快的速度、较好的精度和稳定性;分析卡车携带不同数量无人机的联合配送方案,结果显示,相较于纯卡车配送,携带1-4台无人机的联合配送可降低农村物流配送总成本17.88%~28.94%;对无人机续航里程的敏感性分析,表明随无人机续航里程的增加配送成本呈先快速降低后缓慢降低或趋于稳定。

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