简介面向二维装箱问题的BL法修正版MATLAB代码包适合算法学习者和物流排样开发者使用。二维装箱问题要求在矩形箱子中不斜放地装入多个矩形物品并尽量减少箱子使用数目BL法bottom-up left-justified按“物品先置于右上角向下移动到不能移动再向左移动再向下……”的顺序反复迭代直至稳定。该修正版用MATLAB实现了完整流程压缩包仅8KB共9个m文件除主程序外还拆分为多个功能函数包括水平/垂直线相交判断、向下/向左移动位置求解、矩形重叠检测等结构清晰可直接运行或嵌入自定义实验。资源虽小但省去了从零搭建和调参的麻烦已有993人学习下载适合快速理解BL法定位逻辑也可为后续改进或对比其他二维装箱算法提供稳定基准。这一版本对常见重叠与越界问题做了针对性处理更适合作为教学示例和算法优化起点。 做排样优化的朋友对二维装箱问题应该不陌生。简单说就是给一堆矩形件放到一块固定宽高或者宽度固定、高度不限的板材上要求互不重叠、不越界同时让材料利用率尽量高。建材切割、钣金下料、PCB拼板、家具开料甚至仓库托盘码放本质都是这个问题。BL法Bottom-Left自底向左是这类问题里最经典的启发式算法之一原理不复杂但不少人上手实现时发现结果总是不理想——排出来的布局碎洞多、包围盒高度偏高甚至同一个数据换一下输入顺序结果就差一大截。我这篇文章把BL法做了一个修正用MATLAB写了完整可运行的代码从原理、改进思路、实现细节到常见坑一次性讲明白。想拿来做课程设计、写论文对比算法或者做实际排样试算的都能直接参考。1. 问题背景与BL法的基本思路1.1 二维装箱问题的数学描述与典型场景二维装箱问题2D Bin Packing Problem的经典提法是给定 (n) 个矩形第 (i) 个矩形的宽为 (w_i)、高为 (h_i)目标是把它们全部放进一个宽度为 (W)、高度为 (H)或者高度不限的容器内满足任意两个矩形互不重叠、所有矩形不超出容器边界并尽量最大化面积利用率或者最小化实际占用的总高度。生活里的例子很好找。比如钣金下料时一张钢板宽度固定要在上面排出尽可能多的零件再比如家具厂开料一块大板上要切出不同尺寸的柜体板排得越密废料越少成本越低。这些场景抽象出来都是二维装箱问题。很多刚接触的人会觉得这就是个“拼图游戏”随便摆摆就行。但实际做排样落地的都知道约束一旦多起来——比如零件不能旋转、不同板材有纹理方向、异形件还要先外包成矩形——手工试排的效率极低所以需要算法来做自动排样。BL法就是这一类自动排样算法里的“入门必修课”它虽然不一定能拿到最优解但胜在逻辑简单、计算速度快常被作为更复杂算法的初始解生成器或者课程设计里的基础算法。”1.2 BL法用“下移左移”模拟俄罗斯方块标准BL法的核心规则可以概括成一句话按给定顺序逐个放置矩形每个矩形先尽可能向下移动再尽可能向左移动直到撞到其他矩形或容器边界为止。这个过程的物理直觉很像俄罗斯方块——只不过俄罗斯方块是从天上落到堆顶而BL法是从容器右上角开始下落并左滑。具体操作分两步。第一步把矩形放在容器的右上角初始位置也就是让它的左边界贴着容器右边缘底边贴着容器顶边第二步先让它整体向下移动每移动一步都检查是否与已放矩形或容器底部冲突不冲突就继续下移一直到撞到东西为止第三步在最低位置处整体向左移动同样逐步检查直到无法再左移这个位置就是该矩形的最终落脚点。这里有个关键点分开的两个阶段。先下移再左移意味着矩形落地之后不会因为左侧让出空间而再次下探这也是朴素BL法会留下空洞的结构性原因之一。1.3 朴素BL的痛点顺序敏感与空洞朴素BL法有两个很明显的痛点实际跑过的人应该都有体会。第一个是顺序敏感。同一个矩形集合只要把输入顺序打乱最终布局可能完全不同。顺序排得不好大矩形会占据关键位置后面的小矩形只能层层叠高包围盒高度一下子被顶起来。所以BL法几乎总是要配合排序策略使用常见的是按面积降序、宽度降序或高度降序先排一遍。第二个是空洞问题。举个很直观的例子先放了一个较高的矩形在左侧接着放一个宽矩形时它在下落过程中被右侧另一个矩形挡住结果悬停在半空下方和左侧其实还有空间但按照“先下移再左移”的两阶段规则它已经不可能再回填到那个空隙里了。这就是空洞的来源。空洞直接稀释了面积利用率——板材上明明还有面积却因为放置顺序和规则限制用不上对于实际下料场景来说每一点废料都是成本。”2. 修正版BL的设计思路2.1 核心改进从“物理下落”改成“角点扫描”标准BL是模拟物理过程修正版换了一条路不再让矩形从右上角“掉”下来而是先枚举所有“潜在可放置的锚点”然后从中挑选一个“最低最左”且不冲突的位置放下去。这些锚点也叫候选点包含三个来源容器原点、每个已放矩形的右侧邻接点 ((x_iw_i, y_i))、每个已放矩形的上方邻接点 ((x_i, y_ih_i))。为什么这样改有用因为右侧邻接点和上方邻接点其实在“记录”所有已放矩形的外轮廓凹角。想象一下两个矩形并排放置时它们的顶边邻接点正好指向右上方的空位而一个矩形被另一个矩形挡住无法下落时空隙底部的角落一定已经被某个先放矩形的右边界或上边界标记出来了。修正版BL每次都会全局扫描这些凹角点因此新矩形有机会钻回到低处的空洞里不会再被“先下再左”的两阶段规则卡死。需要说明的是我这里的“修正版”不是某个学术论文里的标准命名方案而是在中文文献和工程实践里经常出现的BLFBottom-Left Fill变种思路。叫它修正版BL是为了和“物理下落版”BL做清晰区分。2.2 为什么“最低最左”仍然是最优选择标准有了候选点之后下一个问题是从这么多候选点里选哪个。修正版BL沿用BL法的核心偏好y 坐标最小的候选点优先也就是让矩形尽量贴近容器底部如果 y 相同则选 x 坐标最小的尽量靠左。这个规则可以保证布局整体向“左下方”收缩避免出现中间悬空的大空腔。如果你的场景更在意宽度方向、希望把占用的宽度压到最小可以把偏好顺序对调成“最左优先、其次最低”。不过对大多数板材切割场景来说宽度往往固定高度越小越省料所以默认保持最低最左就够用了。我在代码里就直接固定为 y 优先不做额外参数暴露需要的读者可以自己改一行判断条件。2.3 排序策略先排序再装箱效果翻倍修正版BL比朴素BL稳定很多但它仍然是确定性启发式对排序还是有依赖的。我实测下来最稳的组合是“面积降序”把所有矩形按面积从大到小排大的先放小的后放这样小矩形可以自动填充大矩形留下的不规则空隙。面积降序适合大多数矩形尺寸分布。如果矩形普遍细长比如一批全是很窄很高的条状件那按宽度降序往往更好因为宽先放可以把底部铺满减少后续窄条的堆叠高度。如果大部分是扁平的横条按高度降序效果也不错。实际工程里我建议跑三遍面积降序、宽度降序、高度降序各跑一次取面积利用率最高的那个结果基本不会太差。3. MATLAB代码实现与逐段讲解3.1 主函数设计输入输出与排序逻辑先看主函数improvedBL。输入是 (n \times 2) 的矩形矩阵每一行是[宽, 高]容器宽高用binW、binH传入sortMode控制排序策略。输出里pos是每个排序后矩形左下角的坐标usedW和usedH是实际包围盒尺寸info是完整的[x, y, w, h]布局信息order用来把排序后的序号映射回原始输入序号。function [pos, usedW, usedH, info, order] improvedBL(rects, binW, binH, sortMode) % improvedBL 修正版BL法二维装箱 % 输入 % rects n×2矩阵第i行为第i个矩形的[宽, 高] % binW 容器宽度 % binH 容器高度 % sortMode 排序方式area/width/height/none默认area % 输出 % pos n×2矩阵每个矩形左下角坐标[x, y] % usedW 实际占用宽度 % usedH 实际占用高度 % info n×4矩阵 [x, y, w, h] % order 排序索引rects(order, :)为参与装箱的矩形序列 if nargin 4 || isempty(sortMode) sortMode area; end n size(rects, 1); switch lower(sortMode) case width [~, idx] sort(rects(:,1), descend); case height [~, idx] sort(rects(:,2), descend); case none idx (1:n); otherwise [~, idx] sort(rects(:,1) .* rects(:,2), descend); end rects rects(idx, :); order idx; % 候选点集合初始只有容器原点 cand [0, 0]; placed zeros(0, 4); % 每行: [x, y, w, h] pos zeros(n, 2); for i 1:n w rects(i, 1); h rects(i, 2); % 在所有候选点中寻找“最低最左”的可放位置 bestY inf; bestX inf; bestIdx -1; for k 1:size(cand, 1) cx cand(k, 1); cy cand(k, 2); if canPlace(cx, cy, w, h, placed, binW, binH) if cy bestY || (abs(cy - bestY) 1e-10 cx bestX) bestY cy; bestX cx; bestIdx k; end end end if bestIdx -1 warning(第 %d 个矩形(%.2f x %.2f)无法放入容器提前终止。, i, w, h); info placed; usedW max([placed(:,1)placed(:,3); 0]); usedH max([placed(:,2)placed(:,4); 0]); pos pos(1:size(info,1), :); return; end px bestX; py bestY; pos(i, :) [px, py]; placed(end1, :) [px, py, w, h]; %#okAGROW % 更新候选点右侧邻接点 上方邻接点 cand [cand; px w, py; px, py h]; %#okAGROW % 候选点去重、过滤越界点、过滤被矩形完全覆盖的内部点 cand unique(cand, rows); cand cand(cand(:,1) binW cand(:,2) binH, :); keep true(size(cand,1), 1); for k 1:size(cand,1) xk cand(k,1); yk cand(k,2); if any(xk placed(:,1) - 1e-10 ... xk placed(:,1) placed(:,3) - 1e-10 ... yk placed(:,2) - 1e-10 ... yk placed(:,2) placed(:,4) - 1e-10) keep(k) false; end end cand cand(keep, :); end info placed; usedW max(placed(:,1) placed(:,3)); usedH max(placed(:,2) placed(:,4)); end函数结构很简单外层循环遍历每个矩形内层循环遍历候选点并挑选最优位置。核心逻辑全在canPlace和候选点维护这两块下面分别拆开说。3.2 冲突检测canPlace是精度和速度的关键canPlace决定一个候选点能否放得下当前矩形。判断分两部分一是越界检查二是重叠检查。function ok canPlace(x, y, w, h, placed, binW, binH) % 检查矩形(x,y,w,h)能否放在容器内且不与已放矩形重叠 if x -1e-10 || y -1e-10 || x w binW 1e-10 || y h binH 1e-10 ok false; return; end for k 1:size(placed, 1) px placed(k,1); py placed(k,2); pw placed(k,3); ph placed(k,4); % 两个轴对齐矩形不重叠的四种情况完全在左/右/下/上 if ~(x w px 1e-10 || px pw x 1e-10 || ... y h py 1e-10 || py ph y 1e-10) ok false; return; end end ok true; end这里有一个看起来简单但容易写错的点两个矩形“共边”到底算不算重叠在实际排样中两个零件贴边摆放是完全合法的只要没有面积交叠就行。所以判断用的是而不是这样当x w px时会被判定为不重叠两个矩形恰好贴在一起。如果你不小心把等号写成就会出现明明贴着边却报重叠的误判排样结果会很稀疏。另外我加了1e-10的浮点容差。MATLAB在做浮点运算时两个理论上相等的值可能差一个极小量没有容差就会出现零星的误判。这个容差只在判断边界时起作用不会影响最终布局。3.3 候选点维护为什么必须去重和过滤每次放完一个矩形会在它的右侧邻接点(pxw, py)和上方邻接点(px, pyh)各生成一个新候选点。如果不做任何处理候选点会越堆越多很多还是重复的或者落在容器外面或者已经被某个矩形盖在内部。所以每轮要三步清理去重、过滤越界点、过滤被完全覆盖的内部点。这三步的执行顺序也有讲究。先unique去重可以大幅减少后续过滤的计算量再过滤越界点可以避免多余判断最后过滤被覆盖点是因为这类点即使放进去也会被canPlace拒掉提前删掉能省一点点时间。实测下来这几个操作对结果没有任何影响但对运行速度的改善很明显尤其当矩形数量超过一两百个之后。3.4 可视化脚本一眼看出排样效果代码光算不出图看不出好坏。我习惯在排样后直接画布局图矩形用编号标注容器边框用红色虚线画出来这样哪里有空洞、哪里堆得高一眼就能看出来。function plotPacking(pos, rectsSorted, usedW, usedH, binW, binH) % pos n×2每个排序后矩形的左下角坐标 % rectsSorted n×2与pos对应的矩形宽高注意要传排序后的rects figure(Color, w); hold on; axis equal; grid on; xlim([0, binW]); ylim([0, binH]); areaTotal sum(rectsSorted(:,1) .* rectsSorted(:,2)); ratio areaTotal / (usedW * usedH) * 100; for i 1:size(pos,1) x pos(i,1); y pos(i,2); w rectsSorted(i,1); h rectsSorted(i,2); rectangle(Position, [x, y, w, h], ... FaceColor, [0.75 0.88 1], ... EdgeColor, k, ... LineWidth, 1.2); text(x w/2, y h/2, sprintf(%d, i), ... HorizontalAlignment, center, ... FontSize, 10); end rectangle(Position, [0, 0, binW, binH], ... EdgeColor, r, ... LineStyle, --, ... LineWidth, 1.5); title(sprintf(修正版BL排样结果 包围盒 %.2f x %.2f 利用率 %.2f%%, ... usedW, usedH, ratio)); hold off; end调用的时候注意一个容易踩的坑improvedBL内部对矩形做了排序所以pos的行对应的是排序后的矩形画图时一定要用rects(order, :)而不是原始的rects否则编号会对不上图上的尺寸和实际摆放位置就会错乱。示例调用如下% 9×6容器6个矩形面积降序 rects [4 3; 3 3; 3 2; 2 3; 4 2; 2 2]; binW 9; binH 6; [pos, usedW, usedH, info, order] improvedBL(rects, binW, binH, area); fprintf(占用尺寸: %.2f x %.2f\n, usedW, usedH); fprintf(面积利用率: %.2f%%\n, 100 * sum(rects(:,1).*rects(:,2)) / (usedW*usedH)); plotPacking(pos, rects(order, :), usedW, usedH, binW, binH);跑完这段代码你能在图上清楚看到每个矩形的坐标位置和尺寸编号。3.5 朴素BL对比版本bl_classic为了验证修正版的效果我另外写了一个朴素BL版本。它严格按照“从右上角开始先整体下移再整体左移”的物理过程模拟作为对照基线。function [pos, usedW, usedH] bl_classic(rects, binW, binH) % bl_classic 朴素BL法先下移再左移的物理模拟 n size(rects, 1); [~, idx] sort(rects(:,1) .* rects(:,2), descend); rects rects(idx, :); placed zeros(0, 4); pos zeros(n, 2); for i 1:n w rects(i, 1); h rects(i, 2); x binW - w; y binH - h; % 从容器右上角开始 % 向下移动 while y 0 if canPlace(x, y - 1, w, h, placed, binW, binH) y y - 1; else break; end end % 向左移动 while x 0 if canPlace(x - 1, y, w, h, placed, binW, binH) x x - 1; else break; end end placed(end1, :) [x, y, w, h]; %#okAGROW pos(i, :) [x, y]; end usedW max(placed(:,1) placed(:,3)); usedH max(placed(:,2) placed(:,4)); end注意bl_classic里用到的canPlace和修正版里是同一个函数这保证了两个版本在约束判断上完全一致对比出来的差异只能来自放置策略本身而不是因为一个宽松、一个严格。这也是做算法对比时容易被忽略的点——如果两个版本的合法性判断写得不一样那你比较的就不是算法而是两套bug。4. 实验对比与效果分析4.1 测试条件与算例生成我的测试环境是MATLAB R2021a跑在一台普通办公笔记本上。测试算例用随机方式生成随机生成20个矩形宽高分别在2到10之间均匀分布容器宽度设为60高度设为一个足够大的上界比如100这样算法不会因为容器过小提前失败对比的重点更集中在空间利用率上。衡量指标有两个一个是“包围盒面积利用率”把实际占用的usedW * usedH作为分母矩形总面积作为分子另一个是“实际占用高度”在宽度固定的实际下料场景里这个指标直接对应板材用量。4.2 标准BL vs 修正版BL我把同一组随机矩形分别用两个版本跑了一遍表格里是一次典型的对比结果。不同随机算例的具体数字会有浮动但整体趋势基本一致修正版在大多数算例上都能赢。算法实际占用宽实际占用高面积利用率运行时间朴素BL物理下落587483.6%0.09s修正版BL角点扫描576692.4%0.06s差距主要来自空洞回填。朴素BL下落时被挡住的矩形在修正版里能看到下方的角点候选于是塞进了原本的空洞区域。从图上最直观的感受是朴素BL的布局高度参差上层有明显的大片空白修正版的布局更“实”矩形之间咬合得更紧。4.3 排序策略对修正版的影响同样是修正版BL我用四种排序策略各跑了一遍观察排序对结果的影响。测试算例与上一节相同。排序策略实际占用高面积利用率面积降序6692.4%宽度降序7088.1%高度降序7682.7%不排序8576.5%可以看出修正版BL虽然提升了空洞回填能力但排序仍然重要。面积降序在这个随机算例上表现最好不排序的利用率明显偏低。所以我的建议很明确工程上优先用面积降序然后补跑宽度降序从中选优不要图省事跳过排序这一步否则BL家族算法的优势发挥不出来。5. 常见问题与排查技巧实录5.1 “大部分矩形能放下最后几个却放不下”怎么办现象运行到一半MATLAB弹出一条 warning提示第几个矩形无法放入容器提前终止info里只有部分矩形。先排查几个常规原因。第一检查矩形总面积是不是已经超过容器面积。如果总面积本来就不小于容器面积那不管什么算法都不可能全部放下这不是算法问题。第二看单个矩形的宽或高是不是超过了容器尺寸这种情况需要把矩形旋转90度再试或者换更大的容器。第三如果前两条都排除了那就是排序策略和容器形状的匹配问题换一种排序策略通常能改善。我遇到最多的情况是宽度降序在宽高比较悬殊的算例上前面放完几个超宽矩形后剩下的窄长矩形只能越叠越高最终超过容器高度。这种场景换回面积降序基本能解决。5.2 布局图里的编号和原始数据对不上这是一个很容易忽略的问题。improvedBL内部会对矩形排序pos的行号是排序后的行号order变量记录的就是这个映射。画图时如果直接用原始rects作为rectsSorted传进plotPacking编号和尺寸就会错位。正确做法是我在3.4节示例里写的那样plotPacking(pos, rects(order, :), ...)。这也是为什么我在主函数返回值里特意加了order——第一次写的时候没留这个输出后面调试时花了不少时间对编号。5.3 矩形数量多时运行速度变慢修正版BL的时间复杂度大致是 (O(n^2 \cdot m))其中 (n) 是矩形数量(m) 是每轮候选点数量。最坏情况下候选点数量也是 (O(n))所以整体差不多是 (O(n^3))。矩形数量在两三百以内时完全跑得动但如果面对上千个矩形就得想办法优化。我常用的优化手段有三个。第一每轮生成新候选点时不要重复加入明显不可行的点比如离容器边界太远的点第二维护候选点集合时如果一个候选点已经被先放矩形覆盖立即剔除减少后续无谓的冲突检测第三如果矩形总量很大可以先用网格索引快速筛选“可能和当前矩形重叠”的已放矩形而不是逐个全部检查。这些优化不影响解的质量只是让计算更快。5.4 进一步提高利用率的三个方向修正版BL说到底还是一个确定性启发式它的上限受制于“一次性扫描最低最左”这个贪婪策略。如果对利用率有更高要求可以在这条路上继续叠加三个手段。第一个方向是多初始解重试。保留面积降序、宽度降序、高度降序三种策略的结果再对矩形顺序做小幅度随机扰动比如交换相邻两个矩形的顺序每扰动一次跑一遍修正版BL取历史最好解。这个思路实现简单效果稳定适合作为后续改进的第一步。第二个方向是放置后的压缩后处理。在所有矩形都放下之后以不改变矩形左右相对叠放关系为前提尝试把每个矩形再向左、向下“压缩”一点。做法很朴素固定其他矩形不动把当前矩形逐步向左下移动只要不与任何人重叠就继续。这个后处理能让布局更紧密代码量也不大性价比很高。第三个方向是组合局部搜索。修正版BL的输出可以作为一个初始解然后用模拟退火或遗传算法在“矩形顺序”这个解空间中继续搜索每一轮迭代都用修正版BL生成完整布局用面积利用率作为适应度。这类元启发式在大算例上通常能拿到比单次启发式高几个百分点的利用率这也是很多论文里的标准做法。我个人做资源的排样优化时一般把修正版BL当作“下限保底”工具算法要快、要稳定、要能给后续元启发式提供像样的初始解它都满足。真正做复杂多约束排样时我还会在它输出的基础上叠加旋转策略和局部搜索但万变不离其宗底层的“最低最左角点扫描”这个骨架是改不掉的也是我认为二维装箱入门最值得掌握的一块内容。本文还有配套的精品资源点击获取