Beam Search 求解马口铁印刷排版19 条行业规则如何转化为算法一、问题的提出马口铁印刷排版是制罐行业的一道核心工序在固定尺寸的马口铁片上排列罐盖、罐底或罐身等产品使得铁片面积利用率最大、生产成本最低。这个问题本质上是一个二维不规则排样问题2D Irregular Packing Problem属于 NP-Hard 组合优化。实际生产中还掺杂着大量行业特有约束刀口加放量模具切割预留量牙口边距印刷机咬口区域不可用铁片最大/最小印刷尺寸限制行列间距上下限2-3 个不同产品混排时的比例约束换版次数限制每次换版约 1500 元开机费圆形产品的特殊排列方式传统做法完全依赖排版师傅的个人经验效率低且无法保证最优解。本文记录我们在开发马口铁印刷排版系统中将这些行业经验转化为算法引擎的完整思路。二、从规则到约束19 条业务规则的建模第一步是将老师傅口中的经验转化为可计算的数学约束。经过多次深入工厂调研我们提取出 19 条核心排版规则大致分为以下几类2.1 几何约束刀口加放量 d_k ∈ [0, 3mm] 牙口边距 d_g ∈ [8, 15mm] 产品间距 d_p ∈ [1.5, 5mm] 行间距 d_row ∈ [1.5, 5mm]2.2 容量约束列数 C: d_g × 2 w × C d_p × (C - 1) ≤ W_sheet 行数 R: d_g × 2 h × R d_row × (R - 1) ≤ H_sheet其中w、h为单个产品在排版中的实际占用宽高含刀口加放W_sheet、H_sheet为铁片有效印刷区域。2.3 印刷机约束每台印刷机有最大/最小印刷尺寸限制排版结果必须落在这个范围内。如果超出需要拆版或多机分印成本会大幅增加。2.4 换版约束每次更换排版图需要停机、换版、重新校色一次开机费约 1500 元。因此系统中引入了最少排版图种类策略——在利用率达标的前提下尽可能用同一张排版图覆盖更多订单。三、搜索策略为什么选 Beam Search3.1 搜索空间分析假设一张铁片最多排 M 行 N 列每种产品可选的排列参数组合间距、方向、边界等约 O(K) 种加上多产品混排时的组合爆炸穷举完全不可行。我们评估了几种方案方案优点缺点暴力穷举保证最优解搜索空间过大不可行贪心算法速度快容易陷入局部最优动态规划最优子结构约束条件太多状态难以定义遗传算法适合组合优化收敛速度不稳定调参困难Beam Search可控精度/速度平衡可能剪掉最优解最终选择了Beam Search束搜索理由如下可控复杂度通过 beam width 调节搜索广度和深度的平衡天然支持 Top-N 输出搜索过程中保留多个候选路径直接产出 Top 3 方案易于融入启发式每种优化策略可以对应不同的评分函数结果确定性不像遗传算法受随机种子影响结果可复现3.2 Beam Search 的实现思路核心思路 1. 初始阶段对每种产品的尺寸参数宽高、间距方向进行合法组合枚举生成候选节点 2. 搜索阶段每轮根据评分函数保留 Top-K 个候选方案分别扩展下一层 3. 终止条件所有产品排完或剩余空间不足 4. 结果输出对所有完整方案按目标函数利用率/成本排序输出 Top 3伪代码示意function beam_search(products, sheet, beam_width): candidates [empty_solution()] for product in products: next_candidates [] for candidate in candidates: // 枚举当前产品在剩余空间中的所有合法排列 layouts enumerate_layouts(product, candidate.remaining_space) for layout in layouts: next candidate.extend(product, layout) next_candidates.append(next) // 按评分排序保留 Top beam_width next_candidates.sort(keyscore, reverseTrue) candidates next_candidates[:beam_width] if not candidates: break return candidates[:3] // 最优 Top 3enumerate_layouts()是规则引擎的核心——每个 layout 都需要通过 19 条规则的校验不合法的排列在这一步就被剪枝了。四、5 种优化策略的设计不同场景下用户关心的目标完全不同。我们设计了 5 种策略本质上是 5 种不同的评分函数策略 1成本优先Cost Priorityscore -total_cost total_cost ∑(sheet_price × sheet_count) ∑(plate_change_cost × change_count)适用于对成本敏感的大批量订单优先保证最终开销最低。策略 2均衡模式Balancedscore utilization × α - cost_per_unit × β在利用率和单位成本之间取加权平衡适合日常排产。策略 3最少铁片Minimum Sheetsscore -sheet_count 同时约束利用率不低于阈值追求用最少的铁片完成订单适合铁片库存紧张的场景。策略 4按款式混排Mix by Stylescore utilization约束所有指定款式都必须排入enumerate_layouts()阶段将 2-3 个不同产品的排列当成组合空间搜索而非独立排布后再合并——这才是真正的混排。策略 5最少排版图种类Minimum Patternsscore -distinct_layout_count在所有方案中找到能够复用同一种排版图的方案组合。这个策略在大规模订单中效果显著——每减少一次换版就是约 1500 元的纯利润。五、六角密排圆形产品的特化优化罐盖和罐底都是圆形产品。如果按矩形网格排列图 1 左侧圆形之间的空隙相当可观。我们为圆形产品实现了六角密排Hexagonal Close Packing普通矩形排列 六角密排 ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ 关键偶数行偏移 w/2半格行距从 h 压缩为 h × √3/2理论上的最优填充率矩形排列π/4 ≈ 78.5% 六角密排π/(2√3) ≈ 90.7%差距超过 12 个百分点对大量圆形产品来说非常可观。实际应用中还要考虑边界效应和刀口加放但我们确实看到了显著提升。实现上并不复杂在enumerate_layouts()中如果能同时满足以下条件就自动启用六角密排条件 1产品形状为圆形或长宽比 ≈ 1 条件 2启用六角密排后不违反几何约束 条件 3利用率确实更高六、成本核算引擎排版的最终目的是控制成本。我们将印刷行业的价格体系抽象为一个独立的成本计算模块// 阶梯定价 LadderPrice { tiers: [ { min_qty: 0, max_qty: 1000, unit_price: p1 }, { min_qty: 1000, max_qty: 5000, unit_price: p2 }, { min_qty: 5000, max_qty: 10000, unit_price: p3 }, { min_qty: 10000, max_qty: ∞, unit_price: p4 }, ] } // 印刷成本计算公式 total_cost sheet_count × tiered_price(sheet_count) // 阶梯单价 sheet_count × waste_rate × material_price // 损耗 color_station_count × station_fee // 色位费 plate_change_count × setup_fee // 开机费 process_extra_fees // 附加工艺排版方案 成本核算的联动是这套系统区别于纯排样工具的核心差异——用户不仅知道利用率多高还知道这个方案最终花多少钱。七、系统技术架构┌─────────────────────────────────────┐ │ Vue 3 前端 │ │ ┌─────────┐ ┌──────────┐ ┌───────┐ │ │ │ Canvas │ │ Excel │ │ PDF │ │ │ │ 可视化 │ │ 导入导出 │ │ 排版图 │ │ │ └─────────┘ └──────────┘ └───────┘ │ ├─────────────────────────────────────┤ │ Spring Boot 3 后端 │ │ ┌─────────┐ ┌──────────┐ ┌───────┐ │ │ │ 规则引擎 │ │BeamSearch│ │成本核算│ │ │ │RuleEngine│ │ Solver │ │CostCalc│ │ │ └─────────┘ └──────────┘ └───────┘ │ │ ┌─────────┐ ┌──────────┐ ┌───────┐ │ │ │ OCR识别 │ │ PDF生成 │ │POI处理│ │ │ │(阿里云) │ │(OpenPDF) │ │(Excel)│ │ │ └─────────┘ └──────────┘ └───────┘ │ ├─────────────────────────────────────┤ │ PostgreSQL Redis │ │ Docker Kubernetes │ └─────────────────────────────────────┘技术选型考量OpenPDF排版图含大量中文字体尺寸标注、标题栏OpenPDF 相比 iText 在中文支持和开源协议上更有优势Apache POI处理工厂上传的 Excel 格式产品清单支持.xls和.xlsx阿里云 OCR不少工厂还在用纸质流转单手机拍照后 OCR 自动录入减少人工录入错误Canvas 2D排版结果实时预览支持缩放和拖拽对工业化场景来说交互够用八、总结这套系统的核心价值不在于功能堆砌而在于两点将不可量化的师傅经验变成了可执行、可优化、可传承的算法规则——行业知识不再随着人员流动而流失排版 成本核算的一体化——不只是排得好不好看而是排得省不省钱从实际数据看排版效率提升 90% 以上相比人工原材料利用率也有显著改善。对于一个月消耗数十万张马口铁的中型制罐厂来说利用率的提升直接转化为实实在在的成本节省。关于我惠州市浅草软件科技有限公司专注于智能制造领域的排样优化算法研发。本文所述系统为实际落地的工业软件产品欢迎技术交流和行业探讨。产品详情https://qiancaosoft.com/products/tinplate-printing