工业下料优化多种启发式策略竞争的 1D/2D 切割算法实践一、问题背景工业下料Cutting Stock Problem是制造业中一道经典的组合优化问题给定若干根固定长度的母材和一批需要切割的短料清单如何分配切割方案使得母材用量最少、材料利用率最高以最常见的铝型材切割为例母材长度6000mm 需求清单 - 1800mm × 5 根 - 1200mm × 8 根 - 900mm × 12 根 - 650mm × 10 根人工排料的典型思路是先切长的、短的填空隙但这个问题已经被证明是NP-Hard——当短料规格超过 10 种、数量超过 50 根时人工几乎不可能找到全局最优解。本文记录我们在材料切割优化系统中的算法设计思路包括 1D线性材料和 2D矩形板材两种模式下的策略选型和工程实践。二、1D 切割贪心策略矩阵 随机扰动2.1 问题建模1D 切割的形式化定义输入 S [s₁, s₂, ..., sₙ] // n 个短料长度 L // 母材标准长度 K // 母材可用数量可动态增加 输出 B {B₁, B₂, ..., Bₘ} // m 个 Bin使用的母材 每个 Bᵢ 包含若干短料满足 Σlen ≤ L 优化目标min(m) // 最小化母材使用数量 max(Σlen / (m × L)) // 等价最大化平均利用率2.2 策略设计没有单一算法能在所有场景下表现最优。我们实现了 5 种策略每种擅长不同的分布特征FFDFirst Fit Decreasing1. 短料按长度降序排列 2. 遍历短料放入第一个能容纳它的母材 3. 如果所有现有母材都放不下开新母材理论近似比FFD(I) ≤ (11/9) × OPT 1经典结论。实际中规格差异大时收敛极快。publicListBinffd(ListIntegeritems,intstockLength){items.sort(Collections.reverseOrder());ListBinbinsnewArrayList();for(intitem:items){booleanplacedfalse;for(Binbin:bins){if(bin.remaining()item){bin.add(item);placedtrue;break;}}if(!placed){BinnewBinnewBin(stockLength);newBin.add(item);bins.add(newBin);}}returnbins;}Best Fit1. 短料按长度降序排列 2. 遍历短料放入剩余空间最紧的那个母材余量最小但不小于短料长度直觉大块填空隙小块留余地。规格均匀分布时利用率优于 FFD。Worst Fit1. 短料按长度降序排列 2. 遍历短料放入剩余空间最大的那个母材直觉为后续的长料预留大空间避免大块被小块挤得无处可放。背包后优化Knapsack Post-OptimizationFor each bin Bᵢ in 初始方案: 将 Bᵢ 中的短料 其他 bin 中可迁移的短料视为一个背包问题实例 容量 L母材长度 价值 短料长度 求解 0-1 背包看是否能重组出更高利用率这个策略在小规模 bin 上效果显著但计算成本随短料数量指数增长实际中对每个 bin 的短料数量做了上限限制。迭代交换Iterative SwapFor round in 1..maxRounds: For each pair (Bᵢ, Bⱼ): 尝试交换二者中的短料 如果总用料数减少保留交换结果 如果本轮无改进提前终止交换策略的关键在于跳出局部最优——FFD/BestFit 等贪心策略容易陷入的陷阱通过跨 bin 交换有望突破。2.3 随机扰动让贪心不再困住贪心类算法的一个致命弱点是对输入顺序敏感。同样的清单短料排序不同结果差异可能很大。我们采用的方案是为每种策略跑多轮每轮对短料列表施加随机扰动publicSolutionsolveWithPerturbation(ListIntegeritems,intstockLength,Strategystrategy){Solutionbestnull;doublebestUtil0;for(intround0;roundMAX_ROUNDS;round){ListIntegerperturbednewArrayList(items);Collections.shuffle(perturbed,newRandom(round));// 确定种子可复现Solutionsolstrategy.solve(perturbed,stockLength);doubleutilsol.getUtilization();if(utilbestUtil){bestsol;bestUtilutil;}}returnbest;}2.4 策略竞争并行择优最终方案所有策略 ⇒ 并行执行 ⇒ 各跑 N 轮随机扰动 ⇒ 统一按利用率排序 ⇒ 返回 Top 1Java 并发实现ExecutorServiceexecutorExecutors.newFixedThreadPool(strategies.size());ListFutureSolutionfuturesnewArrayList();for(Strategys:strategies){futures.add(executor.submit(()-solveWithPerturbation(items,stockLength,s)));}Solutionbestfutures.stream().map(f-f.get())// 实际有超时和异常处理.max(Comparator.comparingDouble(Solution::getUtilization)).orElseThrow();这样设计的好处互补性不同策略擅长不同分布FFD 不行 BestFit 可能有奇效无额外成本策略并行不增加总耗时受限于最慢策略可扩展新增策略只需实现接口、加入策略池即可三、2D 切割Guillotine Shelf 跨 Bin 优化3.1 问题约束2D 切割比 1D 多了一个维度且工艺上通常要求闸刀切割Guillotine Cut——每条切割线必须是从板材一端贯穿到另一端的直线不能中途拐弯。3.2 Guillotine Shelf 算法算法流程 1. 将所有矩形按高度降序排列 2. 初始化第一层 Shelf高度 第一个矩形高度 3. 遍历矩形 a. 如果矩形高度 ≤ 当前层剩余高度 放入当前层水平排列 b. 否则 在当前层上方开新层 c. 矩形允许 90° 旋转横放/竖放各尝试一次取更优的 4. 所有层叠加总高度须 ≤ 板材高度┌─────────────────────────────────┐ │ Shelf 1 (h300) │ │ ┌──────┐┌─────┐┌───┐┌──────┐ │ │ │ ││ ││ ││ │ │ │ └──────┘└─────┘└───┘└──────┘ │ ├─────────────────────────────────┤ │ Shelf 2 (h200) │ │ ┌──────────┐┌────────┐ │ │ │ ││ │ │ │ └──────────┘└────────┘ │ ├─────────────────────────────────┤ │ ↑ 剩余区域 │ └─────────────────────────────────┘3.3 跨 Bin 优化初排完成后系统会自动检测利用率最低的 BinpublicListBincrossBinOptimize(ListBinbins){// 按利用率升序排列bins.sort(Comparator.comparingDouble(Bin::getUtilization));for(inti0;ibins.size();i){Bindonorbins.get(i);if(donor.getUtilization()THRESHOLD){// 比如 60%ListRectitemsdonor.getItems();booleanallMigratedtrue;for(Rectitem:items){booleanmigratedfalse;for(intjbins.size()-1;ji;j--){if(bins.get(j).canFit(item)){bins.get(j).add(item);migratedtrue;break;}}if(!migrated){allMigratedfalse;break;}}if(allMigrated){bins.remove(i);// 这个 Bin 可以省掉i--;}}}returnbins;}如果某个 Bin 的所有矩形全部迁移成功 →直接消除一个 Bin → 省下一整张板。四、核心工程实践4.1 算法引擎与业务逻辑分离┌─────────────────┐ ┌─────────────────┐ │ Strategy 接口 │ ←── │ RuleEngine │ │ solve(items, L)│ │ (约束校验/过滤) │ └────────┬────────┘ └─────────────────┘ │ ┌────┴────┬──────────┬──────────┐ │ │ │ │ FFD BestFit WorstFit KnapsackStrategy 专注搜索RuleEngine 负责合法性校验缺陷区域、最小切割长度、库存余量等职责分离方便各自独立测试和迭代。4.2 结果可视化1D 结果Canvas 绘制横向长条图每根母材用不同颜色区分不同规格短料余料区域灰色标识2D 结果Canvas 绘制矩形布局图支持缩放和 Tooltip 查看每个矩形的尺寸、物料编码4.3 数据导入导出导入EasyExcel 读取 BOM 表自动识别表头列物料编码、规格、数量容错处理空行和格式异常导出Excel 含汇总统计和切割明细两个 SheetPDF 每根母材生成一张切割示意图五、效果对比用一个真实测试案例说明差异母材6000mm × 100 根 短料18 种规格共 420 根方法使用母材数利用率人工排料有经验师傅87 根83.2%FFD 单策略82 根88.4%BestFit 单策略81 根89.5%多策略竞争78 根92.9%多策略竞争比人工少用 9 根母材、利用率提升近 10 个百分点。比单一最优策略也多省 3 根。六、总结这套系统的算法设计核心思路可以归纳为三点不赌单一算法5 种策略覆盖不同数据分布特征并行跑、自动择优随机扰动打破局部最优每轮改变输入顺序大幅降低运气差的概率跨 Bin 优化消除碎片不让低利用率的 bin 拖累整体结果工业下料是一个没有银弹的问题——材料类型、规格分布、工艺约束千差万别不可能有一个算法包打天下。但通过策略组合 竞争择优的架构可以让系统在绝大多数场景下都逼近最优解。关于我惠州市浅草软件科技有限公司专注智能制造领域的排样优化算法研发。本文所述为实际落地的工业软件系统欢迎技术交流。产品详情https://qiancaosoft.com/products/material-cutting