1. 问题引入从一块钢板到千万种可能最近刚带着团队打完2024年五一杯数学建模的A题题目聚焦在一个听起来很工业但内核极其考验数学抽象和算法设计能力的问题上钢板切割优化。简单说就是给你一块大钢板上面有若干种不同形状、不同数量需求的小零件需要切割出来。目标是在满足所有零件需求的前提下尽可能减少切割过程中产生的废料或者说提高这块钢板的材料利用率。这可不是我们手工裁纸画个线剪下来就行。工业级的钢板切割一次下料可能涉及成千上万张钢板每节省1%的废料带来的原材料成本节约都是巨大的。所以这类问题一直是运筹学、组合优化和工业工程领域的经典难题也是数学建模竞赛的常客。五一杯这道题算是把这个经典问题又一次摆在了参赛者面前考验大家如何将实际问题转化为数学模型并设计出高效、可行的求解策略。很多人一看到“优化”、“切割”就觉得头大感觉要动用非常深奥的数学理论。其实不然它的核心思想很直观如何像玩一个最极致的“拼图游戏”把各种形状的零件严丝合缝地排布在钢板这个“画布”上同时还要考虑切割工艺的约束比如切割刀头不能拐急弯切割路径要连续等。这道题的魅力就在于它连接了抽象的数学规划和真实的生产场景。今天我就结合我们团队的解题过程把这里面的门道掰开揉碎了讲清楚从问题理解、模型建立到算法实现给你一条清晰的路径。2. 核心问题拆解我们到底要解决什么面对一个建模问题最忌讳的就是还没看清题目就埋头建模型。我们拿到A题后花了将近一个小时就干了一件事把问题说明书逐字逐句读了三遍并提炼出了几个必须明确的核心点。这是后续所有工作的基石。2.1 决策的本质排样与切割序列首先要明白我们做两个层面的决策排样Nesting决定每个零件放在钢板的什么位置以及如何旋转如果允许的话。目标是让所有零件尽可能紧密地靠在一起减少零件之间的空隙这些空隙就是废料。切割路径Cutting Path决定切割头的移动顺序。就像用笔描边你需要决定从哪个点开始按什么顺序切割每个零件的轮廓。目标是最小化切割头的空行程不进行切割的移动距离因为空行程消耗时间影响生产效率。很多时候排样问题和路径问题是耦合的。一个好的排样方案如果切割路径乱七八糟空行程很长整体效率也可能不高。但在这类竞赛题中通常会更侧重于排样优化将路径优化作为后续的加分项或简化处理。2.2 关键约束与条件题目中一定会给出限制条件这些条件直接决定了模型的复杂度和算法的选择钢板规格是单一尺寸的矩形钢板还是多种尺寸本题通常是单一尺寸长宽固定。零件信息每种零件的几何形状多边形列表坐标、数量需求。形状可能是凸多边形也可能是带“凹”角的复杂多边形。工艺约束切割间距Kerf切割刀具有一定宽度切割时材料会有损耗因此零件之间必须留出最小间距否则两个零件会因切割损耗而连在一起或尺寸不达标。这是必须考虑的约束通常通过将零件轮廓向外“膨胀”一个间距值来实现。零件旋转是否允许零件旋转允许旋转多少度如0° 90° 180° 270°或任意角度允许旋转能极大地提高排样灵活性但也会增加搜索空间。排样方式是“一刀切”的精确排样还是允许零件轮廓相互嵌套即一个零件的凹槽可以放入另一个零件的凸起部分后者对算法要求更高。切割方式是连续的轮廓切割还是更简单的“一刀切”式分条、分割竞赛题通常默认为轮廓切割。2.3 优化目标目标函数通常是单一的也可能是多目标的主要目标最大化材料利用率。即所有零件总面积 / 使用的钢板总面积。利用率越高废料越少。次要或关联目标最小化使用的钢板张数最小化总切割路径长度或切割时间。我们的策略是优先保证主要目标在材料利用率相近的情况下再考虑优化切割路径。3. 模型构建如何用数学语言描述“拼图”把实际问题翻译成数学模型是建模的核心环节。对于钢板切割主流的方法是建立混合整数规划模型但对于复杂形状和大量零件直接求解MIP几乎不可能。因此竞赛中更实用的思路是“启发式算法框架 精确模型局部辅助”。3.1 几何关系的数学表达这是模型的基础即如何用公式判断两个零件是否重叠。No-Fit PolygonNFP 非拟合多边形这是处理不规则形状排样重叠判断的核心工具。简单来说对于两个多边形A和BNFP(A, B)定义了多边形B的参考点相对于多边形A的参考点所有可能放置的位置使得B恰好与A接触但不重叠。如果B的参考点落在NFP内部则两多边形重叠落在NFP边上则相切落在NFP外部则不重叠。基于NFP的重叠约束对于零件i和j设它们的参考点坐标分别为 (xi, yi) 和 (xj, yj) 它们对应的NFP为 NFPij。那么不重叠条件可以表示为(xj - xi, yj - yi) 这个向量不在 NFPij 的内部。这通常转化为一系列线性不等式来近似描述NFP的边界但更常见的做法是在算法中直接进行几何计算判断。内含Inclusion约束零件必须完全放在钢板内部。设零件i的几何外形为Poly_i钢板为矩形Rect则需要满足 Poly_i(平移旋转后) ⊆ Rect。这可以通过判断零件所有顶点坐标都在钢板边界内来实现。3.2 建立优化模型框架虽然不直接求解但建立一个清晰的模型框架有助于理清思路决策变量二元变量是否使用某张钢板如果多张钢板。连续变量每个零件的放置坐标 (xi, yi)。离散变量每个零件的旋转角度 θi如果允许旋转。约束条件所有零件都必须被分配给某张钢板如果多张。同一张钢板上的任意两个零件满足基于NFP的“无重叠”约束。所有零件都必须在钢板边界内。每种零件的放置数量等于其需求数量。目标函数 Max (总零件面积 / 总使用钢板面积) 或 Min (总使用钢板面积)。这个模型本身是NP-Hard问题直接调用商业求解器如Gurobi, CPLEX对于稍大规模算例就会超时。因此我们的重点转向设计高效的启发式算法。4. 算法策略贪心、搜索与智能优化我们采用了“分层优化”的策略将大问题分解为几个可处理的子问题。4.1 底层几何工具NFP的计算与碰撞检测在实现任何高级算法前必须有一个可靠的几何引擎。我们主要用Python的shapely库。计算NFP对于两个多边形可以通过滑动法Minkowski Sum来计算。shapely库提供了object.buffer()和object.difference()等功能可以辅助实现。对于竞赛如果零件是凸多边形计算相对简单如果是凹多边形则需要更复杂的算法。一个实用的竞赛技巧是如果时间有限可以用零件的外接矩形或凸包来近似计算NFP虽然保守但能保证可行性且大大降低计算复杂度。实时碰撞检测在算法迭代放置零件时需要快速判断当前位置是否与已放置零件重叠。使用shapely的intersects()和buffer(kerf/2)可以非常高效地完成。这是算法中调用最频繁的函数其效率至关重要。import shapely.geometry as sg from shapely.ops import unary_union def check_overlap(new_part_poly, placed_polys, kerf): 检查新零件多边形是否与已放置的零件多边形集合重叠考虑切割间距 new_part_poly: 新零件的shapely多边形对象 placed_polys: 已放置零件的shapely多边形对象列表 kerf: 切割间距 # 将新零件轮廓向外膨胀半个切割间距 new_part_buffered new_part_poly.buffer(kerf / 2) for placed_poly in placed_polys: # 如果膨胀后的新零件与任何已放置零件相交则重叠 if new_part_buffered.intersects(placed_poly): return True return False4.2 排样算法从贪心到全局搜索贪心算法Bottom-Left BL这是最基础的启发式算法。将零件按某种规则如面积从大到小排序。对于每个零件从钢板的左上角开始尝试将其移动到“最左下”的可能位置。所谓“最左下”就是先尽可能向下移动直到碰到边界或已放零件再尽可能向左移动。这个算法速度快但容易陷入局部最优排样利用率一般。改进贪心与局部搜索BLFBottom-Left-Fill在BL的基础上不仅尝试“左下”还会尝试填充已放零件之间形成的空洞。随机贪心将零件顺序随机打乱多次运行BL或BLF算法选择最好的一次结果。简单但有效。临界多边形Inner-Fit Polygon, IFPIFP定义了零件可以放置而不超出边界的区域。将NFP和IFP结合可以更精确地找到候选放置点而不仅仅是沿着钢板边界滑动。高级元启发式算法模拟退火SA非常适合这类排列组合优化问题。我们可以将“解”定义为一种零件放置顺序和旋转角度的序列。邻域操作可以是交换两个零件的位置、改变一个零件的旋转角度、将一个零件移到序列末尾等。SA以一定概率接受劣解有助于跳出局部最优。遗传算法GA将排样方案编码为染色体如零件ID序列旋转标记。通过选择、交叉、变异操作进化种群。适应度函数就是材料利用率。GA的优势在于能并行搜索多个区域但编码和解码从序列到实际排样的设计需要技巧且容易早熟。禁忌搜索TS记录最近的操作历史禁忌表禁止短期内重复这些操作从而强制搜索走向新区域。我们的混合策略我们采用了“模拟退火框架”来驱动一个“基于IFP/NFP的贪心放置器”。SA负责宏观搜索它不断生成新的零件顺序列表。贪心放置器负责微观实现对于SA给出的一个零件序列放置器严格按照这个顺序依次为每个零件寻找当前最优的放置位置通过计算与所有已放零件的NFP找到IFP内的最低最左点。这个放置过程是确定的。SA评估放置器完成后得到一个完整的排样方案和对应的材料利用率。SA将这个利用率作为当前解的评价决定是否接受新解。 这样SA不需要关心复杂的几何细节只需优化序列而贪心放置器则高效地将序列转化为实际排样。4.3 切割路径优化从排样到刀路当排样方案确定后所有零件的轮廓位置就固定了。此时切割头需要从一个起点出发依次走完所有轮廓最后返回起点或结束。这本质上是一个**旅行商问题TSP**的变种只不过“城市”变成了一个个封闭的轮廓。每个轮廓需要选择一个“切入点”。图模型构建将每个零件的轮廓看作一个“簇”。我们需要决定访问这些簇的顺序以及每个簇从哪个点切入。两阶段优化簇间排序先忽略每个轮廓的具体切入点只考虑轮廓之间的质心距离用TSP算法如简单的最近邻贪心或更精确的LKH算法确定访问轮廓的大致顺序。簇内切入点选择对于每个轮廓在已确定的访问顺序下选择上一个轮廓出口到当前轮廓上最近的点作为切入点。这通常需要遍历轮廓上的所有点或采样点。Floyd-Warshall算法的应用如果我们将钢板布局离散化为一个图网格虽然不必要或者我们在轮廓上采样了多个候选切入点那么计算任意两个切入点之间的最短距离直线距离需考虑是否跨越已切割区域但通常简化为欧氏距离时如果需要频繁计算所有点对间最短路径Floyd-Warshall算法是一种选择。但在本题的切割路径优化中Floyd-Warshall通常不是首选因为我们的图很小节点数是轮廓采样点数且距离计算简单欧氏距离直接计算即可。Floyd-Warshall的O(n^3)复杂度在这里优势不大。它更适用于有中间障碍、需要计算真正图最短路径的场景。在本题中提到它可能是为了体现对图论算法的了解实际实现时更常用最近邻法、2-opt局部搜索等来解决TSP部分。# 一个简化的切割路径贪心算法示例 def simple_cutting_path(part_polys, start_point): 计算简单的切割路径最近轮廓贪心 part_polys: 放置好的零件多边形列表 start_point: 切割起点如钢板左下角 unvisited part_polys.copy() current_pos start_point path_order [] total_distance 0.0 while unvisited: # 找到距离当前位置最近的轮廓 nearest_poly min(unvisited, keylambda poly: current_pos.distance(poly.exterior)) # 找到该轮廓上距离当前点最近的点作为切入点 nearest_point_on_poly nearest(nearest_poly.exterior, current_pos) # 记录移动 total_distance current_pos.distance(nearest_point_on_poly) path_order.append(nearest_poly) # 更新当前位置为该轮廓的切入点切割完轮廓后终点也是起点 current_pos nearest_point_on_poly unvisited.remove(nearest_poly) # 最后返回起点可选 total_distance current_pos.distance(start_point) return path_order, total_distance5. 代码实现与编程细节我们主要使用Python因其有丰富的科学计算和几何库。核心流程如下5.1 数据预处理import json import shapely.geometry as sg from shapely.affinity import rotate, translate # 假设从文件读取数据 with open(data.json, r) as f: data json.load(f) plate_width data[plate_width] plate_height data[plate_height] kerf data[kerf] parts_data data[parts] # 列表每个元素包含‘id’ ‘vertices’ ‘demand’ ‘rotatable’等 # 将零件数据转换为shapely多边形对象并考虑旋转集合 parts [] for p in parts_data: base_poly sg.Polygon(p[vertices]) rot_angles [0] # 默认不旋转 if p[rotatable]: rot_angles [0, 90, 180, 270] # 假设允许90度整数倍旋转 for angle in rot_angles: rotated_poly rotate(base_poly, angle, origincentroid) # 这里可以预先计算多边形的面积、外接矩形等属性方便后续排序 parts.append({ id: p[id], original_id: p[id], poly: rotated_poly, area: rotated_poly.area, angle: angle, demand: p[demand] }) # 注意由于每个原始零件可能有多个旋转版本且需求数量1我们需要生成待排列表 # 例如零件A需求3个允许旋转0和90度则待排列表里会有6个实体3*25.2 模拟退火主循环import random import math import copy def simulated_annealing(parts_list, plate_poly, kerf, initial_temp1000, cooling_rate0.995, iterations5000): 模拟退火主函数 parts_list: 待排样的零件对象列表已扩展需求数量 plate_poly: 钢板多边形 kerf: 切割间距 current_order parts_list.copy() random.shuffle(current_order) best_order current_order.copy() best_placement, best_utilization greedy_placer(current_order, plate_poly, kerf) current_utilization best_utilization 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_placement, new_utilization greedy_placer(new_order, plate_poly, kerf) # 计算接受概率 delta new_utilization - current_utilization if delta 0 or math.exp(delta / temp) random.random(): current_order new_order current_utilization new_utilization if current_utilization best_utilization: best_order current_order.copy() best_placement new_placement best_utilization current_utilization # 降温 temp * cooling_rate # 可以添加一些终止条件如温度低于阈值或连续多次未改进 return best_order, best_placement, best_utilization5.3 贪婪放置器实现这是算法的核心需要高效地找到当前零件的最佳放置点。def greedy_placer(parts_order, plate_poly, kerf): 贪婪放置器按给定顺序放置零件每个零件放在当前最低最左的可行位置。 返回放置结果多边形列表和材料利用率。 placed_polys [] # 存放已放置的多边形 plate_bbox plate_poly.bounds # (minx, miny, maxx, maxy) for part in parts_order: part_poly part[poly] placed False best_pos None best_poly None # 一个简单的搜索策略在钢板范围内按一定步长如1mm生成候选点 # 更高级的做法是使用IFP和NFP生成候选点 step 5 # 搜索步长影响精度和速度 for x in range(int(plate_bbox[0]), int(plate_bbox[2]), step): for y in range(int(plate_bbox[1]), int(plate_bbox[3]), step): candidate_poly translate(part_poly, xoffx, yoffy) # 检查是否在钢板内 if not plate_poly.contains(candidate_poly): continue # 检查是否与已放零件重叠考虑kerf if not check_overlap(candidate_poly, placed_polys, kerf): # 找到第一个可行位置最低最左策略 placed_polys.append(candidate_poly) placed True break if placed: break if not placed: # 如果当前钢板放不下可以在这里处理多张钢板逻辑 # 对于单张钢板问题这意味着排样失败利用率记为0或很低 pass # 计算利用率 total_part_area sum(p.area for p in placed_polys) plate_area plate_poly.area utilization total_part_area / plate_area if plate_area 0 else 0 return placed_polys, utilization5.4 可视化与结果输出使用matplotlib进行可视化是必不可少的它能直观检查排样结果和切割路径。import matplotlib.pyplot as plt from matplotlib.patches import Polygon as MplPolygon import matplotlib.patches as patches def visualize_placement(placed_polys, plate_poly, path_orderNone): fig, ax plt.subplots(figsize(12, 8)) # 绘制钢板 plate_patch patches.Rectangle((plate_poly.bounds[0], plate_poly.bounds[1]), plate_poly.bounds[2]-plate_poly.bounds[0], plate_poly.bounds[3]-plate_poly.bounds[1], linewidth2, edgecolorblack, facecolorlightgray, alpha0.5) ax.add_patch(plate_patch) # 绘制零件 colors plt.cm.tab20(np.linspace(0, 1, len(placed_polys))) for i, poly in enumerate(placed_polys): x, y poly.exterior.xy ax.fill(x, y, alpha0.6, fccolors[i], ecblack, linewidth0.5) # 可以在零件中心标注ID ax.text(poly.centroid.x, poly.centroid.y, str(i), hacenter, vacenter, fontsize8) # 绘制切割路径如果提供 if path_order: for i in range(len(path_order)-1): p1 path_order[i].centroid p2 path_order[i1].centroid ax.plot([p1.x, p2.x], [p1.y, p2.y], r--, linewidth1, alpha0.7) ax.set_aspect(equal) ax.set_xlim(plate_poly.bounds[0]-10, plate_poly.bounds[2]10) ax.set_ylim(plate_poly.bounds[1]-10, plate_poly.bounds[3]10) plt.title(钢板排样与切割路径示意图) plt.xlabel(X (mm)) plt.ylabel(Y (mm)) plt.grid(True, linestyle--, alpha0.3) plt.show()6. 参赛实战心得与避坑指南带队打完这场比赛有几个深刻的体会这些是光看论文和代码学不到的。6.1 时间分配是生命线数学建模竞赛就三天时间极其紧张。我们的策略是第一天上午全力读题、讨论、确定基础模型和算法路线图。这个阶段不要急着敲代码一定要把问题边界、假设、目标统一清楚。我们甚至画了一个时间甘特图。第一天下午到第二天晚上核心实现期。分工明确一人主攻几何计算和基础放置算法greedy_placer一人主攻优化算法框架simulated_annealing一人开始撰写论文的“问题重述”、“模型假设”和“符号说明”部分。第三天整合、调参、跑最终结果、完成论文主体和摘要。最后留出至少3小时进行论文的整体润色、检查格式和错别字。6.2 模型“简化”的艺术竞赛不是做学术研究不求理论上完美但求结果上有效、可解释。面对复杂多边形NFP计算耗时的问题我们果断采用了外接矩形近似。虽然这会损失一些排样空间导致利用率略低于理论最优但换来了算法速度几十倍的提升让我们有时间进行更多的SA迭代和随机重启。在论文中我们明确说明了这一简化及其可能的影响并给出了如果不采用简化的理论改进方向这体现了对问题的深入思考。6.3 算法参数调优没有银弹模拟退火的初始温度、降温速率、迭代次数对结果影响巨大。我们编写了一个简单的参数扫描脚本def parameter_sweep(): temp_list [500, 1000, 2000] cool_list [0.99, 0.995, 0.999] iter_list [2000, 5000, 10000] best_params None best_util 0 for T in temp_list: for cr in cool_list: for it in iter_list: util run_sa_with_params(T, cr, it) # 封装好的运行函数 if util best_util: best_util util best_params (T, cr, it) print(fBest params: T0{best_params[0]}, cool{best_params[1]}, iter{best_params[2]}, util{best_util})最终我们发现对于我们的问题规模初始温度1000、降温率0.995、迭代5000次是一个不错的平衡点。关键是要在论文中展示你调参的过程和理由这比直接给出一个神奇的数字更有说服力。6.4 可视化是提分利器一张清晰的排样结果图胜过千言万语。我们不仅用matplotlib生成了静态排样图还利用其动画功能FuncAnimation制作了SA算法迭代过程中排样利用率提升的动态过程图插入到论文中。这直观地展示了算法的收敛过程极大地增强了论文的表现力和说服力。评委也是人对直观易懂的图表天然有好感。6.5 代码的健壮性与论文的对应你的所有结果必须由代码生成且代码要能复现。我们养成了一个习惯每产生一个关键结果如最终排样图、利用率曲线、对比表格立即在代码中保存对应的数据和图片并标注好是哪个参数下的结果。论文中提到的每一个数字、每一张图都要能在代码里找到明确的生成段落。这样在最后检查时可以快速验证避免出现论文和代码对不上的致命错误。6.6 切割路径部分不要喧宾夺主在时间有限的情况下如果排样优化是主体切割路径优化可以作为“模型推广”或“优化展望”部分。我们实现了一个简单的最近邻贪心TSP算法来计算路径长度并与“蛇形”扫描等简单策略做了对比证明了优化路径能进一步减少时间。这展示了思维的全面性但没有在核心算法上耗费过多时间。在论文中我们将其放在“模型优化与扩展”章节清晰界定了主次。这次五一杯A题的挑战让我们对运筹优化问题的建模全流程有了更深的体会。从抽象的数学描述到具体的代码实现再到最终论文的呈现每一个环节都需要严谨的思考和灵活的应变。最大的收获不是某个特定的算法而是这种“问题分解-算法选型-实现调优-结果呈现”的系统性解决问题能力。