1. 从一张钢板到千万利润工业零件切割优化的现实意义如果你走进一家大型装备制造厂或者钢结构加工车间最常看到的场景之一可能就是巨大的数控切割机比如等离子切割机或激光切割机正在钢板上“作画”。火花四溅中一个个形状各异的零件被精准地切割出来。这看起来是再平常不过的工业流程但背后却藏着一个直接影响企业利润的“隐形杀手”——材料浪费。一块价值数千甚至上万元的钢板经过切割后剩下的边角料往往只能按废铁价格回收这中间的差价就是纯利润的流失。更关键的是在订单多、工期紧的时候如何用最少的钢板、最短的切割时间完成所有零件的生产直接关系到产能、交付周期和综合成本。这就是“工业零件切割优化”要解决的核心问题。它不是一个纸上谈兵的数学游戏而是制造业每天都在发生的、真金白银的成本博弈。2020年华数杯数学建模竞赛的B题正是将这一复杂的工业现实抽象成了一个经典的“二维不规则排样问题”要求参赛者设计出高效的优化方案。简单来说题目会给你一堆不同形状、不同尺寸、不同需求数量的零件图纸以及规定尺寸的矩形原材料板材。你的任务就是像玩一个没有间隙的“俄罗斯方块”把这些零件合理地排列在板材上目标是让板材的利用率最高也就是废料最少。同时现实生产中还可能考虑切割路径的总长度影响切割时间和耗材磨损、切割起点的数量影响编程和准备时间等因素。这道题考察的远不止是数学计算能力更是将实际问题转化为数学模型并运用智能算法寻找近似最优解的综合能力。对于学习工业工程、机械、自动化乃至管理科学的学生来说掌握这套思路就等于掌握了一把优化生产流程、降本增效的钥匙。2. 问题拆解从现实需求到数学模型的关键跃迁面对“工业零件切割优化”这样一个大命题直接上手编程或套用算法是行不通的。第一步也是最重要的一步是进行严谨的问题分析和数学建模。这决定了后续所有工作的方向和有效性。2.1 核心约束与优化目标的界定首先我们必须明确题目或实际生产给出的所有规则和限制这些构成了模型的约束条件。通常包括原材料约束板材是矩形的尺寸固定如2000mm × 1500mm。零件必须完全放置在板材边界内不能超出。零件约束每个零件有固定的几何形状可能是简单的矩形、圆形也可能是复杂的不规则多边形和需求数量。所有需求数量的零件必须被生产出来。排样约束这是最核心的几何约束。零件在板材上排放时彼此之间不能重叠。这意味着在二维平面上任意两个零件的内部区域没有交集。工艺约束可选但重要实际生产中还会有更多限制。例如零件边缘到板材边缘需要预留一定的“切割余量”或“夹持边”为了切割稳定性零件之间需要保留最小间隙防止热变形导致零件碰撞某些零件由于材质或后续工艺要求必须按特定方向排放如木材的纹理方向、金属的轧制方向。其次我们要定义什么是“好”的方案即优化目标。最常见的目标是最大化板材利用率使所有已排放零件的总面积之和占所用板材总面积的比例最高。这是最直接的经济性指标。最小化板材使用张数在零件需求总量很大的情况下目标可能是用完尽可能少的整张板材。这往往比单张板利用率更重要因为它直接减少了板材采购、搬运和更换的次数。最小化切割路径总长度对于激光或等离子切割切割头移动的路径越长耗时和耗电耗气就越多。优化切割顺序和路径可以显著提高效率。多目标综合优化现实中往往是多个目标需要权衡。例如在利用率相差不大的情况下优先选择切割路径更短的方案。对于华数杯B题这类竞赛题通常会明确给出单一或主要优化目标如最大化利用率并将其他因素作为约束或次要目标处理。2.2 几何关系的数学表达如何判断“不重叠”将“零件不能重叠”这一直观要求用数学语言描述出来是建模的难点。对于不规则多边形零件常用的方法是“No-Fit Polygon”NFP或称“临界多边形”法。它的核心思想非常巧妙我们不直接计算两个多边形是否相交而是计算当一个多边形称为零件A固定时另一个多边形零件B可以放置的位置范围。具体来说我们让零件B沿着零件A的轮廓“滑动”一圈记录下零件B的参考点通常是其几何中心或一个顶点所经过的轨迹。这个轨迹形成的多边形就是NFP。判断逻辑如果零件B的参考点落在NFP内部则两个零件重叠如果落在NFP外部则两个零件分离如果恰好落在NFP的边上则两个零件恰好相切接触但不重叠。通过预先计算好每对零件之间的NFP在排样时我们只需要检查待放置零件的参考点相对于已固定零件的NFP的位置关系即可快速判断是否满足不重叠约束这比实时进行复杂的多边形相交检测要高效得多。计算NFP本身是一个计算几何问题对于凸多边形有成熟的算法如Minkowski和对于凹多边形则更为复杂可能需要分解为凸多边形组合来处理。在竞赛中如果零件形状复杂有时会采用近似处理比如用零件的最小包围矩形来代替不规则形状进行初步排样但这会损失精度和利用率。2.3 模型建立一个优化问题的标准形式综合以上我们可以将切割优化问题构建成一个标准的组合优化模型决策变量每个零件在板材上的位置坐标x, y和旋转角度如果需要考虑旋转。约束条件每个零件必须位于板材边界内。任意两个零件之间满足无重叠关系通过NFP或相交检测判断。每个零件的需求数量得到满足。可选满足其他工艺约束。目标函数最大化板材利用率或最小化板材使用张数等。这个模型本质上是一个复杂的、非线性的、包含几何约束的组合优化问题属于NP-Hard问题。这意味着当零件数量稍多时几乎不可能在有限时间内求出精确的全局最优解。因此我们的重点转向了设计高效的启发式算法来寻找高质量的近似解。3. 算法兵器库启发式策略如何“寻优”既然精确求解不可行我们就需要借助“启发式”的智慧。启发式算法不保证找到最优解但能在可接受的时间内找到令人满意的“优解”。对于排样问题算法通常分为两个层次排放顺序策略和具体排放位置策略。3.1 零件排放的“优先级”制定先放哪个零件后放哪个零件结果大不相同。常见的排序启发式规则有面积优先优先排放面积最大的零件。理由是先把“大块头”安排好它们最难安置剩下的缝隙再用小零件填充。这是一种“先难后易”的思路。周长优先优先排放周长最长的零件。长条状或形状复杂的零件往往更难排早期固定它们有利于整体布局。数量优先优先排放需求数量最多的零件。这样可以尽早确定该种零件的布局模式。综合评分设计一个评分函数例如分数 面积 * 权重1 周长 * 权重2按分数从高到低排序。在实际尝试中并没有绝对最好的规则。通常需要将几种规则进行组合或对比测试。例如可以先按面积降序排对于面积相近的零件再按周长降序排。3.2 确定零件落脚点位置选择策略决定了排放顺序接下来要决定把当前零件放在板材的哪个具体位置。这里有几个经典策略最低水平线算法Bottom-Left, BL这是最基础、最直观的贪心策略。它模拟人排放物品的习惯总是将零件尽可能地向左移动然后再尽可能地向下移动直到碰到板材边界或已排放的零件为止。这个位置称为“最低最左可行点”。BL算法速度极快但容易在板材上方留下难以利用的“天空区域”。最低水平线填充算法BLF对BL算法的改进。它不仅仅寻找一个最低点而是维护一条动态的“轮廓线”由已排放零件的上边缘构成。新零件总是放置在这条轮廓线的最低点并尽可能左移。这能更好地填充凹陷区域利用率通常比单纯BL高。穴度算法这是一种更“精明”的策略。它不只看最低点而是评估板材上每个潜在放置位置周围的空间“紧凑”程度。零件放置后应该使得剩余的空间尽可能规整、易于被后续零件利用。评估标准可以是新零件与相邻零件的贴合紧密程度或者是放置后形成的“空洞”难以利用的小空间的大小和数量。在竞赛或实际应用中往往采用混合策略。例如先用BLF快速生成一个初始解然后再用穴度评估进行局部调整或者同时用多种位置策略尝试放置同一个零件选择其中结果最好的一个。3.3 全局优化引擎超越贪心的搜索贪心策略每一步都做出当前最优选择容易陷入局部最优。为了跳出局部最优找到更好的解需要引入全局搜索机制。模拟退火算法灵感来源于金属退火过程。它允许算法以一定的概率接受一个比当前解更差的“新解”这个概率随着“温度”参数的降低而逐渐减小。在排样问题中一个“新解”可以通过随机交换两个零件的排放顺序、随机旋转某个零件、或者将某个零件移动到另一个随机可行位置来产生。SA算法能有效进行全局探索但参数初始温度、降温速率等设置需要经验。遗传算法模仿生物进化。将一种排样方案编码成一条“染色体”例如一个包含所有零件排放顺序和角度的序列。初始时随机生成一群“个体”即多种方案然后让它们进行“选择”保留利用率高的、“交叉”两种方案交换部分序列、“变异”随机改变某个零件的顺序或角度。通过多代进化种群的整体质量会不断提升。GA擅长在巨大解空间中搜索但对编码方式和遗传算子的设计要求高。禁忌搜索通过一个“禁忌表”记录最近进行的移动禁止在短期内回退到之前的解从而迫使搜索走向新的区域。对于排样问题一次移动可以是交换两个零件的位置。在实际编程实现时我个人的经验是采用“启发式构造 元启发式优化”的框架。即用BLF或穴度算法作为“构造器”快速生成一个可行的排样方案然后将这个方案作为初始解喂给模拟退火或遗传算法进行迭代优化。优化过程中算法可以调用构造器来对局部修改后的零件序列进行重新排放。这种结合方式既能保证解的质量又能将计算时间控制在合理范围内。4. 实战流程与代码骨架从思路到实现有了清晰的算法思路接下来就是将其转化为可运行的代码。以下是一个基于Python的简化实现流程和关键代码段示意。我们假设零件都是矩形这是不规则多边形的基础目标是单张板利用率最大化。4.1 数据准备与几何工具首先定义核心的数据结构和一些基础几何函数。class Rectangle: def __init__(self, width, height, idNone): self.width width # 长 self.height height # 宽 self.id id self.x 0 # 放置位置左下角x坐标 self.y 0 # 放置位置左下角y坐标 self.rotated False # 是否旋转90度 def area(self): return self.width * self.height def get_placed_width(self): return self.height if self.rotated else self.width def get_placed_height(self): return self.width if self.rotated else self.height def overlap(rect1, rect2): 判断两个矩形是否重叠投影法 return not (rect1.x rect1.get_placed_width() rect2.x or rect2.x rect2.get_placed_width() rect1.x or rect1.y rect1.get_placed_height() rect2.y or rect2.y rect2.get_placed_height() rect1.y) def inside_plate(rect, plate_width, plate_height): 判断矩形是否在板材内 return (rect.x 0 and rect.y 0 and rect.x rect.get_placed_width() plate_width and rect.y rect.get_placed_height() plate_height)4.2 核心最低水平线填充算法实现BLF算法需要动态维护一个“轮廓线”这里我们用一组离散的“关键点”来近似表示。def bottom_left_fill(rectangles, plate_width, plate_height): 使用最低水平线填充算法排放一组矩形。 返回排放后的矩形列表和利用率。 # 按面积降序排序一种启发式规则 sorted_rects sorted(rectangles, keylambda r: r.area(), reverseTrue) placed [] # 已放置的矩形 # 初始化轮廓线开始时轮廓线就是板材的底边表示为一系列x坐标高度点 # 简化起见我们用板材左下角(0,0)作为起始放置点 skyline [(0, 0), (plate_width, 0)] # 每个元素是(x, height) for rect in sorted_rects: best_place None best_y float(inf) best_x float(inf) # 遍历轮廓线的每个线段寻找可能的放置位置 for i in range(len(skyline) - 1): x_start, h_start skyline[i] x_end, h_end skyline[i1] segment_width x_end - x_start # 尝试不旋转和旋转两种状态 for rotated in [False, True]: rect.rotated rotated req_width rect.get_placed_width() req_height rect.get_placed_height() if req_width segment_width: continue # 这个线段宽度放不下 # 候选放置位置左对齐于x_start高度为当前线段的高度h_start candidate_x x_start candidate_y h_start # 检查放置后是否超出板材右边界 if candidate_x req_width plate_width: continue # 检查与已放置矩形的重叠简化检查仅与轮廓线逻辑兼容的矩形检查 # 更严格的检查需要与所有已放置矩形进行overlap判断 temp_rect Rectangle(req_width, req_height) temp_rect.x, temp_rect.y candidate_x, candidate_y conflict False for p_rect in placed: if overlap(temp_rect, p_rect): conflict True break if conflict: continue # 计算实际放置后需要支撑的高度可能需要垫高 # 这里简化处理直接使用candidate_y # 更新轮廓线时再计算精确的支撑高度 # 评估位置优先选择y更低y相同时x更左的位置 if candidate_y best_y or (candidate_y best_y and candidate_x best_x): best_y candidate_y best_x candidate_x best_place (candidate_x, candidate_y, rotated) if best_place is None: # 当前板材无法放下该矩形可能需要启用新板材对于单张板优化这里意味着失败或需调整策略 print(fWarning: Cannot place rectangle {rect.id} on current plate.) continue # 放置矩形 rect.x, rect.y, rect.rotated best_place placed.append(rect) # 更新轮廓线这是一个简化更新真实的BLF轮廓线更新更复杂 # 此处为示意实际需要插入新的轮廓点并合并相邻的等高线段 # 简单做法在rect.x和rect.xwidth处将轮廓线高度提升到rect.yheight new_height rect.y rect.get_placed_height() # ... 这里省略具体的轮廓线数据结构更新代码 ... # 计算利用率 used_area sum(r.area() for r in placed) total_area plate_width * plate_height utilization used_area / total_area if total_area 0 else 0 return placed, utilization4.3 优化迭代模拟退火框架我们用模拟退火来优化排放顺序。扰动方式采用随机交换两个零件在排序列表中的位置。import random import math def simulated_annealing(rectangles, plate_width, plate_height, initial_temp1000, cooling_rate0.995, iterations1000): 模拟退火优化排样顺序。 # 初始解按面积排序 current_order sorted(rectangles, keylambda r: r.area(), reverseTrue) current_placed, current_util bottom_left_fill([r.copy() for r in current_order], plate_width, plate_height) best_order current_order.copy() best_util current_util best_placed current_placed temp initial_temp for i in range(iterations): # 产生新解随机交换两个零件的位置 new_order current_order.copy() idx1, idx2 random.sample(range(len(new_order)), 2) new_order[idx1], new_order[idx2] new_order[idx2], new_order[idx1] # 评估新解 new_placed, new_util bottom_left_fill([r.copy() for r in new_order], plate_width, plate_height) # 计算能量差这里利用率越高能量越低 delta_e current_util - new_util # 如果new_util更高delta_e为负表示能量降低 # Metropolis准则 if delta_e 0 or random.random() math.exp(-delta_e / temp): # 接受新解 current_order new_order current_util new_util current_placed new_placed # 更新历史最优 if new_util best_util: best_util new_util best_order new_order.copy() best_placed new_placed print(fIteration {i}: New best utilization {best_util:.4f}) # 降温 temp * cooling_rate return best_order, best_placed, best_util4.4 可视化与结果分析最后将排样结果用图形展示出来这是验证算法效果和发现问题的关键一步。可以使用matplotlib库。import matplotlib.pyplot as plt import matplotlib.patches as patches def visualize_placement(placed_rectangles, plate_width, plate_height, titleCutting Layout): fig, ax plt.subplots(1, figsize(10, plate_height/plate_width*10)) ax.set_xlim(0, plate_width) ax.set_ylim(0, plate_height) # 绘制板材边框 plate patches.Rectangle((0,0), plate_width, plate_height, linewidth2, edgecolorblack, facecolorlightgray, alpha0.5) ax.add_patch(plate) # 绘制每个零件 colors plt.cm.tab20.colors for i, rect in enumerate(placed_rectangles): color colors[i % len(colors)] patch patches.Rectangle( (rect.x, rect.y), rect.get_placed_width(), rect.get_placed_height(), linewidth1, edgecolorblack, facecolorcolor, alpha0.7, labelfPart {rect.id} if rect.id else fRect {i} ) ax.add_patch(patch) # 在零件中心标注ID ax.text(rect.x rect.get_placed_width()/2, rect.y rect.get_placed_height()/2, str(rect.id) if rect.id else str(i), hacenter, vacenter, fontsize8, colorblack) ax.set_aspect(equal) ax.set_title(f{title} (Utilization: {sum(r.area() for r in placed_rectangles)/(plate_width*plate_height):.2%})) plt.xlabel(Width) plt.ylabel(Height) # 图例如果太多可以省略 # plt.legend(bbox_to_anchor(1.05, 1), locupper left) plt.grid(True, linestyle--, alpha0.5) plt.tight_layout() plt.show()调用示例# 1. 定义板材和零件 plate_w, plate_h 2000, 1500 parts [ Rectangle(400, 300, id1), Rectangle(500, 200, id2), Rectangle(300, 300, id3), Rectangle(200, 400, id4), Rectangle(600, 250, id5), # ... 更多零件 ] # 2. 运行模拟退火优化 best_order, best_placed, best_util simulated_annealing(parts, plate_w, plate_h, iterations500) print(fBest utilization found: {best_util:.4%}) # 3. 可视化结果 visualize_placement(best_placed, plate_w, plate_h, titleOptimized Cutting Layout)5. 从竞赛到实战必须考虑的工程化细节上面的代码骨架提供了一个清晰的思路但真要处理像华数杯B题这样的竞赛问题或者应用于实际工业场景还有大量的细节需要打磨。这些细节往往是区分普通解和优秀解的关键。5.1 不规则零件的处理策略现实中零件很少是标准的矩形。处理不规则多边形可能是带孔洞的是真正的挑战。矩形包络法用零件的最小外接矩形MBR或最小面积外接矩形Min-Area Bounding Rectangle来近似。这种方法最简单计算快但浪费严重因为矩形内部的空白区域也被占用了。凸包近似计算零件的凸包用凸多边形来近似。凸包比矩形更贴合零件形状且凸多边形之间的NFP计算有成熟算法。但对于凹多边形凸包会丢失内部凹陷信息。凹多边形分解将复杂的凹多边形分解成多个凸多边形的并集。排样时将这些凸子多边形作为一个整体带相对位置约束进行排放。这大大增加了问题的复杂度但能显著提高利用率。基于像素或栅格的近似将板材和零件离散化为精细的栅格像素零件放置转化为二维矩阵的填充问题。这种方法可以处理任意复杂形状甚至考虑切割缝宽度但计算量巨大栅格精度和计算效率需要权衡。在竞赛中如果题目给出了不规则多边形的顶点坐标通常需要实现真正的多边形NFP计算和相交检测。可以使用shapely这样的几何计算库来辅助但要注意自己实现核心算法以体现建模能力。5.2 切割工艺约束的融入数学模型必须向生产工艺妥协。切割余量/桥接零件之间、零件与板边之间需要预留间隙如2mm。这相当于在排样时将每个零件的几何外形向外“偏移”一个余量距离形成“等距轮廓”然后用这个膨胀后的轮廓进行排样和碰撞检测。共边切割如果两个零件的边是平行的且距离很近可以考虑让切割头只走一次切出共享的边这能缩短路径、减少耗材。在模型中这可以转化为允许两个零件的膨胀轮廓在一定条件下“相切”甚至轻微重叠仅共享边部分。切割起点与路径不同的排放方案会导致完全不同的切割路径。一个复杂的优化目标是“最小化空程移动”切割头在不切割时的移动距离。这需要在排样完成后再运行一个“旅行商问题”的变种来优化切割顺序。5.3 算法性能与效率的平衡当零件数量达到数百甚至上千时算法的运行时间会成为瓶颈。空间索引加速在判断零件重叠时不要总是与所有已放置零件进行遍历比较。可以使用空间索引数据结构如四叉树、R树快速检索出当前位置附近可能发生碰撞的零件只与这些零件进行精确检测。启发式规则的动态调整不要固守一种排序规则。可以采用自适应策略例如在排样初期使用面积优先当板材剩余空间变得碎片化时切换到更适合填充小空隙的规则如优先排放长宽比接近1的小零件。并行计算模拟退火、遗传算法中的大量个体评估是相互独立的非常适合并行化。可以利用多核CPU进行并行计算大幅缩短优化时间。初始解的多样性不要只从一个初始解如按面积排序开始优化。可以随机生成多个不同的初始排序分别进行优化最后取最好的结果这有助于避免陷入某个特定的局部最优。5.4 结果验证与方案输出算法跑出一个高利用率的结果并不代表万事大吉。几何有效性验证必须对最终排样方案进行严格的几何验证。编写一个检查函数确保任意两个零件的膨胀轮廓含余量都不重叠且所有零件都在板材内部。这是防止出错的最后一道防线。生成生产数据最终的输出不能只是一张图片或利用率数字。需要生成机器可读的切割文件如DXF或NC代码。这需要将排样结果每个零件的最终位置和旋转角度转换为具体的切割路径坐标并考虑切割引入、引出线。方案可读性除了机器文件还应生成一份给人看的排样图和生产清单清晰标注每个零件的编号、位置、使用的板材编号方便车间工人核对和上料。在我参与过的实际项目中曾因为忽略了一个1mm的工艺余量导致算法生成的“最优”方案在验证时发现大量零件重叠不得不推倒重来。这个教训让我深刻意识到在优化问题中约束条件的精确性和完整性其重要性丝毫不亚于优化算法本身。一个考虑了80%约束的“最优解”在实际中可能100%不可用。因此在动手编码前花足够的时间与工艺人员沟通吃透每一个生产细节是成功的关键。这道数学建模竞赛题本质上是一次完整的工业问题求解流程训练从问题分析、抽象建模、算法设计、编程实现到最终考虑工程落地每一步都环环相扣。