Cutting Stock Problem

Problem Definition

工业下料本质是一个 NP-Hard 组合优化问题。举个例子：10 种不同长度的短料，用 6 米母材来切，组合方式多到爆炸——算到天黑也算不出最优解。这不是你的问题，是人脑天然不擅长这道数学题。

貌似 MIT的《算法入门》有类似的介绍，暂时只考虑 1D Cutting Stock Problem 。

另外已经有成熟的软件了。

我的算法

我自己写了很垃圾的代码，在没有AI之前写的。其实就是类似 BFD 。

cols = []
bars = []

# 2楼办公室的窗 2C1-2C4
for _ in range(2):
    # 中间的加粗横杆
    # cols.append(2260)
    # cols.append(1325)
    # cols.append(500)
    # 压条
    for _ in range(4*2): bars.append(1285)
    for _ in range(8*2): bars.append(1105)
    for _ in range(4*2): bars.append(460)

if __name__ == '__main__':
    # 默认长度是 6000
    # --------------------------------------------------
    alumin_batten_material_list = []
    # 仓库里的压条
    for _ in range(100): alumin_batten_material_list.append(6000)
    # --------------------------------------------------
    # 添加需要的压条
    # --------------------------------------------------
    batten_list = bars
    # -------------------------------------------------
    batten_spare_used = [ False ] * len(batten_list)
    total_batten_cnt = 0 
    curr_material_idx = 0
    curr_frontier = alumin_batten_material_list[curr_material_idx]
    previous_cut = 0
    while not all(batten_spare_used):
        min_left = float('inf') 
        best_fit_batten_idx = -1 
        for i, curr_batten in enumerate(batten_list):
            if batten_spare_used[i]: 
                continue
            if curr_frontier - curr_batten >= 0: 
                left = curr_frontier - curr_batten
                if left < min_left:
                    min_left = left
                    best_fit_batten_idx = i 

        if best_fit_batten_idx == -1: 
            print("- 剩余: ", curr_frontier, '\n第', total_batten_cnt+1, '条方铝压条(20x20)(', alumin_batten_material_list[curr_material_idx], ')\n\n----------------')
            curr_material_idx += 1
            if curr_material_idx == len(alumin_batten_material_list):
                print('[[ END ]]')
                break
            curr_frontier = alumin_batten_material_list[curr_material_idx]
            total_batten_cnt += 1 
            previous_cut = 0
        else: 
            curr_frontier -= batten_list[best_fit_batten_idx]
            batten_spare_used[best_fit_batten_idx] = True
            print(batten_list[best_fit_batten_idx])  
            # print(batten_list[best_fit_batten_idx] + previous_cut)  
            previous_cut = batten_list[best_fit_batten_idx] + previous_cut

    if curr_material_idx < len(alumin_batten_material_list):
        print("- 剩余: ", curr_frontier, '\n第', total_batten_cnt+1, '条方铝压条(20x20)(', alumin_batten_material_list[curr_material_idx],')\n\n----------------')

    # 剩余多少没有完成
    batten_left_cnt = {}
    for i, bat in enumerate(batten_spare_used):
        if not bat: 
            if batten_list[i] not in batten_left_cnt:
                batten_left_cnt[batten_list[i]] = 1
            else:
                batten_left_cnt[batten_list[i]] += 1
    for k in batten_left_cnt.items():
        print(k[0], k[1])

    total_len = sum(batten_list) 
    cnt = total_len / 6000
    print("\n\n\n理论条数最小值: ", cnt)

    # 20x20的方压条要买
    print('20x20 1.4厚 深灰色方压条 ', round(cnt),' 要买条。')
    print('\n\n----------------------------\n\n')

    # 默认长度是 6000
    # --------------------------------------------------
    alumin_batten_material_list = []
    # 仓库里的压条
    for _ in range(100): alumin_batten_material_list.append(6000)
    # --------------------------------------------------
    # 添加需要的压条
    # --------------------------------------------------
    batten_list = cols
    # -------------------------------------------------
    batten_spare_used = [ False ] * len(batten_list)
    total_batten_cnt = 0 
    curr_material_idx = 0
    curr_frontier = alumin_batten_material_list[curr_material_idx]
    previous_cut = 0
    while not all(batten_spare_used):
        min_left = float('inf') 
        best_fit_batten_idx = -1 
        for i, curr_batten in enumerate(batten_list):
            if batten_spare_used[i]: 
                continue
            if curr_frontier - curr_batten >= 0: 
                left = curr_frontier - curr_batten
                if left < min_left:
                    min_left = left
                    best_fit_batten_idx = i 

        if best_fit_batten_idx == -1: 
            print("- 剩余: ", curr_frontier, '\n第', total_batten_cnt+1, '条方铝压条(20x20)(', alumin_batten_material_list[curr_material_idx], ')\n\n----------------')
            curr_material_idx += 1
            if curr_material_idx == len(alumin_batten_material_list):
                print('[[ END ]]')
                break
            curr_frontier = alumin_batten_material_list[curr_material_idx]
            total_batten_cnt += 1 
            previous_cut = 0
        else: 
            curr_frontier -= batten_list[best_fit_batten_idx]
            batten_spare_used[best_fit_batten_idx] = True
            print(batten_list[best_fit_batten_idx])
            # print(batten_list[best_fit_batten_idx] + previous_cut)  
            previous_cut = batten_list[best_fit_batten_idx] + previous_cut
    if curr_material_idx < len(alumin_batten_material_list):
        print("- 剩余: ", curr_frontier, '\n第', total_batten_cnt+1, '条方铝压条(20x20)(', alumin_batten_material_list[curr_material_idx],')\n\n----------------')

    # 剩余多少没有完成
    batten_left_cnt = {}
    for i, bat in enumerate(batten_spare_used):
        if not bat: 
            if batten_list[i] not in batten_left_cnt:
                batten_left_cnt[batten_list[i]] = 1
            else:
                batten_left_cnt[batten_list[i]] += 1
    for k in batten_left_cnt.items():
        print(k[0], k[1])

    total_len = sum(batten_list) 
    cnt = total_len / 6000
    print("\n\n\n理论条数最小值: ", cnt)

    # 20x20的方压条要买
    print('100x44 1.4厚 深灰色方管 ', round(cnt),' 要买条。')

试了一下，小样本内已经和AI的答案接近了。

理论条数最小值:  10.546666666666667
20x20 1.4厚 深灰色方压条  11  要买条。

需 11 根，利用率 96.0%，废料 2614mm

特别激动，第一次自己想到算法去解决生活中的实际问题。就像第一次拿驾照一样激动。

AI给的答案

这是个经典的一维下料问题（1D Cutting Stock Problem），NP-hard，但 6 米铝型材这个场景下，根据订单规模选不同解法就行，不用一上来就上重武器。

先把两个坑定下来

锯口（kerf）必须扣：铝型材锯片一般 3–5 mm，一根 6 m 料切 20 段就吃掉 60–100 mm，不扣的话最后几段会莫名其妙”放不下”，被迫多开一根料。
单位统一用 mm（6000），别米和毫米混着输，这是车间下单最常见的bug。

算法怎么选

场景	推荐	说明
小订单（总段数 < 30）	暴力 / DP / 回溯	能拿到数学最优
常规车间（几十到几百段）	BFD（Best Fit Decreasing）+ 多轮随机扰动	工程界主流，利用率 90%+，毫秒出结果
大批量 / 要证明最优 / 审计成本	列生成 + ILP（PuLP / Gurobi / SCIP）	能再省几根，但实现复杂

💡 贪心类（FFD/BFD）对输入顺序敏感，同一份清单换个排序结果可能差一根料，所以成熟做法是”随机打乱短料顺序跑 N 轮，取最好的”。这个真没想到，原来可以输入顺序也有影响。

最小可跑版本（BFD，Python）

先给你一个能直接用的骨架，含锯口：

from typing import List, Tuple

def bfd_cut(stock_len: int, kerf: int,
            demands: List[Tuple[int, int, str]]) -> dict:
    """
    stock_len: 母材长，如 6000 (mm)
    kerf: 锯口，如 3 (mm)
    demands: [(长度, 数量, 编号), ...]  e.g. [(2300,5,'A'), (1500,8,'B')]
    返回: 每根料的切割明细 + 总根数 + 利用率
    """
    # 展开成单段列表，降序
    pieces = []
    for length, qty, pid in demands:
        pieces.extend([(length, pid)] * qty)
    pieces.sort(key=lambda x: x[0], reverse=True)

    stocks = []  # 每根: {'items':[(len,id),...], 'rem':剩余可用}

    for length, pid in pieces:
        # 找"放得下 + 剩余最少"的那根（BFD 精髓）
        best_idx = -1
        best_rem = stock_len + 1
        for i, s in enumerate(stocks):
            if s['rem'] >= length + (kerf if s['items'] else 0):
                rem_after = s['rem'] - length - (kerf if s['items'] else 0)
                if rem_after < best_rem:
                    best_rem = rem_after
                    best_idx = i
        if best_idx >= 0:
            stocks[best_idx]['items'].append((length, pid))
            stocks[best_idx]['rem'] = best_rem
        else:
            # 开新料
            stocks.append({
                'items': [(length, pid)],
                'rem': stock_len - length
            })

    # 统计
    total_used = sum(stock_len - s['rem'] for s in stocks)
    util = total_used / (len(stocks) * stock_len) * 100
    waste = sum(s['rem'] for s in stocks)

    return {
        'num_stocks': len(stocks),
        'stocks': stocks,
        'utilization': util,
        'waste': waste
    }


# ===== 试一下 =====
demands = [(2300, 5, 'A'), (1500, 8, 'B'), (1200, 12, 'C'), (800, 6, 'D')]
res = bfd_cut(6000, kerf=3, demands=demands)
print(f"需 {res['num_stocks']} 根，利用率 {res['utilization']:.1f}%，废料 {res['waste']}mm")
for i, s in enumerate(res['stocks']):
    print(f"料#{i+1}: {s['items']} | 余{s['rem']}mm")

输出类似：

需 14 根，利用率 93.2%，废料 2504mm
料#1: [(2300, 'A'), (2300, 'A')] | 余 1397mm  (扣锯口后)
...

想要更优？加两招

1. 多轮随机扰动（成本最低、收益最大）：

import random, copy

def bfd_randomized(demands, runs=200):
    best = None
    for _ in range(runs):
        d = copy.deepcopy(demands)
        # 只对"同长度内"或"整体"做随机 shuffle
        random.shuffle(d)
        res = bfd_cut(6000, kerf=3, demands=d)
        if best is None or res['num_stocks'] < best['num_stocks']:
            best = res
    return best

2. 迭代交换（Swap）：跨两根料互相挪一段，看能不能省出一根——这是突破贪心局部最优的关键。

如果你要”数学最优”

上列生成 + PuLP/Gurobi：主问题是”用哪些切割模式、各几次，母材最少”，子问题是背包问题（找新模式下影子价格最高的组合）。参考实现骨架：

# 列生成思路（伪码）
# 1. 先用手工几个简单模式初始化 RMP（如每根只切一种长度）
# 2. 解 RMP → 拿对偶价 π_i
# 3. 解背包：max Σ π_i * a_i，s.t. Σ l_i*a_i ≤ L，找新列
# 4. 新列加入 RMP，回到 2，直到无正收益列
# 5. 最后把 RMP 转 ILP 整数化，求最终方案

PuLP 写主问题、子问题单独一个 knapsack DP，整套 100 行左右能跑起来。

下次在研究一下背包。

你这边订单规模大概多少段？要不要我直接按你的真实需求（长度 + 数量列表）帮你把 BFD + 扰动版调好，或者一步到位写列生成版？ 另外锯口按几 mm 算也得定一下，铝型材一般 3 mm（超薄锯片）到 5 mm（普通）。

已有的商业软件

切割还在凭经验下料？这套系统让每根材料都“物尽其用“

痛点 1 → 解法：策略竞争机制，让算法替你找出最优解
- 系统内置 FFD、BestFit、WorstFit、背包后优化、迭代交换等多种策略，同时并行跑、多轮加随机扰动、跑完自动比利用率——谁利用率最高谁胜出。
- 同样的材料清单，人工排到 85% 就觉得”差不多了”，算法拉到 95% 甚至更高。差距 10 个百分点，每吨材料按 2 万元算，一年省下的钱自己算算。
痛点 2 → 解法：不限规格数量，自动全局优化
- BOM 单直接导入系统，几十种规格一次全部吃进去。算法在全局范围内搜索最优组合——哪种规格和哪种规格搭在同一根母材上最省料，算法比人想得清楚一万倍。
痛点 3 → 解法：库存联动 + 余料自动入库
- 方案确定后，母材库存自动扣减，余料自动生成入库记录。下次排料时，系统优先消耗余料——“先吃库存余料，不够再开新母材”。
- 角落里的边角料，从此有了数字身份证，永不”失踪”。
痛点 4 → 解法：缺陷标记，算法自动避让
- 在系统中标记缺陷位置（起止点坐标），算法在排料时自动将该区域设为不可用——人只管标注，算法负责绕开。彻底杜绝”一刀切进疤结里”的事故。
痛点 5 → 解法：1D + 2D 双模式，一个系统全搞定
- 1D 线性切割: FFD / BestFit / WorstFit / 背包 / 迭代交换. （铝型材、钢管、钢棒、木方、PVC 管）
- 2D 矩形切割：Guillotine Shelf + 自由矩形 + 跨 Bin 优化，铝板、钢板、木板、亚克力板

三、深入 1D 切割：线性材料的最优下料

适用对象：铝型材、钢管、钢棒、木方、PVC 管——一句话，按长度切割的线性材料。

内置策略矩阵

策略	核心思路	擅长场景
FFD（First Fit Decreasing）	长料优先，贪心放置	规格差异大时收敛快
Best Fit	选余料最少的那个坑	规格均匀时利用率高
Worst Fit	选余料最多的那个坑	为后续长料留空间
背包后优化	先解背包问题再微调	精确求解小规模
迭代交换	跨母材交换短料	突破局部最优

多轮 + 随机扰动

每种策略不只跑一次。系统会在每一轮注入随机扰动（改变短料的处理顺序），跑上十几轮，取利用率最高的那一轮结果。这个设计很重要——贪心类算法对输入顺序敏感，同样的材料清单，换一个排序可能结果完全不一样。多轮扰动大幅降低”差排序导致烂方案”的概率。

可视化结

果切割结果用 Canvas 绘制长条图（Bar Chart），每根母材上不同颜色标识不同规格的短料，直观显示哪里有余料、剩余多长，支持缩放和悬停查看详情。

四、2D 切割：板材的智能排版

适用对象: 铝板、钢板、木板、亚克力板——按矩形面积切割的板材。

Guillotine Shelf 策略

2D 切割采用 Guillotine Shelf（闸刀式层架）策略：

核心逻辑：

1. 将板材划分为若干”层”（Shelf），每层高度由第一个放入的矩形决定
2. 每个矩形按宽度流式放入当前层
3. 新矩形高度超过当前层剩余高度时，开一个新层
4. 所有切割线都是贯通的直线（满足闸刀切割工艺约束）

这保证了所有切割方案都能在真实的闸刀切割机上执行，不会生成花哨但不实用的”锯齿形”排料。

跨 Bin 优化

系统会自动检测利用率最低的母材（bin），尝试将其上的矩形”迁移”到其他母材的缝隙中：

For each low-utilization bin:    
    提取 bin 中的所有矩形    
    For each 矩形:
            尝试放入其他 bin 的空余区域    
    如果全部迁移成功:
            删除该 bin → 直接省下一张板！

零余料 Bin 消除

如果某个 bin 的利用率计算为 0%（所有矩形完全迁移），系统会自动将该 bin 从结果中移除——节省的材料成本立竿见影。

五、技术栈

自由矩形旋转不限制矩形的宽高方向（允许旋转 90°），系统自动探索横放/竖放两种姿态的利用率差异，选最优的那个。

前端：Vue 3 + Canvas API（可视化切割图）
后端：Spring Boot 3（算法引擎 + 业务逻辑）
数据处理：EasyExcel（导入导出）、iTextPDF（PDF 报告）
数据存储：PostgreSQL + Redis
部署运维：Docker + Kubernetes