1. 研究目的与意义
装箱问题（Bin-packing-problem， BPP）就是求解小物品装入大容器的整体布局方案，并且使之在某些约束条件下达到某种优化目标，如消耗的容器数量最少，或者装入的物品总价值最高。装箱问题研究对象包括一维、二维、三维和高维物体，广泛存在于工业生产，包括服装行业的面料肩擦、运输行业的集装箱货物装载、加工行业的板材型材下料、印刷行业额排样和现实生活中包装、整理物件等。尽管装箱问题在生活中有着多方面的广泛应用，但是装箱问题的求解是有很大的困难的，解决装箱问题的方法有精确算法和近似算法，近似算法的速度快但是精确度并不高，在需要解决精度高的问题上有一定的局限性；精确算法虽然精确度高，但是由于这种方法耗时耗力以及成本更高，所以很少能够运用到现实生活中来方便人们的生活。随着计算机科学、管理科学以及现代技术的发展，更加受到各个学科的重视，解决装箱问题的算法变得越来越重要。因此很有必要在现有的研究基础上，设计改进一个新算法，对装箱问题的启发式算法的时间以及空间维度进行优化，使其更加简单、准确、快速、高效，以此解决生活中的问题。
2. 研究内容和预期目标
研究内容：
各大学者对装箱问题的研究早已出现了大量的研究成果，甚至提出的某些算法对解决某些实际问题时可以达到1%的误差，然而存在局限性，并不是适用于任何的实例。相较于精确算法，本文旨在前人的基础之上提出更适合实际生活的一般费用函数的二维装箱问题的启发式算法，希望能够通过研究得出更合适的算法。
具体的内容如下：
3. 国内外研究现状
由于二维装箱问题的广泛应用，许多研究者对其进行了深入的研究，并提出了很多有效的算法。大致能够分成精确算法、启发式算法。
精确算法算法主要包括线性规划、分支界定和动态规划等算法。在面对规模较小的装箱问题时，可以通过线性规划等精确算大的到结果。Gilmore[1]用线性规划方法求得了最优解。Beasley[2]也通过树搜索法解决了二维装箱下料问题得到最优。但是，精确算法有一个缺点就是不能再合理的时间内对一些规模大的实例得出最好的结果。这时，就需要启发式算法来的得到可行的结果，尽管不是最优解。
启发式算法早期作为一种简单的启发式放置规则，学者们提出了BL ( bottom-left )，即最低最左对其算法，该方法首先根据装载物品的宽到窄进行排序，再将待装物品放置在其体积尽量低尽量左的位置。以及BLF ( bottom-left-fill)的放置方法用于多远求解算法的构建。在此基础上，不同的搜索方法，如退火算法[3]、遗传算法[4]和禁忌搜索算法[5]等也被引入装箱问题的求解中。梁星星[6]等将退火算法应用到同样为NP-hard问题的多旅行商问题，田大肥[7]等把遗传算法运用到箱柜装载问题。但是，启发式算法和智能搜索方法解决单一规格物体二维装箱问题时间有时过长，针对这一问题，胡锦超、贾春玉[8]提出新的解法和思路，用线性规划分别在两个维度求出最优解，一最好的方案为近似最优解，这种方法缩短了解决时间也得到来最满意的近似解。
4. 计划与进度安排
2022.12.1-2022.12.12：决定论文主题方向；
2022.12.13-2022.12.31：以论文主题为中心，搜集相关资料；
2022.1.1-2022.1.10：整理搜集的相关资料，论证分析论文的可行性、实际性，确定论文的大致范围，进行开题报告；
5. 参考文献
[1]P. C. Gilmore, R. E. Gomory. A Linear Programming Approach to the Cutting Stock Problem—Part II. 1963, 11(6)
[2]Beasley J.E.. An algorithm for the two-dimensional assortment problem. 1985, 19(2):253-261.
[3]胡智莹,周翔,李建伶,刘峻良.基于混合模拟退火算法的多约束装箱问题研究[J].无线互联科技,2019,16(23):113-114.
以上是毕业论文开题报告，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
