二维非规则带排样问题研究

论文摘要

二维非规则带排样问题,就是给定一个平面布局空间和若干形状不规则的待排件,在满足彼此不重叠的前提下,将待排件摆放在布局空间中,使得材料的利用率最高。排料问题是一个应用极为广泛的问题,在轻工业制造、航空航天、皮革、服装等行业均有涉及。排样结果的优劣直接关系到企业的生产效益。理论上,二维排料问题属于组合优化问题,涉及到计算机图形学和运筹学等多领域的知识,是属于具有最高计算复杂度的NP完全问题,具有重要的研究和实用价值。本文对二维非规则带排样过程中的关键问题进行了深入研究,主要的研究工作如下:1、给出了基于最小移动距离的定位算法,抛弃了NFP（No-Fit-Polygon）预处理和相应的判交方法,采用了更简单直观的多边形碰撞算法,极大地降低了整体的计算消耗时间;2、在经典的BL算法的基础上,根据已排件顶点作为步长递增标准,将原有的定长步长的方式改为不定长步长的方式;并提出了滑动区域、二次滑动等概念,有效地提高排样速度和排样效果;3、针对于BL算法过程中造成的空白区域的问题,提出了可充分填充空白区域的反向检测算法,提高了原材料的利用率;4、在上述工作的基础上,给出了二维非规则带排样算法,并对其进行了数值实验和对比分析。本文所提启发式算法克服了现代智能优化算法运行不稳定的弊端,力求对同一输入样本（待排件）,执行算法都可以得到绝对稳定的输出结果（排料布局）以及相对稳定的运行时间。数值结果表明,本文所提算法能够有效地提高材料利用率并极大地降低整体时间消耗。

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 研究背景与意义
•   1.2 国内外研究历史与现状
•   1.3 本文研究内容与结构
•     1.3.1 本文主要研究内容
•     1.3.2 本文组织结构
• 第2章 相关基础知识
•   2.1 关于NP完全问题
•     2.1.1 算法的时间复杂度
•     2.1.2 与P/NP问题相关的概念
•   2.2 二维排料问题的数学模型
•   2.3 二维排料问题的分类
•   2.4 非规则排料问题经典算法
•     2.4.1 近似算法
•     2.4.2 局部优化算法
•     2.4.3 启发式算法
•     2.4.4 智能优化算法
•   2.5 图形学相关基础
•     2.5.1 点与直线距离公式
•     2.5.2 扩展的点与直线距离公式
•     2.5.3 简单多边形的面积计算
•     2.5.4 多边形的旋转
•   2.6 本章小结
• 第3章 基于最小移动距离的带排样算法
•   3.1 非规则多边形的表示和数据结构
•     3.1.1 坐标系统
•     3.1.2 多边形的表示
•     3.1.3 多边形的边界表示
•     3.1.4 相关的数据结构
•   3.2 最小移动距离求解算法
•     3.2.1 待排件的靠接
•     3.2.2 碰撞区域检测
•     3.2.3 带状区域
•     3.2.4 碰撞点与碰撞前沿的有效交点的判定
•     3.2.5 确定最小移动距离的算法
•   3.3 二维非规则带排样算法
•     3.3.1 数据预处理
•     3.3.2 基于BL的启发式算法
•     3.3.3 多边形的碰撞算法
•     3.3.4 反向检测
•     3.3.5 不定步长的移动策略
•     3.3.6 二次滑动策略
•   3.4 本章小结
• 第4章 数值实验结果与对比分析
•   4.1 算例介绍
•   4.2 实验结果
•     4.2.1 样例测试
•     4.2.2 结果分析
•   4.3 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢

文章来源

类型: 硕士论文

作者: 赵晓龙

导师: 曹大勇

关键词: 最小移动距离,滑动区域,二维非规则排样问题,完全问题

来源: 哈尔滨理工大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 哈尔滨理工大学

分类号: O221

总页数: 64

文件大小: 2073K

下载量: 77