二维不规则下料问题的几何干涉检查及模型简化研究

摘要

资源的有限性和人类对资源需求的无限性的矛盾决定人类需要优化资源配置、充分合理地利用现有资源并且开源节流。正处于经济新常态的中国，经济结构需要优化升级，过去只求数量和速度的粗放型经济发展模式需要进行改进，发展的目标应该更注重于质量和效益。因而有必要对以最大化材料利用率为目标的二维切割与布局问题进行深入研究。
　　二维切割与布局问题是具有广泛应用价值的组合优化问题。其NP-难属性决定了其不存在多项式时间的解法，而其具有的建模和求解的双重复杂性使其难以求解。针对目前二维切割与布局问题中存在的难点问题，本文对干涉检查问题和通用层次上的模型简化问题进行研究，实现了大规模不规则下料问题的求解，主要工作如下:
　　(1)提出一个适用于任意多边形的不干涉多边形生成算法，用于检查多边形的干涉情况。
　　(2)对二维切割与布局问题中的格点简化技术进行研究，从数学模型层次上初步提出了一种与格点简化方法等价的简化方法。相比于传统方法，该方法更便于在不规则下料问题中采用。
　　(3)对生产运作管理中的滚动式生产计划法进行研究，基于其思想提出了切割下料滚动地平线策略，应用于大规模的二维切割下料问题的求解中。
　　(4)应用以上研究成果，以不规则零件为研究对象，对大规模不规则下料问题进行建模求解，并对企业中实际的冲压钣金零件进行布局求解，得到了较好的效果。

目录

声明

致谢

摘要

1 绪论

1．1 选题背景和意义

1．2 切割与布局问题概述

1．3 国内外研究现状

1．4 研究内容

1．5 论文结构

1．6 本章小结

2 几何干涉问题的研究

2．1 几何干涉问题概述

2．2 多多边形交并差运算的研究

2．2．1 多边形交并差运算的研究背景

2．2．2 多边形的表示方法

2．2．3 多多边形交并差运算算法

2．2．4 算法复杂度分析

2．2．5 特殊情况

2．2．6 算例分析

2．3 使用多多边形交并差算法生成不干涉多边形

2．3．1 生成不干涉多边形

2．3．2 算例测试

2．3．3 不干涉多边形检查干涉

2．4 本章小结

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．3 本章小结

4 大规模不规则下料问题的求解

4．1 不规则下料问题概述

4．2 大规模不规则下料问题的求解

4．2．1 决策变量与目标函数

4．2．2 约束条件

4．2．3 模型求解

4．3 求解实例及数值实验

4．4 本章小结

5 总结与展望

5．1 总结

5．2 展望

参考文献

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集