基于类粒子群算法的集装箱装载模型优化研究

连志刚，林蔚天，曹 宇，计春雷

(1. 上海电机学院 电子信息学院，上海 201306；2. 上海电机学院 电气学院，上海 201306)

集装箱运输(Container Transport)是指以集装箱这种大型容器为载体，将货物集合组装成集装单元，以便在现代流通领域内运用大型装卸机械和大型载运车辆进行装卸、搬运作业和完成运输任务，从而更好地实现货物“门到门”运输的一种新型、高效率和高效益的运输方式。学界对集装箱运输的相关研究比较丰富，但大部分都集中在泊位指派、船舶的卸载/装载作业、集卡调度优化、空箱调度、存储与堆放物流的研究。关于集装箱内货物的优化装载研究还是比较少，并都集中在基于启发式规则的集装箱货物装载问题[1-4]。基于优化算法和集装箱货物装载的研究较少，并且优化的模型相对简单[5-6]，离指导实际工作还有很大差距。

通过研究运筹学中集装箱装载的经典实例，笔者发现其数学模型有缺欠，按照该模型无法指导集装箱的货物装载，因此，建立了集装箱装载模型，并提出求解的方法，利用类粒子群算法对所建模型进行优化。仿真实验表明，该方法可行有效，对于提高运输资源利用率和运输组织效率都具有重要意义。

1 集装箱装载实例“数学模型”分析

集装箱货物装载问题常使用的实例见文献[7]。该实例及数学模型问题详细分析如下。

某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表1，那么两种货物各托运多少箱，可使获得利润为最大？

表1 承载货物

依照文献[7]，该数学模型建立如式(1)。

设甲、乙两种货物托运箱数分别为x1，x2，建立的数学规划如下。

Maxz=20x1+10x2

(1)

模型(1)比较简单，且有严重缺欠。下面用简单的反例分析上述模型根本不能指导实际，几乎毫无意义。

反例：某厂拟用集装箱托运一种货物，每箱体积、重量、可获利润以及托运工具的大小及承重限制如表2，那么该种货物托运多少箱，可使获得利润最大？

表2 承载货物特征

若参照文献[7]，设货物托运箱数为x，则建立的数学模型如下：

Maxz=20x

(2)

若按照模型(2)组织托运，因x=2是该模型(2)的解，即托运货物2箱，可获得最大利润为4 000元。这很显然存在错误，因为托运货物是箱装，不能挤压变形，现实当中是1箱都不能托运，因为货物超长，根本不能放入。

2 集装箱货物装载数学模型及其优化

2.1 集装箱货物装载数学模型

装箱问题是指将不同尺寸的物品摆放入有一定容量的容器中, 以获得某种最佳的效益。装箱问题是一个具有复杂约束条件的组合优化问题，在理论上属NP-hard问题。目前所流行的求解集装箱装载问题的方法，还没有一种能有效地求解一切装箱问题。下面以实例分析，先建立集装箱货物装载问题数学模型。

某厂拟用集装箱托运货物，每箱体积、重量、可获利润以及托运工具大小及承重限制如表3，那么货物各托运多少箱，如何装载可使获得利润为最大？

表3 承载货物清单

设D1，D2，…，Dn货物托运箱数分别为x1，x2，…，xn，其数学模型如下：

(3)

模型(3)是一个整数规划，其求解比较复杂，更难的是“装载的货物最优摆放后不能超过装载限制的长、宽、高”。也就是货物装载的时候，横或竖摆放不同直接影响空间的利用效率。不同的摆放方式寻优，其实就是组合优化。下面初步探讨模型(3)的求解。

2.2 集装箱货物装载问题求解

集装箱货物装载一般都是从内到外，从下到上，从左到右(从右到左原理相同)依次装载，至装满为止，如图1。

图1 集装箱货物装载方式Fig.1 Container loading goods mode

针对模型(3)的复杂性，笔者采用迭代进化的方法对其求解。

在数组G1的元素中，可能有m个相同，其表示该装载方案中有m个相同的货物；轴对称相等的边可以看作是同一条边；初始解G1表示，以原点为起始点进行装载，第1个货物Di的装载方式为li，bi，hi边分别与Y，X，Z轴平行；接着装载货物Dj，其装载方式为lj，bj，hj边分别与Dk货物的li，bi，hi边平行；依次类推，直到超出集装箱的长、宽、高任何一个限制即退出。不妨假设装载到货物Dk时，超出了集装箱长的限制。

解G2表示以原点为起始点进行装载，第一个货物Ds的装载方式为hs，ls，bs边分别与Y，X，Z轴平行；接着装载货物Di，其装载方式为li，hi，bi边分别与Ds货物的hs，ls，bs边平行；依次类推，直到超出集装箱的长、宽、高任何一个限制即退出。不妨假设装载到货物Dt时，超出了集装箱长的限制。重组、迭代时，数组的元素互相“交互”，元素内元素也互相“交换”。

步骤5：当迭代停止条件满足，输出数组，即为装载方案。

下面将用类粒子群优化算法进行详细模拟，从而彻底解决模型(3)的求解问题。

3 类粒子群优化算法

3.1 类粒子群优化算法编码

最初提出来的PSO算法是一种基于迭代的优化工具[8-10]。系统初始化为一组随机解，通过迭代搜寻最优值，并没有遗传算法用的交换(Crossover)以及变异(Mutation)，而是粒子在解空间追随最优的粒子进行搜索。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域，但关于OPSO算法应用于NP难的调度问题，报道比较鲜见。

Z.G.Lian，等[11-12]曾用整数编码方法，借鉴OPSO算法的思想及遗传算法(Genetic Algorithm, GA)交换(Crossover)操作，采用整数编码，提出类粒子群算法(Similar Particle Swarm Optimization, SPSO)，并将其应用于有效优化FSSP。刘勇，等[13]利用随机扩散算法求解二次背包问题。

集装箱货物装载也是一个特殊的背包问题。笔者基于其思想，用类粒子群优化算法解决货物装载问题。下面以10箱待装货物为例，介绍一些类粒子群算法优化货物装载问题的算子操作，其具体编码如下。

类粒子群算法交换算子操作如图2。

图2 类粒子群算法交换操作示意Fig.2 Illustration of the various types of SPSO crossover operators with permutation strings

一段交换(C1)：在父代①和②粒子长度内随机选择两个交换点，将父代①和②交换点内的装载货物对应复制到半子代，然后将其互换，如图2(a)。

两段交换(C2)：在父代①和②粒子长度内随机选择两对交换点，将父代①和②交换点内的装载货物对应复制到半子代，然后将其互换，如图2(b)。

三段交换(C3)：类似两段交换，如图2(b)。

类粒子群算法变异算子操作如图3。

图3 类粒子群算法中的变异操作示意Fig.3 Illustration of the shift types of SPSO with permutation strings

一段移动插入(M1)：在父代随机选择一段待装货物，再移至父代的长度内随机选择的插入点后，如图3(a)。

两段移动插入(M2)类似于一段移动插入，如图3(b)。

随机选择货箱翻转(M3)：在父代粒子长度内随机选择几个待装货箱，然后分别随机选择翻转点，将其翻转点和货箱长交换，如图3(c)。

随机选择一段货箱大翻转(M4)：在父代粒子长度内随机选择一段待装货箱，将该段内所有货箱的长、宽、高变为高、长、宽，如图3(d)。

随机选择两段货箱大翻转(M5)类似随机选择一段货箱大翻转，如图3(d)。

随机产生新的待装货箱排序(M6)：如产生新种群内新粒子一样，随机产生新的货物装载序列即可，如图3(e)。

3.2 类粒子群优化算法递推方程

vi(k+1)=pi(k)⊕pg(k)

(4)

(vr1,vr2,…,vrN)(k+1)=M(vr1,vr2,…,vrN)

(5)

xi(k+1)=xi(k)⊕vi(k+1)

(6)

(xr1,xr2,…,xrN)(k+1)=M(xr1,xr2,…,xrN)

(7)

4 类粒子群算法解决货物装载仿真

4.1 货物装载实例模型

货物装载问题为组合爆炸问题，该组合爆炸问题最优解搜索空间非常大，很难搜索到其最优解，有时智能算法搜索到近似解，也很难判断其是否为最优解。为了检测笔者提出的类粒子群算法优化货物装载问题的可行性，下面给出一个测试实例，进行模拟实验。为了用数学原理容易找出其最优解，并与笔者提出的智能算法搜索的最优解进行对比，本实例不妨设定的装载器具、货物尺寸比较特殊。该实例的集装箱也可理解为散货船的船舱，装载的货物是不同大小的木箱。该实例及数学模型问题详细分析如下。

某厂拟用集装箱托运1种货物，每箱的长、宽、高、重量、及托运所受限制如表4，那么该货物最多能托运多少箱？货物所受体积和重量的最大限制如表4。

表4 承载货物实例

(8)

该问题有许多种装载方法，为组合爆炸问题。用常用的数学规划方法解决模型(8)几乎不可能。笔者采用类粒子群优化算法解决。

4.2 类粒子群算法优化货物装载实例模型

步骤3：输出pgbest。

用类粒子群优化算法搜索到了模型(8)的最优解，其装载方法是(30,10,20)针对x,y,z轴的长、宽、高。分别装长5箱、宽3箱，高2箱，共装载30箱。笔者用类粒子群算法及遗传算法对模型(8)进行优化并比较收敛效果，其收敛结果见图4。

图4 类粒子群和遗传算法优化模型(8)的收敛曲线Fig.4 Convergence contrast figure of SPSO and GA algorithmsfor model (8)

从图4明显可以看出类粒子群优化货物装载模型可行、有效，比GA收敛速度快，并且搜索到得最优解好。

5 结 语

分析发现运筹学中被广泛使用的一个集装箱货物装载实例数学模型的缺欠，并建立了适合集装箱运输实际的集装箱货物装载模型，提出求解所建模型方法，利用类粒子群算法对所建模型进行优化，仿真实验表明，该方法可行有效，为该类问题的优化寻找了一条新的途径与方法。

笔者只分析了长方体的同一种货物在集装箱中优化装载的问题。其实当货物装载约束条件多时，如不同种类的货物，大小、重量各异，且货物托运时某些易损品上面压力有限制；还有其他球体，锥体及

不规则体等货物时，其建模及优化更加复杂，是未来研究的一个努力方向。

该文获得连城物流www.1885656.com;www.11056.net的支持。

[1] George J A,Robinson D F.A heuristic for packing boxes into a container [J].Computers & Operational Research,1980,7(3):147-156.

[2] Pisinger D.Heuristics for the container loading problem [J].European Journal of Operational Research,2002,141(2):382-392.

[3] 刘霞,吕汉兴.集装箱装载矩形货物的一种启发式算法[J].起重运输机械,2003(1):16-18.

Liu Xia,Lv Hanxing.A heuristic for packing rectangular boxes in a container [J].Hoisting and Conveying Machinery,2003(1):16-18.

[4] 阎威武,邵惠鹤,田雅杰.集装箱装载的一种启发式算法[J].信息与控制,2002,31(4):353-356.

Yan Weiwu,Shao Huihe,Tian Yajie.A heuristic algorithm for three dimension packing problem [J].Information and Control,2002,31(4):353-356.

[5] Gehring H,Bortfeldt A.A genetic algorithm for solving the Container loading problem [J].International Transactions in Operational Research,1997,4(5/6):401-418.

[6] 卜雷,尹传忠,蒲云.集装箱运输多箱三维装载优化问题的遗传算法 [J].铁道学报,2004,26(2):21-25.

Bu Lei,Yin Chuanzhong,Pu Yun.Genetic algorithm for resolution of the three-dimensional multi-bin packing optimization problem in container transportation [J].Journal of the China Railway Society,2004,26(2):21-25.

[7] 钱颂迪.运筹学[M].修订版.北京:清华大学出版社,2004.

Qian Songdi.Operational Research [M].Revision ed. Beijing :Tsinghua University Press,2004.

[8] Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C]//Proceedings of the 6thInternational Symposium on Micro Machine and Human Science.Nagoya,Japan:IEEE,1995:39-43.

[9] 连志刚,焦斌.一种混合搜索的粒子群算法[J].控制理论与应用,2010,27(10):1404-1410.

Lian Zhigang,Jiao Bin.Particle-swarm optimization algorithm with mixed search [J].Control Theory & Applications,2010,27(10):1404-1410.

[10] 许昆,李智勇.改进的量子粒子群多目标优化算法[J].计算机工程与设计,2009,30 (1):164-167.

Xu Kun,Li Zhiyong.Quantum particle swarm optimization method for multi-objective optimization [J].Computer Engineering and Design,2009,30 (1):164-167.

[11] Lian Zhigang,Gu Xingsheng,Jiao Bin.A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan [J].Applied Mathematics and Computation,2006,175(1):773-785.

[12] Lian Zhigang,Jiao Bin,Gu Xingsheng.A similar particle swarm optimization algorithm for job-shop scheduling to minimize makespan [J].Applied Mathematics and Computation,2006,183(2):1008-1017.

[13] 刘勇,马良.随机扩散算法求解二次背包问题[J].控制理论与应用,2011,28(8):1140-1144.

Liu Yong,Ma Liang.Stochastic diffusion search algorithm for quadratic knapsack problem [J].Control Theory & Application,2011,28(8):1140-1144.