考虑多投递的带无人机车辆路径规划问题研究

摘要

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

关键词