Delivery-RL算法学习

       本文是对github上开源算法具体的思路学习和总结。

Conclusion

最后一公里配送是一个快速发展的领域。每家专注于此的公司都面临如何为客户的订单指派骑手的挑战。核心问题是：如何使这些指派最高效。
在该算法实践中，进行了形式化定义，并在真实世界的仿真环境中，利用强化学习训练神经网络，探索其求解能力。所得到的算法与若干启发式算法进行对比，以评估其相对于基准的性能。

本研究有如下成果：
实现了一套可模拟骑手与订单的基础设施；设计了神经网络架构；并实现了采用强化学习训练模型的算法。
基于不同参数对模型性能进行了分析：测试了多种奖励函数、处理地理坐标的方法以及模型规模。
针对若干类似问题证明了若干理论结论：具体而言，在特定条件下证明了某算法的最优性，并提出了一种应对某些稀疏奖励场景的方法。
目前得出的结论是：对于最基本的指派问题，依赖骑手与订单之间距离的启发式算法已经相当有效。神经网络可以学会以相近水平解决这些问题，但尚未在效果上实现超越。
因此，本工作仅为理解该问题及其可能的解决方案提供了初步视角，并留下若干待未来研究的问题。例如，现有模型尚未考虑将新订单追加到已有订单的可能性，尽管相关功能已在代码中实现。这可能是强化学习有望超越启发式算法的一个方向。

配送问题

问题定义

1. 输入：两条实时流
   • 订单流（claims）：每个订单包含起点、终点、创建时间、取消时间；若长时间未被指派即自动取消。
   • 骑手流（couriers）：每个骑手具有实时位置、开始工作时间、结束工作时间、固定速度。
2. 输出：在线调度函数 D，它根据当前两条流的状态，在每一时刻输出“骑手-订单”配对（assignment）。
3. 目标：最大化长期指标 Q* = lim_{t→∞} Q(t)。实际计算中只需在大规模仿真里优化 Q(t)。

系统模型（连续时间版本）

• Courier = (实时位置，开始时间，结束时间，速度)
• Claim = (起点，终点，创建时间，取消时间)
• Route = 依次经过的一系列坐标点
• Order = (骑手，路线，订单集合)
• 系统 S(D, P) 由调度策略 D 和分布 P 共同决定；每时刻 t 的演化步骤：

1. 初始化到达的骑手和订单；
2. 移除已过期或已完成的骑手/订单；
3. 根据 D 产生 assignment，形成新的 Order；
4. 骑手沿路线移动，到达订单终点即完成该订单；
5. 若 Order 内所有订单完成，Order 被移除，骑手继续留在系统。

评价指标

1. Complete Rate (CR)：已完成的订单 / 总创建订单。最直观，但波动大。
2. Click-to-Delivery (CTD)：已完成的订单里，从创建到送达的平均时长。与 CR 强相关但更稳定。
3. Arrival Distance：指派瞬间骑手到订单起点的平均距离，近似 ETA，用于衡量调度效率。

离散时间版本（实际求解/部署用）

• 采样间隔 δt，把“时间点 t”替换为“区间 [t, t+δt)”。
• 每一步的输入称为 gamble = (当前所有骑手、订单、未完成 Order)。
• 离散调度函数 D 将 gamble 映射到区间内的 assignment。
采用离散化的原因：

• 下游服务（坐标、路径、ETA 等）多为批处理更高效；
• 任何调度算法本身需要执行时间；
• 网络延迟、数据误差使得“连续流”无意义。

现实落地难点

真正难的不在于算法本身的速度或精度，而在于大量本地化约束和边界场景：
• 大客户或 VIP 订单需优先；
• 骑手属性与订单属性不匹配（如徒步骑手不能送重物）；
• 这些约束层层叠加后，理论最优性保证丧失，也难以评估离最优解还有多远。

调度算法

启发式调度（Heuristic Dispatches）——作为基准

1. 随机调度（Random Dispatch）
   对每个订单，按顺序在所有可用骑手里随机挑一个。
   • 作用：提供“最弱”基线，用于衡量任何算法最起码的收益。

2. 贪心调度（Greedy Dispatch）
   对每个订单，按顺序挑“当前最匹配”的骑手。
   • 匹配度函数：Q(A,B)=e^{-d(A,B)}，d(A,B) 为骑手 A 与订单 B 起点的欧氏距离。
   • 思想：永远选距离最近且仍空闲的骑手，简单、可在线执行。

3. 匈牙利调度（Hungarian Dispatch）
   非顺序、全局一次性决策。
   • 建二分图：左侧节点为当前所有可用骑手，右侧为当前所有未指派订单；边权用 Q(A,B)。
   • 使用匈牙利算法求最大权匹配（O(n³)），该匹配即为本轮指派。
   • 优点：在若干理论条件下可证明局部最优（见附录）。
   • 复杂度：n 为几十到几百时完全可接受。

神经网络调度（Neural Network Dispatches）

核心思想：让神经网络充当“打分器”，对每个订单挑选最合适的骑手。

输入：
• 当前待指派订单的特征（起点、终点、已等待时长…）
• 所有 N 名可用骑手的特征（实时位置、剩余工时、已携带订单…）
• 任何附加信息（天气、时段、历史轨迹…）

输出：
• 长度为 N+1 的 logits 向量 → 经 Softmax 转成概率分布
– 前 N 个 logit 对应真实骑手
– 最后一个 logit 对应“假骑手”（即“暂不指派”，订单可继续等待或进入下一轮）

流程（在线推理）：

1. 依时间顺序遍历当前所有未指派订单。
2. 对每一订单，把订单特征 + 所有骑手特征喂入网络。
3. 按输出概率 argmax 选骑手（若抽到假骑手则本轮不指派）。

训练：
• 采用强化学习（策略梯度 / Actor-Critic），奖励基于 CR、CTD 或组合指标。
• 网络结构细节在第 4.4 节给出（包括嵌入层、Attention 机制、坐标编码方式等）。

强化学习（Reinforcement Learning）

采用 RL 的动机

• 无法给出“正确指派”的标签：任何试图先验定义“骑手-订单匹配度”Q(A,B) 的做法，最终都会退化成“直接用匈牙利算法优化 Q(A,B)”——这相当于绕开了学习。
• 因而承认“我们不知道正确答案”，把“什么算好”交给 RL 智能体去自己发现。
• 额外收益：

1. 业务真正关心的指标（CR、CTD 等）是全局的，无法仅在单个 gamble 里局部优化；RL 可以把它们直接设成 reward。
2. 各种本地化约束（VIP 优先、重量限制等）对启发式算法极难调参；在 RL 里只需在 reward 里加惩罚项即可，调优工作转嫁给智能体。

RL 形式化

状态（State）

• 不直接把整个 gamble 当状态，而是把“当前正在考虑的订单”作为原子状态。
• 形式化：s = (G_t, i, A)
– G_t：t 时刻的 gamble（所有骑手、订单、未完成 Order）。
– i：本轮要处理的订单索引。
– A：已累积的指派集合。
• 当 i 是最后一个订单索引时，称该状态为“过渡态”（transitional state），此时返回 A 作为本轮调度结果。

动作（Action）

• a ∈ {0, 1, …, N-1} ∪ {−1}：
– 0 … N-1：把当前订单指派给对应骑手；
– −1：不指派（丢给“假骑手”）。
• 非过渡动作：状态按 (G_t, i, A) → (G_t, i+1, A∪{a}) 确定性转移。
• 过渡动作：输出 A 并进入新 gamble (G_{t+1}, 0, ∅)。

奖励（Reward）

• 仅在过渡动作时给出非零奖励，因为只有此时才真正与环境交互。
• 实验比较三类奖励：

1. 稀疏奖励：按过去 f 步的 CR 作为一次性奖励，其余时刻为 0。直观但稀疏。
2. 加性奖励：R = Σ_j β_j n_j，n_j 为局部统计量（如本轮有效指派数、新订单数）。灵活但需人工调 β_j。
3. 稠密化奖励（Densified）：把形如 M = Σm_τ / Σn_τ 的全局指标（如 CR）转化为每一步都可计算的稠密信号
   R(t) = [m_t N_{t-1} – n_t M_{t-1}] / [N_{t-1}(N_{t-1}+n_t)] （当 N_{t-1}≠0 时）
   可证明 ΣR(t) = CR(T)，从而等价于最大化 CR。
   

训练算法

• 默认使用 PPO（Proximal Policy Optimization）——on-policy，易于稳定收敛。
• 备注：可先用 off-policy 算法在启发式轨迹上做预热，但若要真正超越基线，仍需 on-policy 精调。

神经网络结构

整体为“编码器 + Transformer Attention + Actor-Critic 头”三段式。

状态编码器（State Encoder）

• 输入：G_t 内全部骑手、订单、Order、全局特征、当前已指派集合 A、当前订单索引 i。
• 每个实体（骑手/订单/Order）用独立子编码器转成向量 token；再拼接：
– n_crr 个骑手 token
– n_clm 个订单 token
– n_ord 个 Order token
– 1 个 fake courier token（用于“不指派”）
– 1 个 state-value token（给 critic 用）
• 输出：长度 = n_crr + n_clm + n_ord + 2 的 token 序列。

注意力层（Attention）

• 若干层 self-attention + FeedForward（即标准 Transformer Encoder）。
• 输出序列长度不变，但每个 token 已融合全局上下文信息。

Actor-Critic 头

• Policy Head：对所有骑手 token 过 MLP + Softmax，输出 N 维概率；fake courier token 对应第 N+1 维。
• Value Head：仅对 state-value token 过 MLP，输出标量 V(s)。
• 二者共同构成 PPO 所需的 π(a|s) 与 V(s)。

实验结果与讨论

数据设置

• Easy 数据：坐标、寿命、流量全部均匀分布；差异大、易暴露算法缺陷。
• Hard 数据：强度、密度、寿命按经验分布采样，含高峰/低谷等真实异质性；对模型更困难。
• 度量周期：δt = 30 s，整日需 2880 步；实验取 500 步（≈4 h）即可显著区分算法。

行为克隆（Behavior Cloning）——用监督学习测容量下限

Easy 数据

– 所有 NN（tiny/medium/big）在 CR 上都能完美复现 Hungarian；
– 但在 Arrival-distance 上仍逊于 Hungarian；
– 模型越大，CTD 越接近 Hungarian；
– 复制 Greedy 后得到的 NN 甚至略超 Greedy 本身。
结论：NN 容量充足，可在简单场景下达到或微超最佳启发式。

Hard 数据

– Greedy 与 Hungarian 在 500 步内差异不显著；
– big-Hungarian NN 在 CTD 与 Arrival-distance 上反略优于 Hungarian。
结论：NN 在复杂分布仍有机会局部超越被克隆的启发式。

• NN 可以不强制指派（选 fake courier），且能用额外特征，理论上存在“突破启发式天花板”的可能。

RL 训练的稳定性问题

• 相同超参多次运行结果差异巨大：最好可超 Hungarian，最差低于 Random；
• 训练过程中 CR 可能突然跳水，而 loss 表面正常；
• loss 呈“周期性+缓慢上升”形态，无论学习率、调度器、正则化如何调均无效；
• 应对策略：同一参数多次跑，只保留最佳一次。

奖励函数对比（Easy 数据，5k/10k 迭代）

• 稠密-CR 与加性奖励区间 [0.80,0.84] 无显著差异，均优于 Greedy、劣于 Hungarian；
• 最稳定的奖励：R = n_assign – avg(arrival distance)。但它实质上是在学距离最小化，与启发式目标重合，失去“超越”意义。

距离特征的重要性（Easy 数据）

• 默认特征：CR 0.849；
• 去掉距离特征：CR 跌至 0.736；
• 仅用距离特征：CR 0.845。
→ 模型几乎完全依赖距离，其它特征贡献微弱，这解释了 RL 与启发式差距不大。

训练长度分析

• Short（1500 步，约 6 次轨迹重采样）：
– 100 次迭代后 CR 已达 0.849（≈Hungarian），且后续不再提升；
– 表明模型几乎在“离线”阶段就锁定了距离优先策略。
• Long（30k 步）：
– Easy 数据 CR 反而掉到 0.37；Hard 数据无提升；
– 未见全局更优解，疑似陷入局部极小或过拟合采样轨迹。

最终成绩对比

Easy 数据（500 步）
• Best RL：CR 0.849，CTD 2688，Arrival-distance 0.052
• Hungarian：CR 0.846，CTD 2447，Arrival-distance 0.028
→ RL 在 CR、CTD 上追平 Hungarian，但未在距离指标上超越。

Hard 数据（500 步）
• Best RL：CR 0.534，CTD 2870，Arrival-distance 0.10
• Hungarian：CR 0.624，CTD 2516，Arrival-distance 0.044
→ RL 甚至未能显著优于 Random（CR 0.413）。若改用距离最小化奖励，可勉强击败 Random，但仍远落后 Hungarian。

结论总结

研究回顾

• 对“最后一公里骑手指派”问题给出了严格的数学定义，并实现了可配置的离散时间仿真器。
• 设计并实现了三类启发式基准：随机、贪心、匈牙利。
• 将问题转化为强化学习任务，搭建了基于 Transformer 编码器的 Actor-Critic 架构，并系统比较了稀疏、加性和稠密化三种奖励函数。

主要发现

• 在简单分布的 Easy 数据上，RL 策略可在 100~200 次迭代内逼近甚至轻微超越贪心算法，但仍未在“到达距离”指标上击败匈牙利算法。
• 在更接近现实的 Hard 数据上，RL 训练极度不稳定：同参数多次运行结果方差巨大，常出现性能骤降；最优模型仅略优于随机指派，远落后匈牙利算法。
• 消融实验表明，神经网络几乎只依赖“骑手-订单距离”特征，其它信息对提升效果贡献甚微。
• 增加训练步数到 30k 步未见收益，反而可能过拟合采样轨迹。

未能超越启发式的原因

• 距离-优先的启发式本身已非常强大，额外特征提供的边际信息量不足。
• RL 训练存在周期性、上升型 loss 以及突发崩溃等未解现象，导致策略难以稳定收敛到更优区域。
• 计算资源有限，无法通过大规模调参与集成降低方差。

贡献与意义

• 首次在同一框架内系统比较了“指派-仿真-评价”全链路，并公开了可扩展代码。
• 为后续研究奠定了基准：问题形式、评价指标、数据生成器、启发式与 RL 基线均已就绪。
• 明确指出了 RL 在该任务上的瓶颈：训练不稳定、特征利用单一、奖励塑形困难。

未来工作

• 资源充足的大规模实验（多随机种子、分布式训练、超参搜索）。
• 解释并解决训练不稳定的深层原因（探索-利用失衡、策略熵崩塌、轨迹分布漂移）。
• 开启“订单插入已有路线”功能：
– 允许骑手一次携带多单；
– 重新设计状态-动作空间（订单序列化、路由嵌入）；
– 预期 RL 在组合优化空间更大的场景下才能体现对启发式的优势。