带缺陷矩形切割问题的高效算法研究
发布时间：2021-04-16 05:26
科学技术正在迅速发展,计算机已经融入到国民生产的各个领域中,软件产品正在逐渐成为社会生产中不可缺少的辅助工具。排样问题广泛存在于工业制造、交通运输和日常生活管理等重要领域,本文的工作就是推广和改进优化方法在板材切割问题中的解决方案。排样问题常见于工业生产中,例如玻璃切割、钢材切割、产品包装、集装箱装载、车厢装载、托盘组装,还有文本排版、衣料裁剪以及物品摆放等等。为了降低成本消耗、提高生产效率以及节约社会生产资源,一个好的排样方案将带来巨大的社会生产效益并提高生活与生产质量。切割最优化问题是排样问题的一种具体形式。给定一个二维板材和一定数量的待排样物品,将待排样的物品在符合一定约束条件的前提下合理地摆放在空间内,使得空间利用效率达到某种最优目标。排样的优劣将直接或间接影响相关行业的生产、传输及销售,继而影响其经济收益。切割问题也是一个组合优化问题,其最大的挑战就是组合爆炸,尤其是当计算规模增加时,其组合的规模将呈现指数增长。国内外专家学者在这方面进行了很多探索提出了很多算法,本文就是在这些算法的基础上通过分析比较,设计了一种针对切割问题的拟人算法。讨论了在带有多个缺陷的二维矩形板材上切割...
【文章来源】：江西财经大学江西省
【文章页数】：62 页
【学位级别】：硕士
【部分图文】：
板材一刀切（（a）一刀切
2问题描述9表示：=∑;∈+=1(2.1)其中，F为目标函数，是非负数，表示第类目标块的数量，是正整数，表示第类目标块块的面积。其次，建立二维欧式坐标系，将矩形原板材的左下角置于坐标原点，原板材水平方向跟坐标系轴指向，原板材竖直方向为轴指向。这样，我们可以用四元组=(0,0,,)来表示原板材基本信息，其中(0,0)表示原板材左下角的横纵坐标，表示原板材水平方向的宽，表示原板材竖直方向的高。再次，矩形原板材上不能用于切割出目标矩形块的区域称为缺陷区域。原板材上存在数量为的缺陷区域，每个区域是不规则形状的，为了更好地描述缺陷区域的位置和尺寸信息，我们用一个恰好完全覆盖缺陷的矩形块来表示缺陷区域，并且缺陷的各个边均平行或垂直于坐标轴。因此，缺陷可以用四元组表示为=(,,,)，其中，缺陷区域左下角坐标为(,)，宽为，高为，其中∈。缺陷区域在坐标系中表示如图2.2。图2.2缺陷区域在坐标系中的表示最后，为了后续算法描述方便，我们还要定义两个常量，它们是和，分别表示所有目标块中最小的宽度和最小的高度，其公式表示如下：=();=1,2,…,=();=1,2,…,2.2问题解法本文作为一种优化问题，最大的挑战就是具有组合爆炸[38]。人们在已掌握的技术下无法在能接受的时间范围内找到最优解，尤其是随着问题规模的增加，其
32D_SLOPP的求解算法15子问题_=(0,0+,,)。切割线仅对当前中间板而言，换言之，切割线是一个相对值，如果是竖直切割，c表示中间板的左边界和切割位置横坐标的相对距离，如果是水平切割，表示中间板的下边界和切割位置的纵坐标的相对距离。切割线示意图如图3.1。图3.1切割线的表示3.2离散集在待切割的中间板上我们把同一方向获得的所有的切割线组成一个离散化的集合称之为离散集。把这些切割线所在位置信息记录下来并挨个进行分解计算，将一个大问题分解成若干个小问题然后将所得小问题的解反馈，小问题分解成更小的问题，依次类推，将会得到原板材的解，这样一来即是在原板材上排样了所有可能的切割模式，选取其中最大的一个值即是原板材的最优目标值。在中间板上记录水平和竖直两个方向的所有切割线，将会形成宽为高为的网格，最终将从众多的切割线中寻找出一条作为最优的切割方式进行切割。那么，如果可选的切割线越多就意味着有跟多的可能获得更大的目标值，于是文献[8]考虑了竖直和水平方向所有的位置作为切割线进行计算，将其称之为完全离散集。用()表示水平方向完全离散集，()表示竖直方向的完全离散集，则有：{()={|∈+,1≤≤1}()={|∈+,1≤≤1}(3.1)尝试计算中间板上所有的整数切割位置，意味着枚举所有的可行解，其优点是能够获得最优解，但是缺点是可行解的基数大使得计算量增多，另一方面，相邻的两个切割线计算得到的结果可能对切割质量没影响，只是改变了目标块的摆放位置。使用完全离散集做切割的代价是极大的，随之基础离散集被构造。Herz[16]通过限制离散集的大小，在不损失最优解的情况下可以取代完全离散
【参考文献】：
期刊论文
[1]求解二维矩形Packing问题的一种优美度枚举算法[J]. 王磊,尹爱华. 中国科学:信息科学. 2015(09)
[2]生成矩形毛坯最优两段排样方式的递归算法[J]. 崔耀东,季君,曾窕俊. 南京航空航天大学学报. 2006(01)
[3]生成矩形毛坯最优T形排样方式的递归算法[J]. 崔耀东. 计算机辅助设计与图形学学报. 2006(01)
[4]矩形件排样的模拟退火算法求解[J]. 贾志欣,殷国富,罗阳,徐雷. 四川大学学报(工程科学版). 2001(05)
[5]利用混沌人工神经元网络进行布局优化计算[J]. 李建勇,鄂明成,曹月东. 制造业自动化. 2000(01)
[6]矩形件排样问题的遗传算法求解[J]. 刘德全,滕弘飞. 小型微型计算机系统. 1998(12)
[7]矩形件排样优化的一种近似算法[J]. 曹炬,周济. 计算机辅助设计与图形学学报. 1995(03)
硕士论文
[1]板材切割问题的求解与应用[D]. 饶昊.江西财经大学 2019
[2]全局优化问题的确定性算法研究[D]. 栾世超.曲阜师范大学 2009
[3]矩形件下料优化排样的遗传算法[D]. 黄红兵.广西师范大学 2005
本文编号：3140831
【文章来源】：江西财经大学江西省
【文章页数】：62 页
【学位级别】：硕士
【部分图文】：
板材一刀切（（a）一刀切
2问题描述9表示：=∑;∈+=1(2.1)其中，F为目标函数，是非负数，表示第类目标块的数量，是正整数，表示第类目标块块的面积。其次，建立二维欧式坐标系，将矩形原板材的左下角置于坐标原点，原板材水平方向跟坐标系轴指向，原板材竖直方向为轴指向。这样，我们可以用四元组=(0,0,,)来表示原板材基本信息，其中(0,0)表示原板材左下角的横纵坐标，表示原板材水平方向的宽，表示原板材竖直方向的高。再次，矩形原板材上不能用于切割出目标矩形块的区域称为缺陷区域。原板材上存在数量为的缺陷区域，每个区域是不规则形状的，为了更好地描述缺陷区域的位置和尺寸信息，我们用一个恰好完全覆盖缺陷的矩形块来表示缺陷区域，并且缺陷的各个边均平行或垂直于坐标轴。因此，缺陷可以用四元组表示为=(,,,)，其中，缺陷区域左下角坐标为(,)，宽为，高为，其中∈。缺陷区域在坐标系中表示如图2.2。图2.2缺陷区域在坐标系中的表示最后，为了后续算法描述方便，我们还要定义两个常量，它们是和，分别表示所有目标块中最小的宽度和最小的高度，其公式表示如下：=();=1,2,…,=();=1,2,…,2.2问题解法本文作为一种优化问题，最大的挑战就是具有组合爆炸[38]。人们在已掌握的技术下无法在能接受的时间范围内找到最优解，尤其是随着问题规模的增加，其
32D_SLOPP的求解算法15子问题_=(0,0+,,)。切割线仅对当前中间板而言，换言之，切割线是一个相对值，如果是竖直切割，c表示中间板的左边界和切割位置横坐标的相对距离，如果是水平切割，表示中间板的下边界和切割位置的纵坐标的相对距离。切割线示意图如图3.1。图3.1切割线的表示3.2离散集在待切割的中间板上我们把同一方向获得的所有的切割线组成一个离散化的集合称之为离散集。把这些切割线所在位置信息记录下来并挨个进行分解计算，将一个大问题分解成若干个小问题然后将所得小问题的解反馈，小问题分解成更小的问题，依次类推，将会得到原板材的解，这样一来即是在原板材上排样了所有可能的切割模式，选取其中最大的一个值即是原板材的最优目标值。在中间板上记录水平和竖直两个方向的所有切割线，将会形成宽为高为的网格，最终将从众多的切割线中寻找出一条作为最优的切割方式进行切割。那么，如果可选的切割线越多就意味着有跟多的可能获得更大的目标值，于是文献[8]考虑了竖直和水平方向所有的位置作为切割线进行计算，将其称之为完全离散集。用()表示水平方向完全离散集，()表示竖直方向的完全离散集，则有：{()={|∈+,1≤≤1}()={|∈+,1≤≤1}(3.1)尝试计算中间板上所有的整数切割位置，意味着枚举所有的可行解，其优点是能够获得最优解，但是缺点是可行解的基数大使得计算量增多，另一方面，相邻的两个切割线计算得到的结果可能对切割质量没影响，只是改变了目标块的摆放位置。使用完全离散集做切割的代价是极大的，随之基础离散集被构造。Herz[16]通过限制离散集的大小，在不损失最优解的情况下可以取代完全离散
【参考文献】：
期刊论文
[1]求解二维矩形Packing问题的一种优美度枚举算法[J]. 王磊,尹爱华. 中国科学:信息科学. 2015(09)
[2]生成矩形毛坯最优两段排样方式的递归算法[J]. 崔耀东,季君,曾窕俊. 南京航空航天大学学报. 2006(01)
[3]生成矩形毛坯最优T形排样方式的递归算法[J]. 崔耀东. 计算机辅助设计与图形学学报. 2006(01)
[4]矩形件排样的模拟退火算法求解[J]. 贾志欣,殷国富,罗阳,徐雷. 四川大学学报(工程科学版). 2001(05)
[5]利用混沌人工神经元网络进行布局优化计算[J]. 李建勇,鄂明成,曹月东. 制造业自动化. 2000(01)
[6]矩形件排样问题的遗传算法求解[J]. 刘德全,滕弘飞. 小型微型计算机系统. 1998(12)
[7]矩形件排样优化的一种近似算法[J]. 曹炬,周济. 计算机辅助设计与图形学学报. 1995(03)
硕士论文
[1]板材切割问题的求解与应用[D]. 饶昊.江西财经大学 2019
[2]全局优化问题的确定性算法研究[D]. 栾世超.曲阜师范大学 2009
[3]矩形件下料优化排样的遗传算法[D]. 黄红兵.广西师范大学 2005
本文编号：3140831
本文链接：https://www.wllwen.com/shoufeilunwen/xixikjs/3140831.html
