基于蚁群算法的矩形件优化排样问题研究

论文摘要

计算机辅助排样,又称为CAN(Computer Aided Nesting),是广泛应用的计算机辅助技术之一,用于指导各行业处理各种下料问题,以达到节约材料、降低产品成本的目的。下料问题存在于国民经济的许多行业中,其中二维下料应用广泛,而矩形件下料是二维下料的基础,因此,对矩形件的优化下料进行研究是一个具有重大意义的课题。所谓的矩形件下料问题是利用矩形原材料,寻找最优的排样布局下料出所需的全部矩形毛坯,使得原材料的浪费最少的问题。矩形件排样问题按原材料的不同分为两种:原材料矩形板材具有确定的尺寸,需要用最少的板材下料出所需的矩形毛坯的装箱问题(Rectangular Bin Packing Problem)和原材料板材只有确定的宽度而长度无限,需要用最短的板材下料出所需矩形毛坯的矩形件带排样问题(Rectangular Strip Packing Problem)。国内外学者对该问题进行了深入和广泛的研究,并提出了很多算法,如:线性规划方法、遗传算法、模拟退火算法等。近年来,由于蚁群算法的正反馈并行自催化机制,和具有较强的鲁棒性等优点,使其逐渐成为一种应用广泛的元启发式算法。本文针对矩形件排样中的带排样问题这个NP难问题,提出采用蚁群算法进行求解。主要研究包括以下内容:⑴针对该问题提出一种新的排样方案生成算法—基于长度方向最小浪费准则法。该方法可以有效的提高该类问题的利用率。⑵建立该问题的蚁群算法求解模型,给出合适的构建图定义,信息素和启发式信息以及路径构建和信息素更新规则,设计出合适的算法流程。⑶分析蚁群算法中不同的参数取值对问题求解的影响,得出合适的参数来求解该问题。⑷在采用蚁群算法对矩形件带排样问题的处理基础上,对算法进行补充,使其能够处理矩形件装箱问题。⑸最后,设计开发矩形件下料系统。通过对大量的实验进行测试,并将实验结果与其它中文文献以及商业软件的计算结果进行比较和分析,结果表明,本文算法具有较高的材料利用率。因此,本文所提的矩形件下料算法是一种有效的算法。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 排样问题
• 1.1.1 排样问题的整体描述
• 1.1.2 排样问题的分类
• 1.2 排样问题的研究背景和意义
• 1.2.1 排样问题的应用
• 1.2.2 计算机辅助排样的意义
• 1.3 矩形件下料问题研究现状
• 1.3.1 矩形件排样问题的分类
• 1.3.2 矩形件优化排样技术的研究现状
• 1.4 排样技术存在的问题和发展趋势
• 1.5 本文的主要研究内容
• 1.6 论文研究特色及创新点
• 2 蚁群优化
• 2.1 ACO 算法原理分析
• 2.2 ACO 算法数学描述
• 2.3 ACO 算法流程
• 2.4 ACO 算法特点与优势
• 2.5 ACO 算法在排样问题中的应用
• 2.6 本章小结
• 3 矩形件带排样问题的蚁群算法求解
• 3.1 问题的描述
• 3.2 剪切下料矩形件排样问题的排布算法
• 3.2.1 分层排布（level-packing）算法
• 3.2.2 本文提出的一种新的排布算法—基于长度方向最小浪费准则法
• 3.3 蚁群算法求解
• 3.3.1 矩形件排样问题的蚁群算法模型建立
• 3.3.2 参数选择
• 3.3.3 算法设计
• 3.4 运行实例
• 3.4.1 同公开文献中实例比较
• 3.4.2 同商业排样软件比较
• 3.5 本章小结
• 4 本文算法在其它矩形件排样问题上的应用
• 4.1 矩形件装箱问题中的应用
• 4.1.1 算法修改
• 4.1.2 运行实例
• 4.2 本章小结
• 5 优化排样系统的设计与实现
• 5.1 优化排样系统的总体设计
• 5.1.1 基本功能规划
• 5.1.2 排样系统模块结构
• 5.2 优化排样系统的实现途径
• 5.3 优化排样系统的用户界面设计
• 5.4 优化排样系统的操作步骤
• 5.5 本章小结
• 总结与展望
• 结论
• 展望
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录