二维一刀切装箱问题研究
发布时间：2021-01-21 06:33
二维一刀切装箱问题,指在给定无限多个固定大小的二维板材（箱子）上,将不同规格的待排矩形件,在保证彼此不重叠的前提下,逐个摆放至二维箱子内,使得占用箱子的个数最少,并且在切割时满足一刀切条件约束（此处的一刀切约束是指切割时刀口走线不能弯曲,必须从一条边经直线切割到对边）。二维一刀切装箱问题隶属于组合优化问题中的二维布局问题,最典型的应用是在家具生产过程中玻璃切割的布局优化。从计算复杂性理论的角度来看,该问题属于具有最高计算复杂性的NP完全问题,并涉及到计算几何、运筹学等多学科知识,具有较高的理论研究和实用价值。本文对二维一刀切装箱过程中的相关问题进行了深入研究,主要的研究工作如下:1、首次给出G-区域和GR-区域的概念,用以定量描述排样过程中可被一刀切的区域所需要满足的相关条件。2、提出了顺时针切割线组以及逆时针切割线组等定义。在使用三叉排样树对布局结构进行描述的基础上,相继构造了G-区域的判断算法、GR-区域的延展算法及全局更新算法等子算法。3、在上述工作的基础上,提出了二维一刀切装箱问题的启发式算法,并对其进行了数值实验和结果分析。4、利用所提算法,编制了可被实用的排样软件,并在其中...
【文章来源】：哈尔滨理工大学黑龙江省
【文章页数】：46 页
【学位级别】：硕士
【部分图文】：
BLF算法路径示意图
哈尔滨理工大学理学硕士学位论文13题研究的相关图形表示采用如下坐标系统，如图3-1所示，坐标原点O点为左上角顶点，x轴正方向向右延伸，y轴正方向向下延伸。图3-1坐标系统Fig.3-1Thecoordinatesystem3.3概念及算法3.3.1相关概念及结论定义3.1G-区域给定二维装箱问题中的任意矩形空白区域R，若R可经一组有序的且满足一刀切的切割线而获得，则称该区域为G-区域。显然，对任意一个G-区域而言，对于接下来的一些新的待排项，是一个可能的排放区域。这里我们约定，如果待排项I可以被放入至某个G-区域R内，则该项总是被摆放至R的左上角，即使得I的左上角顶点与R的左上角顶点重合。不失一般性，假设RIheightheight且RIwidthwidth，则摆放I后，由R和I可获得两个可排空白区域1R和2R（21RR），如图3-2所示。图3-2R1和R2的生成示意图Fig.3-2GenerationofR1andR2
哈尔滨理工大学理学硕士学位论文13题研究的相关图形表示采用如下坐标系统，如图3-1所示，坐标原点O点为左上角顶点，x轴正方向向右延伸，y轴正方向向下延伸。图3-1坐标系统Fig.3-1Thecoordinatesystem3.3概念及算法3.3.1相关概念及结论定义3.1G-区域给定二维装箱问题中的任意矩形空白区域R，若R可经一组有序的且满足一刀切的切割线而获得，则称该区域为G-区域。显然，对任意一个G-区域而言，对于接下来的一些新的待排项，是一个可能的排放区域。这里我们约定，如果待排项I可以被放入至某个G-区域R内，则该项总是被摆放至R的左上角，即使得I的左上角顶点与R的左上角顶点重合。不失一般性，假设RIheightheight且RIwidthwidth，则摆放I后，由R和I可获得两个可排空白区域1R和2R（21RR），如图3-2所示。图3-2R1和R2的生成示意图Fig.3-2GenerationofR1andR2
【参考文献】：
期刊论文
[1]基于匀质块排样方式的多尺寸板材下料算法[J]. 向文欣,王宏旭,潘立武. 锻压技术. 2019(07)
[2]矩形件简单块占角排样方式的动态规划[J]. 潘卫平,张瑞友. 中国图象图形学报. 2019(06)
[3]矩形件套裁排样的一种优化解法[J]. 扈少华,张淋江,潘立武,管卫利. 机械设计与制造. 2018(06)
[4]基于矩形拼接的“一刀切”矩形排样优化设计[J]. 张子成. 现代制造工程. 2018(04)
[5]基于改进离散萤火虫算法的二维排样问题优化[J]. 吴堂福,杨建军,刘志浩,姜晓瑜. 中国科技论文. 2018(02)
[6]递归算法在单一矩形毛坯无约束最优排样中的应用[J]. 李海生. 重庆理工大学学报(自然科学). 2017(09)
[7]约束二维排样问题的一种求解算法[J]. 朱强,薛峰,郑仕勇,管卫利. 锻压技术. 2016(09)
[8]单规格一刀切矩形排样问题的启发式搜索算法[J]. 王磊,刘强,陈新. 软件学报. 2017(07)
[9]二维剪切排样的束搜索启发式算法[J]. 陈秋莲,王成栋. 计算机工程与应用. 2017(09)
[10]基于匀质条带的矩形件最优三块布局算法[J]. 潘卫平,陈秋莲,崔耀东,陈怡丹. 图学学报. 2015(01)
硕士论文
[1]二维非规则带排样问题研究[D]. 赵晓龙.哈尔滨理工大学 2019
[2]应用精确两阶段排样图的板材下料算法[D]. 王严欣.广西大学 2016
[3]满足“一刀切”约束的卷型材矩形件排样方法研究[D]. 何霖.广东工业大学 2014
本文编号：2990658
【文章来源】：哈尔滨理工大学黑龙江省
【文章页数】：46 页
【学位级别】：硕士
【部分图文】：
BLF算法路径示意图
哈尔滨理工大学理学硕士学位论文13题研究的相关图形表示采用如下坐标系统，如图3-1所示，坐标原点O点为左上角顶点，x轴正方向向右延伸，y轴正方向向下延伸。图3-1坐标系统Fig.3-1Thecoordinatesystem3.3概念及算法3.3.1相关概念及结论定义3.1G-区域给定二维装箱问题中的任意矩形空白区域R，若R可经一组有序的且满足一刀切的切割线而获得，则称该区域为G-区域。显然，对任意一个G-区域而言，对于接下来的一些新的待排项，是一个可能的排放区域。这里我们约定，如果待排项I可以被放入至某个G-区域R内，则该项总是被摆放至R的左上角，即使得I的左上角顶点与R的左上角顶点重合。不失一般性，假设RIheightheight且RIwidthwidth，则摆放I后，由R和I可获得两个可排空白区域1R和2R（21RR），如图3-2所示。图3-2R1和R2的生成示意图Fig.3-2GenerationofR1andR2
哈尔滨理工大学理学硕士学位论文13题研究的相关图形表示采用如下坐标系统，如图3-1所示，坐标原点O点为左上角顶点，x轴正方向向右延伸，y轴正方向向下延伸。图3-1坐标系统Fig.3-1Thecoordinatesystem3.3概念及算法3.3.1相关概念及结论定义3.1G-区域给定二维装箱问题中的任意矩形空白区域R，若R可经一组有序的且满足一刀切的切割线而获得，则称该区域为G-区域。显然，对任意一个G-区域而言，对于接下来的一些新的待排项，是一个可能的排放区域。这里我们约定，如果待排项I可以被放入至某个G-区域R内，则该项总是被摆放至R的左上角，即使得I的左上角顶点与R的左上角顶点重合。不失一般性，假设RIheightheight且RIwidthwidth，则摆放I后，由R和I可获得两个可排空白区域1R和2R（21RR），如图3-2所示。图3-2R1和R2的生成示意图Fig.3-2GenerationofR1andR2
【参考文献】：
期刊论文
[1]基于匀质块排样方式的多尺寸板材下料算法[J]. 向文欣,王宏旭,潘立武. 锻压技术. 2019(07)
[2]矩形件简单块占角排样方式的动态规划[J]. 潘卫平,张瑞友. 中国图象图形学报. 2019(06)
[3]矩形件套裁排样的一种优化解法[J]. 扈少华,张淋江,潘立武,管卫利. 机械设计与制造. 2018(06)
[4]基于矩形拼接的“一刀切”矩形排样优化设计[J]. 张子成. 现代制造工程. 2018(04)
[5]基于改进离散萤火虫算法的二维排样问题优化[J]. 吴堂福,杨建军,刘志浩,姜晓瑜. 中国科技论文. 2018(02)
[6]递归算法在单一矩形毛坯无约束最优排样中的应用[J]. 李海生. 重庆理工大学学报(自然科学). 2017(09)
[7]约束二维排样问题的一种求解算法[J]. 朱强,薛峰,郑仕勇,管卫利. 锻压技术. 2016(09)
[8]单规格一刀切矩形排样问题的启发式搜索算法[J]. 王磊,刘强,陈新. 软件学报. 2017(07)
[9]二维剪切排样的束搜索启发式算法[J]. 陈秋莲,王成栋. 计算机工程与应用. 2017(09)
[10]基于匀质条带的矩形件最优三块布局算法[J]. 潘卫平,陈秋莲,崔耀东,陈怡丹. 图学学报. 2015(01)
硕士论文
[1]二维非规则带排样问题研究[D]. 赵晓龙.哈尔滨理工大学 2019
[2]应用精确两阶段排样图的板材下料算法[D]. 王严欣.广西大学 2016
[3]满足“一刀切”约束的卷型材矩形件排样方法研究[D]. 何霖.广东工业大学 2014
本文编号：2990658
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2990658.html
