1. 研究目的与意义
由于装箱问题既具有理论价值又具有实际意义，在日常的生产工作中有着广泛的应用，极大地提高了生产效率。装箱问题是一个经典的NP完全问题，有着较高的研究价值。
目前解决装箱问题的算法可以大略分为近似算法和精确算法。近似算法虽然计算速度很快，但计算结果精确度不高，在解决高精度要求的装箱问题中表现一般；而精确算法相较于近似算法，计算结果精确度有所保障，但是耗时较长，成本很高。因此，在实际生产活动中，往往采用近似算法解决相关问题，在花费较少成本的同时，得到较为精确的结果。
装箱问题是理论计算机科学和组合优化领域的一个重要问题，如今，随着计算机科学、管理科学和现代化生产技术的不断发展，组合优化需要得到更多的解决和应用，愈来愈受到运筹学、应用数学、计算机科学和管理科学等诸多学科的重视。装箱问题作为经典的组合优化问题，在近几十年来得到了广泛而又深入的研究，也得到了一些较好的结果，对实际活动有着很好的指导意义。
2. 研究内容和预期目标
考虑一般收费结构的一维装箱问题的启发式算法的定义
一维装箱问题通常是用物品的重量或大小来刻画的，可以用以下数学语言描述：给定n个物品集合L={a1,…,an},假设每个物品ai(1≤i≤n)的重量或大小为w(ai) ∈（0，1]，B1,B2,…是无数个单位箱子，并且要求每个物品ai只能放到一个箱子里，约束条件是每个箱子里的数字和不能超过1，则目标是最小化所用箱子个数，则0-1整数线性规划描述为：
minz=，
3. 国内外研究现状
装箱问题（Bin Packing Problem）是研究最早、应用最广的NP完全问题之一，所谓NP完全问题，即无法在多项式时间内找到最优解的问题。
从20世纪70年代初开始，装箱问题就引起了当时的广泛探讨和研究。虽然经过了近几十年来的不断研究深入，但该问题迄今为止尚未形成成熟的理论和有效的数值计算方法，仍然有着许多值得研究的未知领域。
由于目前NP完全问题不存在有效时间内求得精确解的算法，这使得装箱问题的求解变得极为困难，因此，从70-80年代开始，专家学者陆续提出的装箱算法都是近似算法，比较著名的有下次适应算法（NextFit Algorithm）、首次适应算法（First FitAlgorithm）、最佳适应算法（BestFit Algorithm）、递减首次适应算法（First Fit Decreasing Algorithm）递减最佳适应算法（First Best Decreasing Algorithm）等等。
4. 计划与进度安排
本文从启发式算法入手，首先基于贪心策略构造初始解，并根据问题的特性基于初始解和交换算子进行设计局部搜索算法，最后进行数值实验和敏感性分析。
本文结构如下：第一章介绍研究对象的现状与问题，综述相关问题的研究与应用现状；第二章具体描述一维装箱问题的研究内容，分析问题特性，根据研究内容与问题特性，指出研究与应用价值；第三章分析了近似算法的应用现状并建立于贪婪技术的近似算法；第四章设计实验数据，根据问题特性给出算法的评价指标，比较算法并进行关键参数的敏感性分析；第五章总结了主要结论并指出研究的不足之处。
一、研究背景与意义
5. 参考文献
[1]程会兵. 考虑时间窗约束的装箱问题研究[D].江西财经大学,2019.
[2]刘明明,童小娇,戴彧虹.装箱问题的算法及最新进展[J].计算数学,2016,38(03):257-280.
[3]罗飞,任强,丁炜超,卢海峰.基于最小松弛量的启发式一维装箱算法[J].计算机科学,2019,46(09):315-320.
以上是毕业论文开题报告，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
