带残损原材料二维优化下料问题的研究

论文摘要

目前，随着可持续性发展战略的提出，全球对资源消耗问题日益重视，优化利用资源是我国经济发展战略的重要内容之一，也是整个世界最重要的研究课题之一。从平面原材料上切下各式各样的下料件，使材料的利用率最高，这是二维优化下料问题。二维下料问题广泛存在于机械制造、服装、皮革以及玻璃加工等行业中，它在理论属于具有最高复杂性的NP完全（Nondeterministic Polynomial Time Complete）问题，因此，开展对下料问题的研究具有重要的理论意义和工程应用价值。 本文主要讨论了不规则形状的下料件在带残损原材料上的下料方法。介绍了下料件多边形、残损多边形的表示方法，多边形的平移、旋转、判交等基本理论。通过遗传模拟退火算法产生下料件的最优次序和角度，然后采用基于左下角（Bottom-left）策略的快速定位启发式算法进行布局。 本文的研究工作集中体现在以下几个方面： 1．自动下料系统分为信息输入、自动布局和结果输出三大部分，本文根据课题的主要方向，设计了带残损原材的二维不规则下料系统的结构模型。 2．系统的信息输入主要有AutoCAD绘图软件输入和人机交互界面输入两种，本文介绍了AutoCAD中DXF文件的结构，为系统读取下料件图形数据的程序编写打下了理论基础；同时，本文采用MATLAB语言，设计了友好的人机交互界面，从而实现了原材料信息、初始条件等数据的输入以及结果输出等功能。 3．将残损多边形视为已定位好的下料件，在排样过程中，将每一个待排下料分别与已排下料件和所有的残损进行重叠检验，从理论上较易实现带残损原材料的二维下料问题，但在实际运行时，必定会使系统的计算复杂度和运行时间有所增加，因此，本文采用“最小最大测试”和逐边求交的二次判交法，大大缩短了多边形的重叠判定时间，尤其在待排下料件和残损多边形的判交过程中，效果突出。 4．算法是系统是否真正实现优化的关键，本文从应用的角度对遗传算法

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 选题的意义
• 1.2 下料问题的实质和分类
• 1.3 二维优化下料问题的研究和发展概况
• 1.3.1 二维下料问题的描述
• 1.3.2 国内外的研究状况
• 1.3.3 二维不规则物体下料的主要方法
• 1.4 本文的主要研究内容
• 1.5 论文的内容组织
• 第2章 优化下料系统图像处理技术
• 2.1 优化下料系统的构成
• 2.2 图形数据处理的关键问题分析
• 2.2.1 下料件及残损多边形的表示
• 2.2.2 坐标变换
• 2.2.3 多边形的重叠性检验
• 2.3 从AutoCAD的.DXF文件中读取图形数据
• 本章小结
• 第3章 遗传模拟退火算法在二维下料中的应用
• 3.1 概述
• 3.2 遗传算法简介
• 3.2.1 遗传算法的基本理论
• 3.2.2 遗传算法的实现
• 3.2.3 遗传算法的特点
• 3.3 模拟退火算法简介
• 3.3.1 模拟退火算法的基本理论
• 3.3.2 模拟退火算法的实现
• 3.4 用遗传模拟退火算法求解二维下料问题
• 3.4.1 遗传算法和模拟退火算法的结合
• 3.4.2 遗传模拟退火算法在二维优化下料中的应用
• 本章小结
• 第4章 带残损原材料的不规则多边形的自动下料方案
• 4.1 概述
• 4.2 优化下料方案
• 4.2.1 BL算法
• 4.2.2 基于BL策略的快速定位启发式算法
• 4.3 图形在MATLAB中的数据结构
• 4.4 实例
• 本章小结
• 第5章 结论及展望
• 5.1 研究工作总结
• 5.2 展望
• 附录1 系统使用说明
• 附录2 部分源程序
• 参考文献
• 致谢
• 攻读学位期间所发表的学术论文
• 学位论文评阅及答辩情况表