同日配送中的无人机调度：基于马尔可夫决策过程的动态路径优化方法
一、研究背景与问题提出
随着电动无人机技术的成熟，同日配送成为满足城市快速配送需求的潜在方案。然而在实际运作中，无人机配送面临诸多不确定性：请求的随机到达、负载依赖的能耗、天气对飞行速度的影响以及有限的电池寿命等。这些因素导致传统静态路径规划方法难以适用于动态、不确定的配送环境。
本文关注的场景是一天中多个单品包裹同日递送服务，目标是利用一个由相同型号无人机组成的机队，在满足客户软时间窗的同时，尽可能多地完成配送并降低迟到和能耗成本。主要难点包括：
请求与能耗的不确定性：客户请求随机出现，且能耗受载重及风速等因素影响。 电池管理：无人机需要在多次飞行间更换电池，电池容量有限且换电需要时间。 动态决策：由于新请求不断到达，路线规划和无人机调度必须动态更新。 安全保障：需保证飞行过程中能量充足，避免因电量耗尽而半途返航。作者引入机会约束以确保以高概率满足能量安全阈值。
关键点
研究目标：制定动态的无人机调度策略，在随机需求和能耗不确定条件下，最大化服务客户数量并最小化配送距离和迟到惩罚。 建模方法：将问题刻画为马尔可夫决策过程（MDP），在每个决策时刻根据当前状态（时间、待服务请求、无人机与电池状态等）选择最优动作。 不确定性处理：采用近似动态规划（ADP）结合机会约束，保证能耗安全，并通过成本函数近似（CFA）设计高效策略。
二、模型建模与数学表述
1.1 状态与决策变量
研究将动态无人机配送表述为离散时间的MDP。在每个决策时期 ，系统处于前决策状态，包括：
时间； 两类请求集合：新出现的请求 与等待服务的请求 ； 无人机状态集：记录每架无人机已分配或执行的行程及其电池余量； 电池状态集：记录每块电池已使用的次数，保证电池消耗均衡。
动作集合 包括为待服务请求构造若干行程并分配给可用无人机，以及为返航无人机分配电池或安排充电的决策。
1.2 成本函数与目标
每个行程 由一系列节点组成，起止均为仓库 ，中间为客户点 。行程的成本由两部分构成：距离成本和迟到成本。论文定义行程的期望总成本为：
其中 为期望总飞行距离， 为期望总迟到时间； 和 分别是单位距离和单位迟到的成本权重。
整体目标是在规划期 内，根据随机需求生成适应性路线，最小化累积期望成本并最大化服务客户数。由于硬约束集中在电池能量与容量上，模型允许在软时间窗后服务客户，但迟到将纳入成本罚金。
1.3 能耗建模与机会约束
无人机飞行过程中每段弧的能耗与负载、飞行速度相关。该论文采用基于动力学推导的能耗函数，若无人机从节点 飞到节点 ，携带负载 且平均速度为 ，则单位距离能耗为：
其中 为两点间距离， 是无人机自重， 为重力加速度， 为空气密度， 与 分别为旋翼叶片面积和数量。由于环境风速随机导致速度和能耗随机，因此总能耗是随机变量。
为了保证飞行安全，作者通过机会约束要求行程总能耗 不超过电池可用能量下限 的概率至少为 ：
假设弧能耗服从正态分布且互相独立，机会约束可转化为确定型约束：
根据期望可加性，总期望能耗为所有弧期望能耗之和：
文中利用该等式在构造行程时计算每条路径的期望能耗与方差，并筛选满足约束的安全行程。
1.4 马尔可夫决策过程与动态规划
在MDP框架下，每个前决策状态 的价值函数满足贝尔曼最优性方程：
其中 表示在给定当前状态 和执行动作 后， 在随机外生信息 作用下转移到下一个决策状态 的概率分布； 表示所有可能的外生随机信息（exogenous information）结果集合。
由于状态空间巨大（时间、请求、无人机和电池状态组合）且未来请求未知，直接求解贝尔曼方程计算量极大，即所谓的“维数灾难”。为此作者采用近似动态规划方法，通过设计启发式策略近似价值函数。
三、解决方案：近似动态规划与策略设计
2.1 总体框架
作者将MDP的求解分为三层决策：
构造行程：针对等待服务的请求，根据不同策略构建若干候选行程，每个行程既考虑成本最小又满足机会约束。 选择行程并更新调度表：从候选行程集合中选择要执行的行程并插入相应无人机的调度表。 电池分配：返航的无人机进行电池更换或充电，保证电池均衡消耗。
算法通过近似动态规划（ADP）分两步执行：首先使用后决策状态法评估某个动作带来的未来价值；其次采用蒙特卡洛模拟从物理系统（或仿真）采样随机变量，从而更新策略。
2.2 行程构造：后向标记启发式
行程构造旨在从尚未服务的请求中生成一组可行且不被支配的行程集 。论文提出一种后向标记（backward labeling）算法：首先从终点（仓库）开始，向前逐步插入候选客户节点，确保每一步都满足载重限制和机会约束。关键思想包括：
两种节点排序策略：按距离排序最小化行程长度；按紧迫性排序优先满足早到期的请求，以减少迟到。 支配规则：若两个行程服务相同客户集，则期望能耗较大的行程被淘汰。 候选集合扩展：每次迭代从当前行程末端可插入的邻接节点中选择不超过 个作为扩展，并生成新行程；若无法进一步扩展，则将该行程加入非支配集合。
构造完成后，行程集 中既有距离导向行程也有紧迫性导向行程，为后续调度提供多样选择。
2.3 策略设计：成本函数近似 (CFA) 与策略函数近似 (PFA)
由于难以计算完整的价值函数，作者提出两种策略近似：
策略函数近似（PFA）：根据预定义规则构建行程并立即执行。例如PFA每次只处理最紧迫的请求，不会取消已建行程，执行后再插入新请求。PFA简单但不考虑未来未知请求，因此表现类似贪婪策略。 成本函数近似（CFA）：该策略在构建行程时限制每架无人机可分配的行程数量 ，以保留机队的调度灵活性。CFA通过计算行程成本 及其对未来成本的估计，选择期望成本最低的行程；同时在每个决策时段内使用短期预测时间窗 来评估已知请求的截止期限，从而兼顾当前服务与未来需求。
CFA主要包含以下步骤：
候选行程选择：对于现有请求集，根据距离和紧迫性构建两个行程集（最短距离和最小迟到）。根据当前时间窗选取可满足的行程。 行程分配：按成本从小到大选择行程，并根据无人机可用性和最大行程数量 约束，将行程插入无人机行程表；若无人机无法执行，则保留行程以备后续使用。 电池管理：返航后立刻更换电池；若没有充满电池，则无人机进入等待状态。
通过限制每架无人机的行程数量 和滞后时间窗 ，CFA在提升服务效率和保持调度灵活性之间取得平衡。
2.4 对比方法与基准
为验证策略有效性，作者设置了三类对比策略：
贪婪（myopic）策略：每个决策周期立即安排所有可行行程，并尽快执行，不考虑未来需求。 策略函数近似（PFA）策略：如上所述，采取简单规则直接构建行程。 “Oracle”策略：理想化基准，假设未来所有需求和能耗完全已知，使用确定性规划求解的最优方案，用于评估CFA策略的潜在差距。
四、仿真实验与结果讨论
作者采用300个随机实例评估CFA策略的表现，实验参数包括不同需求规模（200、300、400个客户）、电池数 、最大行程数 和滞后窗口 （30或60分钟）。以下总结关键实验结果，并配合论文图表进行分析。
3.1 参数标定：行程数量上限 (M) 和行程集合大小 (b)
3.1.1 行程数量上限 (M)
图1和图2展示了不同 值下 CFA 策略的平均服务客户数 和平均总迟到 。当 时， 能够取得最大的服务客户数量和最低迟到；而 时， 表现最佳：
下图给出了实验结果，横坐标为最大行程数 ，纵坐标为平均服务客户数／平均总迟到，实线表示 ，虚线表示 ：
由图可见：
当行程数 增大时，平均服务客户数略有减少；这是因为更多的预分配减少了机队对未来需求的响应能力。 时 已足够，无需为每架无人机预留过多行程； 时，为适应更长预测窗， 最优。
因此作者在后续实验中选取 和 两个组合。
3.1.2 行程集合大小 (b)
构造行程时，需要指定每个客户节点的邻接扩展数量 ，等价于行程集合大小 。图3和图4显示在 与 时，平均服务客户数和迟到随 的变化趋势：
结论是：随着 从 增大到约 ，平均服务客户数显著提高且迟到迅速下降；当 后收益趋于平缓。因此实验取 。
3.2 CFA 与贪婪策略对比
对比贪婪策略，CFA 限制每架无人机只执行少量行程，保留调度余地。图5、图6和图7、图8给出了 CFA 相对贪婪策略的改善百分比：分别为平均服务客户数增加百分比和单位客户平均成本降低百分比。
**：
**：
观察可得：
CFA 在所有测试中均提高了服务客户数，尤其在需求规模较大时提升更明显；例如 情况下，服务客户数提升中位数达到 4.80%（200 客户）和 4.72%（300 客户）。 CFA 也降低了单位客户平均成本， 时中位降低幅度在 7.67%—9.93% 间，说明更合理的行程安排减少了总距离和迟到。
3.3 CFA 与 PFA 策略对比
进一步与策略函数近似（PFA）比较，图9–图12展示了 CFA 相对 PFA 在服务客户数和单位客户成本上的提升。
**：
**：
可以看出：
CFA 明显优于 PFA。以 为例，在 400 个需求实例中，CFA 服务客户数提升的中位数达 74.73%，单位客户成本平均降低超过 94%。 PFA 类似贪婪策略，缺乏对未来需求的考虑；CFA 通过控制最大行程数和时间窗有效平衡当前与未来需求，因此在大需求规模下优势尤为显著。
3.4 CFA 与理想 Oracle 对比
最后将 CFA 与理想的全知 Oracle 策略比较。图13和图14给出了在不同需求规模下，CFA（分别为 和 ）与 Oracle 在平均服务客户数和平均迟到方面的对比：
结果表明：
Oracle 因完全掌握未来信息而拥有最高的服务客户数和最低迟到。 CFA 与 Oracle 的差距随需求规模增大而缩小。对于 400 个需求，CFA() 的服务客户数仅比 Oracle 少约 6%，且平均迟到接近 Oracle 的一半。 CFA() 一致优于 CFA()，这与前述参数标定结论一致。
五、结论与启示
本文针对随机需求与能耗不确定的同日无人机配送问题，提出基于马尔可夫决策过程的近似动态规划框架，并结合机会约束确保能耗安全。研究的主要贡献包括：
集成路由与地面服务决策：模型同时考虑行程构造、无人机调度以及电池更换管理。 机会约束下的行程构建：采用后向标记算法和支配规则快速生成满足能耗安全的非支配行程集合。 成本函数近似策略（CFA）：通过限制每架无人机的最大行程数 和使用短期预测时间窗，平衡服务客户数量与调度灵活性；实验表明在各种规模的随机需求中，CFA 显著优于贪婪策略和 PFA 方法。
管理启示方面：
适当控制无人机每次预分配的行程数并预留机动能力，可有效提升动态环境下的服务质量。 机会约束框架可适用于其他能耗或安全敏感的无人机应用，如医疗物资配送和应急物流。 未来可以进一步研究考虑飞行速度可调、充电而非换电、多仓库或异构机队的情况，拓展模型适用范围。
总体而言，CFA 策略在不完全掌握未来需求的情况下，通过合理平衡现有行程和潜在需求，提供了一种有效的动态无人机配送决策方案，具有较高的实际应用潜力。
文章须知
推文编辑：单子叶
责任编辑：弓仪长
原文链接：https://doi.org/10.1016/j.trb.2025.103335
