企业官网建设流程全解析

有段时间我特别怕收到那种消息：“帮个忙，就三十来个订单，六台车，客户还有时间窗，你排一下呗。”听起来是个小事，真动手才发现，三十个订单的全排列是 30!，约等于 2.65×10³²，就算给我一台每秒算十亿次的机器，从宇宙大爆炸排到今天也排不完。这就是组合优化问题的典型面貌：问题规模看着不大，可行解的数量却像开了挂一样膨胀，而你还得在这么多可能性里挑出代价最小的那一个。

这篇是我在带课程第二章第一节（标题就叫“2-1 组合优化问题”）时整理的一份笔记，也是我自己做排产、路径规划、资源分配这些年踩出来的经验汇总。它不讲纯数学证明，讲的是组合优化到底是什么、为什么难、工业现场怎么建模、求解器怎么选、以及哪些地方最容易翻车。如果你刚开始接触运筹优化，或者做过几年业务系统但对“为什么算法跑不出来”一直没搞明白，这篇应该能帮你把整条链路串起来。

1. 组合优化到底在解什么

1.1 决策变量的离散性是分水岭

判断一个问题是不是组合优化，最省事的办法是看决策变量能不能连续取值。连续的问题，比如“这台机器开多大功率”“这一炉温度控制在多少度”，变量在区间里随便取值，那是连续优化，梯度下降、内点法这类方法就能上场。而组合优化里，变量通常是“选不选这台机器”“走不走这条边”“这个人排不排这个班”，取值只能是 0 或 1，或者某个整数编号，中间的过渡状态压根不存在。

这个区别带来的后果比想象中大得多。连续函数在局部是平滑的，你可以顺着斜率往下走，走错了还能退回来；离散的可行域是一堆散落的点，点与点之间什么都没有，你没法“沿着斜率走”，只能一个一个去试或者用某种规则跳着找。整数规划里最麻烦的就是这种“看不见地形”的特性——求解器不会告诉你“往左一点会更好”，它只能告诉你“左边那个点在不在可行域里”。

还有一个容易被忽略的点：变量离散之后，,约束的拓扑结构变得极其重要。同样是一百个 0-1 变量，如果约束是“总和不超过某个值”，问题可能十毫秒就解完了；如果约束里出现了成对关系、顺序关系、时间不重叠关系，难度立刻上一个台阶。我带人做项目时，看到有人把复杂的顺序约束硬塞进一个大不等式里，通常一眼就知道后面会出事。

1.2 目标函数和约束谁说了算

新手最容易犯的错，是把目标函数当成最重要的东西，花大量时间调权重，却忽略了约束才是决定求解难度的核心。目标函数只影响“往哪个方向找”，约束划定的是“哪里能站人”。可行域的形状一旦变得又窄又碎，求解器找可行解本身就要花掉绝大部分时间，目标值好不好反而成了次要矛盾。

举个实际的例子。做车辆调度时，“每辆车载重不超过 8 吨”是典型的能力约束，好处理；但“客户 B 必须在客户 A 之后 30 分钟到 90 分钟之间被访问”这种时间窗加序约束，会把可行域切得极其零碎。我做过一轮统计，同一个 25 客户的小规模实例，去掉时间窗部分求解耗时不到 1 秒，加上时间窗之后同一台机器跑了 8 分钟还没收敛到 1% 的 gap。

所以建模阶段有个很实用的判断原则：先把约束按“是否制造可行域碎片”分类。总量型、容量型约束通常温和，序关系、互斥关系、时间重叠关系通常凶悍。分类完再决定哪些约束必须硬性满足，哪些可以放宽成软约束进目标函数。这一步做不做，直接决定了后面要不要换算法。

1.3 什么时候该上模型，什么时候别碰

不是所有“看起来像优化”的问题都值得建模求解。我个人的经验判断线有三条，满足其中两条以上才值得动手：规模会持续增长（今天 30 个订单，明年 300 个）、约束会频繁变化（客户加时间窗、车辆加跨区限制）、人工排出来的方案有明显可优化空间（比如空驶率常年在 30% 以上）。

反过来说，如果一个场景订单量常年不超过 15 个，约束三年没变过，经验丰富的调度员五分钟就能排出八九不离十的方案，那上模型的收益大概率覆盖不了维护成本。求解器再好，也要人来维护数据接口、处理异常、解释结果，这些隐性成本新手基本不会算进去。

还有一种情况要特别警惕：问题本身没定义清楚。我遇到过项目，业务方说“我们要最优解”，追问下去发现“最优”其实指“司机别太累、客户别投诉、油耗别太高”，三个目标没有优先级，也没有量化口径。这种时候正确的做法是先花两周把评价口径统一，而不是急着写代码。

2. 那些反复出现的经典问题原型

组合优化有个好玩的地方：无论行业怎么变，最后都会归到有限的几个原型上。带过几个项目之后你会发现，所谓“新问题”绝大多数是经典原型的变体。认得原型，就能直接借用几十年的研究成果，不用从零想算法。

2.1 背包、指派、最短路：三个最基础的原型

0-1 背包问题是所有“选或不选、总资源有限”场景的抽象。变量是一组 0-1 变量 x_i，目标最大化价值总和，约束是重量总和不超过容量。听起来简单，但它已经是 NP-hard 的——二十个物品有 2²⁰ 种组合，四十个就是一万亿。实际业务里的预算分配、投资组合中“投不投这个标的”、仓库选址中“开不开这个仓”，本质都是背包或者多重背包。

指派问题处理的是“谁去做哪件事”的匹配关系，变量是 x_ij 表示第 i 个人做第 j 件事，约束是每行每列和都为 1。它的特殊之处在于约束矩阵是全幺模的，用线性规划松弛之后解出来天然就是整数，所以指派问题多项式时间可解，几百个规模秒出结果。匈牙利算法就是干这个的。但一旦加上“一个人最多做两件事”“某些任务必须由持证人员做”这类额外约束，幺模性被破坏，问题立刻掉进 NP-hard。

最短路问题是最容易被低估的一个。Dijkstra、Bellman-Ford 这些算法几乎是计算机专业的基础课，但实际场景里的“带资源约束最短路”（比如电动车续航有限、司机连续驾驶时间有限）就不再是多形式的了，必须上带状态的标号法或者直接建整数规划模型。

这三个原型的价值在于：它们构成了后面所有复杂问题的积木。VRP 是 TSP 加了容量和数量约束，排产可以拆成若干个带优先级的指派，网络设计可以看成带固定成本的背包叠加最短路。

2.2 TSP 与 VRP：路径类问题的统一视角

旅行商问题（TSP）的表述人尽皆知：走遍所有城市回到起点，总路程最短。它的经典解法体系非常值得学，因为后面所有路径问题都在复用这套思路。基础的建模用 MTZ 约束（Miller-Tucker-Zemlin）消除子回路，效果一般但简单；更强的是割平面法，通过不断加入“子集割”把松弛解里的子回路切掉；工程上最实用的还是2-opt / 3-opt / Or-opt 的局部搜索，配合邻域限制和大邻域搜索（LNS），几千个点的实例也能在分钟级找到接近最优的解。

VRP（车辆路径问题）就是把 TSP 加上“多辆车、每车容量有限、可能有时间窗”。它在学术上有几十个变体，带时间窗的 VRPTW、带取送的 PDPTW、带多车场的 MDVRP 等等。我的建议是不要一上来就啃变体文献，先把基础 CVRP 的模型跑通，再逐个叠加约束，每次加一个都重新测一遍求解时间。我见过太多项目一次性把所有业务约束堆进模型，结果求解器直接不收敛，最后只能推翻重来。

2.3 排产、装箱、集合覆盖：车间和后台的高频问题

车间排产（Job Shop / Flow Shop）的核心是“工序之间不能重叠、工序之间有先后”。它的建模通常用区间变量加 NoOverlap 约束，CP-SAT 这类基于约束规划的求解器比传统整数规划更擅长处理它。装箱问题（Bin Packing）是“把物品塞进尽量少的箱子”，物流装车、服务器资源调度、集装箱配载都是它。集合覆盖（Set Cover）则是“用最少的集合覆盖所有元素”，基站选址、消防站布局、测试用例最小化都是它的应用。

下面这张表是我自己整理的对照表，做需求评审的时候拿出来对一遍，基本能定位到该用哪个原型：

表格看着简单，但我要强调一句：真实业务几乎从来不是单一原型，而是两三个原型的叠加。比如“上门服务排程”实际是带时间窗的指派问题加上路径问题——先决定哪个师傅接哪几单，再决定每单的先后顺序。这种情况下分两层建模、分层求解，通常比强行揉成一个大模型效果更好。

3. 难度到底从哪来

3.1 组合爆炸的量化感受

我习惯用一组数字给学生建立直觉。10 个城市的 TSP，可能的巡回数是 (10-1)!/2 = 181440，随手就能穷举。15 个城市是 4.36×10¹⁰，个人电脑穷举要跑好几个小时。20 个城市是 6.08×10¹⁶，按每秒检查一亿条路径算，需要将近 20 年。到了 30 个城市，这个数字大到已经没有物理意义了。

背包也是一样。0-1 背包的搜索空间是 2ⁿ。n=30 是十亿级别，还能硬扛；n=50 是一千万亿级别，暴力法彻底没戏；n=100 就是 1.27×10³⁰，比地球上的沙子还多。关键在于，规模每增加 10 个物品，搜索空间就乘以 1024，这个增长速度远超任何硬件升级速度。

这就是为什么所有实用算法都在做同一件事：想尽办法不去枚举全部解。分支定界靠的是“这个子问题的下界已经比当前最优解差了，整枝剪掉”；动态规划靠的是“不同路径到达同一状态后，后续完全等价，可以合并”；启发式靠的是“只在一个有希望的邻域里搜索”。三种思路，本质上都是在砍搜索树。

3.2 NP-hard 在工程上的真实含义

很多人对 NP-hard 有个误解，以为意味着“绝对解不出来”。其实它的准确含义是：目前没有已知的多项式时间精确算法，而且如果某一个 NP-hard 问题找到了多项式算法，那所有 NP 问题都找到了。它说明的是问题难度的下限，不是“你的实例一定解不动”。

工程实践中真正重要的是：你的实例落在哪个区间。我按经验把实例分成四档：

• 小规模（变量 < 100 且约束简单）：精确算法秒解，直接上求解器。
• 中等规模（变量 100~10000）：精确算法能给出带 gap 的解，30 秒到几分钟不等，通常够用。
• 大规模（变量 10⁴~10⁶）：精确算法基本放弃，靠启发式或者“分解+组合”。
• 超大规模（变量 > 10⁶）：必须做问题特定的结构利用，通用求解器顶不住。

分档的变量阈值不是绝对的，强依赖约束结构。同样是 500 个 0-1 变量的背包，求解器可能 0.1 秒搞定；但 500 个变量的二次指派问题（QAP），可能跑一小时还在 gap 50% 附近晃悠。

3.3 LP 松弛与整数间隙

判断一个模型“紧不紧”，最直接的指标是整数间隙（integrality gap），也就是最优整数解和 LP 松弛最优解之间的相对差距。LP 松弛就是把所有“必须是整数”的要求去掉，变成连续线性规划，它能快速求解，同时给出原问题的一个下界（最小化问题时）。

间隙越小，说明 LP 松弛给出的“乐观估计”越接近真实情况，求解器剪枝就越狠。集合覆盖的 LP 松弛间隙可以做到 ln(n) 级别，而某些图着色或者二次问题，间隙能大到几倍甚至几十倍。我调模型的时候有个习惯：每次加完约束，先把 LP 松弛解打出来看。如果松弛解里一大堆 0.5、0.3 这种“半吊子”值，说明这版模型松得厉害，得想办法加割平面或者改写法。

有个具体的技巧分享：如果松弛解里出现大量分数值，可以试试加“整数性提升约束”，比如对某组互斥变量显式声明和不超过 1，或者对总量约束补一个“至少”方向的下界。这些约束在整数解上都是冗余的，但能显著收紧松弛，有时候效果比调求解器参数好得多。

4. 精确解还是近似解：怎么选

4.1 精确算法的三条主线

分支定界（Branch and Bound）是现代整数规划求解器的骨架。思路是：先解 LP 松弛，如果解已经是整数就结束；否则选一个分数变量分支成“=0”和“=1”两个子问题，递归下去，用下界剪枝。它的效率高度依赖下界的紧度和分支变量的选择策略。Gurobi、CPLEX、SCIP 这些商业或开源求解器，本质上都是分支定界加上大量预处理、割平面、启发式，把一棵巨大的搜索树砍到能跑完。

割平面法是往模型里动态添加“切掉分数解但不切掉任何整数解”的新约束。经典的 Gomory 割、覆盖割、Clique 割都属于这类。手工写割平面的人不多，但理解它的思想很重要——它解释了为什么求解器有时候跑到一半会突然报“添加了 xx 个割”。动态规划在背包、最短路、序列决策这些问题上效率极高，前提是状态能压缩。比如背包的 DP 状态是“前 i 个物品、容量 j”，状态数是 n×C，只要容量不是天文数字就能算。

4.2 启发式与元启发式：为什么它们在实际项目里更常见

精确算法保证最优，但代价是时间不可控。业务系统往往有硬性时间预算——用户点一下按钮，八秒内必须出结果。这时候启发式就成了主力。

• 贪心构造：按某种规则排序后逐个决策。TSP 里最近邻法、背包里按价值密度排序都是。速度极快，解质量一般，但是绝佳的初始解，几乎所有局部搜索都从贪心解出发。
• 局部搜索（2-opt / 3-opt / Or-opt）：在当前解附近做小改动，只接受变好的改动。实现简单，效果立竿见影，缺点是容易卡在局部最优。
• 模拟退火 / 禁忌搜索：允许接受变差的解来跳出局部最优。模拟退火靠温度参数控制“接受坏解的概率”，禁忌搜索靠一个短期记忆表禁止走回头路。这两个我在实际项目里用得最多。
• 大邻域搜索（LNS / ALNS）：每次破坏掉解的一部分（比如删掉 20% 的客户），再重新插入构造。ALNS 额外让多个破坏算子和修复算子按历史表现动态调整权重。这是目前 VRP 类问题上最实用的框架。
• 遗传算法 / 蚁群算法：群体智能类方法，适合解空间极其复杂、目标函数不规则的场景。调参比较玄学，我一般放在最后考虑。

4.3 一张选型表和推进节奏

推进节奏上我有个固定的四步法：先用 PuLP 或 OR-Tools 把模型写成最简单版本，只用小规模数据验证正确性；然后逐步加真实约束，每加一条记录求解时间；接着确定时间预算，选精确还是启发式；最后再做工程优化（热启动、增量求解、并行）。跳过第一步直接上启发式，是新手最常犯的错误——你连最优解长什么样都不知道，怎么判断启发式解得好不好。

5. 一个排产实例的完整建模推演

理论说完了，拿个具体问题走一遍。场景：一个车间有 2 台并行机器，4 个工件，每个工件的加工时长已知，每个工件只能在一台机器上加工一次且不可中断，目标是最小化最大完工时间（makespan）。规模很小，但足够把建模的每一个决策点讲清楚。

5.1 从业务语言到决策变量

业务语言是“哪个工件在哪台机器上做、从什么时候开始做”。翻译成数学变量需要三组：

• 每台机器上每个工件的开工时刻s[j,m]，取整数，范围 0 到时间上限；
• 每个工件在每个机器上的是否分配p[j,m]，0-1 变量；
• 由 s 和加工时长推导出的区间变量interval[j,m]，这个区间只在 p[j,m]=1 时“存在”。

这三组变量里，区间变量是最关键的抽象。用普通的线性约束也能表达“两个任务不能重叠”，但写法是“s_a + d_a ≤ s_b 或 s_b + d_b ≤ s_a”这种析取式，需要引入大 M 变成混合整数约束，不仅难看，松弛还特别松。用区间变量加NoOverlap约束，求解器内部会做专门的传播和检测，效率和可读性都高一个档次。

这里有个经验：只要问题里出现“资源在时间上不能重叠”，优先考虑约束规划风格的建模，别硬凹成纯线性。OR-Tools 的 CP-SAT 在这一点上的优势非常明显，我做过对比，同样的排产实例，CP-SAT 建模的解通常比手工写大 M 的整数模型快三到十倍。

5.2 大 M 法、线性化与模型松紧度

如果非要用线性模型，大 M 是绕不开的。比如“工件 j 在机器 m 上加工”和“机器 m 在 t 时刻只能处理一个工件”之间的关系，常用写法是：

s[j2] >= s[j1] + d[j1] - M * (1 - y)

其中 y 是 0-1 变量，表示 j1 是否排在 j2 前面，M 是一个“足够大”的常数。这里的 M 取值是个大坑。M 太大，LP 松弛会变得极其宽松，求解器剪枝困难，还容易引发数值问题；M 太小，约束会失效，解出来的方案根本不可行。

我的做法是用变量的真实上界代替拍脑袋的 M。比如上面这个约束，M 的合理取值是horizon - d[j1]，而不是随便写个 100000。还有个小技巧：如果能在预处理阶段算出一个更紧的时间上界（比如所有工件总时长），一定用它，模型会紧不少。

另一个高频需求是线性化乘积项。比如成本写成“是否分配 × 分配顺序”的乘积，这就是非线性的。标准做法是引入辅助变量 z = x·y，加三条约束把它夹住（z ≤ x，z ≤ y，z ≥ x + y - 1）。这个技巧不复杂，但很多人写了半天没意识到自己写了个非线性模型，然后奇怪求解器为什么报错。

5.3 求解器不收敛时，先查这三件事

第一，对称性。并行机器之间是完全对称的——把机器 1 和机器 2 的方案整体对调，目标值一样。这种对称会让搜索树的规模直接乘以 m!（m 是机器数），求解器要反复证明“这两个镜像解等价”。解决办法是加对称破缺约束，最常用的是字典序约束：强制工件编号小的优先分配给小序号机器，形式是p[j, m] <= sum(p[j', m'] for j' < j, m' <= m)这类写法。加了之后我的实测数据是求解时间下降 4 到 20 倍不等，规模越大收益越明显。

第二，数值尺度。求解器的默认容差是 1e-6 量级。如果模型里某些系数是 0.001，另一些是 1000000，跨度超过 10¹²，浮点运算就会出问题，表现为“求解器说找到了解但检查发现约束违反了”。我的做法是统一量纲，让所有系数落在 1e-3 到 1e6 之间。

第三，目标函数的权重。多目标加权求和的时候，如果两个目标的量级差了几个数量级，大的那个会完全压过小的。先做归一化，或者用分层求解（先优化主目标，再把主目标固定成约束优化次目标），比调权重靠谱得多。

5.4 代码起手式

下面这段是上面那个排产实例的 CP-SAT 实现，可以直接跑：

from ortools.sat.python import cp_model jobs = {"J1": 12, "J2": 25, "J3": 18, "J4": 9} machines = 2 horizon = sum(jobs.values()) # 用真实上界，不要拍脑袋写大数 model = cp_model.CpModel() intervals, ends = {}, {} for m in range(machines): for j, dur in jobs.items(): s = model.NewIntVar(0, horizon, f"s_{j}_{m}") e = model.NewIntVar(0, horizon, f"e_{j}_{m}") present = model.NewBoolVar(f"p_{j}_{m}") intervals[j, m] = model.NewOptionalIntervalVar( s, dur, e, present, f"itv_{j}_{m}") ends[j, m] = e # 同一台机器上的任务时间不能重叠 model.AddNoOverlap([intervals[j, m] for j in jobs]) # 每个工件只能选一台机器 for j in jobs: model.AddExactlyOne(intervals[j, m] for m in range(machines)) makespan = model.NewIntVar(0, horizon, "makespan") model.AddMaxEquality(makespan, list(ends.values())) model.Minimize(makespan) solver = cp_model.CpSolver() solver.parameters.max_time_in_seconds = 10 solver.parameters.relative_gap_limit = 0.01 status = solver.Solve(model) print(solver.StatusName(status), solver.ObjectiveValue())

两个参数值得单独说。max_time_in_seconds给了硬性时间上限，超时就返回当前最好解，这在业务系统里比“一定求最优”重要得多。relative_gap_limit是提前收工的开关，gap 小于 1% 就停，对绝大多数业务场景这个精度完全够用，而它能省掉大量用来“证明最优”的时间。

如果做的是 TSP 类的路径问题，启发式那套更顺手：

def two_opt(tour, dist, max_pass=200): best, improved, p = tour[:], True, 0 while improved and p < max_pass: improved, p = False, p + 1 for i in range(1, len(best) - 1): for k in range(i + 1, len(best)): a, b = best[i - 1], best[i] c, d = best[k], best[(k + 1) % len(best)] if dist[a][c] + dist[b][d] < dist[a][b] + dist[c][d]: best[i:k + 1] = best[i:k + 1][::-1] improved = True return best

这是我压箱底的 2-opt 简版，几十行不到，几百个点的路径问题通常能比最近邻初始解改善 15%~25%。真正上生产的话，我会把它嵌进 ALNS 框架里，外层做破坏修复，内层用 2-opt 精修。

6. 上线之后才开始的那些坑

模型跑通只是万里长征第一步，真正磨人的是上线之后。这几件事我几乎每个项目都会遇到，列出来给你提个醒。

6.1 数据质量决定算法上限

算法再好，喂进去的数据有错，出来的方案就是废的。我遇到过的典型问题包括：距离矩阵用的是直线距离但实际要绕路、客户时间窗从 Excel 导入时被格式化成了整数、某些订单的载重要求和体积要求互相矛盾、还有最经典的“同一个客户在系统里有两个地址”。上线前一定要做数据体检：空值检查、量纲检查、约束可行性预检（比如总需求是否超过总运力）。

约束可行性预检特别重要。如果业务数据本身就让问题无解，求解器只会返回 INFEASIBLE，但不会告诉你哪条约束冲突。这时候需要把模型的约束一条条关掉重跑，用二分法定位冲突源。我现在的习惯是先把所有硬约束都改成软约束加惩罚，跑出解来之后再看哪些惩罚项被触发，这样既避免了无解，又能反推数据问题。

6.2 时间预算要和业务节奏对齐

我做过一个配送排程项目，第一版模型在测试集上跑得挺好，平均 40 秒出结果，业务方看了没意见。上线之后才发现，调度员的实际操作节奏是“边看边改”——改一个订单就要重算一次，40 秒根本等不了。后来改成两段式：先跑 3 秒出一个可用的粗解，后台继续算 60 秒再替换成精解，体验一下子顺了。

这里的经验是永远给求解器设时间上限，并且分档出解。OR-Tools 支持注册回调，在求解过程中捕获每一个改进解，我就用这个机制把“3 秒首个可行解、10 秒次优解、60 秒最终解”三级方案推给前端。用户看到进度条在动，容忍度会高很多。

6.3 解的稳定性和可解释性

算法解出来的方案，如果每次运行都和上次差很多，调度员会直接不信任它。我遇到过一次，两个方案的 makespan 只差 0.3%，但任务分配完全不同，调度员看了一脸懵：“上次挺好的，这次怎么全变了？”后来我在目标函数里加了一个稳定性惩罚项，对偏离上一版方案的操作加一个很小的成本，方案就稳定多了。

可解释性同样重要。求解器只会给你一堆变量取值，业务人员看不懂。我一般会做一个“变更报告”：相比人工方案，哪些订单换了车、为什么换（比如“合并后节省 12 公里”）。有了归因，人才愿意接受算法建议。纯黑盒的方案，哪怕真优化了，落地的阻力也会大很多。

6.4 热启动与增量求解

每次改动都从头算，是最浪费的做法。我常用的两个优化：

一是热启动。把上一次的解作为初始解喂给求解器，很多求解器（包括 CP-SAT）都支持通过AddHint给变量赋初始值。在有时间上限的情况下，一个好的初始解能显著提升最终解的质量。

二是增量求解。如果只是加了几个订单、改了一个时间窗，不需要重建整个模型。CP-SAT 支持修改已有模型的部分约束后重新求解，比从零建模省下大量预处理时间。我做过对比，增量求解在“小改动”场景下通常能把响应时间压到原来的三分之一左右。

最后分享个我自己的小习惯：每次模型调优，我都会用固定的一组测试实例跑一遍回归，记录目标值、求解时间、gap 三个指标，存成 CSV。调参这件事太容易陷入“改了这个坏了那个”的循环，有回归数据打底，至少知道自己是往前走了还是原地打转。这个习惯看着笨，但真的省了我不少返工的时间。