Abstract: This paper addresses the Vehicle Routing Problem with Drones Considering Multi-Delivery(VRPD-MD).A mixed integer programming model uses the shortest total travel time of trucks performing tasks as the objective function. To solve the model, this paper proposes an Adaptive Algorithm Based on Genetic Method(AAGM), in which two types of neighborhood search operators, anaccess node crossover and intersection node mutation operator, are designed to adjust the combination point of a truck and drone with the parallel-path access point of the truck and drone, respectively. In addition, the operator adaptive selection and inferior solution acceptance mechanisms based on Metropolis rules are added to the algorithm to avoid falling into local optimization, accelerate the algorithm convergence speed, and improve the AAGM performance.The model and algorithm are verified based on the modified CVRP dataset.The results show that the drone delivery mode with multiple trips and deliveries has more advantages.AAGM can effectively solve the VRPD-MD, compared with NAAGM algorithm, the adaptive mechanism improves the average solution time and quality by 30% and 1.83%, respectively.

Key words: vehicle and drone coordination, path planning, adaptive genetic algorithm, drone deliver for multi-customer, vehicle-mounted drone

摘要： 研究一种考虑多投递的带无人机车辆路径规划问题（VRPD-MD），针对该问题，以执行任务车辆行驶总时间最短为目标函数，建立混合整数规划模型。为对该模型进行求解，提出一种基于遗传思想的自适应启发式算法AAGM，在该算法中，设计访问节点交叉算子和交会节点变异算子这两类邻域搜索算子，分别用于调整车辆与无人机的结合点以及车辆与无人机并行路径的访问点。此外，在AAGM算法中加入算子自适应选择机制与基于Metropolis规则的劣解接受机制，在避免算法陷入局部最优的同时加快模型收敛速度，提升算法的求解质量。基于改进的CVRP数据集对模型与算法进行验证，实验结果表明，多架次多投递的无人机配送模式较多架次单投递、单架次多投递模式更具优势，且AAGM算法能够有效求解VRPD-MD，相比NAAGM算法，增加自适应机制后的AAGM算法的平均求解时间与平均求解质量分别提高30%与1.83%。

关键词: 车机协同, 路径规划, 自适应遗传算法, 无人机多点配送, 车载无人机

CLC Number: 

• TP18