板材切割问题的求解与应用

发布时间：2020-09-16 15:03

　　在板材切割的过程中,一个优秀的切割方案可以将原料的使用率大大提高,从而减少板材的浪费,节约经济成本,为厂商带来更大的经济效应。因此,研究出一种高效的板材切割算法具有重要的理论价值和实际应用价值。板材切割问题在理论上是NP难问题,同时在工业上也是一个长期需要解决的重要问题。板材切割问题是一种经典的NP难问题,不断地在时间和优度上做出均衡。论文所研究的切割问题全称为cutting optimization problem,即‘切割优化问题’,是2018年法国运营(OR)和决策支持协会(ROADEF)共同组织的一次ROADEF/EURO挑战赛的挑战题目。问题的主要内容是要将多块板材原料按顺序切割成所需要的目标方块。在该问题中,板材将使用流水线切割的形式进行切割,并且板材原料存在defect(杂质)。由于切割机器及相关硬件的原因,给该切割问题产生了许多的限制约束,大大增加了切割方案设计的难度。论文中使用动态切割与集束搜索相结合的方式,对问题进行分化求解。总体思路是将问题从寻找整体近似最优切割方案拆分成以1_cut切割线为分界线的寻找局部近似最优切割方案。将问题拆开成多个求解局部近似最优解的问题后,再使用集束搜索的方式来寻找这些局部近似最优解。这样就将一个原本巨大的搜索树拆分成了众多的小搜索树,使得搜索的过程更加高效且迅速。当所有的局部近似最优解找出后,组合起来作为总体的近似最优解。方法中定义名为贴边度的指标作为局部搜索时动作的选择因素。将每个1_cut区域的第一个目标方块作为分支节点,按照逐层切割的理念进行切割,将搜索树的分支发展下去,直到该1_cut区域没有多余的空间继续切割出目标方块或所有的目标方块都已有切割线将其切出为止,作为一个局部的终止格局。从所有的局部终止格局中选择当前利用率最大的分支路线进行切割,作为局部近似最优解。同理后续的1_cut区域重复此操作,直到所有1_cut区域切割完毕为止。在集束搜索的过程中,我们还使用动态切割的方式,对每次局部搜索的结果进行调整。在每个局部切割方案计算完成前,所有的切割线都是动态的,不会将该1_cut区域内的切割线位置真正确定下来,而是根据动作选择策略的结果,将某条暂时定下位置的切割线进行向上或向右的浮动平移,以求得更高的局部利用效率。也就是说每一个1_cut区域的宽度不会因为第一个目标方块的放置而被确定,而是会出现一个预1_cut线作为参考线,后面的目标方块若是判定放置位置会压住这条1_cut线,预1_cut线将会向右平移,与超出的部分刚好相切为止。同理横向的2_cut切割线也会因需要进行向上浮动平移。直到整个1_cut区域被切割线分割完毕,才会将这个局部区域内的所有切割线位置确定下来,不再改变。该创新点会为算法提供一定的柔性化,使得在运算过程中切割线存在一定的柔性,来避免某些目标方块只差一点,却由于切割线无法浮动的原因,而无法放置的结果。实验通过计算2018年ROADEF/EURO挑战赛官方所提供的A组算例,来验证该原创算法的优点与不足之处。实验结果通过大赛官方所提供的检测代码进行结果测试,从而保证结果的正确性,并与官方所给出的单例最优解进行比较。单例最优解是官方对每一个实例公布的所有算法最优解。通过分析计算结果得出结论:算法在处理目标方块与板材原料之间的尺寸差距较大的算例时,切割效果较好,算例板材利用率可在80%以上。
【学位单位】：江西财经大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：O224
【部分图文】：

模式图,切割方式,切割工艺,方块

（a）一刀切模式（b）非一刀切模式图 1-1 按切割工艺划分的两种切割方式（3）根据目标方块种类数划分根据目标方块的种类，可将二维板材切割问题划分为单一切割方式和套裁割方式[1]。其中前者单一切割方式的目标方块只含有一种尺寸，虽然会降低板

切割方式,方块,种类,目标

（a）单一切割方式（b）套裁切割方式图 1-2 按目标方块的种类划分的两种切割方式（4）根据目标方块方向划分根据目标方块方向是否允许转向，可以分成两种切割方式，如图 1-3 求中的目标方块给定长宽参数，若约束条件不允许目标方块转向，则在

二维图形,切割方式,方块,目标

（a）目标方块方向固定（b）目标方块允许转向图 1-3 按目标方块是否允许转向划分的两种切割方式（5）根据目标方块类型划分根据目标方块的形状是否是规则形状，可将板材切割问题划分为规则件切不规则件切割。规则件切割如图 1-4（a）所示，目标方块都是规则二维图形（

【参考文献】