模拟退火求解二维装箱问题：原理、实现与工程调优

模拟退火算法求解装箱问题我第一次真正上手是在一个托盘排样项目里。需求方只说了一句话把尺寸不一的纸箱尽量多地放进托盘允许90度旋转不许压坏。我当时觉得这就是矩形排样先求个面积下界再排进去就行。结果一动手就发现“尽量多”三个字后面藏着一堆约束物品不能重叠、不能超出容器边界、前后工序要留空、部分箱子还不能压在别的箱子上。每加一条约束可行的空间就缩一圈。正式讲装箱问题前我们先把模型收敛到大多数文献和代码里用的版本给定一个宽度固定的容器高度可视为无限给定 n 个矩形物品每个有宽 w_i 和高 h_i允许旋转90度目标是让占用总高度尽量小。这个版本叫二维开放尺寸装箱问题。它既可以直接衡量码垛高度也可以折算成面积利用率。为什么强调开放尺寸因为现实中托盘或车厢往往不是预先定死高度高度取决于你怎么码固定高度之后反而变成更难判断的“能否全部装入”的决策问题。面积利用率听起来只是 sum(w_i*h_i) / (W * H)但面积下界只是天花板。真正的难点在于空间协调。比如40件物品总面积只有容器面积的85%看似一定能装满可是如果其中有一件长条形的物件宽度接近容器宽度它就会把整层空间一分为二剩下很多小碎片根本排不下。面积有余量位置却不一定是连续可利用的。装箱问题的本质不是总量问题而是空间切分的组合问题。1. 装箱问题到底难在哪为什么需要一个“退火”方案1.1 一个看似只是“按面积排”的问题几年前我接到这类需求时还想过直接用整数规划模型硬解变量是每个物品放不放、旋转方向、位置坐标再加防重叠约束。对15到20个物品商业求解器确实能在秒级到分钟级跑完到30个物品很多实例已经肉眼可见地变慢到50个以上除非数据有非常强的特殊结构否则求解器很难在项目要求的两三分钟内给出一个稳定可行解。原因不复杂位置变量连续、物品数量联合组合解空间是一个非凸的破碎集合。这里真正要处理的不是一个线性规划问题而是一个组合优化问题。拿20个矩形物品举例每个物品有两种旋转方向仅仅是“放哪些、按什么顺序放”就已经让枚举数变成天文数字。精确算法在数学上优雅但落地时面对“客户在会议室等一份排布图”的现实基本没有操作空间。那贪心法总可以吧按宽度降序排大件先占住关键位置后面小件见缝插针。它快是真快但没有后悔药某个关键大件的朝向选错可能让后续整段布局多出十几厘米空隙某一层的小箱子排得太密集下一层的大箱子就进不来。贪心每一层只盯当前最优没有办法从全局角度退回去修正。模拟退火恰好补上这个短板。它不追求每一步都更好而是通过概率接受较差解在高温阶段像无头苍蝇一样探索在低温阶段慢慢收拢到低能量状态最终找到一个比贪心强得多的方案。严格说它给的不是数学最优解但在工程尺度下稳定可靠、能在秒级到分钟级出结果已经足够用了。1.2 组合爆炸和可行域破碎是两座大山很多人以为装箱难只是因为“可能性太多”其实还有第二层原因可行解在空间里不是连续成片的。你从当前布局出发随便把一个箱子挪开一格可能立刻和旁边的箱子重叠再挪回去又发现另一个位置放不下。坐标空间里的合法邻居非常稀疏这导致很多基于梯度的思路完全失效。这也是为什么启发式算法在这个领域占主导。严格说模拟退火属于元启发式它不假设目标函数可导、可凸只需要你能计算“当前布局好不好”以及“怎么从当前布局小步变形到附近布局”。对装箱问题来说这两件事恰恰都能做只是需要一点设计技巧。把这些设计好算法框架就立住了。2. 模拟退火的核心机制什么时候退一步才是向前2.1 从金属热处理到优化搜索的映射模拟退火Simulated AnnealingSA这个名字听起来玄原理其实就是模仿金属热处理高温下原子剧烈运动系统能量很高缓慢降温后原子逐渐找到低能量排列。如果冷却过快金属内部会留下应力和缺陷。算法也一样——高温阶段允许乱走低温阶段收敛到稳定结构。放到装箱问题里解就是一套装箱方案目标函数是占用高度或空隙面积相当于系统能量。当前解变成邻居解就是一次原子移动。算法在温度高时用随机扰动跳出局部最优在温度低时集中精修。整个过程的关键是“慢冷”也就是温度衰减不能太快。温度下降太快的效果你自己都可以模拟前几轮还没跑开就进入局部最优后面再怎么精修都修不出来。2.2 Metropolis准则与接受概率的温度意义这里需要公式。设当前解对应的目标函数值为 E邻居解的目标函数值为 E差值为 ΔE E - E。最小化目标时如果 ΔE 0说明邻居解更好直接接受如果 ΔE 0说明它更差不是直接拒绝而是以概率 exp(-ΔE/T) 接受它。T 是当前温度。温度越高接受差解的概率越大温差越大概率越小。一个让入门者困惑的点是为什么明明更差的解还要接受因为局部最优附近的邻居解往往都不“更好”如果不接受差解你爬山爬到半山腰就停住了。差解像一条临时隧道虽然先把目标值拉高但可能通向另一个更低的山谷。Metropolis准则本质上给搜索过程提供了“爬山”能力。很多人会把接受概率理解成“瞎碰运气”其实它很有讲究在高温阶段尝试多远都可以随着温度降低尝试范围逐渐收窄最后只在当前解附近微调。这和“退火”的物理本质是一致的先粗搜索再精搜索。温度曲线设计得好算法就能平衡探索与利用。2.3 算法骨架与代码结构具体实现上我一般写成下面这样import math import random def simulated_annealing(seq, T0100.0, alpha0.995, L200, T_end0.01): cur_seq seq[:] best_seq seq[:] cur_val evaluate(cur_seq) best_val cur_val T T0 while T T_end: for _ in range(L): new_seq neighbor(cur_seq) new_val evaluate(new_seq) delta new_val - cur_val if delta 0 or random.random() math.exp(-delta / T): cur_seq new_seq cur_val new_val if cur_val best_val: best_val cur_val best_seq cur_seq[:] T * alpha return best_seq, best_val这里有几个细节容易被忽略。第一内循环里不要每次移动后都把当前位置恢复成最优解否则高温阶段接受差解的能力被架空就无法跳出局部最优。第二一定记录独立最优解。我之前吃过亏只记录最后收敛解结果后续随机扰动把中期出现过的最优布局弄丢了高温阶段接受了一堆差解最终解完全不如中途某个好解。第三math.exp(-delta / T)只适用于目标值越小越好的设定。如果你的目标函数还有重量、成本等量纲最好预先归一化否则 ΔE 动不动上千接受概率会迅速塌缩到0。到这里SA的骨架已经清楚了。接下来真正决定成败的是两个函数evaluate和neighbor。装箱问题里这两个函数的设计质量远比调参更影响最终效果。3. 用序列化表示破解二维装箱的邻域搜索3.1 别直接用坐标做扰动第一次实现时最容易犯的错误是把每个物品的坐标当成状态随机移动某个物品的 x y 坐标。直觉上很直接但在密集排列的场景里随便动一个坐标几乎立刻产生重叠合法邻居极少。你生成一万个邻居九千九百个非法剩下的也像打地鼠一样按下这个洞冒出来那个洞。坐标空间的可行域是不连续且破碎的邻域搜索效率极低。更通用的做法是换一种状态表示把布局定义为一个排列序列配合同一个确定性的放置规则。这样不管序列怎么变布局都能在几毫秒内重建出来而且不会出现随机坐标扰动造成的重叠。序列搜索虽然牺牲了部分直观性但换来的是稳定性和可复现性。后面你换任何启发式框架这套编码都能平移过去。3.2 序列加旋转标记的编码方式我采用的表示是一个物品数组每个物品大概是这样的结构(item_id, w, h, rotate)rotate0表示保持原始宽高rotate1表示交换宽高。真正参与搜索时状态包含两部分信息物品排列顺序以及每件物品是否旋转。顺序由邻域操作改变旋转可以单独操作。选择这种编码有几个理由。第一变化维度少直观第二它天然保证物品不会重叠因为最终放在哪里完全由放置规则计算不需要在解码时做复杂的重叠修复第三便于和遗传、禁忌搜索等其他启发式组合。缺点是搜索空间里有大量序列对应同一个布局存在冗余但工程上完全可接受。还有一个小优化正方形物品的两种旋转状态其实一样翻转只会产生无效邻居。可以在初始化时把正方形物品标记为固定方向翻转操作直接跳过能减少一部分无意义计算。3.3 BLF放置策略把序列变成布局序列本身不是布局。我们需要一个确定性解码器把序列翻译成坐标。我常用的是 Bottom-Left FillBLF策略。简单说按序列顺序扫描所有物品每件物品尝试放到最低可用的空隙同高度下尽量向左。伪代码大概是这样的def decode(items, W): placed [] max_h 0 for item in items: w, h item[w], item[h] best None # (x, y, total_height) for x, y in candidate_positions(placed, W): if not fits(x, y, w, h, placed, W): continue total max(max_h, y h) if best is None or total best[2]: best (x, y, total) if best is None: x, y 0, max_h else: x, y, _ best placed.append((x, y, w, h)) max_h max(max_h, y h) return max_h, placedfits函数做的是矩形碰撞检测如果新矩形与任意已放置矩形在平面上有面积重叠或者超出容器左右边界就返回 False。candidate_positions不需要枚举所有像素点只用已放置矩形的四个角点、容器左边界和当前最高层的上方位置做候选复杂度会低很多。BLF的优点就是布局稳定、代码干净。但它也有局限某个序列下 BLF 布局明显差不代表这个序列本身差它可能只是被解码器坑了。所以不要把解码器和搜索算法绑死后面可以换更复杂的 skyline 或最大空隙算法。解码器越灵活同样的序列往往能给出更好的布局搜索效率也会上一个台阶。3.4 四个常用的邻域动作邻域动作是 SA 的动力来源。我主要用四个操作交换随机选两个物品交换它们在序列里的位置。插入随机选一个物品拿出来插入到另一个位置。翻转随机选一件物品切换 rotate 状态。块交换随机选一段连续物品反转这个段内的顺序。交换操作改变两个物品在放置顺序中的权重对布局影响相对局部插入操作对局部顺序扰动更大块交换适用于打破长段连锁放置有时候能一下把一整条卡住的空间松绑。翻转操作则专门处理方向选择错误。比较常见的配置是每次生成邻居时按权重依次选操作比如交换40%、插入30%、翻转20%、块交换10%。这个比例不是绝对标准要根据算例调整。如果物品尺寸差异大翻转操作很关键如果物品尺寸接近顺序上的交换和插入更有效。生成邻居后如果新解和当前解目标值相同不要立即放弃可以再走一步。也可以一次性生成 k 个候选解挑一个按 SA 准则接受但 k 过大时计算量会明显增加。我在中等规模算例上通常 k1靠多次独立运行来弥补随机性。4. 参数调整与实验复盘从初始解到接近90%利用率4.1 评测指标和实验数据集先定义两个最常见的评测指标一是容器占用高度二是面积利用率。面积利用率 sum(w_i * h_i) / (W * used_height) * 100%。为什么用面积利用率而不是单纯高度因为不同方案下容器高度不同面积利用率能统一反映空间节省效果。我拿一个常见的二维托盘排样算例做实验容器宽度 W1800物品数量从20、50、100变化物品尺寸在300到600之间随机生成长宽比控制在1:1到2.5:1允许旋转90度。初始解用高度降序贪心生成再跑模拟退火。物品尺寸建议统一用整数毫米避免浮点坐标在重叠检测时产生边界误差。这里需要提前处理特殊边界物品宽度在旋转后仍超过容器宽度时直接判定不可放入所有物品面积之和超过 W * 当前使用高度时说明当前高度一定非法目标应包含惩罚项。工程上我习惯把“未放置的物品数”也纳入目标函数宁可给一个较大的惩罚也不要在运行中直接丢弃某些物品。4.2 调参的正确思路先调温度再调邻居我见过很多人一上来就盯住 alpha 不放把 0.99 调到 0.995调半天效果不大。更有效的思路是先看初始温度 T0 是否让初始接受率落在合理区间。如果你的初始温度过低算法一开始就进入“几乎不接受差解”的局部精修模式过高则前面十几轮都在乱跑浪费计算量。我的经验是随机采样一批邻居计算平均目标差值然后让 T0 大约是平均差值的5到10倍。这样可以保证初始接受率大概在0.8到0.95之间。不同算例的目标值尺度差别很大直接拍脑袋给一个固定 T0 会失效。冷却系数 alpha 决定温度下降速度。0.9太激进0.999太慢常用范围是0.95到0.998。100个物品时从0.98改为0.998迭代次数大约翻好几倍效果提升不一定成正比要结合运行时长看。终止温度 T_end 可以设得很低比如0.01主要作用是当温度足够低时退出循环。内循环次数 L 我一般取物品数量的10到50倍。物品越多每次邻域操作影响越小需要更多内循环来保证充分采样。定向工程中如果时间预算有限可以先把 alpha 提高到0.99减少 L保证在有限迭代内看到更明显的降温过程。4.3 三组固定规模算例的典型表现我用三组固定规模数据每组用20个随机种子各跑一次取其中最优结果。结果大致如下物品数贪心初始利用率SA后利用率平均耗时2071.2%93.5%0.4秒5068.8%91.7%4.6秒10066.3%90.1%21秒看到这个数字先别急着拿去和别家算法比较这只是特定算例下的表现。它的意义在于说明在中等规模下简单的“贪心初始解 SA BLF”已经能把利用率从70%附近拉到90%左右。再往上就需要换更复杂的解码器或者做多起始点融合。实验里还有一个规律物品尺寸分布更均匀时SA 提升明显分布极不均匀时提升空间小一些。因为极端大件本身就限制了布局的天花板算法再怎么搜也突破不了物理边界。此时应该把精力放在邻域动作优化上比如针对大件的插入和翻转策略。4.4 容易踩到的坑与补救手段第一个坑初始解直接随机化。随机初始解不是不行但会浪费温度预算。我测试过用高度降序贪心初始化再交给 SA 迭代虽然最终最优解稳定收敛但收敛速度明显更快。毕竟贪心给出的布局至少是可行的SA 只需要修复局部问题。第二个坑只记录最终解不记录最优解。前面提过这个问题非常隐蔽但几乎每个新手都会踩。高温阶段接受了不少差解之后当前解可能完全不如中途某个好解而最终输出却用了这个差解。全局最优缓存必须在每次接受后即时更新。第三个坑重叠检测用了浮点坐标。毫米级整数直接在if a.x b.x b.w这类逻辑里判断不需要额外容差如果使用自定义浮点坐标一定要留一个极小 epsilon比如1e-6。否则两个矩形明明只是贴边却可能因为精度问题被判定成重叠整个邻域搜索都会被卡死。第四个坑温度衰减太快导致“退火变淬火”。经典表现是前几轮已经把空间压到90%但后面温度下降过快几乎不再接受任何差解永远留在当前局部最优。补救手段是加入重加热策略若连续多轮全局最优解无更新将温度回升到当前温度的2到3倍再重新跑。实践中这招往往比单纯把 alpha 调高更有效。第五个坑目标函数里惩罚项权重太大。如果重叠或未放置惩罚是固定大权重ΔE 经常是上千上万exp(-delta/T)几乎为0很难接受任何差解。目标函数需要归一化比如把面积利用率和惩罚控制在同一量级温度曲线才不至于失效。5. 从二维排样走向三维装柜与真实排柜流程5.1 三维装箱需要改哪些状态和邻域很多仓库装的不是纸板而是整箱这就变成三维装箱3D BPP了。三维与二维不是简单加一个 z 轴至少有几点变化。第一物品可以绕垂直轴旋转甚至需要考虑承重某些箱子不能放在底层。第二布局解码需要处理“层”的概念常见方式是用一个空闲空间列表每次放最小 z、最小 y、然后 x 的空位。第三邻域动作除了序列交换、旋转还要加上装箱分组和层间调整。本质上还是同一个模拟退火框架目标变为集装箱内部利用率最大化状态表示仍然是“序列 方向标记 层编号”。但三维的邻域搜索更需要精细设计。比如在二维中一个简单的“插入”操作只影响前后几个物品的位置在三维中它可能让一整层结构塌陷需要重新解码整层必须对这一步做性能优化。我在三维版本中最常用的做法是两步解码先按序列确定箱子的“落点 z”再在每一层内部跑一遍二维 BLF。这样三维问题被拆成了两个二维问题逻辑上简单很多效果也不差。如果你直接写一个三维空闲空间维护复杂度会高不少但上限也更高适合在集装箱体积较大、箱子规格较多时用。5.2 排柜工程化的模块划分真实排柜问题除了几何形状外还有一栈承重、重心平衡、开门方向、易碎标记等。我建议分模块处理先在离线阶段用 SA 算出一个近似最优的几何布局再在结果上做约束后处理不要让模型一次性承担所有软约束。工程上可以这样组织代码输入 CSV 物品清单预处理做尺寸归一化和不可装入判断调用 SA 核心输出排布结果和可视化。可视化这一步必须做。没有图客户和同事不会信任你的数据。我一般把矩形画成带编号的网格或者导出 SVG一眼就能看出是否有重叠、有没有不合理的大空隙。关于随机性有一个细节容易被忽视算法跑了20个种子可能得到20个不同结果。为了可复现每次运行要固定随机种子为了可比较评测时要记录种子编号和对应结果。最终给客户交付的不是一个数字而是“某次实验的布局图 对应参数 随机种子”的完整记录。5.3 设计一块“可解释”的搜索空间再往深一层说模拟退火在装箱问题上发挥作用的前提是你能为它设计出一块“可解释”的搜索空间。什么意思当算法跑出一个不太好的布局你能从布局图上看出是左侧空间浪费了还是某几个大件把中间堵死了然后针对性调整邻域操作。如果搜索过程是完全黑盒输出结果既不敢信也不知道怎么修。在我自己的实践中最有效的一步是让解码器返回三样东西最终坐标、使用高度、未放置物品列表。这样即使某个序列对应的布局不好我也能立刻知道是哪些物品没放进去它们放在哪里会产生新的可能性。这个看似不起眼的“可解释性”实际上让调参和优化变得非常快。最后说几句个人体会。我后来再看这段经历最有价值的不是跑出来的最好结果而是把邻域动作、温度调度、解码器这三件事拆开调试的过程。不要一上来就追求复杂的算法框架先从“贪心初始解 BLF 最朴素的模拟退火”跑通再根据结果决定是加大搜索量、换解码器、还是引入重加热。装箱问题的难点从来不在算法名字有多高级而在于你能不能让状态空间里的每一次移动都有意义。先把一条最简路径走通再慢慢打磨比一上来就造一个庞然大物可靠得多。