企业官网建设流程全解析

简介：面向二维装箱问题的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_i+w_i, y_i))、每个已放矩形的上方邻接点 ((x_i, y_i+h_i))。

为什么这样改有用？因为右侧邻接点和上方邻接点其实在“记录”所有已放矩形的外轮廓凹角。想象一下两个矩形并排放置时，它们的顶边邻接点正好指向右上方的空位；而一个矩形被另一个矩形挡住无法下落时，空隙底部的角落一定已经被某个先放矩形的右边界或上边界标记出来了。修正版BL每次都会全局扫描这些凹角点，因此新矩形有机会钻回到低处的空洞里，不会再被“先下再左”的两阶段规则卡死。

需要说明的是，我这里的“修正版”不是某个学术论文里的标准命名方案，而是在中文文献和工程实践里经常出现的BLF（Bottom-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(end+1, :) = [px, py, w, h]; %#ok<AGROW> % 更新候选点：右侧邻接点 + 上方邻接点 cand = [cand; px + w, py; px, py + h]; %#ok<AGROW> % 候选点去重、过滤越界点、过滤被矩形完全覆盖的内部点 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 候选点维护：为什么必须去重和过滤

每次放完一个矩形，会在它的右侧邻接点(px+w, py)和上方邻接点(px, py+h)各生成一个新候选点。如果不做任何处理，候选点会越堆越多，很多还是重复的，或者落在容器外面，或者已经被某个矩形盖在内部。所以每轮要三步清理：去重、过滤越界点、过滤被完全覆盖的内部点。

这三步的执行顺序也有讲究。先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(end+1, :) = [x, y, w, h]; %#ok<AGROW> 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下落时被挡住的矩形，在修正版里能看到下方的角点候选，于是塞进了原本的空洞区域。从图上最直观的感受是：朴素BL的布局高度参差，上层有明显的大片空白；修正版的布局更“实”，矩形之间咬合得更紧。

4.3 排序策略对修正版的影响

同样是修正版BL，我用四种排序策略各跑了一遍，观察排序对结果的影响。测试算例与上一节相同。

可以看出，修正版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当作“下限保底”工具：算法要快、要稳定、要能给后续元启发式提供像样的初始解，它都满足。真正做复杂多约束排样时，我还会在它输出的基础上叠加旋转策略和局部搜索，但万变不离其宗，底层的“最低最左+角点扫描”这个骨架是改不掉的，也是我认为二维装箱入门最值得掌握的一块内容。

本文还有配套的精品资源，点击获取