多约束有色三维装箱问题的混合遗传算法研究

摘要

三维装箱问题研究历史悠久，是一个典型的NP完全难题，广泛存在于生产生活的各个角落，对国民经济的影响巨大，尤其存在于现代物流行业中。对物流企业来说，优化装载问题，提高箱体体积或载重利用率可以压缩企业成本，从而提高企业竞争力，因此三维装箱问题是现代物流所研究的一个重要问题。
　　按装载目标可将三维装箱问题分为箱柜装载问题、容器装载问题和背包装载问题，其中箱柜装载问题是以最少数目限定规格的集装箱装入所有需要装入的货物为研究目标，是三维装箱问题一类重要的研究方向。本文以箱柜装载问题为主要研究对象，结合实际应用提出了多约束有色三维装箱问题。多约束有色三维装箱问题由多约束三维装箱问题和有色装箱问题组成，其中多约束三维装箱研究者颇多，主要为解决实际生活中货物摆放方式、装卸顺序、承受脆度不同而设计的一类三维装箱问题;而有色装箱是指装入同一个箱子的货物类型或者颜色要互异的一类装箱问题。多约束三维装箱问题是结合两类问题的综合问题。论文从多约束有色三维装箱问题的产生背景以及研究意义出发，对此类问题进行深度剖析，提出了从模型建立到混合遗传算法的一整套解决方案。解决方案首先包括多约束有色三维装箱问题模型的抽象，并在此基础上设计装箱过程中的定位规则，利用遗传算法的全局优化能力寻找近似最佳解。在子空间分解问题上本文提出了基于空间优化分解的空间分解方法，即箱体子空间的划分是基于即将装入未划分的空间的物品对该空间的利用率来决定的，并提出了一种的新的数据结构——改进型三叉树来表示此类空间划分，在子空间使用最佳合并策略进行合并，算例证明该方法的解质量高。此外在设计遗传算法解决此类问题时，将染色体划分为头部和尾部，分别表示箱子的装入顺序和摆放方式，其中头部和尾部的基因在交叉和变异的方式上也各不一样。最后对于多约束有色三维装箱问题，基于文中所提出的算法，编写了一套装箱辅助软件，用测试数据测试了算法的优劣，证明解决方案的有效性。

目录

声明

摘要

第一章 绪论

1．1 选题背景及意义

1．2 研究现状

1．2．1 一维装箱研究现状

1．2．2 二维装箱研究现状

1．2．3 三维装箱研究现状

1．3 研究内容与目的

1．4 本论文结构安排

第二章 三维装箱问题与遗传算法概述

2．1 三维装箱问题

2．1．1 三维装箱问题的分类

2．1．2 三维装箱约束

2．2 有色装箱问题

2．3 弱互斥装箱问题

2．4 遗传算法

2．4．1 遗传算法概述

2．4．2 遗传算法实现步骤

2．4．3 遗传算法的特点

2．4．4 遗传算法的具体实现

2．5 本章小结

第三章 多约束有色三维装箱问题的混合遗传算法设计

3．1 问题模型

3．1．1 问题描述

3．1．2 模型假设

3．1．3 现实约束因素分析

3．1．4 优化目标

3．1．5 建立模型

3．2 混合遗传算法设计

3．2．1 启发式规则

3．2．2 混合遗传算法设计

3．2．3 算法流程

3．3 本章小结

第四章 辅助软件的设计和算例检验

4．1 辅助软件设计

4．1．1 软件开发技术

4．1．2 软件功能介绍

4．1．3 软件扩展性与实用性分析

4．2 算例检验

4．2．1 测试数据

4．2．2 运行配置

4．2．3 运行结果

4．2．4 结果分析

4．3 本章小结

第五章 总结与展望

5．1 总结

5．2 展望

参考文献

致谢

附录A (攻读学位期间取得软件著作权)

附录B (攻读学位期间发表论文目录)