多卡车多无人机灵活协同路径问题优化方法

Optimization approach for multiple trucks and drones flexible collaboration routing problem

关键词:  无人机运输  卡车无人机协同  车辆路径问题  MILP  AHNS

Key words:  drone delivery  truck-drone collaboration  vehicle routing problem  mixed integer linear programming (MILP)  adaptative hybrid neighborhood search (AHNS)

摘要:

为提高配送运输的效率,降低综合成本,针对卡车无人机灵活协同路径问题设计优化方法。首先,综合多卡车多无人机灵活协同和无人机连续运输的特点,以最小化运营成本与客户等待成本为目标,构建混合整数线性规划（mixed integer linear programming,MILP）模型。其次,设计两阶段启发式求解框架,在两个阶段分别优化无人机和卡车路径。最后,结合破坏算子、修复算子和k-opt算子构造混合邻域,提出自适应混合邻域搜索（adaptative hybrid neighborhood search,AHNS)算法进行每个阶段的优化。在Solomon数据集上进行数值实验,结果表明:相较于CPLEX求解器,所提方法可以在短时间内获取质量较高的满意解；相较于迭代局部搜索算法、变邻域搜索算法和蚁群算法,所提方法的求解质量在小、中和大规模算例中分别平均提高了5.49%、6.88%和27.82%；与纯卡车运输模式相比,卡车无人机协同运输模式更适合小、中规模场景的作业,可以降低4.70%~8.56%的综合成本。研究结果可为卡车无人机联合运输实践提供理论基础。

Abstract:

To improve transportation efficiency and reduce total costs, an optimization approach is adopted to address truck-drone flexible collaboration routing problem. Firstly, a mixed integer linear programming model with the goal of minimizing the operation cost and customer waiting cost is formulated, combining the characteristics of multiple-truck-drone flexible collaboration and drone continuous delivery. Secondly, a two-stage heuristic solution framework is designed to optimize the routes of drones and trucks respectively in two stages. Finally, a tailored adaptive hybrid neighborhood search algorithm based on destroy operator, repair operator and k-opt operator is proposed for routing in each stage. The Solomon dataset is selected for numerical experiments, and the results show that: compared with CPLEX solver, the proposed method can obtain satisfactory solutions with higher quality in a short time. Compared with iterative local search, variable neighborhood search and ant colony optimization algorithm, the solution quality of the proposed method is improved by 5.49%, 6.88% and 27.82% in small-, medium- and large-scale instances, respectively. Compared to pure truck transportation mode, the truck-drone collaborative transportation mode is more suitable for small- and medium-scale operations, achieving a 4.70% to 8.56% reduction in overall costs. The research results can provide theoretical basis for the practice of truck-drone collaborative transportation.