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

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

论文摘要

在板材切割的过程中,一个优秀的切割方案可以将原料的使用率大大提高,从而减少板材的浪费,节约经济成本,为厂商带来更大的经济效应。因此,研究出一种高效的板材切割算法具有重要的理论价值和实际应用价值。板材切割问题在理论上是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%以上。

论文目录

  • 摘要
  • abstract
  • 1 绪论
  •   1.1 研究背景及价值
  •     1.1.1 研究背景
  •     1.1.2 研究理论价值
  •     1.1.3 研究实用价值
  •   1.2 切割问题的基本分类
  •   1.3 国内外研究概况
  •     1.3.1 国外研究概况
  •     1.3.2 国内研究概况
  •   1.4 本文研究内容
  •   1.5 论文组织结构
  • 2 板材切割问题
  •   2.1 板材切割问题定义
  •     2.1.1 问题介绍
  •     2.1.2 问题定义
  •     2.1.3 问题难点
  •   2.2 切割问题经典解法
  •     2.2.1 动态规划
  •     2.2.2 BL算法
  •     2.2.3 BF算法
  • 3 基于动态切割的集束搜索算法
  •   3.1 算法基础概念
  •   3.2 算法策略
  •     3.2.1 候选板块的选择策略
  •     3.2.2 放置动作的挑选策略
  •     3.2.3 角区的更新策略
  •     3.2.4 cut线的确定策略
  •     3.2.5 排除defect策略
  •   3.3 算法描述
  •     3.3.1 算法思想
  •     3.3.2 算法步骤
  • 4 实验结果分析
  •   4.1 实验环境
  •   4.2 实验数据来源
  •   4.3 计算结果分析
  • 5 总结与展望
  •   5.1 总结
  •   5.2 展望
  • 参考文献
  • 附录
  • 致谢
  • 文章来源

    类型: 硕士论文

    作者: 饶昊

    导师: 尹爱华

    关键词: 二维切割问题,一刀切问题,启发式方法,杂质

    来源: 江西财经大学

    年度: 2019

    分类: 基础科学

    专业: 数学

    单位: 江西财经大学

    分类号: O224

    总页数: 59

    文件大小: 2585K

    下载量: 180

    相关论文文献

    • [1].设备单行布置近似最优解简便解法的探讨[J]. 宁波工程学院学报 2011(01)
    • [2].向量优化问题局部近似解的等价性[J]. 数学的实践与认识 2020(09)
    • [3].单一规格物体二维矩形条带装箱问题解法研究[J]. 成组技术与生产现代化 2017(02)
    • [4].同顺序排序问题近似最优解的一种简便解法[J]. 成组技术与生产现代化 2015(02)
    • [5].求解一类NP-HARD问题的一个快速算法[J]. 内蒙古大学学报(自然科学版) 2012(01)
    • [6].基于汉明距离递减变换的可逆逻辑综合算法[J]. 计算机学报 2014(08)
    • [7].机组启停优化中遗传算法的应用研究[J]. 中国电业(技术版) 2015(02)
    • [8].最佳组队问题的优化模型与解法[J]. 福建电脑 2015(11)
    • [9].解一类全局优化问题实质ε-最优解的一个新方法[J]. 长春工业大学学报(自然科学版) 2009(06)
    • [10].双机协同战术对策及近似最优解[J]. 系统工程与电子技术 2015(03)
    • [11].访问控制策略中信息流的最优化去环方法[J]. 电子学报 2011(07)

    标签:;  ;  ;  ;  

    板材切割问题的求解与应用
    下载Doc文档

    猜你喜欢