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

1.1目的及意义

装箱问题也叫做背包问题，简单来说，就是把小货物往大箱子里装，要如何才能装得多。比如我们日常生活中最常见的“装冰箱”问题，很有趣的现象就是，我们常常感觉冰箱再也装不下了，但是经过一翻折腾之后又神奇的装下了，在有限的容积下放入了更多的东西，充分地利用了冰箱空间。装箱问题通常可以用大物体和小物品的儿何组合来描述：大物体定义为空的，需要被小物品填充．它最关注的是在装箱过程中通过改善物品的布置方式，达到获得最大利益的目的[3]。

装箱问题广泛存在于工业生产,包括服装行业的面料裁剪、运输行业的集装箱货物装载、加工行业的板材型材下料、印刷行业的排样和现实生活中包装、整理物件等。在计算机科学中,多处理器任务调度、资源分配、文件分配、内存管理等底层操作均是装箱问题的实际应用,甚至还出现在一些棋盘形、方块形的数学智力游戏中。装箱问题的研究文献分布面很广,在运筹学、计算机辅助设计、计算机图形学、人工智能、图像处理、大规模集成电路逻辑布线设计、计算机应用科学等诸多领域都有装箱问题最新的研究动态和成果出现,从这个角度来讲,布局问题涉及到了工业生产的方方面面,也足以证明了装箱问题的应用前景日趋广泛而重要。

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

2.1研究内容

除其次适配（next fit, nf）算法，首次适配（first fit, ff）算法，最佳适配（best fit. bf）算法，最坏适配(worst fit, wf）算法等研究思路以外，蚁群算法也是一种非常经典的优化算法[5]。基于蚁群算法的优化方案也被广泛应用，而且优化效果常常优于其他解决方法[7][11][12]。比如说与一维装箱问题比较类似的一维下料问题，建立在蚁群算法的基础之上，相比较于其他的方法而言，可以得到更加优化的模型和更令人满意的仿真结果，进一步减少了材料的浪费和节省了成本[8][15]。因此，可以作为一个参考，将蚁群分析法融入到一维装箱问题的解决中来，寻求更加优化的装箱方案[9]。

因此，本文的主要内容就是基于蚁群分析法的一维装箱问题的解决[10]。查阅蚁群算法和一维装箱的相关资料，通过matlab建立一维装箱问题的数学模型，结合蚁群算法对数学模型进行求解，并且进行仿真实验[1][2][7]。采取多组经典算例进行实验验证，并对实验结果进行分析。之后，结合一维装箱问题的经典解决思路进行分析对比，总结出蚁群算法的特点及优势，得出结论。

3. 研究计划与安排

1、2018年2月26日~2018年3月18日，完成文献查阅、文献翻译和开题报告；

2、2018年3月19日~2018年4月1日，学习掌握matlab软件。如果已经对matlab有较好的学习基础，可以直接进入下一环节；

3、2018年4月2日~2018年5月20日，实现针对一维装箱问题的蚁群算法，并进行仿真验证；

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

[1]scholl a, klein r, jürgens c. bison: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem. computers amp; operations research,1997;24:627–645

[2]fleszar k, hindi k. new heuristics for one-dimensional bin-packing. computers amp; operations research, 2002;29:821–839

[3]falkenauer e. a hybrid grouping genetic algorithm for bin packing. journal of heuristics, 1996, 2: 5–30