基于蚁群算法的二维下料问题求解开题报告

1. 研究目的与意义（文献综述）

1.1.研究背景及意义

一般来讲，二维下料问题（two-dimensionalcuttingstockproblem）是指，将相同尺寸的矩形原材料板通过剪裁加工成一系列给定长宽的矩形件，目的是使原材料的消耗最少[1]。根据np-completeness理论，二维下料问题属于具有高度复杂性的np完全问题[2]，具有最高复杂性，即使是使用高速计算机也不可能在短时间内求出最优解[3]。并且二维下料问题普遍存在于各个行业中，在船舶主要是将船舶设计图进行分解，将内部板件和外板从设计图中提取出来，从而进一步进行下料生产[4]。因此对该问题的研究具有重要的理论意义和实际应用价值。

1.2国内外研究现状

2. 研究的基本内容与方案

2.1.研究的基本内容及目标：

（1）针对二维下料问题，采用基于长度方向最小浪费与最大空间利用率准则，该准则可以大大提高板材的空间利用率，并保证算法运行速度。

（2）以基于食物量的多种群蚁群算法为模板，通过空间二叉树，提出双信息素模型，并保留算法的顺序学习功能，取消算法的矩形件旋转方向学习功能，测试每个矩形件的两个旋转方向，以选出可以使局部空间利用率最高的矩形件方向。通过改变算法参数：蚂蚁数量m、启发式信息中分别代表面积的影响因子p和浪费的影响因子q、信息素和启发式信息的影响因子α和β、信息素挥发率ρ和初始信息素τ0，分析不同参数下的算法性能，进而得出最适宜当前问题的算法参数。同公开的文献中的实例和商业软件中的不同规模实例相比较，得出该算法的有效性。

3. 研究计划与安排

第1-3周：收集文献和相关资料进行毕业设计调查，完成开题报告与英文翻译；

第4周：熟悉并掌握matlab、autocad等软件在本次研究中需要的操作；

第5-6周：掌握蚁群算法在matlab环境下的基本程序结构，理解蚁群算法对旅行商问题和集装箱问题的matlab程序；

4. 参考文献（12篇以上）

[1]cui y, yang l, zhao z, et al. sequential grouping heuristic for the two-dimensional cutting stock problem with pattern reduction[j]. international journal of production economics, 2013, 144(2):432-439.

[2]gareymr,johnsonds.computersandintractability:aguidetothetheoryofnp-completenes[c]//w.h.freemanandcompany.1979.

[3]曹炬,周济,余俊.矩形件排样优化的背包算法[j].中国机械工程,1994(2):11-12.