面向单箱弱异类CLP的一种改进启发式方法研究

摘要

集装箱装载布局优化问题的本质是复杂约束条件下的组合优化问题，属于NP-Hard问题，难以在有限时间内找到最优解。近年来，一些智能算法，如蚁群算法、遗传算法、模拟退火算法等，及其改进后的智能算法，在解决这类问题方面都提供了有效的方法。尽管这些算法在一定程度上提高了相关的性能，但是，当问题规模和复杂度增加时，都表现出其自身的不足。通过研究大量参考文献，综合对比分析求解集装箱装载布局优化问题的方法，本文提出了一种改进的启发式方法求解单集装箱装载弱异类货物的布局优化问题。
　　本文针对集装箱装载问题的复杂约束条件建立约束函数，并采用集装箱空间利用率最大化函数为目标函数建立数学模型;设计了求解集装箱装载问题的方法，并详细描述了方法步骤;介绍了集装箱装载过程涉及的主要概念以及面临的主要问题。在求解过程中，蚂蚁综合考虑当前迭代次数、待装载货物信息以及通过三空间分割法、空间划分和空间合并策略得到的待装载空间信息，依据选货概率公式选择货物，并对选出的货物用回溯的方式选择摆放方式进行装载，进而生成状态值并根据状态值得到剪枝信息，最后根据此类信息做出剪枝或者继续装载等相应操作，当所有蚂蚁进行完一次装载则更新信息素矩阵。当迭代次数达到要求时，输出近似最优解。最后，通过天津某折叠自行车厂实际数据与Loh&Nee算法中的6组测试数据验证了本文算法的有效性。
　　本文不仅在理论上研究了集装箱装载问题，而且设计实现了求解集装箱装载问题的方法并开发了一个仿真模拟系统，将集装箱装载过程直观的显示出来。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 CLP简介

1．2．1 装箱问题分类

1．3 国内外研究历史及现状

1．4 本文的主要研究工作

第2章 求解CLP的算法综述

2．1 启发式算法

2．1．1 启发式算法简介

2．1．2 启发式算法分类

2．2 构造型启发式算法在CLP中的应用

2．3 其它优化算法在CLP中的应用

2．3．1 蚁群算法

2．3．2 遗传算法

2．3．3 模拟退火算法

2．3．4 禁忌搜索算法

2．3．5 回溯算法

2．4 本文求解CLP的研究思路

2．5 本章小结

第3章 CLP模型构建及改进启发式算法设计

3．1 约束条件及假设

3．2 CLP模型构建

3．2．1 符号定义

3．2．2 目标函数

3．2．3 约束条件

3．3 概念及描述

3．4 改进启发式算法设计

3．4．1 算法步骤

3．5 本章小结

第4章 改进启发式算法实现

4．1 关键问题描述

4．1．1 装箱问题

4．1．2 选货问题

4．1．3 摆放方式问题

4．2 启发式规则设计

4．2．1 算法开始时的启发式规则

4．2．2 选货过程中的启发式规则

4．2．3 摆放方式中的启发式规则

4．3 空间划分及空间合并

4．3．1 EnlargeCurremSpace方法

4．3．2 MergeSpace方法

4．3．3 UpdateSpaceInfo方法

4．4 本章小结

第5章 实验结果分析及仿真

5．1 实验环境搭建

5．1．1 SolidWorks简介

5．1．2 仿真平台图形界面

5．2 实验一

5．2．1 基础数据

5．2．2 结果分析及仿真

5．3 实验二

5．3．1 基础数据

5．3．2 结果分析及仿真

5．4 本章小结

第6章 总结与展望

6．1 总结

6．2 展望

参考文献

附录

攻读学位期间公开发表论文

致谢