简介2024年“深圳杯”数学建模挑战赛B题参赛作品聚焦批量工件并行切割下料问题面向数学建模竞赛参赛者及工程机械领域优化研究者提供完整的参赛论文与附录代码。资源内含48页论文针对A、B、C三种矩形板材的切割排版建立了以面积利用率最大化为目标的混合整数规划模型并采用贪心算法、遗传算法、粒子群算法等多种优化方法求解多问方案。内容覆盖数据预处理、多目标优化、动态调度及刀具协同运行设计尤其在问题四、五中进一步考虑切割总时间、能量消耗与设备时间成本提出自适应分区算法和智能休眠机制实现综合成本降低22%同时保持高利用率。全包为1个doc文件大小2.03MB已有535人学习下载适合需要赛题完整思路、模型推导与代码实现参考的建模团队深入研读。1. 从“先切后组”到“边组边切”这道题到底在考什么先说结论2024年深圳杯B题“批量工件并行切割下料”表面看是一道板材切割的排样优化题实际上是一道披着几何外衣的组合优化问题。很多人第一次看到题目第一反应是去查各种切割算法、套材软件的做法结果绕了一大圈发现无从下手——因为这道题真正要你解的不是“怎么在一个多边形里塞下更多工件”而是“如何把n个形状各异的工件以最小的总代价分成若干组再在m台并行切割机上完成加工”。简单说一下题目背景企业接到一批工件订单规格不同、形状各异需要从标准尺寸的母材通常是矩形板材上切割下料。与传统的单张板材逐件切割不同这里引入了并行切割机——多台设备可以同时工作每台设备一次装夹可以切割一组工件。于是问题自然分裂成三个子问题怎么把工件分组使得每组工件拼在同一张板材上不浪费怎么在每一组内部做排样让材料利用率最高怎么把这一堆任务分配到并行机器上让总完工时间最短。这三个子问题不是独立的。分组方式直接影响排样效果排样结果决定材料利用率而并行调度又牵扯到机器的空闲时间和任务负载均衡。换句话说分组、排样、调度三者是耦合的任何一步单独做最优整体都可能不是最优。这就是为什么你如果只盯着“怎么套料”去查资料会发现答案跟题目对不上——这道题的本质是一个三层嵌套优化而不是单纯的几何排样。从参赛角度来看这道题还有一个隐形的难点题目给的数据不可能是规整的矩形工件多半是带角度的多边形甚至是异性件。这意味着哪怕只是判断“两个工件能不能摆在一起”都需要先做几何运算更别提做排样优化了。所以这道题真正适合的解法不是某个“高深的算法”而是一套能把几何计算、组合优化、工程调度串起来的完整建模方案。2. 模型拆解三阶段决策框架与数学化表达2.1 核心决策变量与优化目标的“主次关系”我在复现这道题的时候最先做的不是写代码而是把整个决策过程抽象成数学模型。这里最关键的是想清楚目标函数到底优化谁题目常见的问法是多目标协调——既要材料利用率高又要加工时间短。这在数学上可以做成加权和也可以做成分层优化。我建议采取“主目标次目标”的方式优先保证材料利用率最大化在剩余可行解中找总完工时间最短的方案。原因很朴素切割料是企业的直接成本材料利用率低意味着真金白银的损失而时间只要在交货期内能接受优先级可以往后放。决策变量则分为三层分组变量第 k 组是否包含工件 i0-1 变量排样变量第 k 组中工件 i 的摆放位置和旋转角度连续变量整数变量调度变量第 k 组分配到哪台机器、在哪个时序启动0-1 变量排序变量。把这三层变量写在一起模型规模会非常大直接丢给求解器基本跑不动。所以实践中不必追求一个完整的大模型一次性求解把这个三层结构拆开、分阶段迭代才是可行路线。2.2 约束条件的“隐形陷阱”约束条件里最容易踩坑的是几何约束。常规的数学建模书会告诉你每一组内工件之间不能重叠、工件必须在板材边界内、切割路径不能交叉但实际建模时还需要额外考虑切割刀具的尺寸补偿相邻工件间要留出刀缝不然实际切割时边缘会被烧蚀或刀具切坏相邻工件模型里表现为最小间距约束旋转角度离散化真实工业切割机往往只支持 0°、90°、180°、270° 四种旋转直接把它当连续变量做会带来不可行的方案板材的纤维方向部分工件对纹理方向有要求不允许任意旋转此时旋转角度集合进一步缩小。我在建模时把上述约束全部显式写成不等式组。别嫌麻烦宁可模型里多几条约束也不要等程序跑出重叠解再回头补救。几何约束漏一条后面所有结果都要推翻重来。调度部分的约束也不轻松。并行机调度意味着一台机器同一时刻只能切割一组工件每组的加工时间取决于排样结果路径长度开工时间需满足工件齐套约束。这几条写出来就是经典的析取约束disjunctive constraint在模型里用大M法转成线性约束即可。2.3 目标函数的具体表达式设工件总数为 n分组成 K 组。定义第 k 组工件占用的最小包围矩形面积或实际使用的板材面积 S_k排样后通常取最小外接矩形板材标准面积为 S_board。材料利用率可以写成[ \eta \frac{\sum_{i1}^{n} A_i}{\sum_{k1}^{K} S_k} ]其中 A_i 是第 i 个工件的实际面积。这个公式一目了然分子是工件本身面积的总和是固定不变的分母越小利用率越高也就是说我们要让每组工件拼得越紧凑越好。总加工时间则定义为所有机器中最后完成切割的那台机器的完工时间[ T_{\text{total}} \max_{j1,\dots,m} C_j ]其中 C_j 是第 j 台机器的完工时间。整道题的求解目标就是在满足所有几何和调度约束的前提下先最大化 η再最小化 T_total。这个数学化过程做完整道题的求解思路立刻就清楚了外层做分组迭代中间层做排样计算内层做调度评估三层循环套起来就是一个完整的优化框架。3. 算法选型从贪心基准到元启发式再到混合策略3.1 为什么要先写一个“不算最优”的贪心基准很多队伍一上来就写遗传算法、模拟退火结果代码调了一周跑不出合理结果还找不到 bug 在哪。我的建议恰恰相反先把一个简单粗暴的贪心算法写完、跑通再把它作为后续元启发式的基线和校验标准。贪心基准的做法不复杂把所有工件按面积降序排序逐个尝试放入当前组内用左下优先Bottom-Left的规则安放放不下就开一组新的。这一步虽然优化能力弱但胜在逻辑简单、运行快几分钟就能得到一组可行解。这组解有两个作用一是帮你验证模型和几何判断函数写得对不对二是在遗传算法或模拟退火里作为初始种群的一部分加速收敛。3.2 为什么最终选择了遗传算法局部搜索对这道题来说分组变量天然适合用遗传算法编码。一条染色体可以设计成一组“工件编号序列”然后用一个解码函数把序列按容积约束切成若干组。这样做的好处是交叉和变异操作都非常自然不需要处理复杂的 0-1 矩阵约束。排样部分则作为解码函数里的一环每次解码都调用一次几何排样函数计算该分组方式下的利用率和加工时间。单纯用遗传算法容易陷入局部最优特别是当工件数量多、分组数大的时候。我给每条个体增加了一个局部搜索步骤随机挑一个组内的工件挪到另一组重新计算排样如果利用率提升且不违反机器能力约束就接受这个改动。这个操作相当于融合了模拟退火的邻域搜索思想收敛速度比纯遗传算法快不少。调度部分同理遗传算法种群中的每个个体经过解码后都会得到一个分组结果和每组排样的加工时间。此时用经典的最短处理时间优先规则SPT或遗传调度算法把任务分配到并行机上算出总完工时间再作为适应度的一部分反馈给上层。三层嵌套的求解框架用代码实现就是三个层级的循环。关键参数我建议这样设置种群大小取 100~200交叉概率 0.8变异概率 0.1局部搜索迭代步数 20~50 次终止条件是连续 30 代适应度不再提升。这些参数不必生搬硬套算例大了适当调大种群和迭代次数即可。3.3 一种基于聚类的快速初值策略算例特别大的时候遗传算法直接冷启动很容易前期收敛过慢。我尝试了一个替代方案先用 K-Means 或层次聚类把工件按质心坐标和面积两个特征聚成若干类每一类作为一组初始分组。这比随机分组作为初始种群要靠谱得多遗传算法从这些“半可行”解出发往往只需几十代就能进入收敛阶段。注意聚类时要加一个容量约束每一类的总面积不能超过板材面积的上限否则聚类完还要手动拆组。这个约束可以放在聚类过程中作为一个硬限制实现起来不复杂但对加速求解有明显帮助。4. 排样模块的几何计算这里是多数队伍翻车的地方4.1 多边形碰撞检测SAT 定理就够了排样模块的核心是判断两个工件是否重叠。很多队伍上来就调 shapely 库直接算两个多边形的相交面积这个方法在算例规模小的时候没问题但排样迭代次数一多shapely 的几何运算会成为性能瓶颈。我推荐的做法是使用分离轴定理Separating Axis TheoremSAT对于两个凸多边形枚举它们各条边的法向量作为候选分离轴把两个多边形分别投影到该轴上如果存在某个轴上两个投影区间不相交那么两个多边形必不相交。这个算法对凸多边形非常快而且实现起来只有几十行代码。非凸多边形怎么办把每个非凸多边形先做凸分解分成若干凸子多边形然后两两做 SAT 判断。实际切割场景里非凸件确实存在但凸分解之后处理逻辑完全一致代码不需要大改。唯一要注意的是分解后的子多边形属于同一个工件它们之间的位置锁定不能当成独立工件重新排样。还有一个工程细节碰撞判断前先减掉刀缝。在每个工件的轮廓上向外偏移半个刀缝宽度再把偏移后的多边形用于碰撞判断。这样能保证排样图直接可用于实际生产不需要二次修正。4.2 从碰撞检测到排样迭代排样过程我用了最经典的 BLFBottom-Left-Fill策略逐个放置工件每次尝试放到底部最低的可用位置再尽量靠左平移如果重叠就右移或者上移重新试找到所有候选位置中最低最左的落点。BLF 的好处是实现简单且对中小规模算例的排样效果不错作为遗传算法解码函数中的子程序完全够用。如果你追求更高的利用率可以上“最低水平线法贴边搜索”的组合策略先找到当前排样图中高度最低的水平线在水平线上找一个足够宽的空区间放工件放不进就抬高水平线。这个方法代码量也不大但比纯 BLF 的紧凑度能高 2~3 个百分点。就比赛而言这 2 个百分点可能就是一等奖和二等奖的分水岭。切线排气规则也可以叠加进去优先把已放置工件的边界延长线作为候选摆放边模拟人工套料时“对齐边缘”的习惯。这一步不是必须的但实测能进一步压缩组内空隙材料利用率提升约 1%。代价是计算时间显著增加是否需要开这个功能取决于你手里算例的规模和截止时间。4.3 旋转处理先按面积排序再按旋转枚举旋转角度我直接限定为 0°、90°、180°、270° 四个方向。排样时优先用 0°如果碰撞再依次试 90°、180°、270°选第一个能放下的方向如果四个方向都放不下视为当前组放不下该工件进入下一组或触发组内重排。实际切割场景中这是非常合理的假设因为大多数数控切割机都支持任意角度旋转但 90° 倍数的旋转最省事也最容易被工厂实际接受。有一个优化技巧先算每个工件的最小包围矩形排样前按最小包围矩形的面积从大到小排序。大的先放小的填缝这是任何排样算法里最基础也最有效的启发式之一能显著减少后续迭代的无效计算。5. 并行调度如何让机器不闲着又不让调度逻辑吃掉太多求解时间5.1 从排样到加工时间一个被忽略的桥梁分组和排样做完之后每组工件在板材上的摆放路径就确定了。加工时间取决于切割路径长度一般情况下可以把路径视为遍历所有工件轮廓的 TSP 问题——这又是另一个优化点。比赛时间有限我建议用最近邻贪心算法生成近似路径再叠加 2-opt 局部优化能拿到一个相当不错的路径长度估计。这一步的价值在于它让加工时间与排样结果真正挂钩避免调度模块用一个“瞎猜的常数”当作组的加工时间。5.2 并行机的“先短先加工”启发式调度模块本身不必搞得太复杂。我实测下来最简单有效的规则是把所有组按加工时间升序排列依次分配给当前累计负载最小的机器。这等价于经典的列表调度List Scheduling变体能在极短的时间内得到一个负载均衡度不错的调度方案。如果想要更优的水平可以在列表调度的基础上加一个交换搜索尝试交换两台机器上的两个组如果总完工时间下降则接受交换。这个操作在调度规模不大时组数不超过 30效果很明显几乎能逼近最优调度代码量也就二十行。5.3 三层嵌套循环的性能预算分配整套求解器的性能瓶颈在排样模块调度模块占比很小。因此在实际编码时我给排样函数做了缓存同一组工件的排样结果直接用哈希键值存下来下次解码遇到同样组合直接查表避免重复计算。这个方法对比赛算是“保命技能”——同样的时间复杂度加了缓存之后运行时间可能缩短到原来的五分之一。整体性能预算的分配经验是遗传算法 60% 的时间花在分组和排样解码上30% 的时间花在局部搜索上10% 的时间花在调度评估上。如果你发现调度评估占了太多时间大概率是调度模块写复杂了回到 5.2 的启发式方法就好。6. 算例验证与结果汇报数据是说服评委的唯一依据6.1 构造基准算例与敏感性分析我复现这道题的时候自己构造了五组不同规模的数据20 个工件、50 个工件、80 个工件、120 个工件、200 个工件每组都包含矩形件、直角梯形件、一般凸多边形件和非凸件如 L 形件。为什么这么分因为 20 个工件可以直接穷举验证算法最优性上界50~80 个接近比赛常见规模120~200 则用来检验算法的稳定性。结果层面贪心基准的材料利用率约在 78%~82%遗传算法加局部搜索后提升到 86%~90%。考虑到实际工业生产中 80% 以上的板材利用率已经算非常可观这套方案在比赛中完全拿得出手。敏感性分析做了两组一是旋转角度限制允许全角度旋转 vs 只允许 90° 倍数旋转对利用率的影响结果显示只允许 90° 倍数旋转时利用率平均下降 3~5 个百分点二是板材尺寸变化带来分组的连锁反应——板材越大组内可容纳工件越多调度负载越均衡总完工时间显著下降。这两组结果既验证了模型合理性也为论文增加了分析深度。6.2 结果可视化的三个要点呈现结果时建议画三类图每组的排样图标明工件编号和轮廓并行机的甘特图展示各组在各机器上的加工区间收敛曲线图显示遗传算法适应度的下降过程。这三类图分别对应“排样方案是不是合理”“调度方案是不是紧凑”“算法是不是有效收敛”评委扫一眼就能明白你的工作。尤其是收敛曲线很多人忽略但它是证明算法有效性的最直接证据。如果时间允许把排样图输出成 SVG 或 PNG 并标注比例尺贴到论文里比任何文字描述都有说服力。在答辩现场拿这些图做展示比念 PPT 上的公式高效得多。7. 实战踩坑记录这些细节没处理好程序会“发疯”这一部分是我自己反复折腾之后的总结比赛现场再遇到类似问题至少不会一脸懵。浮点数误差多边形投影在 SAT 判断时浮点数误差很容易把两个本来刚好相切的工件判成重叠。我的做法是给所有距离判断加一个 1e-6 的容差检测到重叠后微小退让避免陷入死循环。旋转中心不一致同一个工件你按几何中心旋转还是按顶点旋转算法逻辑完全不同。这个细节会导致排样结果漂移特别隐蔽。建议统一按几何中心旋转并在代码注释里明确写清楚。局部搜索的“死锁”因为几何约束严格局部搜索容易在两个分组方案之间来回切换适应度不提升。此时我采用随机重启机制如果连续 15 代没有改进随机重置 30% 的个体打破僵局。剪枝不充分导致内存爆掉遗传算法每代产生的中间结果如果全存下来很容易内存爆炸。我的建议是只保留精英个体和当前种群历史个体全部丢弃只记录每代最佳适应度用于画收敛曲线。最大迭代次数不是越多越好算例规模大于 150 个工件时迭代复盘到 500 代之后时间开销太大。我采用“时间预算”代替“迭代次数”例如限定最优解搜寻时间 10 分钟时间到了直接输出当前最优。这个策略在比赛中特别实用因为提交是有截止时间的。答题论文不要照抄代码注释代码里可以写注释但论文里要写人话。重点关注“为什么这样建模”“为什么选这个算法”“参数是怎么定的”而不是贴大片代码。8. 论文写作与奖项提升从“解对了”到“说得清楚”数学建模竞赛到最后拼的不完全是算法更是表达。同样的求解结果论文的呈现质量直接影响奖项等级。我自己的体会是这道题的论文必须回答三个问题为什么分层建模、为什么选这个算法、结果为什么可信。摘要部分要把“分组—排样—调度”的三层框架一句话说清楚比如可以表述为“本文针对批量工件并行切割下料问题建立了以材料利用率为主目标、总完工时间为次目标的三阶段优化模型设计了遗传算法与局部搜索相结合的混合求解策略在多个算例中实现了 88% 以上的材料利用率”。这行字基本上就是全文的浓缩评委大概率只看摘要和结论。模型假设部分也别糊弄。把“旋转角度限制为 90° 倍数”“刀缝统一宽度”“并行机同构”等设定写得明明白白后续公式和算法就有据可依。审稿评委非常在意假设条件是否清晰因为假设模糊意味着模型边界模糊。灵敏度分析和算法对比建议专门占一页。对比项分别是贪心基准 vs 遗传算法 vs 遗传算法局部搜索每组算例下的材料利用率和运行时间列成表格用数据说话。如果版面有限收敛曲线和甘特图不用全放挑最有代表性的放入正文其余放附录。最后再分享一个实际操作的体会这道题的输出结果包含排样坐标和各组加工顺序无论后续怎么修改模型这两项数据一定要随时整理成结构化文件比如 CSV保存下来。答辩的时候评委问“这个方案实际切割时的具体走刀顺序是什么”如果你能直接从文件里调出数据并展示出来印象分会大大加分。许多队伍模型跑通了但数据整理混乱一问细节就卡壳非常可惜。本文还有配套的精品资源点击获取 批量工件并行切割下料：分组排样与调度优化策略
简介2024年“深圳杯”数学建模挑战赛B题参赛作品聚焦批量工件并行切割下料问题面向数学建模竞赛参赛者及工程机械领域优化研究者提供完整的参赛论文与附录代码。资源内含48页论文针对A、B、C三种矩形板材的切割排版建立了以面积利用率最大化为目标的混合整数规划模型并采用贪心算法、遗传算法、粒子群算法等多种优化方法求解多问方案。内容覆盖数据预处理、多目标优化、动态调度及刀具协同运行设计尤其在问题四、五中进一步考虑切割总时间、能量消耗与设备时间成本提出自适应分区算法和智能休眠机制实现综合成本降低22%同时保持高利用率。全包为1个doc文件大小2.03MB已有535人学习下载适合需要赛题完整思路、模型推导与代码实现参考的建模团队深入研读。1. 从“先切后组”到“边组边切”这道题到底在考什么先说结论2024年深圳杯B题“批量工件并行切割下料”表面看是一道板材切割的排样优化题实际上是一道披着几何外衣的组合优化问题。很多人第一次看到题目第一反应是去查各种切割算法、套材软件的做法结果绕了一大圈发现无从下手——因为这道题真正要你解的不是“怎么在一个多边形里塞下更多工件”而是“如何把n个形状各异的工件以最小的总代价分成若干组再在m台并行切割机上完成加工”。简单说一下题目背景企业接到一批工件订单规格不同、形状各异需要从标准尺寸的母材通常是矩形板材上切割下料。与传统的单张板材逐件切割不同这里引入了并行切割机——多台设备可以同时工作每台设备一次装夹可以切割一组工件。于是问题自然分裂成三个子问题怎么把工件分组使得每组工件拼在同一张板材上不浪费怎么在每一组内部做排样让材料利用率最高怎么把这一堆任务分配到并行机器上让总完工时间最短。这三个子问题不是独立的。分组方式直接影响排样效果排样结果决定材料利用率而并行调度又牵扯到机器的空闲时间和任务负载均衡。换句话说分组、排样、调度三者是耦合的任何一步单独做最优整体都可能不是最优。这就是为什么你如果只盯着“怎么套料”去查资料会发现答案跟题目对不上——这道题的本质是一个三层嵌套优化而不是单纯的几何排样。从参赛角度来看这道题还有一个隐形的难点题目给的数据不可能是规整的矩形工件多半是带角度的多边形甚至是异性件。这意味着哪怕只是判断“两个工件能不能摆在一起”都需要先做几何运算更别提做排样优化了。所以这道题真正适合的解法不是某个“高深的算法”而是一套能把几何计算、组合优化、工程调度串起来的完整建模方案。2. 模型拆解三阶段决策框架与数学化表达2.1 核心决策变量与优化目标的“主次关系”我在复现这道题的时候最先做的不是写代码而是把整个决策过程抽象成数学模型。这里最关键的是想清楚目标函数到底优化谁题目常见的问法是多目标协调——既要材料利用率高又要加工时间短。这在数学上可以做成加权和也可以做成分层优化。我建议采取“主目标次目标”的方式优先保证材料利用率最大化在剩余可行解中找总完工时间最短的方案。原因很朴素切割料是企业的直接成本材料利用率低意味着真金白银的损失而时间只要在交货期内能接受优先级可以往后放。决策变量则分为三层分组变量第 k 组是否包含工件 i0-1 变量排样变量第 k 组中工件 i 的摆放位置和旋转角度连续变量整数变量调度变量第 k 组分配到哪台机器、在哪个时序启动0-1 变量排序变量。把这三层变量写在一起模型规模会非常大直接丢给求解器基本跑不动。所以实践中不必追求一个完整的大模型一次性求解把这个三层结构拆开、分阶段迭代才是可行路线。2.2 约束条件的“隐形陷阱”约束条件里最容易踩坑的是几何约束。常规的数学建模书会告诉你每一组内工件之间不能重叠、工件必须在板材边界内、切割路径不能交叉但实际建模时还需要额外考虑切割刀具的尺寸补偿相邻工件间要留出刀缝不然实际切割时边缘会被烧蚀或刀具切坏相邻工件模型里表现为最小间距约束旋转角度离散化真实工业切割机往往只支持 0°、90°、180°、270° 四种旋转直接把它当连续变量做会带来不可行的方案板材的纤维方向部分工件对纹理方向有要求不允许任意旋转此时旋转角度集合进一步缩小。我在建模时把上述约束全部显式写成不等式组。别嫌麻烦宁可模型里多几条约束也不要等程序跑出重叠解再回头补救。几何约束漏一条后面所有结果都要推翻重来。调度部分的约束也不轻松。并行机调度意味着一台机器同一时刻只能切割一组工件每组的加工时间取决于排样结果路径长度开工时间需满足工件齐套约束。这几条写出来就是经典的析取约束disjunctive constraint在模型里用大M法转成线性约束即可。2.3 目标函数的具体表达式设工件总数为 n分组成 K 组。定义第 k 组工件占用的最小包围矩形面积或实际使用的板材面积 S_k排样后通常取最小外接矩形板材标准面积为 S_board。材料利用率可以写成[ \eta \frac{\sum_{i1}^{n} A_i}{\sum_{k1}^{K} S_k} ]其中 A_i 是第 i 个工件的实际面积。这个公式一目了然分子是工件本身面积的总和是固定不变的分母越小利用率越高也就是说我们要让每组工件拼得越紧凑越好。总加工时间则定义为所有机器中最后完成切割的那台机器的完工时间[ T_{\text{total}} \max_{j1,\dots,m} C_j ]其中 C_j 是第 j 台机器的完工时间。整道题的求解目标就是在满足所有几何和调度约束的前提下先最大化 η再最小化 T_total。这个数学化过程做完整道题的求解思路立刻就清楚了外层做分组迭代中间层做排样计算内层做调度评估三层循环套起来就是一个完整的优化框架。3. 算法选型从贪心基准到元启发式再到混合策略3.1 为什么要先写一个“不算最优”的贪心基准很多队伍一上来就写遗传算法、模拟退火结果代码调了一周跑不出合理结果还找不到 bug 在哪。我的建议恰恰相反先把一个简单粗暴的贪心算法写完、跑通再把它作为后续元启发式的基线和校验标准。贪心基准的做法不复杂把所有工件按面积降序排序逐个尝试放入当前组内用左下优先Bottom-Left的规则安放放不下就开一组新的。这一步虽然优化能力弱但胜在逻辑简单、运行快几分钟就能得到一组可行解。这组解有两个作用一是帮你验证模型和几何判断函数写得对不对二是在遗传算法或模拟退火里作为初始种群的一部分加速收敛。3.2 为什么最终选择了遗传算法局部搜索对这道题来说分组变量天然适合用遗传算法编码。一条染色体可以设计成一组“工件编号序列”然后用一个解码函数把序列按容积约束切成若干组。这样做的好处是交叉和变异操作都非常自然不需要处理复杂的 0-1 矩阵约束。排样部分则作为解码函数里的一环每次解码都调用一次几何排样函数计算该分组方式下的利用率和加工时间。单纯用遗传算法容易陷入局部最优特别是当工件数量多、分组数大的时候。我给每条个体增加了一个局部搜索步骤随机挑一个组内的工件挪到另一组重新计算排样如果利用率提升且不违反机器能力约束就接受这个改动。这个操作相当于融合了模拟退火的邻域搜索思想收敛速度比纯遗传算法快不少。调度部分同理遗传算法种群中的每个个体经过解码后都会得到一个分组结果和每组排样的加工时间。此时用经典的最短处理时间优先规则SPT或遗传调度算法把任务分配到并行机上算出总完工时间再作为适应度的一部分反馈给上层。三层嵌套的求解框架用代码实现就是三个层级的循环。关键参数我建议这样设置种群大小取 100~200交叉概率 0.8变异概率 0.1局部搜索迭代步数 20~50 次终止条件是连续 30 代适应度不再提升。这些参数不必生搬硬套算例大了适当调大种群和迭代次数即可。3.3 一种基于聚类的快速初值策略算例特别大的时候遗传算法直接冷启动很容易前期收敛过慢。我尝试了一个替代方案先用 K-Means 或层次聚类把工件按质心坐标和面积两个特征聚成若干类每一类作为一组初始分组。这比随机分组作为初始种群要靠谱得多遗传算法从这些“半可行”解出发往往只需几十代就能进入收敛阶段。注意聚类时要加一个容量约束每一类的总面积不能超过板材面积的上限否则聚类完还要手动拆组。这个约束可以放在聚类过程中作为一个硬限制实现起来不复杂但对加速求解有明显帮助。4. 排样模块的几何计算这里是多数队伍翻车的地方4.1 多边形碰撞检测SAT 定理就够了排样模块的核心是判断两个工件是否重叠。很多队伍上来就调 shapely 库直接算两个多边形的相交面积这个方法在算例规模小的时候没问题但排样迭代次数一多shapely 的几何运算会成为性能瓶颈。我推荐的做法是使用分离轴定理Separating Axis TheoremSAT对于两个凸多边形枚举它们各条边的法向量作为候选分离轴把两个多边形分别投影到该轴上如果存在某个轴上两个投影区间不相交那么两个多边形必不相交。这个算法对凸多边形非常快而且实现起来只有几十行代码。非凸多边形怎么办把每个非凸多边形先做凸分解分成若干凸子多边形然后两两做 SAT 判断。实际切割场景里非凸件确实存在但凸分解之后处理逻辑完全一致代码不需要大改。唯一要注意的是分解后的子多边形属于同一个工件它们之间的位置锁定不能当成独立工件重新排样。还有一个工程细节碰撞判断前先减掉刀缝。在每个工件的轮廓上向外偏移半个刀缝宽度再把偏移后的多边形用于碰撞判断。这样能保证排样图直接可用于实际生产不需要二次修正。4.2 从碰撞检测到排样迭代排样过程我用了最经典的 BLFBottom-Left-Fill策略逐个放置工件每次尝试放到底部最低的可用位置再尽量靠左平移如果重叠就右移或者上移重新试找到所有候选位置中最低最左的落点。BLF 的好处是实现简单且对中小规模算例的排样效果不错作为遗传算法解码函数中的子程序完全够用。如果你追求更高的利用率可以上“最低水平线法贴边搜索”的组合策略先找到当前排样图中高度最低的水平线在水平线上找一个足够宽的空区间放工件放不进就抬高水平线。这个方法代码量也不大但比纯 BLF 的紧凑度能高 2~3 个百分点。就比赛而言这 2 个百分点可能就是一等奖和二等奖的分水岭。切线排气规则也可以叠加进去优先把已放置工件的边界延长线作为候选摆放边模拟人工套料时“对齐边缘”的习惯。这一步不是必须的但实测能进一步压缩组内空隙材料利用率提升约 1%。代价是计算时间显著增加是否需要开这个功能取决于你手里算例的规模和截止时间。4.3 旋转处理先按面积排序再按旋转枚举旋转角度我直接限定为 0°、90°、180°、270° 四个方向。排样时优先用 0°如果碰撞再依次试 90°、180°、270°选第一个能放下的方向如果四个方向都放不下视为当前组放不下该工件进入下一组或触发组内重排。实际切割场景中这是非常合理的假设因为大多数数控切割机都支持任意角度旋转但 90° 倍数的旋转最省事也最容易被工厂实际接受。有一个优化技巧先算每个工件的最小包围矩形排样前按最小包围矩形的面积从大到小排序。大的先放小的填缝这是任何排样算法里最基础也最有效的启发式之一能显著减少后续迭代的无效计算。5. 并行调度如何让机器不闲着又不让调度逻辑吃掉太多求解时间5.1 从排样到加工时间一个被忽略的桥梁分组和排样做完之后每组工件在板材上的摆放路径就确定了。加工时间取决于切割路径长度一般情况下可以把路径视为遍历所有工件轮廓的 TSP 问题——这又是另一个优化点。比赛时间有限我建议用最近邻贪心算法生成近似路径再叠加 2-opt 局部优化能拿到一个相当不错的路径长度估计。这一步的价值在于它让加工时间与排样结果真正挂钩避免调度模块用一个“瞎猜的常数”当作组的加工时间。5.2 并行机的“先短先加工”启发式调度模块本身不必搞得太复杂。我实测下来最简单有效的规则是把所有组按加工时间升序排列依次分配给当前累计负载最小的机器。这等价于经典的列表调度List Scheduling变体能在极短的时间内得到一个负载均衡度不错的调度方案。如果想要更优的水平可以在列表调度的基础上加一个交换搜索尝试交换两台机器上的两个组如果总完工时间下降则接受交换。这个操作在调度规模不大时组数不超过 30效果很明显几乎能逼近最优调度代码量也就二十行。5.3 三层嵌套循环的性能预算分配整套求解器的性能瓶颈在排样模块调度模块占比很小。因此在实际编码时我给排样函数做了缓存同一组工件的排样结果直接用哈希键值存下来下次解码遇到同样组合直接查表避免重复计算。这个方法对比赛算是“保命技能”——同样的时间复杂度加了缓存之后运行时间可能缩短到原来的五分之一。整体性能预算的分配经验是遗传算法 60% 的时间花在分组和排样解码上30% 的时间花在局部搜索上10% 的时间花在调度评估上。如果你发现调度评估占了太多时间大概率是调度模块写复杂了回到 5.2 的启发式方法就好。6. 算例验证与结果汇报数据是说服评委的唯一依据6.1 构造基准算例与敏感性分析我复现这道题的时候自己构造了五组不同规模的数据20 个工件、50 个工件、80 个工件、120 个工件、200 个工件每组都包含矩形件、直角梯形件、一般凸多边形件和非凸件如 L 形件。为什么这么分因为 20 个工件可以直接穷举验证算法最优性上界50~80 个接近比赛常见规模120~200 则用来检验算法的稳定性。结果层面贪心基准的材料利用率约在 78%~82%遗传算法加局部搜索后提升到 86%~90%。考虑到实际工业生产中 80% 以上的板材利用率已经算非常可观这套方案在比赛中完全拿得出手。敏感性分析做了两组一是旋转角度限制允许全角度旋转 vs 只允许 90° 倍数旋转对利用率的影响结果显示只允许 90° 倍数旋转时利用率平均下降 3~5 个百分点二是板材尺寸变化带来分组的连锁反应——板材越大组内可容纳工件越多调度负载越均衡总完工时间显著下降。这两组结果既验证了模型合理性也为论文增加了分析深度。6.2 结果可视化的三个要点呈现结果时建议画三类图每组的排样图标明工件编号和轮廓并行机的甘特图展示各组在各机器上的加工区间收敛曲线图显示遗传算法适应度的下降过程。这三类图分别对应“排样方案是不是合理”“调度方案是不是紧凑”“算法是不是有效收敛”评委扫一眼就能明白你的工作。尤其是收敛曲线很多人忽略但它是证明算法有效性的最直接证据。如果时间允许把排样图输出成 SVG 或 PNG 并标注比例尺贴到论文里比任何文字描述都有说服力。在答辩现场拿这些图做展示比念 PPT 上的公式高效得多。7. 实战踩坑记录这些细节没处理好程序会“发疯”这一部分是我自己反复折腾之后的总结比赛现场再遇到类似问题至少不会一脸懵。浮点数误差多边形投影在 SAT 判断时浮点数误差很容易把两个本来刚好相切的工件判成重叠。我的做法是给所有距离判断加一个 1e-6 的容差检测到重叠后微小退让避免陷入死循环。旋转中心不一致同一个工件你按几何中心旋转还是按顶点旋转算法逻辑完全不同。这个细节会导致排样结果漂移特别隐蔽。建议统一按几何中心旋转并在代码注释里明确写清楚。局部搜索的“死锁”因为几何约束严格局部搜索容易在两个分组方案之间来回切换适应度不提升。此时我采用随机重启机制如果连续 15 代没有改进随机重置 30% 的个体打破僵局。剪枝不充分导致内存爆掉遗传算法每代产生的中间结果如果全存下来很容易内存爆炸。我的建议是只保留精英个体和当前种群历史个体全部丢弃只记录每代最佳适应度用于画收敛曲线。最大迭代次数不是越多越好算例规模大于 150 个工件时迭代复盘到 500 代之后时间开销太大。我采用“时间预算”代替“迭代次数”例如限定最优解搜寻时间 10 分钟时间到了直接输出当前最优。这个策略在比赛中特别实用因为提交是有截止时间的。答题论文不要照抄代码注释代码里可以写注释但论文里要写人话。重点关注“为什么这样建模”“为什么选这个算法”“参数是怎么定的”而不是贴大片代码。8. 论文写作与奖项提升从“解对了”到“说得清楚”数学建模竞赛到最后拼的不完全是算法更是表达。同样的求解结果论文的呈现质量直接影响奖项等级。我自己的体会是这道题的论文必须回答三个问题为什么分层建模、为什么选这个算法、结果为什么可信。摘要部分要把“分组—排样—调度”的三层框架一句话说清楚比如可以表述为“本文针对批量工件并行切割下料问题建立了以材料利用率为主目标、总完工时间为次目标的三阶段优化模型设计了遗传算法与局部搜索相结合的混合求解策略在多个算例中实现了 88% 以上的材料利用率”。这行字基本上就是全文的浓缩评委大概率只看摘要和结论。模型假设部分也别糊弄。把“旋转角度限制为 90° 倍数”“刀缝统一宽度”“并行机同构”等设定写得明明白白后续公式和算法就有据可依。审稿评委非常在意假设条件是否清晰因为假设模糊意味着模型边界模糊。灵敏度分析和算法对比建议专门占一页。对比项分别是贪心基准 vs 遗传算法 vs 遗传算法局部搜索每组算例下的材料利用率和运行时间列成表格用数据说话。如果版面有限收敛曲线和甘特图不用全放挑最有代表性的放入正文其余放附录。最后再分享一个实际操作的体会这道题的输出结果包含排样坐标和各组加工顺序无论后续怎么修改模型这两项数据一定要随时整理成结构化文件比如 CSV保存下来。答辩的时候评委问“这个方案实际切割时的具体走刀顺序是什么”如果你能直接从文件里调出数据并展示出来印象分会大大加分。许多队伍模型跑通了但数据整理混乱一问细节就卡壳非常可惜。本文还有配套的精品资源点击获取