具有重心平衡约束的集装箱装载问题研究

杨会志

摘要：针对集装箱装载问题中混合禁忌搜索算法虽然满足集装箱重心平衡约束但存在装载率较低的缺点，从采用基于矩阵的空间约束表达形式、基于简单块构造装载方案、根据禁忌搜素算法的编码次序选择装载货物种类以及设计新的装载方案的评价函数等方面对G2LA算法进行改进，并把改进后的G2LA算法作为混合禁忌搜索算法中的基础启发式装载算法。实验结果表明了本算法的有效性。

关键词：集装箱装载；重心平衡约束；禁忌搜索；编码；G2LA算法

中图分类号：TP391.72 文献标识码 A 文章编号：1009-3044（2015）08-0220-03

Abstract： This paper presents a novel hybrid tabu search approach to the container loading problem to provide a better space utilization in the case of satisfying the constraint of weight distribution. An improved G2LA algorithm， which covers the spatial representation system based on matrices， using simple blocks to construct loading plan， using encoding order of tabu search to load blocks， as well asnew evaluation function of loading solutions， is devised as a loading heuristic to incorporate tabu search. Experimental results with benchmark data show that the new approach is effective.

Key words： container loading problem； weight distribution； tabu search； encoding； G2LA algorithm

1 前言

在集裝箱的实际装载过程中，除了考虑最大化空间利用率之外，往往需要考虑多种约束，如：货物的摆放方向；某些货物的隔离性；货物的承载能力；货物装载的稳定性；装载的优先级；集装箱的承重性等。目前，针对具有重心平衡约束的集装箱装载问题的研究成果还比较少，主要有H. GEHRING等人【1】提出的方法，首先把货物根据一定的规则组成多个塔（box tower），然后基于某种优化标准来优化这些塔在集装箱中的位置，进而可以调整货物的重心在集装箱长度和宽度方向上的位置；Michael Eley【2】把集装箱在长度方向上分成相等大小的3个子空间，然后把货物分别装载到这3个子空间，最后通过交换这3个子空间中的货物来达到集装箱重心平衡的目的；E.E. Bischoff【3】提出的方法是在集装箱装载货物的过程中用具有权重系数的5个标准来进行装载空间和货物组合的选择，通过把其中第五个标准改变为货物装载后重心在水平面的变化量，然后通过优化规则的权重系数达到控制重心位置的目的，该方法避免了前面两种方法控制重心位置精度不高的缺点，但是该标准的公式作者并没有明确给出；我国学者刘嘉敏等人【4】提出的混合禁忌搜索算法，设计了货物装载过程的基础启发式方法，并根据货物种类进行禁忌搜索算法的编码，该算法可以在同时满足集装箱装载总重量约束的同时，精确地控制货物重心在三维空间中的位置，但该算法的体积利用率较低。G2LA算法【5】是集装箱装载领域非常优秀的算法，集装箱装载的体积利用率非常高。本文从采用基于矩阵的物体空间约束表达形式、基于简单块构造装载方案策略、根据禁忌搜素算法的编码次序选择装载货物等方面对G2LA算法进行改进，改进后的G2LA算法作为混合禁忌搜索算法中的基础启发式装载算法，并基于新算法在国际标准测试数据集上进行了计算实验。

2 基于G2LA算法的基础启发式方法

Zhu Wenbin等【5】通过分析多个优秀的基于块装载的集装箱装载算法，提出了由6个关键部分组成的此类算法的分析框架，并在此基础上提出来一度成为此类问题最优秀算法的G2LA算法。本文通过对G2LA算法进行改进，使它能够作为混合禁忌搜索算法的基础启发式方法，下面从6个方面对算法进行描述：

（K1）集装箱中空间约束的表达形式，采用基于矩阵的空间约束表达形式，而没有采用G2LA算法的cover representation，目的是方便以后对该算法进行扩展。

（K2）把G2LA算法的采用复合块构造装载方案策略改变为采用简单块构造装载方案的策略，目的是能够适应混合禁忌搜索算法的编码方式。

（K3）修改G2LA算法的选择具有最小anchor distance的可用空间作为待装载空间的方法，把定义集装箱通过原点的底面宽度的两个点作为计算anchor distance的依据，然后选择具有最小anchor distance的可用空间作为待装载空间，目的是能够适应混合禁忌搜索算法的编码方式来按照货物类型的次序装载货物。示意图如图1所示。

（K4）简单块选择算法采用G2LA算法的2LA算法。2LA算法示意图如图2所示。

根节点代表当前的搜索状态。当要装载一个货物块时，利用评价函数检查最好的w个货物块所生成的装载方案，对w个货物块中的每一个所生成的部分装载方案，再次检查最好的w个货物块所生成的装载方案，这样每次迭代要总共检查w2个装载方案。对w2个部分装载方案，采用基于最大体积的贪婪算法得到一个完整装载方案。然而，基于最大体积的评价函数没有反应当装载一个货物块时造成的浪费空间的大小（例如，那些不能被任何以后装载的货物块使用的空间）。因此，对一个可装载空间s和一个货物块b，采用如下的评价函数：

改進后的G2LA算法的伪代码如图3所示。

3 基于混合禁忌搜索算法和改进G2LA算法的具有重心平衡约束的集装箱装载算法

我国学者刘嘉敏等人提出的混合禁忌搜索算法可以在同时满足集装箱装载总重量约束和重心平衡约束的同时最大化集装箱的装载率，但装载率较低，因此，把该算法的装载过程所用的基础启发性方法改变为前面阐述的改进后的基于G2LA算法的基础启发式方法，并采用该算法原来的编码和解码方法。新算法的主要步骤如下：

1）采用前面说明的改进后的基于G2LA算法的基础启发式方法生成初始解。采用禁忌搜索算法产生多个可行解。

2）由禁忌搜索算法生成的每个可行解通过基础启发式方法转化为装载方案。

3）每个装载方案采用定义好的评价函数进行评价，最好的装载方案作为最优解。

4）把上次迭代过程生成的最优解作为初始解，通过禁忌搜索算法生成多个可行解。

5）重复上述过程直到满足程序结束标准（如迭代次数或者计算时间）并得到优化解。该过程的伪代码如图4所示。

4 算例分析

由于满足重心平衡约束的集装箱装载问题及结果的完整数据还没有文章发表，为了分析和比较算法性能，采用集装箱装载领域的标准数据集对本文算法进行测试。Bischoff和Ratcliff算例，算例分为7组，分别标识为BR1—BR7，每组100个装载实例，在Intel 酷睿2双核 T7200，2G内存计算机上每个实例运行150秒，与其它算法的计算结果对比情况如表1所示【6】，其中混合禁忌搜索算法用HTS标识，本文算法用TS-2LA标识。从表中可以看出，TS-2LA算法在具有HTS算法满足重心平衡约束的同时，对集装箱装载领域标准数据集的计算结果要优于HTS算法，从而可以推出满足重心平衡约束的集装箱装载结果也优于HTS算法的结论。但对标准数据集上的计算结果比G2LA算法差，这是由本算法特殊的编码方式做决定的。

5 结论

本文针对集装箱装载问题中混合禁忌搜索算法虽然满足集装箱重心平衡约束但存在装载率较低的缺点，从采用基于矩阵的空间约束表达形式、基于简单块构造装载方案策略、根据禁忌搜素算法的编码次序选择装载货物以及新的完整装载方案的评价函数等方面对G2LA算法进行改进，并把改进后的G2LA算法作为混合禁忌搜索算法中的基础启发式装载算法。实验结果表明了本算法的有效性。今后的主要工作是该算法在多箱装载问题中的推广应用。

参考文献：

[1] Gehring H，Bortfeldt A. A genetic algorithm for solving the container loading problem[J]. International Transactions in Operational Research，1997（4）：401-418.

[2] Eley M. Solving container loading problems by block arrangements[J]. European Journal of Operational Research， 2002（141）：393-409.

[3] Bischoff E E. Three-dimensional packing of items with limited load bearing strength[J]. European Journal of Operational Research， 2006（168）：952-966.

[4] Liu J， Yue Y， Dong Z， et al. A novel hybrid Tabu Search approach the container loading[J]. Computers & Operations Research， 2011（38）：797-807.

[5] Zhu W， OonW， LimA， WengY. The six elements to block-building approaches for the single container loading problem[J]. Applied Intelligence， 2012， 37（3）： 1-15.

[6] Araya I， Riff M C. A beam search approach to the container loading problem[J]. Computers & Operations Research， 2014（43）： 100-107.