钢管切割问题：从组合优化建模到车间落地的完整求解流程

钢管切割这个问题乍一看像是车间里的粗活真上手算过一遍的人都知道它骨子里是一道披着工业外衣的组合优化题。我最早接触它是在一个做金属结构件的小厂里当时车间主任拿着一张三米长的原料清单和一堆长短不一的订单尺寸凭老师傅的经验画切割线一天下来料头堆了半人高月底一算账光原料浪费就吃掉了小半利润。后来我们把这个问题抽象出来用一套可复现的方法重新做了一遍排产同样的订单量原料消耗降了将近一成。这篇文章就把这套东西完整拆开讲清楚钢管切割问题到底是什么、为什么它比看起来难、怎么从零搭一套能落地的求解流程、以及实际跑起来之后那些文档里不会写的坑。不管你是做生产排程的工程师、学运筹学的学生还是单纯被这类下料问题卡住的人都能从里面拿到能直接抄作业的东西。1. 钢管切割问题的真实面目不是画线是决策很多人对钢管切割的第一印象是拿尺子量、拿粉笔画、上锯床切这是操作层面的理解。但从排产角度看真正决定成本的那一步发生在锯床启动之前——你决定每一根原料钢管上切出哪几种长度、各切几段、剩下多长的料头。这个决策做得好不好直接决定了要用掉多少根原料。所以钢管切割问题的本质是在满足所有订单长度和数量需求的前提下让消耗的原料总根数或总长度最少。1.1 一个具体例子把问题说透假设原料钢管统一长度 6000mm订单需要三种规格A 长 2100mm 要 30 段B 长 1500mm 要 40 段C 长 900mm 要 50 段。最朴素的做法是一种规格切一根原料一根 6000mm 的料切 2100mm 只能切 2 段剩 1800mm 料头切 1500mm 能切 4 段刚好 6000mm切 900mm 能切 6 段剩 600mm。按这个思路算A 需要 15 根、B 需要 10 根、C 需要约 9 根合计 34 根。但如果你把不同规格混在一根原料上组合切比如一根料上切 1 段 A 2 段 B 1 段 C210030009006000刚好零料头这种组合就能同时消化三种需求总根数会明显下降。这就是组合切割的威力也是这个问题的核心价值所在。我当时的实际数据比这个还极端规格有七八种长短跨度大单规格切法浪费惊人。所以第一件要建立起来的认知是钢管切割的优化空间几乎全部来自不同长度在一根原料上的混排组合而不是来自切得更准这种操作细节。1.2 为什么它属于 NP 难问题从数学上看钢管切割问题是一维下料问题One-dimensional Cutting Stock Problem的典型代表它和装箱问题Bin Packing是近亲。你要把一堆物品订单段塞进若干个箱子原料钢管里箱子容量固定目标是用最少的箱子。这个问题在规模小的时候可以暴力枚举但组合数随规格种类和数量呈指数级膨胀。举个直观的数如果一根原料上最多能放 5 个位置每个位置有 8 种可选长度那单根原料的可行组合就有 8 的 5 次方量级再乘上要排的原料根数搜索空间大到不可能穷举。这就解释了为什么老师傅的经验排法在规格少的时候很管用一旦规格多起来就力不从心——人脑处理不了这种多维组合。也解释了为什么这个问题值得用算法来做不是人不够聪明是搜索空间天然超出了手工能覆盖的范围。1.3 和切割顺序锯缝损耗的关系有一点必须提前说清楚否则后面建模会漏项实际切割是有锯缝损耗的也就是每切一刀会吃掉几个毫米的材料常见带锯在 2~5mm具体看设备和锯片。这意味着你算组合的时候每段长度要加上锯缝宽度再参与容量约束。比如一根 6000mm 原料上切 3 段实际占用是 3 段长度之和加上 3 个锯缝如果两端也要修整还要多算。这个细节在教科书例题里经常被忽略但在车间里忽略它会导致排出来的方案根本切不出来——最后一段总是差那么几毫米。另外切割顺序也有讲究通常从长到短切更稳因为长段先切掉后剩余部分短夹持和支撑更容易处理反过来先切短段长段留在后面容易因为悬伸过长产生振动影响精度。这些属于工艺约束建模时可以作为软约束或者排产后的二次调整来处理。2. 把车间问题翻译成能算的模型模型建得对不对决定了后面所有工作的上限。我见过不少人一上来就写遗传算法结果连目标函数都没定义清楚跑出来的方案看着花哨实际根数比老师傅手排还多。所以这一节把建模这件事掰开揉碎讲重点是让你明白每个决策变量和约束为什么这么设。2.1 决策变量的两种建法按根数还是按模式第一种建法叫按原料根数建模思路是假设最多用 K 根原料每根原料上放哪些段用 0-1 变量表示。这种建法直观但变量数量是订单段数 × 原料根数订单一多变量爆炸求解器直接罢工。第二种建法叫按切割模式建模这是下料问题的经典做法。所谓切割模式就是一根原料上各规格切几段的一个组合比如1 段 A 2 段 B 1 段 C就是一个模式。你先把所有可行的切割模式枚举出来或者生成一部分然后决策每种模式用几次。变量数量从段数 × 根数降到模式数通常小一个数量级。我实际项目里用的就是这种规格 8 种、原料 6000mm 的情况下可行模式枚举出来几百个求解秒级完成。用表格对比一下两种建法的差异方便你选型对比维度按根数建模按切割模式建模决策变量规模段数 × 根数规模大模式数规模小建模直观程度高容易理解中需要先枚举模式求解速度慢规模稍大就卡快线性松弛质量好适合场景小规模、教学演示实际生产排产扩展难度加约束灵活模式需重新生成2.2 目标函数与约束的完整写法按切割模式建模的标准形式是这样的设共有 m 种可行模式第 j 种模式使用次数为 x_j非负整数第 j 种模式中规格 i 的段数为 a_ij规格 i 的需求量为 d_i。那么模型就是目标最小化 Σ x_j总原料根数最少或者最小化 Σ x_j × 原料长度总长度最少两者在原料等长时等价。约束对每种规格 iΣ a_ij × x_j ≥ d_i即切出来的数量不少于需求。整数约束x_j 为非负整数。这里有个细节值得说约束用的是≥而不是因为实际生产中允许超产少量多切几段备用用 ≥ 能让模型更容易找到可行解避免因为整除问题无解。如果严格要求不超产就改成 但要做好可能无解的准备需要配合松弛变量。2.3 锯缝和料头怎么进模型锯缝的处理方式是在生成切割模式时就扣掉。具体做法判断一个模式是否可行时计算 Σ(段长 锯缝) ≤ 原料长度。注意如果一根原料上切 n 段锯缝数量通常是 n每段一刀或者 n-1最后一段靠原料端面不用切取决于工艺。保守起见按 n 算留出的余量正好当安全裕度。料头剩余废料不需要单独建模它天然体现在模式可行性判断里——只要总占用不超过原料长度剩下的就是料头。但如果你有料头必须小于某长度才能回收利用的约束那就要在模式生成阶段过滤掉料头过长的模式或者在目标函数里加惩罚项。我一般会在模式生成时就把料头超过阈值的模式剔除简单直接。提示锯缝宽度一定要用实测值不要拍脑袋填 3mm。不同锯片、不同管径、不同进给速度下差异不小填小了方案切不出来填大了浪费原料。第一次做建议拿几根废料实测几刀取平均。3. 从枚举模式到求解一套能跑通的完整流程理论讲完落到代码。这一节给出一条从原始订单到最终切割清单的完整链路每一步都能单独验证出了问题好定位。我用 Python 演示因为生态成熟、上手快换成别的语言逻辑完全一样。3.1 第一步清洗订单并统一单位原始订单往往是一张 Excel 或者手写单子长度单位可能混着毫米和厘米数量可能有重复行。第一步必须做的是把所有长度统一到毫米、把相同规格合并数量、剔除明显异常值比如长度为 0 或者超过原料长度的段——超过原料长度的段根本切不出来要单独标记出来走拼接或者外协。from collections import defaultdict raw_orders [ (A, 2100, 30), (B, 1500, 40), (C, 900, 50), (A, 2100, 5), # 重复规格需合并 ] demand defaultdict(int) for name, length, qty in raw_orders: demand[(name, length)] qty stock_length 6000 kerf 3 # 锯缝毫米 # 校验超过原料长度的段单独拎出来 oversize [(k, v) for k, v in demand.items() if k[1] stock_length] for k, v in oversize: print(f超长段需特殊处理: {k}, 数量 {v})这段代码看着简单但合并重复规格这一步经常被跳过导致后面模式枚举时同一规格出现两次约束写重了结果偏大。我踩过这个坑排查了半天才发现是数据没洗干净。3.2 第二步枚举所有可行切割模式这是整个流程里计算量最大的一步也是最需要技巧的一步。核心是一个带剪枝的深度优先搜索从最长规格开始依次决定每种规格在当前原料上切几段累计占用段长锯缝不超过原料长度就继续超过就回溯。def generate_patterns(lengths, stock_length, kerf): lengths: 去重后的长度列表升序或降序均可 lengths sorted(lengths, reverseTrue) # 从长到短剪枝更有效 patterns [] n len(lengths) def dfs(idx, remaining, current): if idx n: if any(current): patterns.append(tuple(current)) return L lengths[idx] max_count int(remaining // (L kerf)) for cnt in range(max_count 1): current.append(cnt) dfs(idx 1, remaining - cnt * (L kerf), current) current.pop() dfs(0, stock_length, []) return patterns这里有几个实操要点。第一从长到短排序能让max_count更快收敛到 0剪枝效率高。第二remaining // (L kerf)这个整除直接给出了当前规格最多能切几段避免了无效循环。第三模式数量可能很大规格 10 种、原料 6000mm 时枚举出上千个模式很常见这时候要考虑去重不同顺序生成的相同组合和过滤料头过长的模式。我实测过一个规格 12 种、原料 6000mm 的案例枚举出约 2000 个可行模式耗时不到一秒。但如果规格到 20 种模式数会涨到几万甚至更多这时候就不能全枚举了要用列生成Column Generation按需生成模式。列生成的原理是先只用一部分模式求解然后通过求解一个子问题本质是带权背包找出能改进当前解的新模式加入后重解直到找不到改进为止。这套方法在学术上很成熟工程上也有现成库可用规模大的时候值得上。3.3 第三步整数规划求解模式生成好之后套整数规划求解器。小规模用 PuLP 就够大规模上 OR-Tools 的 CP-SAT 或者商用求解器。import pulp def solve_cutting(patterns, lengths, demand, stock_length): prob pulp.LpProblem(cutting_stock, pulp.LpMinimize) x [pulp.LpVariable(fx_{j}, lowBound0, catInteger) for j in range(len(patterns))] # 目标最少原料根数 prob pulp.lpSum(x) # 约束每种规格满足需求 for i, L in enumerate(lengths): prob pulp.lpSum(patterns[j][i] * x[j] for j in range(len(patterns))) demand[L] prob.solve(pulp.PULP_CBC_CMD(msg0)) return [(patterns[j], int(x[j].value())) for j in range(len(patterns)) if x[j].value() 0]跑完之后你会拿到一个每种模式用几次的清单把它展开就是具体的切割方案。这里要注意求解器返回的是最优解在给定模式集合下但如果模式集合不全这个最优只是局部最优。所以模式枚举的完整性直接决定了解的质量这也是为什么前面强调枚举要尽量全。3.4 第四步把模式清单还原成可执行的切割单求解结果是一堆模式编号和次数车间要的是第 1 根切什么、第 2 根切什么这种逐根清单。这一步就是把模式按次数展开同时做两件收尾工作一是按切割顺序重排长段在前二是计算每根的料头长度并汇总总利用率。def expand_to_cutlist(solution, lengths, stock_length, kerf): cutlist [] idx 1 for pattern, count in solution: for _ in range(count): segments [] for i, cnt in enumerate(pattern): segments.extend([lengths[i]] * cnt) segments.sort(reverseTrue) # 长段先切 used sum(s kerf for s in segments) waste stock_length - used cutlist.append({ no: idx, segments: segments, waste: waste, utilization: round(used / stock_length * 100, 2) }) idx 1 return cutlist总利用率这个指标要重点看。我做过的一个项目优化前利用率约 87%优化后到 94%别小看这 7 个百分点按年用量几千根原料算省下来的材料费相当可观。利用率低于 90% 的时候要回头检查是不是模式枚举不全、是不是锯缝设太大、是不是有可以合并的规格。4. 实测中那些文档不会告诉你的坑算法跑通只是开始真正让方案在车间落地的是这一节的内容。下面这些坑我基本都踩过写出来帮你省时间。4.1 求解器给出的最优解可能切不出来这是最典型的一个坑。数学模型只关心长度加总不超限但车间有夹持长度要求——太短的尾段比如最后剩 200mm锯床夹不住切不了。所以模型算出来的方案里如果出现超短段要么在模式生成阶段就限制每段最小长度要么在还原切割单后人工调整。我的做法是在模式生成时加一个min_segment参数低于它的段直接不允许出现在模式里从源头杜绝。另一个类似问题是重量和吊装。单根原料如果特别重大口径厚壁管切完之后剩余部分可能超出吊装设备能力这属于物理约束模型里体现不了只能靠排产后的工艺复核。所以我的习惯是算法出方案、人工过一遍工艺可行性两道关都过才算数。4.2 需求波动时别每次都重算全量实际生产里订单是滚动来的今天来一批、明天来一批。如果每次都把所有历史订单加新订单一起重算计算量越来越大而且方案会频繁变动导致车间无所适从。更合理的做法是增量处理已排产的部分锁定只对新订单做优化同时允许在剩余料头里捡漏——也就是把之前切剩的、长度还够用的料头当作一种特殊的原料参与新订单的模式生成。这个思路实现起来不复杂维护一个料头库存表长度、数量新订单求解时把标准原料和可用料头一起作为候选原料料头的成本设得比标准原料低因为它本来就是废料用掉就是赚求解器自然会优先消耗料头。我实测下来这个改动能让综合利用率再提两三个百分点而且料头库存不会越积越多。4.3 多目标的时候别只盯根数只优化根数有时候会得到一个根数最少但料头很碎的方案——总根数确实少了但每根都剩一点这些碎料头没法再利用实际浪费反而更大。这时候要引入第二个目标在根数相同的前提下让料头尽量集中也就是让部分原料切得满、部分原料剩得多剩得多的还能当料头回收。实现方式有两种一是字典序优化先求最小根数把根数固定为最优值再求料头最集中二是加权目标函数写成根数 × W1 料头分散度 × W2调权重。我一般用字典序逻辑清晰不容易调参调到怀疑人生。料头分散度可以用料头长度的方差或者料头超过阈值的根数来度量看你的回收策略而定。4.4 数据质量比算法重要说句实在话这类项目里算法部分占的工作量不到三成剩下七成都在跟数据较劲。订单表里的长度有笔误、单位不统一、规格命名不规范同一个长度叫法不同、数量填错这些都会让优化结果失真。我现在的习惯是求解前先跑一遍数据校验长度分布直方图看一眼有没有离群值、每种规格的数量和总量对一遍、和上一批订单比对看有没有异常跳变。这几步花不了几分钟但能挡掉大部分算法算错了的假警报——十次里有八次是数据问题不是算法问题。5. 规模上去之后列生成和启发式的取舍前面给的枚举加整数规划方案在规格十几种、原料单一长度的情况下足够用。但实际项目里经常遇到更复杂的场景原料有多种长度比如既有 6000mm 也有 9000mm 的现货、规格几十种、还要考虑不同材质不能混切。这时候全枚举模式不现实得换思路。5.1 多原料长度怎么处理原料有多种长度时模式生成要按原料长度分别做每种原料长度对应一套模式集合求解时决策变量变成第 k 种原料的第 j 种模式用几次目标函数里每根原料的成本按实际长度加权长的原料成本高。约束还是各规格满足需求。这样模型规模会变大但结构不变求解器还能扛。如果原料长度是连续的比如可以从供应商按任意长度订货问题就变成选什么长度的原料 怎么切的联合优化复杂度上一个台阶。这种情况我一般建议先离散化——把可选原料长度限制在几个标准档位上把连续问题转成离散问题牺牲一点理论最优性换取可解性和采购便利性。实际生产中供应商也不会给你任意长度标准档位反而更贴合现实。5.2 列生成的适用边界规格数量超过 20 种、模式枚举爆炸的时候列生成是正路。它的核心是把枚举所有模式换成按需生成有潜力的模式先用少量初始模式求解一个受限主问题拿到对偶价格可以理解为每种规格的边际价值然后解一个子问题——在原料长度约束下选一组规格使总边际价值最大这本质上是个背包问题用动态规划秒解。子问题找到的新模式如果边际价值为正说明它能改进当前解加入主问题重解循环直到没有正价值的新模式。列生成的实现门槛比直接枚举高但好在有成熟的开源实现可以参考OR-Tools 里也有相关组件。我的建议是规格 15 种以内直接枚举超过 20 种考虑列生成中间地带看模式枚举出来的实际数量决定——枚举出来超过一万个模式就该上列生成了。5.3 什么时候启发式反而更合适不是所有场景都值得上精确算法。如果订单批量小、交期紧、每天要重排好几次精确求解的那几秒到几十秒延迟可能就影响响应速度了。这种场景下一个设计良好的启发式比如首次适应递减把段按长度降序排列依次往当前原料里塞塞不下就开新原料能在毫秒级给出接近最优的解配合人工微调完全够用。启发式的价值在于快且稳缺点是解的质量有波动。我的经验是把启发式作为默认方案精确算法作为优化模式按需触发——平时用启发式快速出单遇到大订单或者月底冲指标的时候跑一次精确优化。这种双轨制在实际生产里比单纯追求最优解更实用。6. 一套可以直接复用的落地检查清单最后把整个流程里需要盯的关键点整理成清单下次做类似项目直接照着过一遍能少走很多弯路。检查项具体内容常见问题数据清洗单位统一、重复合并、超长段标记同规格重复计数导致结果偏大锯缝参数实测取值按每段一刀计拍脑袋填值导致方案切不出模式枚举从长到短剪枝过滤超长料头枚举不全导致解非最优最小段长设置下限避免夹持问题尾段过短无法加工求解器选择小规模 PuLP大规模 CP-SAT规模大时求解超时结果还原长段先切计算料头与利用率切割顺序不合理影响精度增量处理锁定已排产料头参与新订单每次全量重算效率低多目标权衡根数优先料头集中度次之只盯根数导致碎料头多工艺复核重量、吊装、夹持人工过一遍纯算法方案脱离车间实际这套东西我从最早的手工排产一路迭代过来中间换过建模方式、换过求解器、也推翻过好几版方案。现在回头看钢管切割问题最迷人的地方在于它的性价比——模型不复杂、代码量不大但优化带来的收益是实打实能算成钱的。一根原料省几十块一年几千根就是一笔不小的数目而且这套方法迁移到板材切割、型材下料、甚至卷材分切上逻辑几乎不用改。真正需要花心思的从来不是算法本身而是把车间的约束一条条摸清楚、把数据洗干净、把方案落到能执行的颗粒度。这些活儿琐碎但恰恰是决定项目成败的地方。