Abstract: Owing to the current situations of terminal distribution such as poor traffic conditions and low network coverage in rural areas, and the characteristics of cluster distribution in rural settlements, cluster-based truck and drone routing problem is proposed. Considering the cooperative mode between truck and drone as well as multipackage distribution of drone, a mixed integer programming model is established to minimize the comprehensive distribution cost, and a two-stage hybrid ant colony algorithm is proposed to jointly optimize the truck route and drone route. In the first stage, an improved adaptive ant colony algorithm based on 2-opt local search strategy is designed to calculate the truck path. In the second stage, the nearest clustering mechanism and ant colony algorithm are used to calculate the drone path, and the integrated solution of the truck and drone paths is obtained by combining the two stages. Finally, the feasibility of the built model and the effectiveness of the designed algorithm are verified by numerical examples. The proposed approach also provides decision-making reference and basis regarding cost reduction and efficiency increase of terminal logistics distribution in rural areas.

Key words: truck and drone collaborative distribution, vehicle routing problem, ant colony algorithm, local search

摘要： 针对农村地区末端配送道路通行条件差、网点覆盖率低等现状及乡村聚落集群分布的特点，提出基于集群的卡车和无人机路径问题。考虑卡车与无人机协同方式、无人机多包裹配送等约束，以最小化综合配送成本为目标建立混合整数规划模型，并提出了一个两阶段混合蚁群算法对卡车路径和无人机路径进行联合优化以实现问题求解：第一阶段设计基于2-opt局部搜索策略的改进自适应蚁群算法求解卡车路径，第二阶段借助就近聚类机制和蚁群算法求解无人机路径，综合两阶段求出卡车和无人机路径的综合方案。通过算例实验验证所建模型的可行性和设计算法的有效性，为实现农村地区末端物流配送降本增效提供决策参考和依据。

关键词: 卡车与无人机协同配送, 车辆路径问题, 蚁群算法, 局部搜索