集装箱装载问题的分析及其有效算法的研究

摘要

随着经济贸易的增长，物流效率的提高成为物流产业发展的一个主题。集装箱作为物流活动中最为重要的工具之一，其优化问题的研究直接影响着企业物流费用的支出。集装箱装载问题是一个经典的组合优化问题：给定的一些不同规格的三维箱子，将箱子的一个子集装载进集装箱，使得集装箱的空问使用率最大。近几年，该问题的研究相对于过去有较大的突破，这主要源于一种基于块构造的观念的提出。本文称使用这个观念的算法为基于块构造途径的算法。近期的一些成功的算法本质上都是一类基于块构造途径的算法。然而这些具体的算法各自包含了许多看似区别很大的模块，这使得对该问题及其有效算法做一个系统的分析显得非常困难。
　　 本文针对基于块构造途径的算法提出了一个包含6个关键决策因素的分析框架，它们是：1)可行放置区域的表示；2)候选块的构造；3)可用空问的选择；4)装载块的选择；5)块在所选的空间中的装载；6)总体上使用怎样的搜索策略。从本质上讲，所有基于块构造途径的算法之间的区别，仪在于它们对这6个决策要素各自采用的启发策略不同。基于该框架，本文对近期发表的两个成功但内部结构复杂的算法进行剖析，它们分别是划分控制树搜索算法(CLTRS)和极大化空问表示算法(MS)。结合该框架的分析使得这些优秀算法内部的工作原理可以被更好的理解，另外其不足之处也得以呈现。本文通过组合有效的策略，改进评估函数的准确度，设计了一个新的启发式算法。新算法使用一个3维的R-Tree来管理集装箱内部的剩余空间，这相对于基于列表的方式能更高效进行数据维护。此外，新算法也加入了稳定性约束的考虑，保证了装箱方案中货物的摆放平稳。
　　 本文在集装箱装载问题的1600个被广泛使用的基准数据上进行计算实验，结果表明新算法优于CLTRS算法，能够获得更高的空间使用率。

目录

文摘

英文文摘

声明

第1章绪论

1.1问题的背景与意义

1.2问题陈述

1.3研究现状

1.4本文贡献及创新点

1.5论文内容安排

第2章基于块构造的CLP算法的分析框架

2.1基于块构造途径的6个决策要素

2.2基于划分控制树搜索的算法

2.3基于极大化空间表示的算法

2.4本章小结

第3章6个决策要素的有效策略研究

3.1剩余空间的表示(K1)

3.2块的构造(K2)

3.3空间的选择(K3)

3.4块的选择(K4)

3.5块的摆放(K5)

3.6总体搜索策略(K6)

3.7本章小结

第4章一个新的启发式算法

4.1求解无支撑约束的G2LA算法

4.2求解完全支撑约束的G2LA-FS算法

4.3可用空间的维护技术

4.4本章小结

第5章计算实验

5.1测试数据与实验环境

5.2与现有算法的对比

5.3 G2LA算法策略有效性的研究

5.4装箱方案稳定性的研究

5.5本章小结

第6章总结与展望

参考文献

作者简历

致谢