二维矩形件排样问题高效求解算法研究

发布时间：2022-02-22 09:02

　　随着经济的高速发展,科技的不断进步,提高资源利用率和制造效率十分重要。在生产过程中,优良的排样方案可以很好地提升材料的利用率及切割效率。因此,研究二维矩形件排样问题具有重要的实际应用意义和理论价值。二维矩形件排样问题是经典的NP难度问题。受前人研究成果启发,结合人类的生活习惯得到整齐度的概念。该概念主要融合了角区和放置空间,并希望已摆放的小矩形块和剩余空间越平整越好。整齐度不仅考虑了目前矩形块的摆放状态,还考虑了剩余空间的状态,为之后的格局做好可持续发展准备。论文中设计了以整齐度为核心,动作自由度为辅助的占角动作挑选策略。在此策略的基础上得到了基本算法。该算法的主要思想是,每一步根据占角动作挑选策略选择出最好的占角动作,再根据占角动作的指示对矩形块进行放置,直到矩形框放不下或矩形块全部放完为止,此时得到终止格局。一个好的挑选策略,不仅能提高基本算法的精度,还能减少基本算法花费的时间。为了扩宽解空间的搜索领域,从而得到更优质的解,结合基本算法和集束搜索策略,设计了加强算法。在加强算法中,每一步按照占角动作挑选策略挑选出若干个占角动作,将挑选出来的占角动作进行试放。每一个试放的占角动作都运... 

【文章来源】：江西财经大学江西省

【文章页数】：59 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
1 绪论
    1.1 研究背景及意义
        1.1.1 研究背景
        1.1.2 研究理论意义
        1.1.3 应用价值
    1.2 国内外研究概况
        1.2.1 国外研究概况
        1.2.2 国内研究概况
    1.3 本文的研究内容
2 问题的描述和研究
    2.1 矩形件排样问题描述
    2.2 二维矩形件排样问题定义
    2.3 问题难点
    2.4 典型算法
        2.4.1 BL算法
        2.4.2 BF算法
        2.4.3 优美度算法
    2.5 本章小结
3 基本算法和加强算法
    3.1 算法基础概念
    3.2 整齐度和动作自由度
    3.3 算法策略
        3.3.1 矩形块排序规则
        3.3.2 占角动作挑选策略
        3.3.3 角区更新策略
        3.3.4 放置空间更新策略
    3.4 算法描述
        3.4.1 算法思想
        3.4.2 基本算法
        3.4.3 加强算法
    3.5 本章小结
4 实验结果与对比分析
    4.1 算例介绍
    4.2 实验结果
        4.2.1 算例C21实验结果分析
        4.2.2 算例N13实验结果分析
    4.3 本章小结
5 总结与展望
    5.1 总结
    5.2 展望
参考文献
附录
致谢


【参考文献】：
期刊论文
[1]二维Packing问题拟人型算法中的动作空间更新过程求解[J]. 胡文蓓,饶昊.  软件导刊. 2017(08)
[2]二维矩形条带装箱问题的离散化左下角定位模型[J]. 李明,张曼曼,亓晓莹,唐秋华.  武汉科技大学学报. 2016(06)
[3]求解二维正交矩形布局问题的动态填空启发式算法[J]. 孙宝金,贺良华.  计算机应用研究. 2017(06)
[4]基于自适应遗传算法和多条带策略的排样方法研究[J]. 许华杰,檀洪森,胡小明.  计算机科学. 2016(04)
[5]基于遗传模拟退火算法的矩形件优化排样[J]. 杨卫波,王万良,张景玲,赵燕伟.  计算机工程与应用. 2016(07)
[6]求解二维矩形Packing问题的一种优美度枚举算法[J]. 王磊,尹爱华.  中国科学:信息科学. 2015(09)
[7]矩形件二维下料问题的一种求解方法[J]. 易向阳,仝青山,潘卫平.  锻压技术. 2015(06)
[8]求解二维矩形Packing问题的完备算法[J]. 何琨,姚鹏程,李立文.  计算机科学. 2014(08)
[9]基于动作空间求解二维矩形Packing问题的高效算法[J]. 何琨,黄文奇,金燕.  软件学报. 2012(05)
[10]三维矩形Packing问题的拟人求解算法[J]. 何琨,黄文奇.  中国科学:信息科学. 2010(12)

博士论文
[1]基于同形块的剪切下料布局算法研究[D]. 季君.北京交通大学 2012



本文编号：3639133