集装箱堆场(预)翻箱问题建模与优化研究

摘要

随着我国经济的持续快速发展，港口集装箱吞吐量快速增加，港口码头集装箱拥堵和港口压船现象不断出现。如何提高港口集装箱码头的装卸速度和吞吐效率，从而减少船舶在港停泊时间成为我国集装箱码头的当务之急。在集装箱堆场，影响装船效率的主要因素之一是堆场翻箱问题，除了对装船时取箱过程中的翻箱问题进行优化，提高装船效率的另一种方法就是对集装箱进行预翻箱整理，使得集装箱的堆放顺序符合取箱顺序，以尽量减少取箱装船过程中的翻箱次数。本文以集装箱堆场单贝位出口箱装船时和装船前的翻箱过程为研究对象，对其进行优化，从而减少翻箱次数，达到提高集装箱码头装船效率的目的。
　　 本文首先介绍了集装箱堆场和（预）翻箱问题，分析了翻箱操作产生的原因和其造成的影响，分析了降低翻箱次数的重要性和解决方法;然后提出了集装箱堆场单贝位出口箱装船时翻箱问题的假设，构建了翻箱问题的整数模型，结合贝位规模和箱子数量不断变化的翻箱案例，利用分支定界精确算法对其进行了优化，并对优化结果进行了分析。
　　 鉴于集装箱堆场装船时翻箱问题属于组合优化问题，具有NP特性，在问题规模较大时利用分支定界算法难以或者无法在可以忍受的时间内得到最优解，因而本文针对装船时翻箱过程中落箱位置的箱位选取设计了启发式规则，利用visual c++编写了翻箱问题的程序，结合贝位规模及集装箱数量不断变化的翻箱问题随机案例，对其进行了优化，并对优化结果进行了分析，同时和分支定界算法的优化结果进行了比较，验证了其正确性。由于启发式算法本身的特性，其对问题进行优化得到的解只能是问题的近优解或可行解，本文基于问题空间搜索算法的思想对提出的启发式算法作了进一步改进。
　　 本文提出了集装箱堆场单贝位出口箱装船前预翻箱问题的假设，构建了装船前预翻箱问题的整数数学模型，利用分支定界精确算法对预翻箱随机案例进行了求解优化，并对优化结果进行了分析。
　　 优化实验结果及其分析表明:1）分支定界算法能够结合数学模型获得问题的精确解或最优解，但随着贝位规模及箱子数量的增大，时间成本呈指数增加;2)启发式算法及基于问题空间搜索的改进启发式算法，能在较短时间内得到问题的近优解或可行解;3）随着案例规模的增大，改进后的启发式算法能够较改进前的启发式算法得到质量更高的解。

目录

声明

摘要

第1章 绪论

1．1 研究背景和意义

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状

1．2．1 堆场箱位分配

1．2．2 贝内落箱位置

1．2．3 装船前预翻箱

1．2．4 装船时翻箱

1．2．5 现有研究存在的问题

1．3 研究内容、技术路线及创新点

1．3．1 研究内容与技术路线

1．3．2 特色与创新点

1．4 本章小结

第2章 集装箱堆场翻箱操作分析

2．1 集装箱堆场翻箱概述

2．1．1 集装箱堆场

2．1．2 集装箱堆场翻箱操作

2．1．3 预翻箱问题和翻箱问题

2．2 堆场翻箱操作产生原因及影响

2．2．1 翻箱操作产生原因

2．2．2 翻箱操作影响

2．3 减少翻箱量的解决思路及对策

2．3．1 减少翻箱量的解决思路

2．3．2 减少翻箱量的对策

2．4 本章小结

第3章 翻箱问题数学建模及精确算法优化

3．1 翻箱问题数学建模

3．1．1 模型特征

3．1．2 数学模型

3．2 翻箱问题精确算法优化

3．2．1 精确算法优化概述

3．3．2 优化过程

3．3．3 案例优化及结果分析

3．3 本章小结

第4章 翻箱问题启发式算法优化

4．1 启发式算法概述及规则

4．1．1 启发式算法概述

4．1．2 箱位选取启发式规则

4．2 启发式算法设计

4．2．1 算法步骤

4．2．2 算法流程图

4．3 算法实现及优化过程

4．3．1 算法实现

4．3．2 优化过程

4．4 案例优化及分析

4．4．1 小规模案例

4．4．2 大规模案例

4．5 本章小结

第5章 翻箱问题改进启发式算法优化

5．1 箱位选取改进启发式算法

5．1．1 算法思想

5．1．2 算法步骤和流程图

5．2 算法优化过程及实例

5．2．1 算法优化过程

5．2．2 算法优化实例

5．3 改进启发式算法优化效果对比

5．3．1 改进前启发式算法案例优化

5．3．2 改进后启发式算法案例优化

5．4 案例优化及分析

5．4．1 小规模案例

5．4．2 大规模案例

5．5 本章小结

第6章 预翻箱问题数学建模及精确算法优化

6．1 预翻箱问题数学建模

6．1．1 模型特征

6．1．2 数学模型

6．2 预翻箱问题精确算法优化

6．2．1 优化过程

6．2．2 案例优化及结果分析

6．3 本章小结

第7章 总结与展望

7．1 全文总结

7．2 研究展望

致谢

参考文献

作者攻读硕士期间参与项目及发表的论文

附录A 翻箱问题随机案例

附录B 预翻箱问题随机案例

附录C 翻箱问题启发式算法程序部分代码