二维矩形条带装箱问题的左下角定位模型

发布时间：2020-11-05 01:49

　　二维矩形条带装箱问题(2DR-SPP)是典型的组合优化问题,也是NP-Hard问题,求解的难度较大,有重要的研究意义。该问题在计算机辅助设计、图像处理、大规模集成电路逻辑布线设计等领域有广泛应用,有较高的实际应用价值。构建2DR-SPP的简单数学模型,既可实现对中小规模问题的有效求解,又可为研究求解大规模问题的快速高精度的数学规划启发式算法奠定基础,有重要的研究价值。对2DR-SPP,为构建其准确、有效、简单的数学模型,本文主要做了以下两个方面的工作:(1)针对不旋转置于条带箱中的任意两个矩形物体,提出并理论论证这两个物体被重叠放置时,其左下角单元坐标应满足的充要条件,基于此充要条件构建两矩形互不重叠放置的约束模型;然后针对问题的其它要求和目标构建问题的其它约束模型和目标函数,得到不旋转问题的线性整数规划模型;最后引入辅助变量,将不旋转模型拓展得可旋转情况下问题的数学模型。实验结果验证了模型的准确性和较已有模型的更有效性。(2)将基于任意两矩形左下角单元坐标的内在关系构建约束模型的建模思想进行改进,利用矩形左下角单元坐标和条带箱单元坐标的内在关系构建禁止矩形重叠放置的约束模型,得到问题的改进左下角定位模型;然后根据矩形放置方式选择的特性,将可旋转情形转化为不旋转情形,并构建其模型。可旋转2DR-SPP的改进模型在决策变量个数和约束条件个数两方面都较已有模型有较大幅度的减少,所以模型更为简单、有效。对12个标杆算例的求解结果进一步验证了所建改进模型的准确性和更有效性。
【学位单位】：武汉科技大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157
【文章目录】：
摘要
ABSTRACT
第1章绪论
    1.1 问题背景
    1.2 国内外研究现状
    1.3 选题意义
    1.4 论文结构安排
第2章 2DR-SPP的左下角定位模型
    2.1 问题离散化描述
    2.2 符号设定
    2.3 左下角定位模型
        2.3.1 不旋转模型
        2.3.2 可旋转模型
    2.4 小结
第3章 2DR-SPP的改进左下角定位模型
    3.1 符号说明
    3.2 改进左下角定位模型
        3.2.1 改进不旋转左下角定位模型
        3.2.2 改进可旋转左下角定位模型
    3.3 小结
第4章实验算例
    4.1 模型准确性检验
        4.1.1 左下角定位模型检验
        4.1.2 改进左下角定位模型检验
    4.2 模型复杂性检验
        4.2.1 不旋转模型检验
        4.2.2 可旋转情况下的模型验证
    4.3 小结
第5章总结与展望
    5.1 总结
    5.2 创新点
    5.3 展望
致谢
参考文献
附录1 攻读硕士学位期间发表的论文
附录2 攻读硕士学位期间参加的科研项目

【参考文献】

相关期刊论文前10条

1 易向阳;仝青山;潘卫平;;矩形件二维下料问题的一种求解方法[J];锻压技术;2015年06期

2 孔令熠;陈秋莲;;二维多阶段矩形剪切排样算法[J];计算机应用与软件;2015年05期

3 田大肥;申喜;周巍;;二维装箱问题的遗传算法求解[J];舰船电子工程;2014年01期

4 彭碧涛;周永务;;求解2D条带矩形Packing问题的迭代启发式算法[J];软件学报;2012年10期

5 黄岚;齐季;谭颖;杨滨;;一种求解矩形排样问题的遗传-离散粒子群优化算法[J];电子学报;2012年06期

6 蒋兴波;吕肖庆;刘成城;;二维矩形条带装箱问题的底部左齐择优匹配算法[J];软件学报;2009年06期

7 于洪霞;张绍武;张立卫;;二维装箱问题非线性规划模型和算法[J];大连理工大学学报;2008年02期

8 张德富;韩水华;叶卫国;;求解矩形Packing问题的砌墙式启发式算法[J];计算机学报;2008年03期

9 汤岩;胡俊敏;武立丰;;一种改进的二维装箱问题的混合遗传算法[J];集美大学学报(自然科学版);2006年03期

10 赵中凯,梅国建,沈洪,赵战彪;基于混合蚂蚁算法的二维装箱问题求解[J];计算机应用;2004年S1期

相关博士学位论文前1条

1 姚怡;二维装箱问题的启发式算法研究[D];华南理工大学;2016年