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

装箱问题即将一组具有不同尺寸的物品打包成最小数量的大小相同的箱子,使得每个箱子中的物品大小之和不超过箱子的容量并且使得所用的箱子数目最少，以获得某种最佳、最理想的经济效益,因此提出了一种解决一维装箱问题的启发式算法。装箱问题广泛的应用于交通运输和工业生产等行业当中，对于这种问题的求解方法的研究无论是在理论上还是在实践中都具有很高的价值。一方面，装箱问题属于一种组合最优化问题,而所谓组合优化，是指在离散的、有限的数学结构上，寻找一个满足给定条件，并且使其目标函数值达到最大或最小的解。一般来说，组合优化问题通常含有大量的局部极值点,往往是不连续，不可微的，有约束条件的，高度非线性的np完全问题，各种尺寸的物品必须在固定容量的箱子内进行分组，并且不可能有一个多项式算法来最优地解决这个问题，为此开发了一种分支定界算法。因此具有很高的理论价值；另一方面，一维装箱问题出现在实际生产的一些领域，因此也具有很高的实际价值。

基本粒子群优化算法最先由eberhart博士和kennedy博士提出，它是一种基于具有群体的具有全局寻优能力的优化工具，它需要确定的参数并不多，操作较为简单，但是容易陷入局部极值点，搜索精度不高。对于装箱问题，还提出了一个混合改进启发式算法，它的特点是通过参考最小最大问题来生成初始解，对于非常广泛的基础实例已经获得了令人鼓舞的结果，说明了算法的稳健性。尼尼奥（ninio）和施耐德（schneider）通过提出一种基于加权退火（wa）的算法，使得bpp得到简单而快速的解决，它关键的思想是改变问题格局并且能利用每一次优化运行的历史记录，虽然wa技术对于tsp实例通常会比sa技术得到更好的结果，但是在sk实例中，wa算法且无法超越sa算法；20世纪70年代初开始，装箱问题就引起了广泛的探讨和研究，然而该问题可以追溯到1831年高斯开始研究的局部问题，虽然历经几百年的努力探索，但是仍然没有较为成熟的理论以及行之有效的计算方法进行支撑；由于关于装箱问题的解答非常困难，因此自20世纪70-80年代就陆续出现下次适应、首次适应、最佳适应，降序首次适应、降序最佳适应等算法，1983 年,s. kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于monte-carlo迭代求解策略的一种随机寻优算法，该算法是一种随机算法，并不一定能找到全局的最优解，但是可以较快地找到问题的近似最优解，而且假设初始参数设置得当，模拟退火算法比穷举法的搜索效率要高。模拟退火算法是按自然法则计算较新的一个分支，符合自然科学及其分支相互影响、相互渗透的基本规律。

我国黄文奇教授提出用于解决np难度问题的拟人拟物的近似算法，其途经是到物理世界中去寻找与原始数学问题等价的自然现象，然后观察其中物质运动的演化规律，从中受到启发以得出形式化的，对于数学问题的求解算法。单纯的拟物方法就已经能够解决许多问题，当遇到难度高的问题时还能将拟物和拟人算法相结合起来，其中的占角和洞穴度的思想十分精妙，但是拟人退火算法并不能保证找到全局最优解，不容易从局部的陷进中跳出来；崔耀东等人提出了一种新的递归分支定界算法，这种算法是在基于递归分治上而得出来的，但是它也只能在某一些问题的处理上才取得了不错的结果。

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

1、建立一维装箱问题的数学模型，借助matlab，基于模拟退火算法对该模型进行求解。

2、完成相关的仿真实验，通过多个算例对对第1点中实现的算法进行仿真验证和分析。

3. 研究计划与安排

1）第1周~第3周，完成文献查阅、文献翻译和开题报告；

2) 第4周~第5周，学习掌握matlab软件。如果已经对matlab有较好的学习基础，或者可以熟练应用其它编程语言如c、c 、java等，可以直接进入下一环节；

3) 第6周~第12周，实现针对一维装箱问题的模拟退火算法，并进行仿真验证；

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]schwerin p, wascher g. the bin-packing problem: a problem generator and some numerical experiments with ffd packing and mtp. international transactions in operational research, 1997, 4: 377–389

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