原文传递
基于禁忌搜索算法的集装箱装载问题研究
| 论文题名： | 基于禁忌搜索算法的集装箱装载问题研究 |
| 关键词： | 集装箱装载;禁忌搜索;布局优化;NP完全问题;启发式算法 |
| 摘要： | 集装箱装载问题(Container Loading Problem，简称CLP)属于“切割和装入”问题，在数学理论上为NP完全问题，即不能在多项式时间内找到问题的最优解。CLP虽然求解困难，但随着计算机技术的发展，使用计算机辅助求解CLP成为可能，但因CLP本身特征，实际应用中无法采用纯数学方法，而是采用基于启发式的近似求解方法。 计算机辅助布局优化能够有效提高空间装载效率，在铁路和远洋运输中能够降低运输成本，研究成果还可以推广到计算机内存分配等空间资源优化领域，因此有着重要的实际意义。近年来CLP逐渐成为人们关注的焦点。 本文绪论先对CLP的产生背景及实际意义进行论述，然后对其研究范畴和分类予以介绍，最后在查阅大量文献的基础上阐明了CLP的国内外发展现状。 禁忌搜索算法(Tabu Search，简称TS)是近年来逐渐引起人们兴趣的一种现代启发式算法，因其特殊的“记忆”机制，表现出极好的全局寻优能力，在对一些复杂、困难问题的求解中取得了很好效果。本文从TS的原理、搜索技术以及收敛理论等方面进行说明。 应用TS求解CLP在国内还没有相关研究，本文结合CLP的实际特征，提出了不同于Bortfeldt和Gehring方法的新的编码、解码及邻域解构造方法；在解码中引入了新的空间合并策略，提高了集装箱利用率；应用“组合块”思想减少了剩余空间的零碎划分，降低了搜索代价；本文创造性的将TS应用于求解多箱装载问题，取得了理想效果。 结果显示对于集装箱装载系统的应用有重要意义，本文给出了数据显示和图形显示两种方式。数据显示精确描述装载方案中物体顺序、位置等信息；图形显示提供了装载方案的可视化效果，更便于用户观察。 实例分析部分通过对4个标准数据集进行测试，证明了用TS求解CLP的有效性和实用性，同时讨论了算法中存在的优点与不足。 最后对全文工作进行总结并对以后的研究方向进行了展望。 |
| 作者： | 董宗然 |
| 专业： | 计算机应用技术 |
| 导师： | 刘嘉敏 |
| 授予学位： | 硕士 |
| 授予学位单位： | 沈阳工业大学 |
| 学位年度： | 2007 |
| 正文语种： | 中文 |
检索历史
应用推荐
