精读笔记

Problem Setting

《A Deep Reinforcement Learning Algorithm for the Vehicle Routing Problem with Stochastic Demands and Outsourcing》（arXiv preprint / 2026）研究的是 VRP-PFCC 的一个更难版本：外包决策必须在需求揭示前做出，而自有车队服务 committed customers 时面对随机需求、补货、残余需求、多车重复访问和 overtime cost。

关键矛盾是第一层 outsourcing decision 是静态组合优化，第二层 routing cost 却是随机动态策略优化。一个外包集合看起来便宜还是贵，取决于剩余客户在需求 realization 下的 expected routing + overtime cost；而这个 cost 不能用 deterministic route length 粗略替代。

以前方法卡在两个方向：deterministic VRP-PFCC 可以做 customer selection，但 routing cost model 太静态；SVRP / ADP / RL 可以做动态 routing，但通常针对固定客户集合，无法在 ILS 中被反复调用成千上万次。论文真正要解决的是二层 stochastic dynamic oracle 的 amortization 问题，而不是单纯提出一个新的 VRP variant。

Motivation

作者的核心动机是 online evaluation bottleneck。每天客户集合刚出现，LSP 需要很快提交外包客户；但任何认真搜索 outsourcing partition 的算法都会频繁问同一个问题：如果我 commit 这一批客户，期望 routing cost 是多少？

传统 simulation / rollout / ADP 在单次 routing 上可以接受，但放进第一层搜索后会成为瓶颈。作者看到的缺口是：需要一个能对任意 committed subset 近似返回 routing value 的 reusable oracle。

因此方向自然转向 offline learning：把每天重复发生的二层 routing policy/value learning 提前做掉。这个思路的前提是客户位置、需求、规模有稳定历史分布；如果这个分布稳定，二层 routing value 可以被看作一个从 customer-vehicle state 到 cost-to-go 的函数，而不是每天重新求的优化问题。

Core Idea

论文真正核心不是“用 DQN 解 VRP”，而是把 VRP-SDO 改写成一个 bilevel search-with-learned-oracle 框架：第一层 ILS 只负责探索外包集合；第二层不再在线求解 VRP-SD，而是调用离线训练的 Q-network 估计 committed set 的 expected routing cost，并用该估计指导外包搜索。

GAT 的本质作用是改变 state abstraction。Dastpak et al. 2023 的 observation 依赖 grid aggregation 和手工 target customers，本质上是把可变客户集合硬压成固定特征，容易丢掉局部邻域、客户间空间结构和车队上下文。本文用 attention 把所有客户和车辆相对 active vehicle 重新加权，形成 fixed-size observation。这个 inductive bias 更接近 routing 决策本身：下一步动作不是由单个客户属性决定，而是由客户在空间图、剩余容量、车辆状态和时间压力中的相对位置决定。

和 prior 的本质区别在于它没有直接用 attention decoder 输出路线，而是用 GAT 构造 value-function observation，再由 Q-learning 做 action valuation。也就是说，attention 在这里服务于 cost-to-go representation，而不是端到端 sequence construction。

Method

第一，two-level decomposition 解决目标函数结构问题。外包成本可以直接算，但 committed customers 的 routing cost 是隐藏的 stochastic dynamic value。分解后，第一层只需要一个 cost oracle，避免把随机动态 routing 显式嵌入整数规划。

第二，generalized MDP 解决 customer set variability。固定 committed set 的 MDP 对另一个 subset 不再定义，因此作者把 committed set 视为来自某个分布的随机对象，在 union state space 上训练一个共享 policy/value function。核心变化是从 instance-specific policy 转为 distribution-level amortized policy。

第三，MDP-CO 和 consecutive action rule 解决动作空间爆炸。多车同时决策会产生联合动作约束，难以学习；论文把决策序列化为 active vehicle one-at-a-time。这个近似牺牲了一部分同步协调能力，但大幅降低 action evaluation 难度。

第四，GAT observation function 解决可变规模状态表示。Node Embedder 聚合客户-客户与客户-车辆关系，Vehicle Embedder 表示 active vehicle 相对车队状态，Graph Embedder 让 active vehicle 根据时间和节点 embedding 形成图级 observation。机制上它把“挑固定数量 target customers”变成“对所有节点做 soft selection”。

第五，online fine-tuning 解决 value estimate 与 rollout cost 不一致导致的搜索误导。它不是核心 routing policy learning，而是 test-time calibration：在 ILS 找到局部解后用 simulation 估计真实 routing cost，并用监督式微调修正初始状态 value prediction。

Key Insight / Why It Works

最可能真正有效的部分是 representation alignment：routing 决策天然依赖相对空间结构、剩余需求、车辆容量和时间压力；GAT observation 比 grid/hand-crafted target list 更对齐这个结构。它让 value estimator 在不同客户数量下共享“局部拥挤度、远端客户、车辆覆盖、补货风险、overtime 风险”等隐式模式。

第二个关键是 memory reuse / amortized optimization。论文不是让 RL 在线规划得更聪明，而是把大量二层 routing 求解的计算前移到离线训练。ILS 中的每次 cost query 变成一次神经网络前向传播，因此第一层可以搜索得更快。这是工程上非常重要的变化，但本质上是 offline compute 换 online latency。

第三个有效因素可能是 data coverage，而不是纯粹算法新意。DQNCO 训练五百万 trials，SQNCO 三百万 trials，且 DQNCO 网络更深、表示更强。文中虽然把优势归因于 GAT，但增益来源不清：GAT inductive bias、训练数据量、网络容量、训练时长都混在一起。严格归因需要等训练预算、等参数量、等 trials 的 ablation。

online fine-tuning 的作用更像 test-time compute / local calibration，而不是新的 planning ability。它修正的是 value oracle 在某些 committed set 上的 systematic misranking。对 DQNCO 增益较小，说明主误差已经被更强 representation 吃掉；对 SQNCO 增益较大，说明浅 observation 的 value estimate 更不稳定。

需要直接指出：这里的“泛化到任意 daily realization”主要是在同一 instance generator / historical distribution 下的插值泛化，不是强 OOD 泛化。所谓 routing intelligence 也不一定是长期推理，可能相当大部分来自对训练分布中 routing cost landscape 的函数逼近和 retrieval-like interpolation。

Relation To Prior Work

它最接近三条线：deterministic VRP-PFCC 的 customer outsourcing/search；SVRP with stochastic demands 的 dynamic routing/recourse；以及 Dastpak et al. 2023 的 MDP-CO + offline approximate dynamic programming。

相对 VRP-PFCC，本文的新增信息是把 outsourcing decision 放在需求揭示前，并让 committed side 成为动态随机 routing policy，而不是确定性 route construction。这个建模差异是实质性的，因为 outsourcing cost 与 routing risk 之间出现了新的 trade-off。

相对 SVRP/ADP，本文并没有提出全新的 MDP 求解范式；consecutive action、Q-learning、replay memory、double DQN 都是已有组件。真正新增的是让二层 policy/value 在 variable committed sets 上离线训练，并作为第一层 metaheuristic 的快速 oracle。

相对 attention-based neural routing，本文不是 encoder-decoder constructive policy，也不是直接输出 tour，而是把 attention 用作 observation compression for value approximation。这一点比较重要：它把 neural architecture 插入到传统 OR decomposition 中，而不是替代整个 solver。

所以这篇更准确的位置是：OR bilevel/metaheuristic 框架中引入 learned stochastic dynamic cost oracle；GAT 是该 oracle 的 inductive bias，而不是完整 solver 的唯一创新。

Dataset / Evaluation

实验主要使用合成 instances，来自 Dastpak et al. 2023 的生成协议扩展，覆盖三种 customer density 和三种 vehicle capacity。测试规模大，需求 realizations 多，足以评估同分布下 expected cost，但任务覆盖仍然较窄：没有真实运营数据，没有跨城市/跨分布验证，没有 time windows、traffic uncertainty、service time、driver constraints 等真实 last-mile 约束。

benchmark 设计能支持局部 claim：DQNCO 比简单 dispatching policies 和 SQNCO 更好；IDQNCO+ 比同一 ILS 下的其他 routing oracle 更好；learned oracle 比 simulation-based evaluation 快很多。但它没有完全支持强泛化 claim，因为 train/test 来自同一生成机制，且 committed set 训练分布用 random removal 近似 ILS search distribution，这个 surrogate 是否匹配真实 ILS trajectory 文中未充分说明。

另一个评估限制是 attribution 不干净。DQNCO 与 SQNCO 不只差 GAT observation，还可能差训练量、网络容量和 representation dimension。论文报告的 13.7% / 19.6% 类增益说明系统有效，但不能严格证明“主要因为 GAT”。

full enumeration 只在 low-density 小样本上做，说明 ILS 在小规模下能找到与枚举一致的解，但不能证明中高密度下 search quality 接近最优。高密度结果主要是相对 benchmark superiority，而非 optimality evidence。

Limitation

第一，方法把难度从在线优化转移到离线训练。DQNCO 训练需要数天到十几天 GPU 时间，这在稳定运营环境中可接受，但不是轻量方法。若客户分布、需求模式、服务区或成本结构频繁变化，重训或持续校准成本会成为核心问题。

第二，泛化依赖分布 overlap。训练时 committed set 由随机删除客户产生，在线 ILS 产生的 committed set 可能有强结构偏差，例如外包远端、高需求、低密度区域客户。若训练 surrogate 没覆盖这些结构，value oracle 会系统性误估，进而误导第一层搜索。

第三，consecutive action rule 是强近似。它降低动作空间，但也把多车同步协调问题序列化。文中认为多车同时到达不常见，但初始时刻和对称场景中同步决策很关键。这个近似的最坏情况损失没有分析。

第四，GAT masking 和 n_max 设定限制 scalability。attention 对所有节点聚合，在客户数继续变大时计算成本和 memory 会上升；固定 n_max 也意味着部署时需要预设规模边界。超过训练规模或空间密度显著变化时，性能不确定。

第五，value estimate 可能只是同分布 cost interpolation。论文没有证明 Q-network 学到了可解释的 recourse strategy 或 robust long-horizon planning。尤其在 stochastic demand 下，长期价值来自大量 demand scenarios 的经验平均，可能主要是数据覆盖驱动。

第六，真实 deployment gap 明显。实际 last-mile 通常有 time windows、服务时长、司机班次规则、交通动态、客户取消、multi-depot、heterogeneous fleet 和 carrier SLA。本文问题定义已经很 rich，但仍是受控合成环境。

Takeaway

• 第一，最值得迁移的不是 DQN 本身，而是 learned second-level oracle + classical first-level search 的结构。
• 很多 stochastic bilevel / two-stage-with-dynamic-recourse 问题都可以用这个套路：离线学 recourse value，在线快速搜索 first-stage decisions。
• 第二，attention/GNN 在 OR 中最有价值的位置未必是直接构造解，也可以是为 value approximation 提供可变规模、 permutation-aware、context-conditioned state abstraction。
• 第三，未来真正值得做的是 oracle distribution alignment：训练 committed-set distribution 应该主动匹配 first-level solver 的访问分布，而不是随机删除客户。

一句话总结

这篇论文的贡献是在随机需求外包 VRP 中把昂贵的动态 routing recourse 训练成可复用的 GAT-DQN value oracle，并嵌入传统 ILS 做在线外包搜索，属于“learned recourse evaluator for OR metaheuristics”的方法演化，而不是单纯的 neural VRP solver。