WEB模式下三维装箱问题求解方法研究

论文摘要

集装箱装配货物方案是将具有一定体积、重量、价值、数量的不同种类不同数量的货物合理地放置在一个具有一定体积和载重量限制要求的集装箱空间内的过程,装箱问题广泛存在于工业领域,在实际应用中,装箱问题的解决效果影响最直接和显著的领域是物流运输业。随着我国市场经济的发展,物流活动越来越显示出它的重要性,装箱问题作为物流配送过程中的一个关键性技术,对提高配送业务的自动化水平、提高货物装载的优化程度、提高配送业务的工作效率和规范业务流程都有重要的意义。实际求解中,看似简单的装配问题也往往是NP完全问题,即在有限时间内找不到问题最优解。论文首先指出课题产生的时代背景,然后对装箱问题的研究现状进行了分析,阐述了本文的研究内容及其意义。接着着重对三维装箱问题的实际需求进行了分析,指出WEB模式的装载是解决实际问题的必然发展趋势,接着对三维装箱问题的常用算法进行分析,从问题的启发式方法和进化算法角度研究现有解法的思路,并指出其针对WEB模式下装载的优点与缺点。在此基础上,针对实际装载中单种类型货物数量一般较多、使用现有启发式算法空间利用率较低和在WEB模式下使用以遗传算法为代表的进化算法存在装载速度较慢的问题,从优化搜索策略方面入手,引入免疫克隆选择算法(ICSA),利用克隆扩增、克隆选择算子完成种群进化,并结合基于六空间分解的启发式策略对ICSA算法加以改进,使两者相辅相成,构造了混合克隆选择算法求解WEB模式下的三维装载问题。免疫克隆选择算法作为模仿自然免疫系统功能的一种智能方法,具有记忆和自我调节的特性,在求解优化问题中显示了优越的性能。鉴于目前免疫克隆选择算法在图像处理、组合优化、控制和故障诊断等领域的成功经验,将其与六空间启发式算法相结合构造混合克隆选择算法,以保证快速获得全局最优解解。通过对实际装箱数据的算例分析和与每种货物数量较多的现有结果比较,表明本文算法处理复杂集装箱单箱装载问题是有效的,具有较高的空间利用率和计算效率。根据本文提出的混合克隆选择算法,开发了电子配载系统。该软件具有能够满足实际集装箱装载中的多约束条件、升级和使用灵活方便的优点,可真正用于物流企业的配载实践。论文介绍了系统功能和数据流程,并简要说明了操作过程。论文最后对研究成果进行总结,分析了混合克隆选择算法及电子配载系统的成功与不足,并对今后系统的深入研究进行展望,指出未来的一些研究方向。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 问题产生的时代背景
• 1.2 装箱问题的研究现状
• 1.2.1 装箱问题的分类
• 1.2.2 装箱问题的国内外研究方法
• 1.2.3 小结
• 1.3 本文研究的主要内容
• 2 WEB 模式下三维装箱问题求解方法分析
• 2.1 WEB 模式下的装箱问题
• 2.1.1 问题的分类
• 2.1.2 问题描述
• 2.2 问题的启发式算法分析
• 2.3 问题的遗传算法分析
• 2.3.1 标准遗传算法
• 2.3.2 改进的遗传算法
• 2.3.3 混合遗传算法分析
• 2.4 其它进化方法
• 2.5 小结
• 3 WEB 模式下三维装箱问题的混合克隆选择算法
• 3.1 免疫克隆选择算法概述
• 3.1.1 免疫克隆选择算法的起源
• 3.1.2 免疫克隆选择算法的基本原理
• 3.1.3 免疫克隆选择算法的工作机理
• 3.1.4 免疫克隆选择算法的特点
• 3.2 基于六空间分解的启发式算法
• 3.2.1 装载摆放方式
• 3.2.2 空间划分
• 3.2.3 空间合并
• 3.2.4 基于空间划分的启发式算法流程
• 3.3 算法的比较
• 3.4 装箱问题的混合克隆选择算法设计
• 3.4.1 抗体的编码方法
• 3.4.2 初始种群与亲和度函数
• 3.4.3 克隆算子
• 3.4.4 变异算子
• 3.4.5 选择算子
• 3.4.6 混合克隆选择算法流程
• 4 算法性能分析
• 4.1 算法实现
• 4.2 算例分析
• 4.2.1 容积利用率比较
• 4.2.2 时间性能比较
• 4.3 课题取得的成果
• 5 电子配载系统
• 5.1 系统功能
• 5.2 系统操作演示
• 6 结论与展望
• 参考文献
• 致谢
• 个人简历