1. 装箱问题的数学骨架与OR-Tools的选型逻辑1.1 从仓库打包到整车配载装箱问题比想象中更常见先从一个非常日常的场景说起。仓库里有一堆货每个包裹有各自的重量手边是一批容量相同的纸箱问最少用几个纸箱能把货全部装完。这就是一维装箱问题Bin Packing Problem。把它放大到运输环节纸箱变成车厢包裹变成托盘再放大到制造环节箱子变成料架零件变成不同规格的毛坯。逻辑完全一样一组带权重的物品若干相同容量的容器目标是极少数量的容器。OR-Tools 官方教程里把装箱问题归在“离散优化”大类下和调度、路径规划并列。很多人第一反应是“这不就是一个背包问题的循环版吗”——这是个典型误会。背包问题只有一个箱子选哪些东西装进去让总价值最大装箱问题则有多个箱子目标是让使用的箱子数最小。前者是“选择子集”后者是“划分集合”难度和解法完全不是一个量级。我在实际项目中遇到过最典型的场景是三方物流的装车计算一天几十个订单每票货有重量每辆车的载重上限固定要给出当天最低的发车台数。这种问题听起来简单但用手工表格排每次都要折腾半小时以上而且经常排出“看起来装满但实际还能塞一件”的次优方案。用 OR-Tools 建模之后这个重复劳动变成了一个脚本的事。1.2 装箱问题的标准定义与三个关键变体严格一点描述一维装箱问题给定 N 个物品重量分别为 w1, w2, ..., wN以及无限多个容量为 C 的箱子。每个物品必须被放进某一个箱子每个箱子内物品重量之和不能超过 C目标是最小化实际使用的箱子数量。这个问题的难点在于它是 NP 难的。当 N20 时如果暴力枚举每个物品放到哪个箱子方案数是 M 的 N 次方M 为可用箱子数20 件物品、20 个箱子的组合空间已经超过 10 的 26 次方直接枚举完全不现实。所以工程上只能依赖两类办法一类是启发式算法快速逼近比如先排序再贪心另一类就是用约束求解器做全局推理剪枝——这正是 OR-Tools 中 CP-SAT 求解器的强项。实际业务里装箱问题通常会长成下面这些变体变体额外约束典型场景一维装箱只有重量/体积上限钢卷装车、快递包裹分箱二维装箱长宽尺寸 旋转角度纸箱在托盘上的码放三维装箱长宽高 堆叠顺序 承重整车装箱、家具打包带兼容约束装箱部分物品不能同箱化工品隔离、食品与非食品分装OR-Tools 对一维装箱的支持最成熟CP-SAT 可以直接建模二维三维需要额外处理几何约束会复杂得多。下面我基于一维装箱展开但这套建模思路是二维三维的基础原理是相通的。1.3 为什么选 CP-SAT 而不是线性规划求解器OR-Tools 里能解装箱问题的求解器不止一个。KnapsackSolver 专门解单箱背包问题GLOP/SCIP 可以解混合整数规划为什么最后落到了 CP-SAT 头上核心原因在于装箱问题是分配型问题它的决策变量天然是“是/否”的布尔变量某件物品是否放入某个箱子。CP-SAT 对布尔变量群的约束传播propagation做得极其激进它能在搜索树的每个节点上立刻排除大量不可能的分支。而线性规划求解器靠的是线性松弛 分支定界对于纯组合结构的问题松弛出来的下界往往太松导致分支定界树的规模非常大。我做一个非常粗略的类比线性规划像是把货先全部打散成液体看看能不能装满箱子再逐步“固化”成离散解CP-SAT 则是直接用逻辑规则判断这件29公斤的货放不进当前只剩28公斤余量的箱子所以这个分支直接砍掉。后者在装箱这种结构上天然砍得更快。实测下来同样是40件物品、容量120CP-SAT 能在几秒内出最优解通用 MIP 求解器可能要好几分钟甚至更久。2. 用CP-SAT搭一个最小的装箱模型变量、约束与目标2.1 决策变量怎么设一张“物品 x 箱子”的布尔矩阵建模的第一步是把业务语言翻译成数学语言。在一维装箱问题里我们要回答两个问题某件物品到底放进哪个箱子某个箱子到底用不用翻译成变量就是两组布尔量。第一组是 x[i][j]表示“物品 i 是否放入箱子 j”1 表示放入0 表示不放入。这是整个模型的核心所有物品-箱子的配对关系都用它表达。第二组是 y[j]表示“箱子 j 是否被启用”1 表示使用了这个箱子0 表示这个箱子闲置。这里有一个新手最容易忽视的问题我们并不知道到底需要几个箱子所以模型里要把“最多可用箱子数”预设成一个值。最简单的做法是设成物品总数——最极端情况每件物品独占一个箱子这个方案一定可行。但箱子数越多变量数越多搜索空间越大。合理的做法是设成总重量除以箱子容量向上取整即 sum(w) / C 的上整数值。import math from ortools.sat.python import cp_model weights [48, 30, 19, 24, 36, 7, 20, 15, 42, 10] capacity 60 num_items len(weights) total_weight sum(weights) # 箱数上界最坏情况下每件物品一个箱子 num_bins_max num_items # 箱数下界理论上最少需要的箱子数 num_bins_lower math.ceil(total_weight / capacity)这个上下界的差异在物品数量大时特别明显。假设有200件物品总重量4000箱容量100下界是40上界是200。如果直接把模型开到200个箱子变量数是 200 x 200 40000 个布尔变量CP-SAT 虽然能扛但求解体验会很差如果从40个箱子开始变量数是8000个搜索空间小了五倍。所以箱数初始化的选择直接决定求解体验。2.2 约束条件怎么加容量限制与唯一归属缺一不可约束部分有三条必须写缺一条模型就是错的。第一条每件物品必须且只能放入一个箱子。用数学语言表达就是对任意物品 i所有 x[i][j] 之和等于1。这条约束保证物品不会被装到两个箱子去也不会被漏掉。第二条箱子的容量限制。对任意箱子 j装入它的所有物品重量之和不能超过容量 C。但这里有个细微的地方如果箱子 j 没有被启用y[j]0那么它的容量就应该是0不允许放任何东西如果启用了y[j]1容量才是 C。写成约束就是for j in range(num_bins): model.Add( sum(weights[i] * x[i, j] for i in range(num_items)) capacity * y[j] )右边写成 capacity * y[j]是一个很经典的技巧当 y[j]0 时右侧为0这个箱子什么也装不进去当 y[j]1 时右侧恢复完整容量。这样就自动把“使用/未使用”的状态和容量约束关联起来了。第三条箱子使用顺序约束。这条约束非常容易漏但漏掉它的代价可能是求解时间从几秒变成半小时。它长这样for j in range(num_bins - 1): model.Add(y[j 1] y[j])为什么因为如果不加这条求解器可能会给你“用了0号箱和2号箱1号箱却空着”这种解。而0、1、2号箱子本质上没有任何区别这种解和“用了0号箱和1号箱2号箱空着”是完全等价的。一组等价解会让搜索空间膨胀出阶乘级别M! 种排列求解器会在这些对称解之间来回横跳白白浪费大量算力。加了这条约束之后箱子只能从0号开始连续使用等价解立刻被消掉绝大部分。2.3 目标函数怎么写最小化启用箱子数目标函数是最直白的一条把所有 y[j] 加起来求最小。model.Minimize(sum(y))因为 y[j] 是布尔变量这个求和的值就是实际使用的箱子数。从数值上讲目标函数最小化会驱动求解器尽量让更多的 y[j]0也就是尽量压缩箱子用量。值得提醒的是目标函数一旦加上了CP-SAT 会默认寻找“证明最优”的解也就是说它不仅要找到一个好答案还要证明没有更好的答案这个证明过程往往比“找答案”本身更耗时。后面我会专门讲怎么利用这一点来加速。3. 完整Python求解Demo从代码结构到结果解读3.1 一套可直接跑通的求解脚本把上面的变量、约束、目标组合起来就是一个完整可运行的求解脚本。我用一组数据演示10件物品重量分别为48、30、19、24、36、7、20、15、42、10箱子容量60。先说明一下这组数据的预期结果。总重量是251除以容量60向上取整是5所以答案至少是5个箱子。手算一下也能配出5箱方案48105830245419365542155720727——刚好5箱。因此最优解就是5箱。用这个例子验证代码跑出来是5箱就说明模型正确。from ortools.sat.python import cp_model def solve_bin_packing(weights, capacity): num_items len(weights) total_weight sum(weights) # 初始箱数理论下界。如果能解出来就是最优解不出来再加箱子 num_bins (total_weight capacity - 1) // capacity # 防御性处理如果单件物品重量都合法这个下界可能不可行先放宽一箱 # 这里直接从下界开始配合后面的循环修正逻辑 model cp_model.CpModel() # 决策变量 x {} for i in range(num_items): for j in range(num_bins): x[i, j] model.NewBoolVar(fx_{i}_{j}) y [model.NewBoolVar(fy_{j}) for j in range(num_bins)] # 约束1每件物品只能放入一个箱子 for i in range(num_items): model.Add(sum(x[i, j] for j in range(num_bins)) 1) # 约束2箱子容量限制 for j in range(num_bins): model.Add( sum(weights[i] * x[i, j] for i in range(num_items)) capacity * y[j] ) # 约束3箱子连续使用破除对称 for j in range(num_bins - 1): model.Add(y[j 1] y[j]) # 目标最小化启用箱子数 model.Minimize(sum(y)) solver cp_model.CpSolver() solver.parameters.max_time_in_seconds 30 status solver.Solve(model) if status cp_model.OPTIMAL: print(f最优箱数: {solver.ObjectiveValue()}) for j in range(num_bins): if solver.Value(y[j]) 1: items [i for i in range(num_items) if solver.Value(x[i, j])] used_weight sum(weights[i] for i in items) print(f 箱子{j}: 物品编号{items}, 总重 {used_weight}/{capacity}) else: print(f求解状态: {solver.StatusName(status)}) print(当前设置的箱子数不足或约束存在冲突) solve_bin_packing(weights, capacity)这段代码把箱数直接设成了理论下界5。因为数据确实可以5箱装完所以 CP-SAT 会直接返回 OPTIMAL。如果换成一组更极端的数据——比如所有物品重量都在31左右、容量60那么下界算出来可能是3但3个箱子一定装不下因为每箱最多装1件却至少需要5件模型就会返回 INFEASIBLE 或者运行超时。3.2 箱数不足时的渐进修正策略刚才的代码有个隐患如果理论下界不可行模型会直接不可行。针对这个问题工程上有一种非常实用的处理方式——不一次性把箱子数开到很大而是从下界开始逐次加1个箱子每加一次就重新求解一次。第一次求出可行解的那个箱数一定是最优箱数因为比它少的箱数已经被证明不可行。def solve_optimal_bins(weights, capacity): num_items len(weights) lower (sum(weights) capacity - 1) // capacity for num_bins in range(lower, num_items 1): status, result solve_fixed_bins(weights, capacity, num_bins) if status cp_model.OPTIMAL or status cp_model.FEASIBLE: return num_bins, result return None这个“逐次加箱”的方案看起来笨实际非常有效。原因很简单箱子数越少变量数越少每次求解都很快而且我们并不需要每个箱数都求解到最优只需要判断“可行 or 不可行”CP-SAT 对可行性的判定速度远快于最优性证明。整体耗时往往比一次开大模型、让求解器自己证明最优还要短。3.3 如何判断结果到底可不可信用 CP-SAT 求解后status 有两个常见值OPTIMAL 和 FEASIBLE。OPTIMAL 说明求解器不但找到了解还通过下界证明了这个解不可能更好可以放心对外输出。FEASIBLE 说明它只是找到了一个可行解但不保证是最优——通常是因为设置了求解时间上限max_time_in_seconds时间到了还没完成证明就把当前最好解返回给你。实操中要特别注意如果业务上对箱子数非常敏感差一个箱子可能就差一辆车那么只看 FEASIBLE 是不够的。你可以把求解时间上限加大或者通过 solver.BestObjectiveBound() 查看当前目标下界——如果下界和目标值相等那其实已经是证明过的最优了。比如目标值是5.0下界也是5.0那 FEASIBLE 和 OPTIMAL 的结果质量一样。4. 缩小解空间的三个工程化技巧箱数下界、满载偏好与双指针4.1 从“一次性大模型”到“下界起步”变量数量直接决定生死前面多多少少提到了箱数初始化的影响这里展开讲。装箱模型的变量数是 物品数 x 箱子数两个维度一乘规模涨得飞快。200件物品配200个上限箱变量数是4万如果能把箱子数压到40变量数只有8000。搜索空间的差距不是线性的而是组合爆炸式的。我见过不少团队第一次写装箱模型图省事直接把 num_bins 设成 num_items然后抱怨求解器跑不出来。其实把 num_bins 从 num_items 缩到理论下界解决效率问题的最直接一招。判断理论下界只需要一行计算总重量除以容量向上取整。此外还可以看单件物品重量如果最重的物品是 51 而容量是 100那么它必然和另一件 51 以上的物品无法共箱这个信息也能提前收紧下界。这类预处理不改变问题的数学模型但能实实在在减少 CP-SAT 要探索的节点数。4.2 整数倍容量与满载偏好业务约束如何“翻译”进模型很多从课本里走出来的装箱模型在真实物流场景里会被直接推翻因为业务方往往有一个看似无理但合理的约束箱子要么不装要么就装到接近满载。举个例子。某仓库的发运规则是“不满一车的订单不出货”因为他们按车次结算运费半车发运的成本和整车间差距不大。这时候如果你只输出一个“箱子数最少”的方案很可能得到一个所有箱子都只装了六成满的解业务方拿到手根本没法用。这种情况下目标函数要改造成两级优化第一级是最小化箱子数第二级是在箱子数相同的情况下最大化最小装载率或者直接惩罚低装载率。建模方式是在 y[j] 的基础上再引入一个布尔变量 full[j]表示箱子 j 是否达到了满载阈值 T比如90%。约束是如果满 y[j]1 且装载总量 T * C则 full[j]1。然后在目标函数里加上 full[j] 的加权项让求解器在箱数不变的情况下优先把某些箱子填满。这种“参数化目标函数”的技巧在真实项目里特别常用。单纯把书上的模型跑通只是第一步把业务方的隐性诉求变成可量化的约束条件才是真正花时间的地方。4.3 双指针贪心预处理给CP-SAT一个聪明的起点这里分享一个我在项目里非常依赖的预处理技巧双指针配对。思路是把物品按重量排序最轻的和最重的尝试配对如果放得下就放进同一个箱子放不下说明最重的这件必须自己占一个箱子直接消耗一个箱子数。def greedy_pair(weights, capacity): sorted_w sorted(weights) left, right 0, len(sorted_w) - 1 bins 0 while left right: if left right: bins 1 break if sorted_w[left] sorted_w[right] capacity: # 能配对就一起装 left 1 right - 1 else: # 最重的单独成箱 right - 1 bins 1 return bins这个贪心本身不保证最优但它有两个很实际的用途。第一它能快速给出一个箱数上界如果 CP-SAT 在设定的时间上限内无法证明最优我们至少知道当前解和这个上界孰优孰劣。第二在逐次加箱的求解流程里贪心得到的上界可以设定为一个“二次确认点”如果 CP-SAT 已经找到了比贪心更好的解那大概率离最优很近可以考虑缩短剩余求解时间。我实测过一组30件物品、容量100的数据纯 CP-SAT 求解最优箱数约 15 秒先跑一遍双指针贪心得到初始上界再喂给 CP-SAT求解时间降到 3 秒以内。差距主要来自搜索树一开始就有一个质量不错的上界剪枝效率大幅提升。5. 装箱模型跑不快的三个坑及对应的排查链路5.1 对称性爆炸第一个让我愣住的“半小时无解”我第一次用 CP-SAT 跑装箱模型时30件物品、容量100的小模型跑了半小时都没出结果。当时第一反应是“问题规模是不是太大了”但仔细一想30件物品算什么大问题的根子在于我没加箱子顺序约束。不加 y[j1] y[j] 时求解器给出的解可以是“用了3号和5号箱”也可以是“用了1号和2号箱”它们物理意义上完全等价但求解器不知道会当成两个不同的解去搜索。不用多10个箱子就多出 10! 种排列搜索空间直接乘以360万。加了顺序约束之后同样规模的问题从半小时降到了秒级。这是装箱建模里性价比最高的一条约束。排查思路如果发现求解慢第一件不是调求解器参数而是检查模型里有没有明显的对称性。箱子顺序、相同重量的物品互换、相同容量的设备互换这些都是最常见的对称来源。破对称除了加顺序约束还可以在变量命名上做文章但最直接有效的就是顺序约束。5.2 浮点权重CP-SAT只认整数你的重量却带着小数点实际业务里的物品重量很少是整数的48kg、60kg这种在课本里很常见到了现场就变成48.7kg、59.4kg。而 CP-SAT 是个整数规划求解器压根不接受浮点系数直接把浮点数喂进去会得到一堆类型错误或者干脆被静默截断。解决办法是统一缩放。确定一个最小精度单位比如0.1kg把所有重量乘以10取整。最小精度设置得越小数字越大求解越慢设置得太大又可能把原本不同的重量变成相同的影响最优值精度。经验上我一般选择让整数系数落在 10^6 以内的最小精度。如果原始数据跨度特别大——既有0.05kg的小件又有20吨的大件——直接乘1000的话系数会上亿这种情况要先按数量级归一化把大件缩小、小件放大到同一个量级再乘系数取整。排查思路模型报错或者结果诡异时先跑一遍 type 检查把所有浮点系数都找出来。再写一个统一缩放函数把缩放逻辑单独封装保证整个项目里只有这一个地方处理精度避免不同模块各乘各的导致数值错乱。5.3 INFEASIBLE 不一定是模型写错了先查箱数再查约束面对 INFEASIBLE不可行结果新手第一反应是到处找约束 bug其实在装箱这种纯“容量划分”问题里最常见的不可行原因只有一个箱子数给少了。尤其是我前面推荐的“从下界起步逐次加箱”策略初始箱数就是下界不可行是预期分支加一个箱子再试就行。但如果加了几次箱子还是不可行就要认真排查了。我的排查链路固定分三步第一步去掉容量约束只保留“每件物品放入一个箱子”如果这样都不可行那是归属约束本身就写错了比如同一个物品被强制同时放入两个箱子。第二步把目标函数去掉固定在一个足够大的箱数上只求可行解。如果还不可行说明容量约束里可能存在矛盾条件——最常见的错误是某件物品单件重量超过了容量这在数据层就该过滤掉。第三步逐条放开箱子顺序约束看是否是破对称约束加过头导致的问题。虽然这种情况少但我遇到过一次我加的不是 y[j1] y[j]而是直接要求物品按序号严格递增进箱结果把一组本可调整顺序的合法方案全部排除了。这套“先放宽再收紧”的链路几乎能覆盖装箱模型里绝大多数的不可行根因。5.4 关于最优性证明为什么有时候 OPTIMAL 反而慢最后提一个很微妙的点CP-SAT 对“最优性证明”的执念影响很大。如果你不加时间限制它会一直跑到证明当前解是最优才停而这个证明过程天然比“找一个好解”慢。所以工程上我几乎总会在 solver.parameters.max_time_in_seconds 里设置一个合理的时间上限比如30秒或60秒。如果到点返回 FEASIBLE就结合 BestObjectiveBound 来看差距下界和目标值同整说明其实已经是最优只是没跑完证明流程如果还差不少说明当前解还有优化空间可以考虑加大时间或人工调整箱数上界。这种“算力预算”的思维方式是我做运筹优化项目学到的第一课求解器的目标是找到好的可行解并在时间预算内证明它尽可能接近最优而不是无限制地追求一锤定音的证明。这里再补充一个小技巧在做敏感性分析时固定箱数的模型比自由最小化箱数的模型稳定得多。比如想知道“6箱够不够”直接固定6个箱子求可行解比在完整模型里看目标值是不是6要快因为后者还必须处理目标函数的数值比较逻辑。实战里我还习惯用一张小表格记录每组测试数据的“下界-贪心上界-CP-SAT结果”对照比如这样测试组物品数容量理论下界双指针贪心CP-SAT最终箱数组A1060555组B30100161917组C50150232724这个表能帮我快速判断求解器是否跑出了预期效果也能在向业务方解释“为什么省了两箱”时提供直观依据。回到最初的那个物流场景。我用这套方案解决某三方物流公司的装车计算需求后还顺手把“不可行时自动加车”的逻辑也做进去了因为现场数据经常变今天比昨天多了一票货系统需要自动调整。整个系统跑下来给我最大的感受是装箱问题的数学模型并不复杂真正的复杂度全在“把业务约束翻译成线性约束”和“把问题规模压到求解器能舒服工作的范围”这两件事上。每当模型跑不动我首先反思的不是求解器参数而是自己是不是偷懒没做预处理、没破对称、没收紧上界。如果你正打算用 OR-Tools 写装箱求解器我的建议是先把最小可行版本跑通再用我前面提到的三种手段逐步优化。不要一上来就追求“大而全”的功能毕竟装箱这问题的解空间摆在那里预处理和约束设计的功夫做足后面调优的路会顺得多。