研究背景

无人机在物流配送中的应用正快速扩展。与传统地面运输相比，无人机可从起点直飞目的地，绕开交通拥堵和地理障碍，大幅缩短运输时间。在医疗物资和紧急救援场景中，无人机的时效优势尤为关键。此外，电动无人机零排放的特性使其在碳减排方面具有积极意义，运营成本也因无需驾驶员而显著降低。

业界已有规模化实践：Wing自2022年起在美国提供无人机配送服务，最大载荷1.5公斤、航程10公里；亚马逊同期启动无人机配送计划；韩国Pablo Air与便利店合作开展无人机商品配送。然而，随着货运需求增长和品类多样化，单一机型机队逐渐难以满足差异化服务要求。引入混合机型机队，根据配送距离和货物重量为订单分配合适的无人机类型，已成为提升运营效率和灵活性的现实选择，但这也显著增加了调度决策的复杂度。

已有文献中，纯无人机机队研究多假设单一机型（如Pachayappan和Sundarakani、Yan等人），未明确评估机型与包裹的匹配性。混合机型研究（如Liu等人、Jiang等人）虽然出现，但较少同时考虑订单放弃策略和服务延迟阈值设计。本研究在此基础上，将电池约束、变动货物重量对成本的影响、订单放弃和延迟惩罚一体纳入模型，构成了更完整的混合机型规划框架。

核心问题

本研究从物流运营商的视角出发，解决以下规划问题：在每日运营开始前，给定次日所有预约订单的起止站点、货物重量和服务时间窗（STW），运营商需要为混合机型机队——包含载荷10公斤、时速54公里的A型无人机（38架）和载荷20公斤、时速30公里的B型无人机（7架）——制定最优的配送路径和时间表，目标是最小化总运营成本。

运营约束包括：无人机每日从满电状态出发，电池电量不得低于20%下限，可在任一服务站更换电池；订单可在服务时间窗截止后的15分钟延迟窗口（DSTW）内完成，但需支付延迟惩罚；运营商有权放弃订单，但需承担更高的放弃惩罚。这两种策略成本反映了服务水平下降带来的经济代价。

模型框架

模型采用网络流建模方法，将每架无人机的日度配送过程构建为一层网络。纵轴为连续时间（9小时、37个时间点），横轴为38个服务站位置。网络由节点和弧两类元素构成：节点包括出发节点（源点，电量100%）、服务节点（特定时间与位置的转运节点）和收集节点（汇点，表示当日服务结束）。

混合型无人机网络结构。每层代表一架无人机的配送时间表，网络包含45层（A型38层、B型7层），节点表示无人机状态，弧表示无人机移动。图中标注了订单1的服务时间窗（8:00-9:00）和延迟窗口（9:00-9:15），弧a表示延迟服务。取自Fig.1。

弧代表无人机的移动活动，分为五类：服务弧（携带货物从起点到目的地的配送）、渡运弧（空载移动至下一位置）、电池交换弧（更换电池，耗时一个时间间隔）、停留弧（在站点空闲等待）和收集弧（结束当日服务）。每类弧的成本构成包括电力消耗、无人机折旧、电池折旧和维护费用，服务弧还额外包含延迟惩罚。

相关研究对比。本研究是唯一同时覆盖混合机型、服务时间窗、电池换电、包裹重量、订单放弃和服务延迟六个维度的研究。取自Table 1。

数学规划模型以最小化总运营成本为目标函数，包含三类成本项：A型无人机运营成本、B型无人机运营成本和订单放弃惩罚。约束条件涵盖：网络流守恒（每层每节点流量平衡）、电池电量递推（到达节点的剩余电量不超过出发节点电量减去路径耗电）、出发节点满电、运行电量上下界约束，以及每笔订单必须被服务或被放弃的互斥约束。模型属于带边约束的混合整数网络流问题，归类为NP-hard。该模型最终包含360,568个变量和655,956个约束（基例），问题规模庞大。

求解算法

面对大规模NP-hard问题，直接使用CPLEX等通用求解器难以在合理时间内获得满意解。本研究基于拉格朗日松弛方法设计了一套上下界求解算法。核心思路是将数量最多的电量约束（式4、5）松弛为罚项并入目标函数，将原问题分解为三个独立子问题求解，再用次梯度法或直接取线性规划对偶变量值作为最优拉格朗日乘子。此前Yan（1996）已证明，线性松弛问题的最优对偶变量可直接用作最优拉格朗日乘子，本研究的数值实验也验证了该性质。

模拟路径示意。当上界算法第二阶段的松弛解中出现两条平行弧（如停留弧和电池交换弧），可将二者合并视为一条有效弧，通过将停留弧流固定为0、电池交换弧流固定为1来修正为可行解。取自Fig.3。

案例验证与结果

案例基于真实物流企业数据构建，辅以合理假设。基例包含240笔订单（200笔≤10公斤、40笔>10公斤）、45架无人机（38架A型、7架B型）、38个服务站，运营时段8:00-17:00。CPLEX在86,400秒（24小时）内得到目标值NTD 30,641.8，最优性间隙3.16%。而拉格朗日松弛算法仅用12.28秒即得到目标值NTD 30,652.5，下界为NTD 29,670.5（算法间隙3.3%），所有订单均被完成。

在算法性能评估中，研究设计了6种订单量场景（200至300单）。当订单量不超过基例时，算法在Phase 1即终止，求解时间不超过20秒，目标值与CPLEX的差异在±0.08%以内。当订单量超过260单时，算法进入Phase 2，效率优势更加突出：场景6中算法目标值NTD 39,809.4，仅为CPLEX目标值（NTD 1,026,294.3）的3.9%，时间缩短98.4%。

算法性能评估结果。场景4-6中算法目标值较CPLEX降低超过90%，体现了大规模实例下的求解优势。取自Table 6。

为进一步验证鲁棒性，研究在三个关键因素上各随机生成15个测试实例（共45个）：需求地理分布（距离区间比例随机扰动±20%至±100%）、服务时间窗松紧度（各时段订单量随机变动±20%）、订单类型比例（B型订单数量随机变动±30%）。算法在所有45个实例上均保持1.0%至3.9%的间隙，平均间隙2.54%，平均求解时间14.59秒。这些结果表明算法在不同运营条件下均能稳定高效地给出近似最优方案。

灵敏度分析

研究进一步从订单量、电量上界、功耗和延迟惩罚四个维度开展了灵敏度分析，揭示了影响运营成本的关键参数。

订单量灵敏度分析。当前运力可承受约20%的需求增长；+30%时出现订单放弃，且模型偏好放弃B型订单，提示运营商在扩编机队时应优先增加B型无人机。取自Table 8。

值得关注的是电量上界和功耗的非对称影响。电量衰减20%导致成本暴增23倍以上，而功耗降低50%仅节省2.17%的成本——成本的上升弹性远大于下降弹性。随着无人机电池在使用中逐渐老化，运营商需要将电池健康状态作为日常调度的核心监控指标。此外，延迟惩罚在2倍以上时对调度方案不再产生边际影响，说明适度的惩罚阈值即足以约束延迟行为。

结论与管理启示

本研究针对混合型无人机配送场景，构建了综合考虑电池约束、服务时间窗、订单放弃和延迟策略的网络流数学规划模型，并设计了高效的拉格朗日松弛求解算法。案例验证表明，算法在12秒内即可获得与商业求解器24小时运算相差仅0.03%的近似最优解，在51个测试实例中平均间隙2.73%，平均求解时间46.27秒，展现出良好的实用性和鲁棒性。

管理启示可归纳为四点。第一，当前45架机队运力可满足最多20%的需求增长，超出后需优先扩充B型无人机，因为模型在运力紧张时倾向于放弃重型订单。第二，电池容量衰减和功耗上升对运营成本的影响具有非对称放大效应，运营商应将电池健康度纳入日常监控，并及时更换老化电池。第三，算法的高效性使运营商能够在执行前对不同的延迟惩罚政策进行多情景模拟，选择兼顾成本与服务水平的最优策略。第四，延迟惩罚设置在2倍于基础弧成本时即足以消除不必要的延迟行为，继续加大惩罚不再产生额外约束效果。

本研究也存在若干局限。由于混合机型纯无人机配送路径调度问题尚属新颖，缺乏可直接对标的基准方法。未来可在拉格朗日松弛框架内引入禁忌搜索、阈值接受、蚁群优化等元启发式方法进一步缩小算法间隙；也可尝试将拉格朗日松弛嵌入分支定界框架的反向算法设计；还可扩展至实时动态调度场景，应对无人机故障或需求突变的非确定性环境。

服务站位置分布。案例包含38个服务站，构成无人机配送网络的空间基础，订单的起止站点在此网络内分布。取自Fig.4。