卡车-无人机-调度车协同模式下的应急物资调度:增强型 NSGA-II 优化框架

论文摘要

本研究针对突发灾害情况下的应急物资配送，提出了卡车–无人机–调度车协同多目标路径规划模型（Vehicle Routing Problem with Dispatch vehicle and Drones，VRPDD）。该模型扩展了传统的卡车–无人机协同配送模式，在路况受限的受灾点附近引入“调度车”运载无人机，与卡车协同完成多段配送任务。模型以最小化受灾点等待时间和总配送成本为双目标，通过混合整数线性规划建模，并考虑了受灾点能否被卡车到达、无人机载重与航程限制等约束。为求解这一NP‑难问题，作者设计了增强型双种群 NSGA‑II（Enhanced Dual‑Population NSGA‑II，EDPNSGA‑II）算法，综合采用改进选择算子、局部搜索和精英种群机制，提升了种群多样性和收敛速度。论文通过随机实例对算法进行对比实验，并应用于四川省绵阳市地震应急案例，展示了所提模型与算法在实际应急调度中的有效性与可行性。

一、问题背景与模型设计

1.1 灾害应急配送难题

地震、洪灾等突发灾害往往导致道路受阻，传统卡车无法及时到达受灾点，严重影响救援效率。近年来，无人机因机动性强被用于应急配送，但仅使用无人机无法满足远距离或大载重需求。为解决道路受阻和远距离配送的矛盾，本文提出卡车–无人机–调度车协同的应急物流模式。调度车用于运载无人机到适宜的发射点，卡车则负责运送大件物资，两者配合完成受灾点的覆盖。

下图展示了传统卡车–无人机模式与新增调度车模式的区别。

1.2 模型基本概念与集合集合

• 受灾点集合：，其中根据道路条件分为可通行的受灾点  和只能由无人机服务的受灾点 。

• 运输载具：配送中心配备  辆卡车、调度车和无人机，各类载具具有固定运费和单位距离成本。

• 受灾点分类：

• 无路障受灾点 ()：可以被卡车直接服务，也可由无人机服务。
• 路障受灾点 ()：道路受损，只能由无人机服务。
• 超载或超距受灾点：需求超出无人机载重或距离超出航程，只能由卡车服务。

调度过程示意如图2：卡车先服务部分受灾点并送达无人机发射点，调度车运载无人机至发射点后，无人机完成路障点配送并返回调度车，最后调度车回到卡车或配送中心。

1.3 模型目标与约束

模型以最小化受灾点等待时间和最小化总成本为双目标。等待时间包括卡车服务的受灾点等待时间与无人机服务的受灾点等待时间；总成本包括卡车、调度车和无人机的行驶成本及固定使用成本。

为了便于理解，简化的目标函数形式如下：

• 目标1：最小化等待时间

  其中  和  分别表示第  次配送中卡车和无人机是否从节点  到节点 ， 为相应的行驶或飞行时间。

• 目标2：最小化总成本

其中  是单位距离成本， 是固定使用成本， 表示在第  次配送中是否启用卡车、调度车或无人机。

约束条件主要包括：各类车辆路径衔接约束、每个受灾点被一次服务、载重和航程限制、车辆出发和返回配送中心的顺序约束等。

二、数学求解与改进算法

2.1 编码方式与传统 NSGA‑II 问题

VRPDD 属于混合整数多目标优化问题，常规的 NSGA‑II 算法在求解大规模离散问题时容易陷入局部最优，且收敛效率不高。为此，作者对染色体结构进行了双链编码设计：一条链表示卡车与调度车服务的受灾点序列，另一条链表示无人机服务的受灾点序列及发射点位置，保证染色体既能描述车辆路线又能描述飞行任务。

2.2 加强型双种群 NSGA‑II（EDPNSGA‑II）

EDPNSGA‑II 在传统 NSGA‑II 基础上引入三项改进：

• 改进选择算子：融合拥挤距离与权重策略，同时考虑解的密度与目标权重，使选择阶段兼顾多样性与优良解的保留。
• 局部搜索算子：设计7种邻域操作，包括卡车/无人机之间受灾点的交换、插入和运输方式变换等，以增强解的局部搜索能力，提高跳出局部最优的概率。
• 精英双种群策略：在进化过程中构建两个种群。种群1通过常规交叉和变异生成后代；种群2不执行交叉和变异，而是基于种群1的 Pareto 前沿解生成邻域解。双种群独立演化，但相互补充：种群2在种群1的 Pareto 邻域中搜索更优解，提升了收敛速度和解的多样性。

EDPNSGA‑II 的流程可用下图表示。算法通过初始化双种群、快速非支配排序、局部搜索和精英策略循环迭代，最终输出 Pareto 前沿解集。

2.3 局部搜索策略详解

局部搜索是 EDPNSGA‑II 的核心。作者设计了如下 7 种算子：

• 交换算子 N1/N2/N3/N4：在不同子路径之间交换卡车服务点、无人机服务点或可双重服务点，以调整任务分配并提升多样性。
• 插入算子 N5：将一个受灾点从一条子路径插入到另一条子路径的任意位置。
• 改变算子 N6/N7：在子路径内改变受灾点的服务方式，将无人机服务点改为卡车服务或反之，从而探索不同的运输方案。

通过随机选择这些算子，算法在保持全局搜索的同时加强了局部探索能力。

三、实验设计与性能评估

3.1 实例生成与参数设置

由于缺乏公开的 VRPDD 数据集，作者参照文献生成了90个随机实例，分为小规模（）、中等规模（）和大规模（）三类。受灾点随机分布在不同面积的区域内，其中20%为路障点，其余80%为无路障点；部分无路障点由于需求或距离限制只能由卡车服务。

算法参数统一设置：交叉概率，变异概率，种群规模，迭代次数根据问题规模取200或300；双种群策略的邻域概率参数选择1.0，对算法性能最优。

3.2 性能对比与统计分析

作者将 EDPNSGA‑II 与传统 NSGA‑II 及其三个单改进版本（改进选择算子、局部搜索、双种群）进行比较。采用非劣解数量(QP)、收敛性指标(GD)、覆盖指标(CS)、超体积(HV)等多项指标评估。实验结果表明：

• 改进选择算子显著提升非劣解数量和算法效率，中规模实例平均非劣解数从6.28提升至24.14，且计算时间更短。
• 局部搜索算子提升了收敛精度，GD和IGD指标明显优于传统 NSGA‑II，特别是在大规模实例中能找到更多极值解。
• 双种群策略在中等规模实例中实现了较高的极值搜索能力，Pareto 前沿更均匀，证明双种群机制能在种群邻域内快速探索优良解。
• 综合算法 EDPNSGA‑II在所有指标上整体表现最佳，尤其在大规模实例上能获得更多、更均匀分布的 Pareto 解，但计算时间相对略长。

四、案例分析：四川地震应急调度

4.1 案例背景与数据

论文选取2008年汶川地震后绵阳市73个乡镇的应急配送作为案例。根据灾区道路状况，将受灾点分为可通行和不可通行两类。以一个配送中心为出发点，利用 EDPNSGA‑II 求解多目标路径规划。

4.2 结果分析与路线展示

在300个体、2000次迭代的条件下，算法得到72个非劣解，通过熵权法从中选出最优方案，其等待时间和成本分别为6471.16s和2456.99元。下图展示了该非劣解方案的运输路线：蓝色虚线为卡车路线，红色虚线为无人机飞行路线，黑色为调度车路线。

从结果可见，调度车作为无人机的移动发射平台，使无人机能够到达远距离路障点，而卡车则通过多次卸货为无人机补给，三者协同显著缩短等待时间。熵权法分析显示，等待时间目标的熵权较大，说明该目标在优化中占主导地位；尽管成本目标权重较低，但仍需在预算约束内控制总成本。

4.3 管理启示

论文对比例敏感性进行了扩展分析，指出随着路障受灾点比例增加，平均等待时间下降45.10%，但总成本增加32.29%；提高无人机速度可显著缩短等待时间，超出某一速度阈值后则对成本影响有限。这些结果提示救灾决策者应根据灾情严重程度、预算和设备条件灵活调整无人机覆盖范围和速度。

五、创新点与研究贡献

• 提出 VRPDD 模型：首次将调度车引入卡车–无人机协同配送，在数学上建立了包含卡车、无人机和调度车的多段路径规划模型，可处理远距离或路障情况下的物资配送。
• 双目标优化：同时考虑等待时间与成本，满足快速救灾和成本控制双重需求；采用混合整数线性规划准确建模。
• 增强型双种群 NSGA‑II：综合改进选择算子、局部搜索和精英双种群策略，大幅提升了种群多样性和收敛性能，适用于大规模多目标组合优化。
• 实践验证：通过90个随机实例和四川地震实证案例验证模型与算法的有效性，为未来灾害应急调度提供了可操作的方法和决策依据。

六、总结

本文围绕应急物资配送在道路受阻和资源受限条件下的困难，提出了卡车–无人机–调度车协同的多目标路径规划模型，并设计了增强型双种群 NSGA‑II 算法。研究表明，模型兼顾等待时间和成本，实现了高效、经济的应急调度；算法利用改进选择、局部搜索和双种群策略，显著提升了解空间探索能力和解集质量。四川地震案例进一步证明了该方法在真实场景中的适用性和优势。未来研究可在考虑多配送中心、动态需求和不确定因素下进一步扩展该模型，为灾害救援提供更全面的决策支持。