运筹调度 / 04
调度、分配与资源约束
调度问题的本质，是在有限资源下做连续决策。即时物流派单、网约车匹配、客服排班、仓储拣货、广告预算分配都属于这一类。
调度难，不是因为单个规则复杂，而是因为目标多、约束多、状态变化快，而且当前决策会影响未来。
调度系统的基本结构
一个典型调度系统可以拆成四层：
- 状态感知：订单、骑手、车辆、库存、需求、位置、时间窗。
- 预测模型：ETA、需求量、接单概率、完成概率、风险概率。
- 决策优化：匹配、排序、路径、排班、预算分配。
- 反馈闭环：执行结果、异常 case、实验指标、策略复盘。
预测模型给优化器提供输入，优化器根据约束输出动作，反馈数据再回流训练和策略迭代。
订单分配
订单分配常见于外卖、即时零售、网约车、配送和客服系统。
基础问题：
- 哪个订单分给哪个资源。
- 是否允许一个资源同时服务多个订单。
- 分配后路径顺序是什么。
- 当前最优和未来最优如何平衡。
如果只看当前成本，可能会把关键资源用在低价值任务上，导致后续高价值任务无人服务。因此真实调度要考虑未来机会成本。
排班
排班是调度的上游。排班解决“未来某个时间和区域需要多少资源”的问题。
关键输入：
- 需求预测。
- 历史峰谷。
- 活动、天气、节假日。
- 人员可用时间。
- 成本预算。
- 服务水平要求。
排班做得不好，实时调度会很被动。如果晚高峰供给明显不足，实时调度再聪明也只能在差方案里选相对不差的。
资源约束
调度问题里的约束通常分为硬约束和软约束。
硬约束不能违反：
- 容量限制。
- 时间窗。
- 服务范围。
- 合规要求。
- 预算上限。
软约束可以违反但要付出代价：
- 骑手空驶距离。
- 用户等待时间。
- 工作量公平性。
- 策略稳定性。
- 成本平滑。
建模时要区分硬约束和软约束。把所有东西都设成硬约束，可能无解；把所有东西都设成软约束，可能损害体验或合规。
实时调度的难点
实时调度有几个典型挑战：
- 状态变化快：订单、位置、接单、取消随时变化。
- 决策时间短：系统不能长时间等待优化器。
- 预测有误差：ETA、需求、接单概率都不完美。
- 局部和全局冲突：当前最近不一定全局最优。
- 干扰效应强：一个资源的动作会影响其他资源可用性。
因此常用滚动优化：每隔一小段时间重新读取状态、生成候选、求解并执行部分动作。
目标函数示例
以即时物流为例：
minimize:
超时风险
+ 用户等待
+ 骑手空驶
+ 商家等待
+ 补贴成本
+ 公平性惩罚
+ 频繁改派惩罚
也可以用约束形式：
准时率 >= 目标阈值
补贴成本 <= 预算
骑手平均收入 >= 下限
在满足约束下最小化总配送成本
策略稳定性
调度不是每次算出更优就一定要改。频繁改派可能让骑手和用户体验变差，也会增加系统复杂度。
所以需要改派成本和稳定性约束：
- 已接单任务不轻易重排。
- 路径变化要有限制。
- 同一资源短时间内不频繁切策略。
- 高风险动作需要灰度。
仿真和回放
调度策略上线前通常要做回放和仿真。
回放：用历史订单和状态，模拟新策略在当时会做什么。
仿真：构建环境模型，模拟订单到达、资源移动、接单行为和异常。
回放更贴近历史，仿真更适合压力测试和极端场景。两者都不能完全替代线上实验，但可以降低试错风险。
面试题：如何提升配送准时率
回答框架：
- 先做归因：超时来自需求预测、供给不足、出餐慢、路径长、派单晚还是 ETA 错。
- 如果供给不足，优化排班和补贴。
- 如果派单不合理，优化候选生成、边权和匹配目标。
- 如果路径问题突出，引入路径规划和多单组合优化。
- 如果 ETA 偏乐观，做风险校准和承诺时效调整。
- 最后通过分区域、分时段实验验证。
面试题：为什么不能只优化平均配送时长
平均值会掩盖长尾。用户对超时和极端等待更敏感，所以要看 P90/P95、超时率、投诉率。只优化平均时长，可能牺牲一部分困难订单。
调度系统通常要同时看均值、分位数和失败率。
面试题：资源公平性怎么考虑
可以把公平性写进目标函数或约束。例如限制骑手收入差异、坏单比例、空驶距离分布，或者对长期低收益骑手增加补偿权重。
但公平性和效率可能冲突，需要业务定义底线，再在底线内优化效率。
总结
调度和分配不是简单的“把任务分给最近的人”。成熟方案要同时考虑预测、约束、实时性、未来机会成本、策略稳定性和实验验证。
如果你能在面试里把调度问题讲成“状态 -> 预测 -> 决策 -> 反馈”的闭环，会比只说一个匹配算法更有竞争力。