求解三维装箱问题的遗传算法研究【开题报告】.doc

毕业设计开题报告 计算机科学与技术 求解三维装箱问题的遗传算法研究 一、选题的背景与意义 装箱问题是物流企业在装卸环节上必须面对的一个核心问题，通常其装载的规模达到上千，而且非常频繁。如果能设计出一个有效的装载方案，提高装载的空间利用率，势必会给物流企业带来相当可观的利润。因此，研究出能够有效求解三维装箱问题的遗传算法，对物流企业来说，显得尤为重要。 三维装箱问题属于NP问题，传统算法耗时极大不能满足实际应用的需求，所以目前学者都转向启发式搜索算法研究，尤其是遗传算法，但在国内还没有出现在效率和精度上都十分优秀的求解三维装箱问题的遗传算法。 通过对国内外现有的求解三维装箱问题的遗传算法的考察，本课题的目的是设计出一种能够满足实际应用需求的求解三维装箱问题的遗传算法，其中，如何进一步提高求解三维装箱问题的遗传算法的求解速度，是本课题需要解决的重点问题之一。 二、研究的基本内容与拟解决的主要问题 研究的基本内容： 1. 完成求解三维装箱问题的遗传算法的设计，包括适应度函数、遗传算子等； 2. 画出求解三维装箱问题的遗传算法的流程图； 3. 按流程图编码、调试； 4. 完成求解三维装箱问题的遗传算法的程序编码、文献综述、外文翻译、等工作。 拟解决的主要问题： 适应度函数和遗传算子的设计； 提高遗传算法求解速度的方法和途径； 如何提高求解三维装箱问题的遗传算法的精度。 三、研究的方法与技术路线 研究方法： 通过收集和查阅各种文献和资料，学习求解三维装箱问题的遗传算法的原理、方法和应用，掌握目前求解三维装箱问题的遗传算法的研究和应用动态，了解求解三维装箱问题的遗传算法中存在的各种问题。学习和掌握求解三维装箱问题的遗传算法的设计理论和方法，通过比较和分析，提出求解三维装箱问题的遗传算法的设计和改进方案，确定求解三维装箱问题的遗传算法设计过程需要注意的各个方面问题。根据求解三维装箱问题的遗传算法的设计理论和方法，确定求解三维装箱问题的遗传算法的流程图。结合国内外文献，提出改进求解精度的方案，分析装箱的实现效率。最终完成求解三维装箱问题的遗传算法的设计工作。 技术路线： 文献检索和阅读－－掌握求解三维装箱问题的遗传算法的设计方法－－求解三维装箱问题的遗传算法的设计－－求解三维装箱问题的遗传算法的编码－－求解三维装箱问题的遗传算法的调试与修改－－撰写使用说明书－－答辩。 四、研究的总体安排与进度 第1-3周（2010.11.27-2010.12.19）：收集资料，完成文献综述 第4周（2010.12.20-2010.12.26）：完成开题报告，完成开题答辩。 第5-8周（2010.12.27-2011.1.16）：参考国内外文献，设计求解三维装箱问题的遗传算法。 第9-12周（2011.02.17-2011.03.13）：求解三维装箱问题的初步编码、调试。 第13-18周（2011.03.14-2011.04.24）：完成求解三维装箱问题的完整编码，撰写毕业论文。期间还将组织毕业设计的中期检查，执行“毕业设计（论文）中期黄牌警告制度”。 第19-21周（2011.04.25-2011.05.15）：毕业设计资料整理，提交完整的毕业设计（论文）资料。 第22-23周（2011.05.16-2011.05.27）：毕业设计（论文）答辩准备、答辩、毕业设计成绩评定。 五、主要参考文献 [1] 钟石泉, 王雪莲. 多箱型三维装箱问题及其优化研究[J]. 计算机工程与应用，2009, 45（22）：197~199 [2] 周明，孙树栋. 遗传算法原理及应用[M]. 北京：国防工业出版社，2000 [3] 方平, 李娟. 求解装箱问题的遗传算法[J]. 南昌航空工业学院学报, 1998, 2（2）：21~24 [4] 王长春，李锐，孙友. 基于遗传算法的军用集装箱装载优化[J]. 物流科技，2007，5 [5] H Gehring,K Menschner,M Meyer.A computer-based heuristic for packing pooled shipment containers.Europe Journal of Operational Research.1990,44: 277-288 [6] Johnson,D.S.Near-Optimal bin packing algorithms.Technical Report,MAC TR-109(1973),Project MAC,MIT,Cambridge,Mass [7]Yang Chuan-min,Chen Shao-wei.Discontinuous optimization on the containerization of cubic.Package Engine