集装箱单箱三维装载优化研究——一种基于改进的最小浪费算法的解决方案

摘要

集装箱装配货物是将具有一定体积、重量、价值、数量的不同种类货物合理地放置在一个具有一定体积和载重量限制要求的集装箱空间内的过程。装配方案必须满足定性和定量两方面的要求。在定性方面,主要考虑空间的合理利用,提高货运途中的安全系数等因素；在定量方面,主要考虑有限空间内的不同种类不同数量的货物价值最大化。这一类问题是多约束多目标的组合优化问题,称为复杂集装箱装载问题。许多看似简单的装配问题也往往是NP完全问题,即在有限时间内找不到问题最优解。
　　 论文首先指出课题产生的时代背景,然后对装箱问题进行分类,阐述了本文的研究内容及其意义。接着着重对装箱问题中的复杂三维集装箱装载问题进行分析,概述国内外研究现状,并指出现有成果的优点与缺点。从集装箱装载问题的变化形式、问题分类角度来考察各子问题在约束条件和目标函数方面的区别,从问题的启发式方法和进化算法角度研究现有解法的思路。
　　 在此基础上,针对实际装载中每种类型货物数量一般较多、使用现有针对单个物品的基于三维空间的启发式算法存在装载效率和空间利用率低的问题,采用同客户货物一次性装载的思想,提出了一种新的基于最小浪费原则的启发式算法并给出了其定序规则、约束条件处理方法和算法流程。
　　 局部搜索算法作为一种随机性搜索算法是求解优化问题中一种常用的算法。本文将其与改进的最小浪费算法相结合以保证获得全局最优解或次优解。通过对实际装箱数据的算例分析和与单种货物数量较多的现有结果比较,表明本文算法处理复杂集装箱单箱装载问题是有效的,具有较高的空间利用率和计算效率。

目录

文摘

英文文摘

图目录

表目录

第一章 绪论

1.1 课题背景

1.2 本文的主要研究工作

1.3本章小结

第二章 集装箱问题综述

2.1 集装箱装载问题

2.1.1 集装箱问题的分类

2.1.2 集装箱问题的一般模型

2.2 启发式算法

2.2.1 启发式算法分类

2.2.2 启发式算法在集装箱问题中的应用

2.3 元启发式算法

2.3.1 元启发式算法分类

2.3.2 元启发式算法在集装箱问题中的应用

2.4 精确算法

2.4.1 精确算法分类

2.4.2 精确算法在集装箱问题中的应用

2.5 本章小结

第三章 改进的最小浪费算法

3.1 算法总体结构

3.2 上下界算法

3.2.1 下界函数:

3.2.2 上界算法:

3.3 改进的最小浪费算法

3.3.1 寸货物盒子的选择

3.3.2 对可装载点的搜索

3.3.3 对装载规则的设计

3.4 外层局部搜索算法

3.5 本章小结

第四章 算法应用与算例测试

4.1 具有先进后出原则的单集装箱装载问题

4.2 算例分析

4.3 本章小结

第五章 结语与展望

参考文献

致谢