训一次模型，之后每次求解都是一次前向传播：VRP 的摊销优化

  • 关联论文：1802.04240

车辆路径问题（VRP）：给定一个仓库和一批带需求量的客户，用一组容量有限的车辆，设计总行驶成本最低的配送路线。难在解空间组合爆炸，论文说它 "computationally difficult to solve to optimality, even with only a few hundred customer nodes"，属 NP-hard。

传统方案三个痛点：每次新订单都要把 OR-Tools 重跑一遍；车辆数本身常常是决策的一部分；更关键的是——在调度、共享出行、算力调度场景里，路由决策要跟其他决策耦合、需高频重算，求解器的时延就成了硬伤。

为什么重要

思路很直接：既然同一分布下的实例反复出现，就训练一个模型直接生成解。 训练付出一次昂贵成本，推理每次只需一次前向传播，输出的是一整条解（不像经典解法要迭代收敛）。

"每次求解跑一次优化器"换成"训练一次、推理 N 次"，比 VRP 本身更有普适价值——调度、路由、装箱、排程、资源分配全在这个模式里。

核心机制

建模为 MDP。 状态是当前部分解（已访问哪些客户、剩余需求、车辆位置）；动作是"下一个访问哪个客户"或"返回 depot"；奖励与路径成本成比例。

可行性靠掩码，不靠惩罚项。 这是全文最值得抄的一条：容量超限的客户不可选，通过 masking 在打分阶段硬排除，而不是在 reward 里罚。作者的公开讲解视频明确说过，剩余需求为 0 的客户其被选中的 likelihood 被置为接近负无穷的极小值。这条被整条 neural CO 路线继承。

Encoder 用图嵌入 + 动态特征。 输入分静态部分（坐标、depot 标记）与动态部分（时刻 t 的需求量、剩余载重），二者各自嵌入到 128 维再进 attention——这个分层决定动态量能否影响打分。最关键的是 time-in-system（客户已在系统中的时间），论文原话是它让训练过程 "learn customer abandonment behavior"，即模型学会"等太久就放弃"。

Decoder 是带 attention 的 LSTM，每步对候选节点打分、掩码、采样或取 argmax。训练用 policy gradient：Algorithm 3 明确是 actor-critic 双网络。

证据边界

  • 限定条件有三个：capacitated VRP 这一变体、medium-sized instances 规模区间、训练之后。
  • "comparable computation time" 必须带限定。论文自己写明：OR-Tools 是 C++，其余基线是 Python，精确时间比较不可能，不是严格计时。
  • "给定分布"是 arXiv v2 的措辞，NeurIPS 正式版写的是 "a broad range of problem instances of similar size"——更弱，易被误读成"规模相同就适用"。
  • 已核验的原文数字：50 与 100 客户实例上约 61% 的情形路径更短；最差结果仍相对接近最优（定性判断，非带公差的数字）；split delivery 平均约 0.6% 改善；VRP20 训练 20 epoch 约 13.5 小时（单 K80）；VRP10×1000 逐条解码 50 秒、批量 1 秒（约 50×）。
  • 解质量随规模衰减的交叉点未量化。
  • venue 是 NeurIPS 2018（Nazari / Oroojlooy / Takáč / Snyder，Lehigh ISE）。常见的 "ICLR 2018" 是 v1 标题被二手沿用导致的误引。
  • 训练稳定性归因要小心：论文抱怨的不是方差（它有 critic baseline），而是 "REINFORCE is not an efficient algorithm in dealing with the long trajectories"——长轨迹信用分配的效率问题，所以随机 VRP 上改用 A3C。归成"种子方差大"就错过改造点。

工程局限

先算摊销账，可能算完就不想训了。 训练 VRP20 就要 13.5 GPU·小时。只有当"日调用量 × 单次求解器成本"显著超过"训练 + 运维成本"时摊销才为正。若你的场景 OR-Tools 本来就够快，收益极薄。论文没给盈亏平衡点，只有定性说法。

"单次前向传播"不等于"快"。 注意力对全部 N 个节点打分，单实例推理是 O(N²) 量级。50× 的加速来自批量解码——1000 个实例一次性送进 GPU。单条在线解码要 50 秒，拿"每秒 1000 实例"承诺低延迟会违约。

可行性靠掩码 + 启发式拼凑，不靠 LP 约束。 节点级掩码挡得住单点非法动作，挡不住路径级约束（时间窗、路径长度上限、司机工时）。模型会生成"每点合法、整体不可行"的解，到执行端才炸。必须配独立校验器当硬门禁。

分布漂移是静默的。 模型永远能给出合法解，只是解很烂，系统不会报警。上线要跑求解器影子链路对比，监控解成本漂移，超阈值降级。

reward 与业务 KPI 可能脱钩。 论文的 reward 只对齐路径长度，实际成本还包括停车、装卸、服务时长、工时。

split delivery 别默认开启。 论文的数字是平均仅约 0.6% 的路径长度改善，而业务侧拆单成本通常远大于此。做成可切换开关让业务方签字。

更大的规模要走混合路线。 规模越大，自注意力越容易丢掉全局结构，解质量衰减快于经典启发式。更稳的形态是"学习出初解 + 求解器收敛"。

标题变体

  1. 训一次模型，之后每次求解都是一次前向传播：VRP 的摊销优化
  2. 3.6% 的胜率、13.5 小时训练成本：神经 VRP 到底划不划算
  3. 别把"推理是单次前向传播"当成"推理是快的"

小红书卡片文案

一个 2018 年的思路，如今在物流、调度、装箱里都很常见：训一个模型，把"每次跑一次求解器"变成"训练一次、推理 N 次"。

但这篇论文最有价值的其实是它诚实的限定条件： ① 赢的区间是 capacitated VRP + 中等规模 + 训练之后，"comparable computation time" 建立在 C++ 比 Python 的跨实现粗略比较上。 ② 单条在线解码要 50 秒，批量才是 1 秒——50 倍差距来自攒批，单条低延迟场景拿不到。 ③ 训练 VRP20 约 13.5 GPU·小时。论文没给摊销盈亏平衡点，"训模型到底省不省"必须自己算。

两条可以直接抄的设计： 可行性用掩码硬排除，别丢给 reward 去罚。 time-in-system 这种动态特征要单独嵌入再进 attention。 让模型自己学会"等太久就放弃"，比在规则层硬编码省事。

最实用的提醒：解靠掩码拼出来，不保证路径级可行。上线必须配独立的可行性校验器当硬门禁，否则非法解会一路流到执行端才炸。