原文传递
复杂集装箱装载问题求解方法研究
| 论文题名： | 复杂集装箱装载问题求解方法研究 |
| 关键词： | 复杂集装箱装载;多约束条件;空间分解;启发式算法;混合遗传算法 |
| 摘要： | 集装箱装配货物是将具有一定体积、重量、价值、数量的不同种类货物合理地放置在一个具有一定体积和载重量限制要求的集装箱空间内的过程。装配方案必须满足定性和定量两方面的要求。在定性方面，主要考虑空间的合理利用，提高货运途中的安全系数等因素；在定量方面，主要考虑有限空间内的不同种类不同数量的货物价值最大化。这一类问题是多约束多目标的组合优化问题，称为复杂集装箱装载问题。许多看似简单的装配问题也往往是NP完全问题，即在有限时间内找不到问题最优解。 论文首先指出课题产生的时代背景，然后对装箱问题进行分类，阐述了本文的研究内容及其意义。接着重对装箱问题中的复杂三维集装箱装载问题进行分析，概述国内外研究现状，并指出现有成果的优点与缺点。从集装箱装载问题的变化形式、问题分类角度来考察各子问题在约束条件和目标函数方面的区别，从问题的启发式方法和进化算法角度研究现有解法的思路。 在此基础上，针对实际装载中每种类型货物数量一般较多、使用现有针对单个物品的基于三空间的启发式算法存在装载效率和空间利用率低的问题，采用同种类型货物一次性装载的思想，提出了一种新的基于六空间分解的启发式算法，将同类型货物一次性装载到待布空间，根据是否能够摆满分别采用“标准装载方式”和“非标准装载方式”来定位货物，给出了其定序规则、空间分割方法、约束条件处理方法和算法流程。 遗传算法作为一种模拟自然进化过程的随机性全局优化概率搜索算法，在求解优化问题中显示了优越的性能。鉴于目前遗传算法在装箱领域的成功经验，将其与本文提出的启发式算法相结合构造混合遗传算法，以保证获得全局最优解或次优解。 通过对实际装箱数据的算例分析和与单种货物数量较多的现有结果比较，表明本文算法处理复杂集装箱单箱装载问题是有效的，具有较高的空间利用率和计算效率。同时，通过与每种货物数量唯一的现有结果比较分析可见，算法虽是针对每种货物一次装载较多的情况设计的，但对于每种货物数量唯一且没有约束条件的情况，也具有较好的适用性。 根据本文提出的启发式算法和混合遗传算法，开发了电子配载系统。该软件具有能够满足实际集装箱装载中的多约束条件、安装使用灵活方便的优点，可真正用于物流企业的配载实践。论文介绍了系统功能和数据流程，并简要说明了操作过程。 论文最后对研究成果进行总结，分析了基于六空间分解的混合遗传算法及电子配载系统的成功与不足，并对今后系统的深入研究进行展望，指出未来的一些研究方向。 |
| 作者： | 胡瑞 |
| 专业： | 通信与信息系统 |
| 导师： | 丁香乾 |
| 授予学位： | 硕士 |
| 授予学位单位： | 中国海洋大学 |
| 学位年度： | 2006 |
| 正文语种： | 中文 |
检索历史
应用推荐
