考虑装卸约束的二维矩形装箱问题研究

摘要

本文拟对考虑装卸约束的二维矩形装箱问题(2DOPU)进行研究，该问题是在物流配送中经常遇到的一类实际问题。物流配送是将货物从集散中心配送到各个客户点，在进行配送之前，首先需要对指定货物进行装箱，当这些待装填的货物为家用电器或其它易碎物品时，由于其不能被叠加放置，货物能否成功被装填取决于其底面在车厢底面的拼装结构是否合理（二维矩形装箱问题）;此外，由于同一车辆需要配送不同客户点的货物，为了满足后续卸载操作的方便性，装箱过程中还必须考虑货物的卸载顺序（后进先出），称此时的装箱问题为考虑装卸约束的二维矩形装箱问题。2DOPU是经典二维矩形装箱问题的一个扩展，对其研究能够提高配送效率，进而节约物流配送过程中耗费的时间和经济成本;同时，研究2DOPU能够丰富组合优化领域的内容，也为后续学者求解类似装箱问题提供参考。 为了研究考虑装卸约束的二维矩形装箱问题的高效求解算法，本文首先研究了考虑装卸约束的二维矩形条装箱问题(2DSPU)，然后通过设定2DSPU的大矩形容器长度为一个有限值将该问题转化为2DOPU，最后通过比较2DSPU的实际最小装载长度与设定有限值的大小判断该装箱方案是否为2DOPU的可行解。关于2DSPU的研究思路为:首先，建立了2DSPU的数学模型;然后根据该问题的特点，引用“开空间”来表示装填位置并进一步提出了基于开空间的首适应算法;接着，分析了生成开空间的最大数量并通过使用线段树给出了首适应算法的一个高效实现方法;最后，通过迭代搜索算法（Iterative Search，文中简称为IS算法）提高了解的质量。 为了检验本文中IS算法的效率，实验部分分别测试了样例集1（7组共825个实例）和样例集2（6组共3282个实例），测试结果显示:IS算法在样例集1的大部分测试实例上的表现均优于文献中最好的GRASP算法，在样例集2的大规模实例上，IS算法较B&C算法有明显优势（前者在后者十分之一的时间内找到大部分或全部可行解），并在有效时间内找到了283个开放例子的可行解。因此，本文得到的结论为:基于开空间的首适应算法非常适合求解带装卸约束的装箱问题。

目录

声明

摘要

1 绪论

1．1 问题的研究背景及意义

1．2 国内外研究现状

1．3 研究内容及创新点

1．3．1 研究内容

1．3．2 研究的创新点

1．4 本文的内容安排

2 二维矩形装箱问题

2．1 二维矩形装箱问题的分类

2．1．1 二维背包装箱问题

2．1．2 二维矩形条装箱问题

2．1．3 二维矩形柜装箱问题

2．1．4 带实际约束的二维矩形装箱问题

2．2 求解二维矩形装箱问题的常用算法

2．2．1 解空间的表示方法

2．2．2 求解二维矩形装箱的启发式算法

3 考虑装卸约束的二维矩形条装箱问题的数学模型

3．1 模型假设及符号说明

3．1．1 模型中的假设

3．1．2 模型中的符号说明

3．2 研究问题的描述

3．3 建立数学模型

4 基于开空间算法求解考虑装卸约束的二维矩形条装箱问题

4．1 开空间表示装填候选位置

4．2 基于开空间的首适应启发式算法

4．3 首适应启发式装箱算法的时间复杂度分析

4．3．1 通过线段树结构实现卸载约束

4．3．2 线段树构造

4．3．3 线段树更新

4．3．4 线段树查询

4．4 迭代搜索算法(IS算法)

5 实验结果分析

5．1 IS算法求解考虑装卸约束的二维矩形条装箱问题的结果分析

5．2 IS算法求解考虑装卸约束的二维矩形装箱问题的结果分析

6 总结与展望

6．1 本文的工作总结

6．2 研究展望

参考文献

致谢

附录