大邻域搜索用于车辆路径和资源调度，通过 destroy/repair 提升明显，但要覆盖城市配送、干线、仓内三类场景，领域算子越来越多，团队扩展慢，业务要求 30 秒出方案。作为技术负责人，你怎么设计算子体系、自适应权重、并行化、与精确/约束规划混合？如何组织跨团队算子贡献和回归验收？

面试官在考什么

判断能否构建可扩展 LNS 平台，做场景路由、算子治理和精确-启发式混合。

大邻域搜索

回答框架 · 前两步

1. LNS 核心：大邻域 destroy/repair，接受准则；破坏度与修复强度要匹配，太小退化成局部搜索，太大退化成重建。
2. 算子体系：随机、最差、相关、历史、路径移除，修复用贪婪、regret、精确小修复；按场景路由和算子白名单。

同一能力域的其他题

• 你说做过排产调度，用了遗传算法/模拟退火。请说明你的编码方式（染色体/状态表示）是什么？适应度函数里有没有加惩罚项？为什么？
• 你要实现一个最小化 0-1 整数规划的分支定界求解器。某实例根节点 LP 松弛下界 = 100，已知最优整数解 = 118。跑完 10 万个节点后 incumbent 仍是 118，open list 里还有 5 万个节点，其中最好的下界是 104。请回答：(a) 你用什么指标判断瓶颈在“下界太松”还是在“分支/节点选择策略差”？(b) 如果不改模型语义，只改界的紧度，列出两种手段并说明各自代价；(c) 当前 incumbent = 118，某子节点 LP 下界恰好等于 118 且解是分数，你是否剪枝，为什么？
• 一个 0-1 整数规划模型：200 个 0-1 变量、500 条约束，用求解器跑 1 小时，MIP gap 仍有 28%。日志显示 root LP relaxation 的目标值只比初始可行解好 5%，搜索树在第 3 层就展开出上万个节点。你会优先动哪几个地方？先动哪个、为什么？
• 你负责一个生产排程的混合整数规划求解服务：约 10 万变量，约束以背包和先后关系为主，16 核机器，当前分支定界跑 20 小时仍有 5% gap，LP 重求解占 80% 时间。业务要求 2 小时内给出可执行方案。团队提出三条路线：A 自研强分支+并行 B&B；B 增加问题特定割平面；C 改用约束规划/商用求解器或启发式先给可行解。作为技术负责人，你如何诊断瓶颈、排序路线、做 build/buy 取舍，并给出 90 天落地计划与验收指标？
• 整数规划：max z = 5x1 + 4x2，约束 2x1 + 3x2 ≤ 12，2x1 + x2 ≤ 7，x1, x2 ≥ 0 且取整。它的 LP 松弛最优解是 (x1, x2) = (2.25, 2.5)，z = 21.25。请回答：(1) 你会对哪个变量分支，两个子问题分别是什么，各自 LP 上界大概是多少；(2) 如果某个子问题的 LP 松弛最优解恰好是整数解，是不是就可以直接把它从待探索列表里删掉，为什么；(3) 搜索过程中的“当前下界”是怎么来的、什么时候更新它。
• 你用列生成求解一个集合覆盖型主问题（最小化总成本）。当前 RMP 的对偶解为 π = (3, 2, 5)（对应 3 个需求）。子问题返回一条覆盖需求 2 和 3、成本为 6 的列。请回答：(a) 这条列的 reduced cost 是多少？该不该加入 RMP？(b) 列生成收敛后 RMP 的 LP 最优值是 100，四舍五入得到的整数可行解是 115，这个 gap 你打算怎么处理？(c) 如果子问题改用启发式搜索而不是精确最短路，对 (b) 中的下界和剪枝会有什么影响？