集装箱单箱三维装载优化研究

论文摘要

集装箱装载问题是货物运输过程中普遍存在的一个重要环节,一个合理的装箱方案可以提高集装箱的空间利用率,降低运输成本,从而带来巨大的经济效益。从理论角度来看,集装箱装载问题属于NP（Non—deterministic Polynomial,NP）完全问题,确定最优解非常困难。因此,寻找一个有效的解决集装箱装载问题的算法对于解决集装箱装载的实际问题以及求解NP完全问题都具有非常重要的意义。本文首先对集装箱装载问题进行了简单的介绍,然后对解决该类问题的启发式算法和遗传算法进行了详细地分析和比较,提出了一种基于空间分解的启发式方法和遗传算法相结合的混合遗传算法。该算法首先利用启发式规则产生问题的初始解群,然后采用三空间分解法对剩余空间进行分解,采用空间合并原则将闲置空间与可用空间进行合并以达到充分利用,并根据待装货物种类和数量的不同采用了不同的装载顺序,最后对遗传算法的相关参数进行了分析比较,找出适合该类问题的最佳参数取值,并对交叉操作和变异操作进行了相应的改进。文章最后应用VC++的界面设计功能和OpenGL三维图形技术开发了一个简单的装箱系统,能够生成装箱方案,供实际装箱操作中参考。本文采用混合遗传算法主要解决的是弱异类货物的装箱问题,对强异类和具有特殊约束条件的装箱问题也进行了简单的研究和探讨。通过对算例的分析比较,该算法在求解集装箱装载问题时表现出良好的性能,最终的装载结果与以前文献中记载的相比都有了很大的提高,所以应用本文设计的混合遗传算法求解集装箱单箱三维装载优化问题是非常可行的。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景
• 1.2 集装箱装载问题
• 1.2.1 装箱问题简介
• 1.2.2 集装箱装载问题及其研究现状
• 1.2.3 集装箱装载问题的一般数学模型
• 1.3 本文的主要研究工作
• 第二章 集装箱三维装载优化算法综述
• 2.1 启发式算法
• 2.1.1 启发式算法的定义与发展
• 2.1.2 启发式算法的分类
• 2.1.3 启发式算法在集装箱装载问题中的应用
• 2.2 遗传算法
• 2.2.1 遗传算法简介
• 2.2.2 基本遗传算法
• 2.2.3 遗传算法的基本实现技术
• 2.2.4 遗传算法改进方式
• 2.2.5 遗传算法在集装箱装载问题中的应用
• 2.3 其他优化装箱算法介绍
• 2.4 本文算法的研究思路
• 2.5 本章小结
• 第三章 应用混合遗传算法求解不同规格货物的三维装箱问题
• 3.1 基于混合遗传算法的弱异类货物装箱问题求解
• 3.1.1 问题描述和数学建模
• 3.1.2 启发式规则
• 3.1.2.1 定序规则
• 3.1.2.2 定位规则
• 3.1.2.3 剩余空间划分策略
• 3.1.2.4 空间合并原则
• 3.1.3 遗传算法的基本思路
• 3.1.3.1 编码预处理
• 3.1.3.2 个体编码及解码
• 3.1.3.3 适应度函数
• 3.1.3.4 遗传操作
• 3.1.3.5 终止准则
• 3.1.4 算例分析及比较
• 3.2 基于混合遗传算法的强异类货物装箱问题求解
• 3.2.1 建立强异类装箱问题的数学模型
• 3.2.2 算法的改进思路
• 3.2.2.1 剩余空间划分策略
• 3.2.2.2 遗传操作的改进
• 3.2.3 算例分析及比较
• 3.3 影响算法性能的因素
• 3.4 本章小结
• 第四章 具有特殊约束条件的装箱问题求解
• 4.1 问题描述
• 4.2 目标函数及约束条件
• 4.3 个体编码及解码
• 4.4 适应值的计算
• 4.5 遗传操作
• 4.6 算例分析
• 4.7 本章小结
• 第五章 制作简单的装箱系统
• 5.1 用户界面设计
• 5.1.1 输入界面
• 5.1.2 输出界面
• 5.2 应用OpenGL绘制三维装箱图
• 5.3 实例演示装箱系统操作过程
• 5.4 本章小结
• 第六章 结论与展望
• 6.1 结论
• 6.2 展望
• 附录 Loh&Nee算法的测试数据
• 参考文献
• 致谢
• 攻读硕士学位期间发表的学术论文
• 学位论文评阅及答辩情况表