基于聚类和区域寻优的零部件排版启发式搜索算法研究

发布时间：2017-07-14 08:25

  本文关键词：基于聚类和区域寻优的零部件排版启发式搜索算法研究

  更多相关文章： 布局问题 多形状二维图形 包络矩形 区域寻优 邻界计算 聚类 启发式搜索算法

【摘要】：布局问题广泛存在于多种生产实践领域,诸如卫星舱布置、服装裁剪、板材下料和电子线路设计等领域,其研究具有理论价值和实际应用价值。Packing和Nesting问题,又称为装填问题和排版问题,是两类典型的布局问题。本文以课题来源单位大型起重机制造为背景,研究基于聚类和区域寻优的零部件排版问题。其特点是零部件种类繁多、形状差异很大且多为不规则形状。目前课题来源单位使用的是美国开发的排版软件SigmaNest10,但对于批量板材的大规模多形状零部件排版本问题求解却是不尽于人意,只好对其排版方案采用人工调整。为此,本文基于概率论、运筹学、计算机图形学和人工智能理论,对该问题展开研究,提出了解决瓶颈问题和技术难点的方法,申请了发明专利1项。本文的工作和创新如下:(1)提出了零部件CAD图形的DXF文件编码规则,开发了自动生成图元数据文件的软件。设计的编码规则和开发的软件适用于由线段、圆弧及圆图元组成多形状二维图形,图元数据文件包括其最小包络矩形。设计的算法的计算复杂度低,求解速度快。(2)提出了一种基于区域寻优的多形状零部件包络矩形排版的启发式搜索算法。基于区域寻优启发式搜索算法的排版方案,多形状二维零件间存在间隙。对此,本文进一步提出一种基于Lagrange乘子和kuhn-Tucker条件的邻界计算法,使得图形之间尽量靠紧,得到进一步优化的布局方案。(3)在批量钢板大规模多形状零件排版问题中,针对前面排版利用率高,后面排版利用率低这一难点,提出了一种基于聚类的启发式搜索算法,并且设计了排版流程步骤。通过对比实验表明,本文排版程序运行效率高,布局效果好,材料利用率较高。本文以某制造企业的大型起重机零部件排版问题为研究背景,针对单块矩形板排版问题,提出了基于区域寻优的启发式搜索算法和基于Lagrange乘子和kuhn-Tucker条件的邻界计算法;针对批量矩形钢板大规模多形状零部件排版问题,提出了一种基于聚类的启发式搜索算法。通过实验对比,得出本文算法具有较好的性能。
【关键词】：布局问题 多形状二维图形 包络矩形 区域寻优 邻界计算 聚类 启发式搜索算法
【学位授予单位】：湘潭大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TH21;TP301.6
【目录】：

• 摘要4-5
• Abstract5-9
• 第1章 绪论9-15
• 1.1 课题的背景9
• 1.2 二维排版问题现状综述9-14
• 1.2.1 国外研究现状9-10
• 1.2.2 国内研究现状10-14
• 1.3 论文的组织14-15
• 第2章 零部件图元的数据文件生成15-22
• 2.1 引言15
• 2.2 多形状二维零件图形数据格式15-16
• 2.3 多形状二维零件包络矩形求解算法16-20
• 2.4 小结20-22
• 第3章 基于区域寻优和邻界计算的零部件排版启发式算法22-37
• 3.1 问题的提出22
• 3.2 问题描述及数学模型22-23
• 3.3 基于区域寻优的启发式搜索算法23-30
• 3.3.1 前两个包络矩形的定位23-26
• 3.3.2 基于区域寻优放置其它包络矩形26-30
• 3.3.3 基于区域寻优的启发式算法步骤30
• 3.4 邻界计算法30-35
• 3.4.1 数据结构及核心思想30-31
• 3.4.2 直线与圆弧最小距离求解31-34
• 3.4.3 邻界计算法流程与步骤34-35
• 3.5 单块矩形板的排版算法与实例35-36
• 3.5.1 单块矩形板的排版算法步骤35
• 3.5.2 单块矩形板的排版实例35-36
• 3.6 小结36-37
• 第4章 基于聚类的批量板材大规模零部件排版方法37-43
• 4.1 问题的提出37
• 4.2 问题的数学模型37-38
• 4.3 基于聚类的批量板材大规模零部件排版方法38-39
• 4.3.1 难点的突破38
• 4.3.2 算法思想38-39
• 4.3.3 算法步骤39
• 4.4 实验结果与分析39-42
• 4.5 小结42-43
• 第5章 总结与展望43-44
• 参考文献44-47
• 致谢47-48
• 附录A：攻读硕士学位期间科研成果及参与的研究项目48-49
• 附录B：SIGMANEST排版与本文算法排版效果图49-54

【相似文献】

中国期刊全文数据库 前10条

1 陈小苹,乔谊正,戴汝为;一种用于手写速记连笔符切分的改进型启发式搜索算法[J];山东工业大学学报;1999年01期

2 徐雷;关于SA算法的几点看法[J];清华大学学报(自然科学版);1988年01期

3 曾岳,严新平,谭德荣;加快启发式实时算法的收敛[J];山东理工大学学报(自然科学版);2003年02期

4 唐朝舜,董玉德;八数码的启发式搜索算法及实现[J];安徽职业技术学院学报;2004年03期

5 金之滨;蒋志方;李玉忱;;基于感兴趣集的启发式搜索算法IA[J];山东工业大学学报;1993年01期

6 曾妮,李成刚,胡于进,黄嵩;虚拟制造组织中协作关系建模的研究[J];锻压装备与制造技术;2003年04期

7 王士同;模糊广义与或图的研究(Ⅲ)——并行模糊启发式搜索算法LIDFAO[J];华东船舶工业学院学报;1993年04期

8 王士同;模糊广义与或图的研究(Ⅰ)——模糊启发式搜索算法FAO~*′和FAO~*[J];镇江船舶学院学报;1992年04期

9 王士同;广义AND/OR图的自底向上启发式搜索算法BHAO~*[J];镇江船舶学院学报;1992年01期

10 王士同;并行启发式搜索算法PANO和PBHAO[J];镇江船舶学院学报;1993年01期

中国博士学位论文全文数据库 前1条

1 夏小云;随机启发式搜索算法的性能分析[D];华南理工大学;2015年

中国硕士学位论文全文数据库 前4条

1 王露;基于聚类和区域寻优的零部件排版启发式搜索算法研究[D];湘潭大学;2016年

2 周爱民;布局知识图矩形检测与加权圆集装填的启发式搜索算法研究[D];湘潭大学;2014年

3 陈宇;基于EOPN和启发式搜索算法的FMS仿真平台研究[D];南京航空航天大学;2004年

4 毕玉峰;公路施工网络图优化研究[D];长安大学;2001年

，

本文编号：540384