外观
调度与运筹优化中的 RL
一句话定位：这一页讲清楚强化学习怎么进入运筹优化（OR）——把库存、调度、装箱、路由这类组合问题重写成 MDP，用 RL 训练"学习式求解器"，以及它与经典 OR 方法（MILP、CP、启发式）是竞争还是互补。这是RL vs 相邻领域页"RL vs 运筹优化"一节的案例深化。
一、OR 问题如何写成 MDP
1. 组合优化的核心困难
运筹优化的经典问题——旅行商（TSP）、车辆路径（VRP）、车间调度（JSP）、装箱（Bin Packing）、库存管理、网络路由——本质都是组合优化：在指数级离散方案中找最优。它们的共同结构是：
text
minimize 目标函数（成本/时间/路程）
subject to 约束（资源、时限、容量、顺序）
经典求解：MILP（混合整数规划）/ CP（约束规划）→ 精确解或分支定界
启发式（NEH、ALNS、遗传算法）→ 近似解精确方法在规模变大时指数爆炸（NP-hard），启发式需要领域专家手写邻域/规则。RL 进入的方式是把"构造一个解"变成"顺序决策"：
2. 序列化：把解构造当作 MDP
几乎所有 OR 问题都能重写成一个顺序决策过程：
text
状态 s_t ：已构造的部分解（已排的工件/已走的路径/当前库存水平）
动作 a_t ：下一步决策（下一个插入的节点/下一个调度的工件/订多少货）
奖励 r_t ：该步的增量成本（负值）或完成时的目标值
转移 ：加入决策后更新部分解
结束 ：解构造完成，获得终局奖励
策略 π：P(下一步选择 | 当前部分解) —— 由神经网络参数化一个例子（TSP）：
text
s_t = 已访问的城市集合 + 当前位置
a_t = 下一个要去的城市
r_t = 到该城市的距离（负奖励）
策略学习目标：期望总路径长度最小这个"学习式构造（learning to construct）"范式就是 L2S（Learning to Schedule）、Learning to Optimize 等方向的基础。代表方法有 Pointer Networks（Vinyals et al., 2015）、Attention Model（Kool et al., 2018）、以及调度领域的 GPN（Zhang et al., 2020）。
INFO
序列化的奥妙在于：它把一个"一次性全局优化"拆成了"一步步的局部决策"。局部最优不保证全局最优，但配合好的策略学习（多看几步、考虑全局特征），RL 学出的构造启发式往往能逼近最优，且不需要手写领域规则——策略是从数据里学出来的。这与马尔可夫决策过程页的"决策序列"框架完全同构。
二、案例一：库存管理与报童问题的动态版
1. 静态报童 → 动态库存
经典报童问题（newsvendor）：报童一天进货 q 份报纸，需求 D 随机，卖不掉的部分亏本，卖掉的部分赚钱。静态版求一个最优 q。它的 RL 化（动态版）是：
text
状态 s_t ：当前库存水平 I_t
动作 a_t ：本周期订货量 q_t
随机项 ：需求 D_t ~ 已知分布
奖励 r_t ：销售收益 − 订货成本 − 持有成本 − 缺货惩罚
转移 ：I_{t+1} = max(I_t + q_t − D_t, 0)| 维度 | 静态报童 | 动态库存 RL |
|---|---|---|
| 决策 | 一次性订多少 | 每周期订多少 |
| 状态 | 无 | 库存、需求预测、在途量 |
| 目标 | 单期期望利润 | 长期期望利润（含持有/缺货代价） |
| 求解 | 解析（分位数公式） | 价值/策略学习 |
2. 为什么行业更倾向"解析+规则"而非 RL
诚实地说：单品、需求分布已知的库存问题，用报童公式/DP 就能精确解，RL 没有优势。RL 只在三个条件下才值得：
- 多品、多仓、共享资源：状态爆炸，解析解不存在；
- 需求非平稳（促销、季节、突增），分布持续漂移；
- 有仿真器：供应链仿真（如 AnyLogic、自建模拟）可以提供训练数据。
这个判断适用于整个 OR 领域：RL 不是来取代经典方法的，它只解决经典方法做不了的规模与复杂度。这是RL vs 相邻领域里"RL vs OR"的核心结论。
三、案例二：车间调度与装箱（学习式构造）
1. 车间调度（JSP/Flow Shop）
作业车间调度问题（Job Shop Scheduling）：n 个工件在 m 台机器上按工序加工，每台机器同一时间只能做一个工件，目标是让总完工时间（makespan）最短。这是 NP-hard 里的"硬骨头"，工业界靠启发式（如优先规则、遗传算法）求解。
RL 路线（GPN，Graph Pointer Network，Zhang et al., 2020）把调度写成图上的顺序决策：
text
状态 ：一个异构图（工件节点+机器节点+工序边），表达"还有哪些工序待排"
动作 ：选择"下一道要开工的工序"
奖励 ：完成解后 −makespan（或逐步的机器空闲惩罚）
策略 ：图神经网络（GNN）在图上打注意力分数 → 选工序实验结果：GPN 在基准实例上的 makespan 接近甚至优于传统启发式，且泛化到训练时未见过的规模（如从 15×15 训练迁移到 20×15 测试）有一定能力，但随规模变大性能下滑——这暴露了学习式求解器的关键弱点（见第七节）。
2. 装箱（Bin Packing）与更多
- 在线装箱：物品顺序到达，必须立即放入某箱子，RL 可学习"放哪个箱/开新箱"。
- 2D/3D 装箱（集装箱装载、仓库码放）：状态是箱内占用体积的表示，动作是"放哪个箱子、怎么旋转"。
- 车辆路径（VRP）：Nazari et al. (2018) 把 Attention Model 扩展到 VRP，学"从哪个顾客出发去哪个顾客"的构造策略。
3. 与经典启发式的胜负
| 方法 | 解质量 | 求解速度 | 泛化 | 需要专家知识 |
|---|---|---|---|---|
| MILP/CP | 精确最优 | 指数级 | 完美（精确） | 建模能力 |
| 手写启发式（ALNS 等） | 好 | 快 | 依赖实例结构 | 高（领域专家） |
| 学习式构造（RL） | 好~接近最优 | 快（单次前向） | 训练分布内强、分布外退化 | 低（只需仿真器） |
关键认识：学习式求解器真正的卖点不是解质量，而是"一次前向给一个可用解"——在需要实时响应（仓库作业中一个订单波次要毫秒级出方案）的场景，MILP 根本来不及，RL 的价值就在这里。
4. 学习式求解器的三种范式
学习式求解器不止"构造"一种，实际有三大范式，别混为一谈：
| 范式 | 做什么 | 代表 | 优点 | 弱点 |
|---|---|---|---|---|
| 学习式构造 | 一步步从空解搭出完整解 | Attention Model、GPN | 一次前向、快 | 解质量依赖训练分布 |
| 学习式改进 | 从给定解迭代局部修改 | 如 RL 版的 LNS/ALNS | 可逼近最优 | 需要好初始解、迭代成本 |
| 神经引导搜索 | 指导 MILP/CP 的分支选择 | Gasse 2019 | 精确性保留 | 不改求解器，集成复杂 |
选型建议：追求"实时出解"选构造；追求"解质量"选改进或神经引导；两者都想要时做两阶段（构造给初始解，改进/求解器收尾）。
四、案例三：网络路由与资源分配
1. 网络路由：让数据包"学会"走哪条路
网络流量工程（traffic engineering）的问题：在给定拓扑与流量矩阵下，决定流量在各链路上的分配，最小化最大链路利用率。RL 化：
text
状态 ：全网链路负载/队列长度（部分可观测，需聚合）
动作 ：各入口流量在出口路径上的分配比例
奖励 ：−(最大利用率) 或 −(时延/丢包)
转移 ：流量矩阵动态变化（非平稳！）代表性工作（如 DeepMind 与 Google 合作 2018 年的 Machine Learning for Network Routing 公开演示）证明：训练好的 RL 路由策略可以适配突发流量，比传统算法更快重路由。注意这里有个巨大的坑：流量是持续变化的、网络状态是分布外频繁出现的——所以网络 RL 至今也没有大规模替代 OSPF/MPLS 等协议，主要用在特定数据中心内部优化。
2. 资源分配：带宽、算力、频谱
云平台分配、无线频谱分配、算力调度同样适合 RL：状态是资源占用与任务队列，动作是"把资源给谁"，奖励是完成率/时延。多租户场景下还叠加了多智能体强化学习的博弈问题——每个租户都在策略性竞价/抢占。
五、学习式求解器思路：RL 训练构造启发式
把前面串起来，一套可复用的"用 RL 训求解器"方法论：
text
1. 定义问题的"构造过程"（顺序决策展开）
2. 选表示：序列(Transformer) 或 图(GNN) 编码当前部分解
3. 定义奖励：完成解的目标值（或逐步增量）
4. 训练：REINFORCE 带 baseline（或 PPO）最大化期望奖励
5. 推理：贪心 or beam search 采样多个解取最优其中训练目标与实现细节（baseline 设计、reward shaping）都在策略梯度方法页。REINFORCE 的 baseline 常用"当前 batch 的平均奖励"（如 Attention Model 的 rollout baseline），是为了降低方差。
L(θ) = E_{π_θ}[ (G − b) · log π_θ(a|s) ]
↑ ↑ ↑
期望 奖励减基线 选动作的对数概率
（让"比平均好的决策"概率上升——策略梯度的核心，见 policy-gradient 页）训练与推理细节：baseline、采样与热力图
学习式求解器的性能很大程度取决于三个实现细节：
| 细节 | 常见做法 | 作用 |
|---|---|---|
| baseline | 贪心 rollout 基线 / batch 平均基线 | 降方差（REINFORCE 的关键） |
| 推理采样 | 贪心 / beam search / 多次采样取最优 | 采样越多解越好，成本线性上升 |
| 输出形式 | 概率分布（softmax）或热力图（heatmap） | 热力图便于配合搜索后处理 |
工程上的"免费午餐"：训练好一个随机策略后，推理时做 beam search（宽度 100–1000）通常能立刻把 TSP 解质量提升到接近最优——因为在构造过程中多保留几条候选路径，最后挑最好的。这等于"推理时算力换解质量"，和 AlphaGo 的搜索思想同源（见AlphaGo 与蒙特卡洛树搜索）。很多论文报告"RL 已超过最优解"，其实用的是这种"策略 + 采样"组合，而不只是策略本身——读结果时务必看清推理协议。
和 MILP 的关系：不是替代而是混合
业界（2020 年代）最被认可的做法是神经引导搜索（neural-guided search）：
- 用 RL/GNN 学一个"预选择器"，把 MILP 的候选分支/变量排序后交给求解器（如 SCIP），不改变求解器本身；
- 学习器当"导航"，MILP 当"验证与精确化"，两头都占。
Gasse et al. (2019) 的 Exact Combinatorial Optimization with GNN 是这一方向的代表——用图神经网络给 MILP 分支定界的选择打分，在中等规模实例上大幅减少求解时间。这说明 RL 与 OR 的关系是互补而非取代。
机制细节：从 Pointer Network 到 Attention Model
理解"学习式构造"的直觉，最好看它的两个源头模型：
| 模型 | 结构 | 一句话机制 |
|---|---|---|
| Pointer Network（Vinyals 2015） | seq2seq + 指针注意力 | 每一步从输入序列里"选一个"，输出是索引序列 |
| Attention Model（Kool 2018） | Transformer 编码器 + 上下文注意力 | 用注意力分数直接当选择概率，支持 REINFORCE 训练 |
text
Attention Model 选择下一步的过程（以 TSP 为例）：
1. 编码器：所有城市坐标 → 节点嵌入（自注意力互相交换信息）
2. 上下文：当前部分解的"最后访问节点 + 已访问掩码"
3. 注意力：上下文与每个未访问城市的相似度 → softmax → 选择概率
4. 训练：REINFORCE + 贪心 rollout baseline（见策略梯度页）为什么这种结构有效：注意力把"部分解信息"和"候选动作信息"显式关联，模型能学到"在哪个位置该选哪个"的组合关系——这比纯 RNN 更适合处理"选择顺序"类组合问题。它也是后来大规模路由求解器（如 Amazon/物流公司内部系统）的通用骨架。
六、评估与泛化：问题分布是最大命门
1. "训练分布"是学习式求解器的软肋
学习式构造的训练与测试必须指定问题分布（规模、结构）。三个必须回答的问题：
| 问题 | 风险 | 对策 |
|---|---|---|
| 规模泛化 | 15 城市 TSP 训练，50 城市测试，性能骤降 | 课程学习（从小规模逐步加大）、多尺度训练 |
| 结构偏移 | 训练全是"均匀分布客户"，真实是"聚类分布" | 训练分布要覆盖真实业务分布 |
| 分布外（OOD） | 遇到从未见过的约束组合，策略瞎编 | 保留经典启发式作 fallback |
这正是离线强化学习里 OOD 问题的近亲：策略在训练分布外没有可靠信号，任何"自信的错"都会变成事故。
2. 评估协议
- 在同一组公开基准上对比（如 TSPLIB、VRPLIB、JSP 标准实例库），别自造数据集；
- 报告最优 gap（相对最优解的偏差）与求解时间两个维度；
- 多 seed 多次运行报告均值/方差——和评估与基准页的纪律一致。
3. 一个完整的数值演练：15×15 JSP
把整页方法串起来，看一个可重复的评估演练（车间调度 15 个工件 × 15 台机器）：
text
步骤 1 生成实例分布：工序时长、机器顺序随机采样（固定随机种子）
步骤 2 训练：GPN 在 5000 个训练实例上训到收敛（REINFORCE + 贪心基线）
步骤 3 评估：对 100 个测试实例报告
- 平均 makespan
- 相对最优解 gap（用 OR-Tools/CP-SAT 解出参考最优）
- 单实例求解耗时（毫秒 vs 秒级）
步骤 4 泛化测试：20×15、25×20 的未见规模再测一轮
步骤 5 多 seed（≥3）重复步骤 2–4，报告均值±方差这组协议能回答的四个问题：学习式构造在训练分布内能到多好？比启发式快多少？换规模掉多少？seed 稳定性如何？——四个答案凑齐，才配写进项目结论。缺任何一个，结论都不完整。这正对应评估实践页的实验矩阵规范。
七、落地现实：供应链与调度软件里 RL 的位置
1. 真实的行业形态
- ERP/供应链软件（如 SAP、Oracle SCM 生态）里 RL 尚未成为标准组件；主流仍是启发式+求解器。
- 头部物流/电商（京东、菜鸟、顺丰、亚马逊等）在内部用学习式求解器优化仓储作业、装箱、路径；公开论文较少，多以技术分享形式出现。
- 云厂商用 RL 做资源调度（数据中心制冷、任务分配）已有公开案例（如 DeepMind 的谷歌数据中心冷却优化）。
2. 落地建议（来自工程经验）
- 先问"经典方法为什么不够"：规模太大？要求实时？分布太乱？——答案决定 RL 有没有价值。
- 仿真器先于算法：OR 的 RL 依赖高质量问题模拟器；没有模拟器就没有数据。见RL 系统解剖"环境即产品"。
- 护栏与 fallback：RL 输出必须能回退到传统启发式；上线用"混合调度"逐步放量。
- 奖励设计要贴近真实成本：makespan 之外还有切换成本、能源成本、人效——把奖励工程做扎实再谈算法。
3. 离线 RL 在 OR 中的角色
真实调度系统积累了海量"历史调度日志 + 事后结果"。用离线 RL 从这些日志学"更好的调度策略"是当前研究热点，但要小心：
- 日志里只有"当时采用的策略"的决策，缺失"其他选择的后果"（反事实）；
- 调度环境高度非平稳（需求、机器故障、人员变动），历史分布快速过时。
4. 何时不要用学习式求解器
最后给一张"别用 RL"的清单，避免为用而用：
| 情形 | 为什么别用 |
|---|---|
| 实例规模小且固定 | MILP/CP 秒出精确解 |
| 实例结构高度同质 | 一个启发式就够，RL 学不到新东西 |
| 需求极度非平稳 | 训练分布持续失效，重训追不上变化 |
| 不允许近似解 | 有硬约束的最优性要求（如法律/审计） |
| 无模拟器/无数据 | 学习式求解器没有数据就是空转 |
这些情形与RL vs 相邻领域的"何时不用 RL"决策框架一脉相承：RL 是 OR 工具箱里的一件工具，不是整个工具箱。
5. 一个与 MILP 混合的落地蓝图
现实系统里 RL 与求解器混用，有一个可落地的蓝图（以车间调度为例）：
text
第 1 层 数据与实例：从 MES/APS 系统拿历史工单、机器、工艺数据 → 生成问题实例分布
第 2 层 学习式构造：GPN/Attention 模型秒出初始排程（毫秒级）→ 给调度员"起始点"
第 3 层 经典求解器：对"关键瓶颈周"跑 MILP/CP-SAT 精修（分钟级）→ 高质量最终排程
第 4 层 兜底规则：求解器超时/失败时回退优先规则（如 SPT/EDD）→ 保证永远有方案| 层 | 输出 | 耗时 | 作用 |
|---|---|---|---|
| 学习式构造 | 可用初始解 | 毫秒 | 兜底 + 热启动 |
| 求解器精修 | 高质量解 | 秒-分钟 | 提升解质量 |
| 规则回退 | 可行解 | 瞬时 | 可靠性最后防线 |
为什么这个分工合理：RL 负责"快"，求解器负责"准"，规则负责"稳"——三者互不抢戏，任何一层出问题都有下一层兜底。这比"让 RL 端到端取代调度系统"的现实可行度高一个量级，也与RL 系统解剖"安全护栏"层的思想一致。大多数工业 OR 项目的第一版，都应该是这个三层结构。
八、总结：RL × OR 的一张决策表
| 情形 | 用什么 | 说明 |
|---|---|---|
| 小规模、精确可行 | MILP/CP | RL 无意义 |
| 中等规模、结构稳定 | 启发式/求解器 | 先用经典，别急着 RL |
| 大规模、要求实时出解 | 学习式构造（RL 训练）+ 启发式兜底 | RL 主战场 |
| 环境持续演化、日志海量 | 离线 RL 预训练 + 在线微调 | 前沿方向，落地谨慎 |
| 多主体竞争（多租户/多承运） | 多智能体 RL（研究） | 现实中通常当噪声处理 |
TIP
给工程团队的一句话：在 OR 领域，RL 的第一个成功不是"替代求解器"，而是"让求解器更快"（神经引导搜索）。从"给现有系统加速"入手，比"端到端替代"现实得多，失败率也低得多。
延伸阅读
- 马尔可夫决策过程 —— 把 OR 问题写成 MDP 的全部形式化工具。
- RL vs 相邻领域 —— RL 与 OR、规划、搜索的边界辨析。
- 离线强化学习 —— 调度日志上离线学习的方法与陷阱。
- 多智能体强化学习 —— 多机协同调度、多租户资源分配的博弈视角。
- 奖励工程 —— makespan、成本、能耗多目标奖励的写法。
- 策略梯度方法 —— REINFORCE baseline、PPO 在求解器训练中的实现。
参考资料
- Vinyals, O., Fortunato, M., & Jaitly, N. (2015). Pointer Networks. NeurIPS 2015.（arXiv:1506.03134）
- Bello, I., et al. (2017). Neural Combinatorial Optimization with Reinforcement Learning. ICLR 2017.（发表于 ICLR 2017，2016 年 11 月提交预印本）
- Kool, W., van Hoof, H., & Welling, M. (2018). Attention, Learn to Solve Routing Problems! arXiv:1803.08475.（ICLR 2019）
- Nazari, M., et al. (2018). Reinforcement Learning for Solving the Vehicle Routing Problem. NeurIPS 2018.（arXiv:1802.04240）
- Zhang, C., et al. (2020). Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning. NeurIPS 2020.（arXiv:2010.12367）
- Gasse, M., et al. (2019). Exact Combinatorial Optimization with Graph Convolutional Neural Networks. NeurIPS 2019.（arXiv:1906.01629）
- DeepMind & Google 博客 (2018). Machine Learning for Network Routing（数据中心流量工程公开演示）。
- Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.（MDP 形式化与动态规划见第 3–4 章）