基于二维不规则鞋片的自动排料系统研究

摘要

不规则形状物体的自动排料问题,一直受到广泛的重视和研究,研究方法涉及了计算几何学、人工智能、组合优化等各种理论.由于二维不规则形状的布局问题属于NP难度问题,因此解决该问题的关键是:解决计算的可解性(capability)和难解性(intractability).所以计算机鞋片自动排料系统首先要解决计算量的问题.要努力减少计算量,提高运算速度;其次要提高利用率,使计算机排料所得到的利用率接近或超过人工水平.利用率和运算时间是计算机排料自动化的一对重要参数,二者是对立统一的存在.本文在基于人工智能的启发式搜索方法的基础上提出了一种计算机自动鞋片排料算法.本算法不仅适用于鞋片的排料问题,还适用于其他各种套料问题,具有较强的通用性.

目录

文摘

英文文摘

第一章绪论

1.1引言

1.2研究背景与意义

1.2.1排料问题的研究背景

1.2.2排料问题研究的意义

1.3国内外研究历史及现状

1.3.1国外研究概况

1.3.2国内研究概况

1.4基于启发式搜索的排料算法的可行性

第二章自动排料算法

2.1 NP完全问题

2.1.1 NP完全问题的引出[41]

2.1.2解决NP完全问题的思路[42]

2.1.3排料的实质问题

2.2常见的几种算法的介绍

2.3矩形件排料

2.3.1BL算法

2.3.2下台阶算法

2.3.3最低水平线法

2.4问题求解与搜索

2.4.1状态空间搜索

2.4.2搜索算法分析

2.5启发式搜索算法[45，48]

2.6搜索过程

2.7估计函数与启发信息[47]

第三章排料系统设计

3.1鞋片的表示和结构

3.1.1鞋片的表示

3.1.2鞋片的档案结构

3.2经验库

3.3图形学相关算法

3.3.1线段相交

3.3.2点是否在多边形内部

3.3.3多边形重叠算法

3.3.4多边形面积计算

3.4自动排料系统

3.4.1人工智能启发式搜索方法的引入

3.4.2二维布局问题的表示

3.4.3自动排料算法的实现

第四章自动排料实例及系统改进

4.1自动排料实例

4.2系统改进

4.2.1嵌套处理

4.2.2不规则料片处理

4.2.3余料处理

第五章结论与建议

5.1结论

5.2建议

5.2.1自动布局算法的理论分析方法

5.2.2自动布局算法在本鞋片排料系统中的应用建议

参考文献

致谢