简介二维矩形排样是工业制造与数学建模中的典型优化问题直接关系到材料利用率和生产成本与背包问题同属组合优化范畴。压缩包内共打包30个文件以14篇caj和6篇pdf学术论文为主体覆盖遗传算法、蚁群算法、动态规划、填充式启发式等多种求解思路同时附带下料软件、数据库、说明文档等配套内容便于理解算法原理并体验工程实现。整包大小约37.65MB已有762人学习浏览。资料从最大覆盖问题、裁剪算法、预处理技术到下料问题均有涉及既适合机械、包装、印刷等行业从事排样研究的技术人员也适合算法学习者与数学建模参赛者作为参考集合。通过研读不同角度的论文并运行配套程序可快速把握二维矩形排样的数学建模方法与优化策略为设计更高效的排样方案提供可操作的借鉴。1. 二维矩形排样论文包先想清楚它解决什么再打开做板材切割、玻璃排版、木工下料甚至 PCB 设计的人多半都遇过同一个问题一堆大小不一的矩形零件怎么摆进一整块板里能省料最快。这个场景落地到算法侧就是二维矩形排样问题也叫矩形件排样、二维背包问题或下料问题。它和经典的切割下料问题本质同源却多了一个二维空间约束所以论文库里既有构造式启发式也有遗传、粒子群这类深度搜索方法。这个打包资源把该方向的代表论文集中在一起适合正在做排样算法选型、准备复现对比、或者要找灵感写方案的人。先别急着翻摘要先把它面对的两个真实问题搞清楚一是板材利用率从 60% 提到 85% 靠什么手段二是论文里的实验结论换到你的零件集上还成立吗这两件事决定了你该怎么用这份资料。2. 排样问题的完整分类从一维下料到二维矩形背包2.1 三种典型场景决定你读论文时的目标函数二维矩形排样论文看着庞杂其实场景可以收敛成三类。第一类是单板排样即固定一块已知长宽的大板把尽量多的矩形零件放进去高度或面积利用率优先这是家具开料和钣金套料最常见的形态。第二类是无限板排样板材宽度固定但长度不限目标是最小化总使用长度典型场景是卷材横切。第三类是托盘装载在固定二维空间里最大化填充率本质上接近集装箱码放。拿到论文包先确认一个事情每篇论文的假设是这三类里的哪一类。因为同样的遗传算法套在单板排样上优化的是零件序列套在无限板排样上优化的是总高度套在托盘装载上优化的又是填充率。目标函数不同交叉变异算子的设计就不一样你复现时的收敛曲线也完全不具备可比性。我见过有人拿托盘的 98% 填充率结果对比单板的 85% 利用率说自己的算法差太多其实就是场景没对齐。这三类场景还决定读论文时该重点关注哪一段。单板排样重点看局部搜索和边界处理无限板排样重点看水平线维护和剩余空间利用托盘装载重点看两阶段启发式和剩余矩形合并。论文包目录里如果按场景分了组直接按你的业务场景挑着读效率最高。2.2 矩形排样与二维背包问题的数学关系二维矩形排样之所以能在论文库里和背包问题、下料问题反复关联是因为它在数学上就是一个带几何冲突的二维背包问题。一维背包的核心是重量和价值的取舍到二维就变成了面积和位置的取舍每个矩形相当于一个物品它的价值就是面积大板相当于背包维度从一维容量扩展成了二维平面。转换视角后你会发现论文里的模型约束可以统一表达成两类。第一类是几何约束任意两个矩形不能重叠且都在板材边界内第二类是工艺约束比如有些零件不允许旋转、某些零件必须挨在一起、刀具切割顺序限制等。大量论文的数学公式差异只是这两类约束的不同排列组合。读论文时把模型列出来我先不看目标函数先看它列了哪几个约束条件。同一个算法如果处理了旋转和未处理旋转论文里的结果是不能直接比较的。这里有一个我很习惯的检查动作看它的实验设置里是否允许 90° 旋转这个开关对最终利用率的影响通常在 5% 到 12% 之间属于排样结果的大变量。有些论文为了数据好看会默认允许旋转但你的实际场景板材有纹理方向这时必须关掉旋转结论就要打折。2.3 数据与算例论文包里最容易被忽略的一类内容论文包中有一类正文之外的素材份量被严重低估附录里的测试算例和实验结果明细。二维排样方向长期以来缺乏统一基准很多论文用自建数据集或者从某个经典算例集里挑一部分。如果你要复现对比第一步不是改算法而是把论文里的算例配置提取出来板宽多少、零件数量多少、尺寸范围如何、有无旋转、间隙要求多少。复现时要非常小心尺寸生成逻辑。很多算例的零件尺寸在某个区间内随机生成例如宽度 10 到 50、高度 5 到 30但如果你按整数生成论文可能用的是实数或者是按特定种子生成。这个细节直接导致你的复现实验从一开始就和论文对不上。我处理这类问题的习惯是先把论文里的数据表截图存进场景文件标注清楚板宽和零件数量再写生成器不要凭印象猜。论文包里往往还会包含从易到难的算例分组比如小规模 20 件、中等规模 50 件、大规模 100 件以上。这组分类本身就是分析算法的线索元启发式在小规模算例上可能接近最优解在 100 件以上就会因为搜索空间膨胀而显出差距。读论文时把每个算例组的结果抄在一个表里作为后续自己做基准的起点这份资源的价值就翻倍了。3. 论文包的算法主线按流派拆解阅读顺序3.1 构造式启发式先掌握放置策略二维矩形排样论文里最底层的组件是放置策略它回答一个核心问题给定一个零件序列怎么把它们逐个放进板材里。经典的做法有三种BLBottom-Left算法、BLFBottom-Left-Fill算法和最低水平线算法Lowest Horizontal Line。BL 算法的逻辑是每个零件从板材右上角开始先向下再向左不停移动直到卡住为止。这个策略简单直观适合入门。但它的缺陷很明显零件只能按给定顺序依次放置无法填充先放置零件留下的左下空腔。BLF 对此做了改进在放置下一个零件时先搜索板材上已有的所有空腔如果有放得下的位置就先填进去。代价是搜索从 O(1) 变成 O(n)但板材利用率通常能提升不少。最低水平线算法则维护板材整体高度轮廓每次找最低的水平线段来放置适合高矮差异明显的零件组合。阅读论文包时先把这三类放置策略的实现了然于心再去看遗传算法嵌入的是哪一类。因为后续所有元启发式都是在某个放置策略基础上套一层优化搜索放置策略的质量直接决定上层算法的天花板。在具体实现上我建议用最低水平线法作为自己复现实验的基线后续第 4 章会给出可运行的实现。它比 BL 能填缝隙比 BLF 实现简单最主要是它天然返回排样的总高度方便各种场景下换算利用率。3.2 元启发式理解为什么都要套一层搜索只看放置策略排样结果完全由零件序列决定所以论文包里的元启发式核心在解决一件事搜索最优的零件排列顺序。遗传算法是其中最常见的一支个体编码为零件序列交叉采用顺序交叉OX变异采用交换或插入适应度函数就是放置策略返回的总长度或利用率。粒子群优化在这个方向上的做法类似把每个粒子当作一个序列更新时引入序列之间的相似度概念但实现比遗传略微繁琐。模拟退火则直接在当前序列的邻域里做随机干扰以一定概率接受劣解来跳出局部最优论文里常用于对遗传结果的二次精修。如果你手里的业务是中小规模排样几千件以内遗传加模拟退火的组合通常是性价比最高的选择。这里的评估指标也要理解到位论文里报告的算法运行时间往往是在某种特定配置下得到的直接对比秒数意义有限。真正有价值的对比是达到特定利用率需要多少次适应度评估这个指标排除了不同机器的干扰也便于你在自己的代码里做公平对比。3.3 混合算法实际落地里性价比最高纯构造式启发式快但质量不稳纯元启发式质量高但算得慢所以近些年的论文里出现很多两阶段混合算法。第一阶段用遗传或粒子群搜索一个全局较优的零件序列第二阶段用局部搜索针对放置结果里的空隙做微调或者针对序列做有限次交换尝试。这种设计在工程落地里非常有参考价值因为你的实际场景往往不允许跑十分钟才出结果。我一般会把论文里的混合策略拆成三个可独立评估的模块序列生成器、放置器、局部优化器。分别测量每个模块对最终利用率的贡献再考虑上线时的算力限制。有时候全局搜索跑一半轮次就切到局部搜索最终结果反而更好这也是论文里常见的观察。读混合算法论文时记得看它两个阶段的切换条件。有的按代数切换有的按收敛速度阈值切换有的按适应度停滞代数切换。这些切换条件都直接影响结果在复现时属于敏感参数不能只照抄数值要结合自己的算例做微调。3.4 一份推荐的阅读顺序拿到论文包后如果时间有限可以按下面这个顺序读从底向上建立完整框架先读 2 至 3 篇关于最低水平线法和 BLF 的原始文献把放置策略吃透。再读 1 至 2 篇遗传算法应用于矩形排样的早期文献理解编码、交叉、变异的标准套路。接着读 2 至 3 篇近年的混合算法论文关注阶段切换和局部搜索细节。最后读算例对比类的论文把其中数据表作为自己实验结果的参照。选一篇论文做深度复现先不管改进部分把它的基线复现出来再往上加自己的模块。这五步走完后你手里的论文包就从文献合集变成了可操作的算法参考系。之后再拿到新的排样论文只要判断它属于哪个流派对照着找差异即可不用每一篇都从头读。4. 从论文到代码复现一个BLF基准4.1 BLF放置策略的核心流程最低水平线法可以在 O(n) 时间内完成单个零件的放置是排样论文里最常用的效率基线。它的核心流程可以归纳成四步初始化一条横跨整个板材底边的水平线段每一次放置时从所有水平线段中选取 y 坐标最小的那条有多个 y 最小就选 x 较小的尝试把当前零件放在该水平线上方如果宽度放不下就向右移动这条线段到下一个 x 位置放置完成后更新水平轮廓把被零件覆盖的线段切掉并加入零件顶部形成的新的水平线段。这个策略最妙的地方是它对零件顺序极其敏感同一个零件集合换一个排列顺序得到的板材高度可能差 10% 以上。所以它既是完整的排样方案也是遗传算法的适应度函数内部的核心组件。理解它先于实现任何元启发式。4.2 最小化复现Python实现下面给出一个可以在本地直接运行的实现将一组矩形零件按给定顺序放入宽度为 W 的板材返回最终所需的高度。def lowest_horizontal_line(rects, W): rects: list of (w, h) tuples已经按给定顺序排好 W: 板材宽度 返回: 排样完成后所需的总高度 # 水平线段按 (x, y, length) 存储初始化为整条底边 lines [[0.0, 0.0, float(W)]] for w, h in rects: # 遍历所有水平线段找 y 坐标最小的y 相同取 x 更小的 while True: lines.sort(keylambda seg: (seg[1], seg[0])) x, y, seg_w lines[0] # 当前线段宽度不够把这条线段向右移动 if seg_w w: lines[0] [x seg_w, y, float(W) - (x seg_w)] continue # 放置矩形占据从 x 到 xw、从 y 到 yh 的空间 rect_top_y y h # 从 lines 中移除被矩形占据区域的线段 new_lines [] for lx, ly, lw in lines: if ly rect_top_y or lx lw x or lx x w: # 完全没有被矩形覆盖保留 new_lines.append([lx, ly, lw]) elif ly rect_top_y: # 水平线位于矩形下方区域且与矩形占据的 x 范围相交 left_overlap max(lx, x) right_overlap min(lx lw, x w) if left_overlap lx: new_lines.append([lx, ly, left_overlap - lx]) if x w lx lw: new_lines.append([x w, ly, lx lw - (x w)]) # 被矩形覆盖的部分不加入 # 矩形顶部形成新的水平线段 new_lines.append([x, rect_top_y, w]) lines new_lines break return max(line[1] line[2] for line in lines) # 高度取最大 y # 示例板宽 100零件按 (宽, 高) 排列 rect_list [(30, 20), (40, 35), (25, 15), (50, 30), (10, 45)] final_height lowest_horizontal_line(rect_list, W100) print(排样总高度:, final_height)核心逻辑概括lines数组维护当前所有水平线段每次取最低线段放置零件。高度返回是所有线段最高点而不是最后一个零件的顶边因为后面的零件可能放到更早零件上方。这个实现刻意把线段合并逻辑写得简单每次放置后统一重建列表虽然时间复杂度比专门的数据结构略高但对几百件零件的算例完全够用也便于理解。4.3 参数怎么调队列排序与旋转开关在上述代码中唯一的输入除了零件尺寸就是排列顺序。这也正是它作为基线的价值所在你可以随意测试不同排序策略下的结果差异。常见排序方式有按面积降序、按高度降序、按宽度降序、按随机顺序。通常高度降序在大零件占主导的场景效果好面积降序在零件尺寸均匀时更稳但没有绝对所以要用自己的数据跑一遍。论文里的实验常设置一个旋转开关即零件是否允许旋转 90°对应到代码就是循环里加一个判断比较(w, h)和(h, w)哪个放置后高度更低。注意这会让问题复杂度翻倍因为同一个序列代表的不再只是顺序还隐含了每个零件的朝向选择。复现时我建议先关闭旋转把基线跑通确认数据和论文对得上再打开旋转开关。还有一个小坑浮点数精度。上面代码里的 x 坐标全部用的浮点如果零件尺寸也是浮点多次切割拼接后可能出现 1e-12 级别的误差。稳妥做法是所有尺寸先乘以 100 转成整数再排样或者在做线段合并时加一个1e-9的容差值做比较。论文里通常不写这种细节但它经常是复现结果和论文数值对不齐的元凶之一。5. 复现排样论文常见问题与避坑记录5.1 坑一利用率和论文对不上差在零件是否允许旋转现象我用论文里的同样的算例和同样的算法跑出来的利用率比论文低了 8%。原因论文的实验设置里零件允许 90° 旋转而我的复现代码默认不旋转。解决回到论文的实验参数部分找到 rotation 相关描述。通常会在实验设置的一个小段落里写all items can be rotated by 90 degrees。如果你的场景不允许旋转则不需要修改。如果想和论文对齐在放置每个零件时额外尝试一次旋转后的方案选高度更低的那种。这个坑极其常见因为很多论文的默认值并不是标准它藏在行文里不仔细读根本看不到。我现在拿到论文第一件事就是标出四个开关是否旋转、板宽多少、零件尺寸是否取整、有无间隙约束。5.2 坑二复现结果波动大但论文只报一个最好值现象一个遗传算法跑十次利用率最好 92%、最差 87%论文却只写了 92%。原因论文报告的是多次运行的最优结果而不是均值或中位数。这在元启发式论文里是普遍做法但它也会让复现者误以为算法稳定。解决复现时固定随机种子统一运行 10 次同时记录最好值、均值、标准差。与论文对比时只用最好值对比衡量稳定性时再看标准差。如果论文连随机种子或运行次数都没写那它的结果只能作方向参考不能作精确 benchmark。这个现象也是排样方向极度依赖数据一致性的一种体现同一种群大小、相同的交叉率只要种子不同、零件序列初始化不同结果就可能有几个百分点的浮动。5.3 坑三算例里板材的宽和高被对调现象我用论文里描述的板宽 200 复现怎么放都放不下它说的 30 个零件但把宽和高互换后恰好能放下。原因部分论文的数据表里把板材的宽和高定义与常规相反或者算例命名里w代表长边。解决解析算例时先做一个一致性校验把论文报告的最终利用率和总零件面积做反推。即用利用率乘板材面积得到零件总面积再手算一下零件面积求和两者是否吻合。如果吻合说明宽高定义没问题如果不吻合大概率是板材方向反了。这个校验过程只需要两行代码但能省掉一下午的排查时间。我一般会先计算total_area sum(w * h for w, h in rects) board_area W * H expected_utilization total_area / board_area print(expected_utilization)把结果和论文的数值对比一下误差 1% 以内说明数据对齐了差异大就要检查方向定义。5.4 坑四水平线合并算法的边界处理有误现象自己实现的 BLF 在某些算例里零件重叠了但看起来算法逻辑是完整的。原因放置后更新水平线时被矩形覆盖的线段的切割逻辑没处理好。具体来说一条水平线的 x 范围部分在矩形左边界之外、部分在矩形覆盖范围内切割时左段和右段的坐标计算需要独立判断。解决不要手工处理线段切分改用统一的覆盖剔除逻辑遍历每条线段若与矩形的 x 范围有交集且 y 值在矩形底部之下则把该线段按交叠点切成至多两段保留未覆盖部分。覆盖部分删除矩形顶部则新增一条长为 w 的水平线。这类 bug 在某些包含大量小零件的算例中尤其容易暴露因为水平线数量激增切分路径变多肉眼排查已不现实。建议在开发期加入断言检查确保任意两个已放置矩形不重叠。这也是排样算法工程师常说的随手埋验证逻辑上线前能兜住大量低级问题。5.5 坑五间隙约束被忽略优化结果无法落地现象算法跑出 95% 的利用率但拿到实际切割时发现零件间隔太小刀具过不去。原因论文里的二维排样模型通常假设零件可以紧密贴合即间隙为 0。而真实切割场景需要留 3mm 到 10mm 的刀缝或安全间隙。解决在实验前就把间隙换算进零件尺寸而不是放在排样后处理。常见做法是把每个零件的宽和高都加上一个 gap然后排样完成后总尺寸再减去一个 gap。这样可以在不修改算法的情况下模拟真实工艺约束。这个坑在论文包内多篇应用型论文里有不同处理方式有的把间隙建模为约束有的直接不提。我自己的经验是业务排样里永远默认有间隙哪怕是 1mm也必须让算法感知到它否则交付时一定翻车。6. 验证进阶如何判断一篇论文值不值得照抄6.1 解构一篇排样论文的五步流程拿到任何一篇排样论文我都有一个固定的五分钟解构动作直接把它的可复现性打分。这五步做完你基本能判断出这篇论文是能跑的改进还是只画饼的理论。第一步读实验设置提取板材尺寸、零件数量、旋转开关、间隙值这四个参数直接决定你后续是否要对齐。第二步找出它对比的基线算法通常是 BL、BLF 或某种遗传算法变体把这个基线在同一个算例上跑一遍。第三步看它的改进模块报告在相同的迭代次数下它的结果比基线高多少如果论文只报了收敛曲线不报具体数值这个改进量就要打问号。第四步看算例来源如果是随机生成看生成边界的具体数值如果是标准基准集看它取了哪些子集。第五步看运行时间报告方式理想的是报适应度评估总次数其次才是秒数。整套做下来大概需要 10 到 15 分钟但它能过滤掉一半以上水分很大的论文。反而是数据表非常规范、改进了哪一部分写得很清楚的论文通常可以直接进入复现阶段。6.2 判断依据改进比例和稳定性的双重验证假设论文宣称它的混合算法比 BLF 基线提升了 7% 的利用率你的复现目标是验证这个 7 是否在自己环境下成立。强烈建议你把复现分成两步先在 50 件零件的中小规模算例上跑通常差异比较小再在 100 件以上算例上跑这时元启发式和纯启发式的差距会被放大你才能看清改进模块的贡献到底在哪。对比项BLF 基线论文改进算法你的复现结果平均利用率84.1%90.2%86.5%最好利用率85.0%91.8%89.3%标准差01.8%2.5%这张表从三个维度看平均值看一般水平最好值看潜力标准差看稳定性。如果论文的平均值提升 6%你复现出的平均值只能提升 2%不用急着否定论文先检查算例是否一致、是否开了旋转、种群是否跑够代数。这些因素里任何一项都能吃掉几个百分点的差距。那之后我养成了一个习惯每次打开新的排样论文不管它写得多漂亮都先跑上面的解构流程再决定它在自己的项目里值不值得深挖。这个习惯帮我筛掉了至少一半看起来有用、实际没法落地的方案也让我在给业务方汇报利用率提升时敢用复现数据说话。希望大家拿到这份论文包后也能少走弯路把时间花在真正能落地的算法上希望帮到你。本文还有配套的精品资源点击获取