运筹调度 / 03
启发式、局部搜索与元启发式
很多工业优化问题没有时间求全局最优。即时物流、广告竞价、仓储调度、车辆路径规划都要求在很短时间内给出可行解。这时启发式比精确求解更常见。
启发式的目标不是证明最优，而是在有限时间内找到稳定、可解释、足够好的解。
为什么不能总用精确求解
原因主要有四个：
- 问题规模大：变量和约束数量随订单、骑手、路径组合爆炸。
- 实时性强：在线系统可能只给几十毫秒到几秒。
- 输入不确定：需求、ETA、接单概率都是预测值，不值得为有噪声的输入追求精确最优。
- 工程稳定性：精确求解器超时或不可行会影响线上服务。
所以工业系统常采用“规则生成候选 + 模型打分 + 启发式优化 + 兜底策略”的组合。
贪心算法
贪心是最简单的启发式：每一步选择当前看起来最好的动作。
例如订单分配：
- 按订单紧急程度排序。
- 对每个订单选择成本最低的可用骑手。
- 更新骑手状态。
优点是快、简单、稳定。缺点是短视，容易局部最优。比如当前最近的骑手可能更适合后面更紧急的订单。
面试时可以说：贪心适合做 baseline 或兜底策略，但核心策略需要考虑全局和未来机会成本。
局部搜索
局部搜索从一个可行解出发，不断做小范围调整，让目标函数变好。
常见操作：
- swap：交换两个订单的骑手。
- insert：把一个订单插入另一个骑手路径。
- relocate：把任务从一个资源移到另一个资源。
- 2-opt：优化路径顺序。
局部搜索适合路径、排班、调度等组合优化问题。它的关键是设计邻域动作和停止条件。
Beam Search
Beam search 在序列决策里常用。它每一步保留 top K 个候选状态，而不是只保留一个最优状态。
在调度里，可以把订单按时间处理，每一步扩展若干个分配方案，只保留成本最低的 K 个。这样比贪心更不容易短视，但计算量仍可控。
Beam size 越大，解质量可能越好，但耗时也越高。
模拟退火
模拟退火允许偶尔接受更差的解，以跳出局部最优。温度高时探索更多，温度低时逐渐收敛。
适用场景：
- 排班。
- 路径规划。
- 组合分配。
- 目标函数复杂但可快速计算。
缺点是参数敏感，线上实时场景要谨慎。更常用于离线规划或候选方案优化。
遗传算法
遗传算法把一个方案看作个体，通过选择、交叉、变异产生新方案。它适合搜索空间大、目标函数复杂的问题。
在业务里，遗传算法常用于排班、路径、选址、组合推荐等离线优化。但它解释性和稳定性较弱，面试时不要把它当万能答案。
机器学习辅助启发式
现在很多系统会用模型辅助搜索：
- 模型预测某个候选动作的价值。
- 模型估计未来机会成本。
- 模型选择搜索顺序。
- 模型剪枝，减少无效候选。
例如骑手调度中，先生成一批可行动作，再用模型预测动作对未来准时率的影响，最后由优化器选出满足约束的动作组合。
如何评价启发式
评价启发式不能只看一次结果。
需要看：
- 解质量：目标函数比 baseline 好多少。
- 稳定性：不同场景下是否波动。
- 耗时：P50/P90/P99 延迟。
- 可行率：是否经常违反约束。
- 可解释性：业务能否理解和调参。
- 线上收益：A/B 实验是否提升业务指标。
面试题：精确解和启发式怎么取舍
理想回答：
如果问题规模小、实时性要求低、约束清晰，我会优先用精确优化，因为可解释且有最优性保证。如果在线规模大或决策时间短，我会先用候选裁剪降低规模，再尝试快速匹配或 min-cost flow；如果仍然太慢，就用贪心、局部搜索或 beam search，并设置耗时上限和兜底策略。最终用仿真和 A/B 实验比较解质量和业务指标。
面试题：局部搜索容易卡住怎么办
可以从四个方向回答：
- 扩大邻域：允许更复杂的 swap 或 insert。
- 多初始解：从不同贪心策略开始搜索。
- 随机扰动：跳出局部最优。
- 分阶段优化：先满足硬约束，再优化软目标。
工业落地注意点
启发式上线要保证可控：
- 每一步都产生可行解。
- 设置最大迭代次数和耗时上限。
- 任何异常都能退回 baseline。
- 关键参数可配置。
- 记录搜索过程，方便复盘 bad case。
总结
启发式不是“低级方案”，而是工业调度里非常实用的工具。面试中成熟的回答不是堆算法名，而是说明为什么需要近似、如何保证可行、如何控制延迟、如何验证收益。
下一篇建议继续看：