一维下料问题的研究

---

一、概念

下料：有若干规格的原材料，要切割成一批若干规格的零件，确定一种切割方式，使得原材料用料最少、产生的废料最少。

一维下料：上面提到的规格，可以包含很多属性，比如：长度、宽度、厚度等等。所谓一维下料，只关注其中一种属性，而其它属性被认为全部相同，这样便大大降低了下料问题的处理难度。本文研究的一维下料，以长度作为优化目标。

二、术语定义

原料：用于切割的原材料，长度不定。

零件：从原料中切割下来的短料。

废料：一根原料被使用后，剩余长度无法再用于生产任意零件。一般定义为阈值。

余料：一个原料被使用后，剩余材料仍然可以在后续生产中进行零件切割。

三、问题描述

现有N段长度不等的原料（当然，也可以全部长度相等或者其中一部分长度相等），现需要切割为M段长度不等的零件，生成一种切割方案，使产生的废料最少（阈值）、若必须要产生余料应使余料大于指定长度（阈值）以便余料再利用。

四、解决方案

1）穷举法

当原料和零件数量很小时，穷举法可以对所有切割方案进行穷举遍历，寻找最优解。但是如果原料和零件数量达到一定量后，穷举法时间复杂度成指数级增长，计算机无法算出结果。这里给一些定量的概念，比如从零件的角度穷举，M=20时，穷举数量级为1,048,576，M=30时，穷举数量级为1,073,741,824。即时间复杂度为O(2^M)，隐藏零件数量到达20以上时，就变成了无法完成的任务。

2）遗传算法

百度搜索“一维下料 遗传算法”，会得到非常多的相关论文搜索结果。遗传算法以进化论为依据，当种群进化若干代后，便会得到一个相对精英的种群。将一维下料问题转化为遗传算法模型如下：

a）染色体：a1,a2,a3......am，表示第m个零件在第am根原料上截取；

b）种群初始化：初始化x个可行染色体种群

c）交叉算子：按交叉概率，对染色体进行两两交叉，注意不要交叉出无效染色体

d）变异算子：按变异概率，对染色体中的基因进行剔除并变异，注意不要变异出无效染色体

e）选择算子：采用锦标赛算法或轮盘赌算法，对优秀染色体进行选择

f）适应度函数：根据优化目标设计适应度函数，一般从利用率、废料率角度设计

遗传算法能对下料方案有一定程度的优化，但是优化不明显，或许是哪个算子设计不合理、或者参数没有调到合适的值。（注：相关的论文中，结果数据非常优秀，但本人无法调出那么优秀的方案，所以对有些论文报怀疑态度）。

2023-5-11更新:遗传算法解决下料问题，参考我最新文章“使用遗传算法解决一维下料问题”。

3）动态规划

一维下料的核心，其实可以对接背包问题，而动态规划实际上是一种解背包问题的其中一种算法。看了几个论文资料，算法没看太懂，暂没时间做实验，不做评价。

4）自研算法

涉及到商业上的问题，不便多说，但整体思路是模拟人工的操作。一般一个工人，拿到一组原料和一组零件规格后，只要给足够的时间，总能设计出一些比较优秀的方案，而此算法正是模拟这个过程。

五、总结

算法的东西，需要深入研究，但是不能一味的陷进去，有时候换个思路，可能得到意想不到的效果。大道至简才是精髓。

最后，欢迎使用一维下料网进行下料优化计算：一维下料网

下面贴一组数据：

原材料(长度*个数):150*500

切口宽度:0

切割零件(长度*个数):

50*200
39*100
37*100
36*100
33*100
32*200
31*100
29*200
28*100
25*200
24*200
23*100
21*200
19*100
18*100
17*100
14*200
13*100
12*100
5*100
1*100

下料方案如下：

利用率：1.000000，原料使用总根数：468
序号【 1】：使用根数【 200】，余 0，150=50*1+32*1+29*1+25*1+14*1
序号【 2】：使用根数【 100】，余 0，150=37*1+36*1+24*1+21*1+19*1+13*1
序号【 3】：使用根数【 100】，余 0，150=39*1+33*1+31*1+24*1+23*1
序号【 4】：使用根数【 50】，余 0，150=28*2+21*2+18*1+17*1+12*1+5*1
序号【 5】：使用根数【 16】，余 0，150=18*3+17*3+12*2+5*3+1*6
序号【 6】：使用根数【 2】，余 0，150=18*1+17*1+12*9+5*1+1*2