集装箱单一规格物体装箱的优化算法

Shenzhen City Employees Institute of Continue Education，Shenzhen 518029，China

Abstract：Various container loading algorithms published only suit multi-type objects, not one-type．An optimum algorithm that only applies to container loading one-type of objects is provided here．For given space，it can change 3D loading into 2D loading to calculate the possible height and the distribution of object layers of the combinative objects along the coordinate directions．Each layer of loading is given by the optimum calculating and mirror copy methods．Then，the most suitable layer can be loaded and the rest space is lessened．By repetition the same process，the result of loading optimization can got finally．Through the experiments，the algorithm seems more effective and simple． 收稿日期：2006-06-19. 作者简介：杨德荣（19-），男，江西临川人，硕士，深圳市职工继续教育学院高级工程师，主要研究方向为CAD和智能布局。 17 交通运输工程与信息学报 2007年 第2期

Key words：Container loading，optimum algorithm，one type of objects，computer apply 0 引 言 集装箱优化装箱问题，由于具有重大的社会经济意义，近年来引起专家学者的广泛关注，有大量文献发表[1]。但由于集装箱优化装箱属于三维规则布局问题，而三维规则布局又是NP-完全问题，因此，很多算法[1]-[3]都是求近似优化解的启发式算法，这些算法显然不适合单一规格物体情况。文献[4]提出一种单向寻优算法，能有效避免NP-完全问题，在特定方向进行充分搜索，计算结果自动形成装箱顺序。但该算法也不适合单一规格物体情况。 本文在文献[5]的基础上，提出一套完善的单一规格物体优化装箱算法。该算法先沿三个坐标方向计算最优高度，得出层的分布，将问题转化为平面布局；再通过优化计算和镜向复制，得到完全的平面优化结果。然后，比较三维空间的三个坐标方向的优化趋势，选择可能装入物体最多的方向的最好的一个平面优化布局结果装填入集装箱。如此重复计算，最后使集装箱装满。 不论如何布局，问题归结为： ⎧a1x+b1y+c1z≤ X⎪ ⎨a2x+b2y+c2z≤ Y （1）⎪ax+by+cz≤ Z33⎩3式中所有系数必须是正整数，因此，问题归结为如何选取这些系数，使得： ⎧a1x+b1y+c1z⇒X⎪＇ ⎨a2x+b2y+c2z⇒Y （1）⎪ax+by+cz⇒Z33⎩3由式（1）第3式，令a3 = i，b3 = j，则有： c3≤Z−ix−jy⎡Z⎤ i = 0, 1, 2, K,⎢⎥ z⎣x⎦j = 0, 1, 2,…,⎢⎡Z⎤ ⎥ （2）⎣y⎦因此，式（1）＇的第3式转化为如何选取i和j，使得c3⇒Z−ix−jy，即： zZ−ix−jy⎡Z−ix−jy⎤−⎢ ⎥⇒0 （3）zz⎣⎦令zs=Z−ix−jy，当Zs≥0时计算： z1 定 义 待布空间（集装箱）定义：设坐标原点在后部箱底，长度方向为x轴，箱体长度为X；宽度方向为y轴，箱体宽度为Y；高度方向为z轴，箱体高度为Ｚ。 待布物体定义：假设待布物体为长方体，尺寸为（x，y，z），在装箱过程中可以侧翻。 ⎡Z⎤⎡Z⎤ s3=minzs−[zs]i=0,1,2,󰀢,⎢⎥j=0,1,2,󰀢,⎢⎥（4）⎣x⎦⎣x⎦对于s3，有is3，js3，[zs]s3，使得待布物体沿z轴方向分层布局，即以x为高度分布is3层，以y为高度分布js3层，以z为高度分布[zs]s3层，可使得装填后的集装箱在z方向剩余空隙最少，即有： Zmin=Z−is3×x−js3×y−[zs]s3×z （5） 同样，由式（1）和式（1）＇的2式和3式，可得 2 方法描述 由于（x，y，z）、（X，Y，Z）已定，且最后装填入集装箱的待布物体总数及沿集装箱的x，y，z轴方向的个数只能是正整数，因此，不存在连续的目标函数，使装填的待布物体数最多。但我们可通过分别使集装箱装填后沿x，y，z轴方向留下的间隙最少来达到优化装填的目的。 Xmin=X−is1×x−js1×y−[zs]s1×z （5）＇ Ymin=Y−is2×x−js2×y−[zs]s2×z (5)″ 在（5）式中，以z为高度分布的 [zs]s3层的布局问题，实际上是一个以（X, Y）为布局空间，以（x, y）为待布物体的矩形平面布局问题。如果 [zs]s3 ≠ 0，设： ⎡Y⎤⎡X⎤N1=⎢⎥ M1=⎢⎥ ⎣x⎦⎣y⎦ 18

集装箱单一规格物体装箱的优化算法 杨德荣

⎡XN2=⎢⎣y⎤⎡Y⎤⎥ M2=⎢⎥ ⎣x⎦⎦ yY−iy令yi=，当yi≥0时，计算 xsy = max [(i × N1 + [yi] × N2) i = 0, 1, 2, …] 对应sy，有isy、[yi]sy，可求得 k1 = isy × N1 + [yi]sy × N2 （6） （6）式只在布局空间的y方向进行了优化，x方向并未得到优化，因此，X边的另一端可能会留有较大空隙，见图1的阴影部分，需通过镜向复制方法作进一步处理。假设（6）式的布置总是先长条后短条，这里为叙述方便，令长条为N1 × x，如图1所示。 y x图2 图1的镜向复制 Fig.2 Mirror copy of Fig.1 物体为 [yi]sy(N2 − i1) + isy(N1 − j1) （8）（2）当isyy≤1Y时，即布置图与复制图长条在y2方向不相交时，除应删除（8）式确定的物体外，还应以删除后的复制图短条为界，删除布置图短条多余物体；并以删除后的布置图短条为界，删除复制图长条多余物体，即： 由有序集{y, 2y, 3y,…, N2 × y}可求出i2，满足 x (i2 − 1)y≤X − i1y < i2x 图1 平面y方向优化布置示意 得出应删物体数 [yi]sy(N2 − i2 + 1) 由有序集{X − x, X − 2x, X − 3x,…, X − N1 × x}可Fig.1 2D optimum loading in y-direction 令K1 = k1。如果 max(X − N1 × x, X − N2 × y)≥则： （1）将布置图先后沿水平和垂直方向作镜向复制，得出如图2所示的复制图并移入待布空间，与原布置图关于待布空间对角线对称。对于布置图的长条，有有序集合： {x, 2x,…, N1 × x} 对于复制图短条，有有序集合： { X − y, X − 2y, …, X − N2 × y} 并有矩阵： 或 求出j2，满足X − (j2 − 1)x≥(i2 − 1)y > X − j2x，得出1 ×min(x,y) （7）2应删物体数isy × (N1 − j2 + 1)。 另外，此种情况下可能会在待布空间中形成一个方洞： (x1, y1) = (X − (i1 + i2 − 1)y, Y − 2isy × y) 但能否装填进待布物体，需满足： ⎧min(x,z)≤ min(X1,Y1)⎪⎨max(x,z)≤ max(X1,Y1) ⎪y≤ [zs]s3×z⎩⎡X−y−x⎢󰀣⎢⎢⎣X−N2×y−x⎤⎥󰀣󰀣󰀣⎥ X−N2×y−2x󰀢X−N2×y−N1×x⎥⎦X−y−2x󰀢X−y−N1×xmin(X1,Y1)⎧min(y,z)≤ ⎪max(X1,Y1) ⎨max(y,z)≤ ⎪x≤ [zs]s3×z⎩假设装填进T个待布物体，则本层方洞装填T。 [zs]s3由此找出最小正数项“X − i1y − j1x”，得出应删 因此，这种情况下实际装入的待布物体数为： 19

交通运输工程与信息学报 2007年 第2期

K1=2k1−[yi]sy(N2−i1)−isy(N1−j1)−[yi]sy(N2−i2+1) T −isy(N1−j2+1)+[zs]s3=2k1−[yi]sy(2N2−i1−i2+1) −isy(2N1−j1−j2+1)+计算结果见图3。 y x yT （9） [zs]s3 x 图4 平面y方向优化布置示意 Fig.4 2D optimum loading in y-direction y图3 根据图1所得的平面优化布置结果 Fig.3 2D optimum loading according to Fig.1 x （3）当isyy>1Y时，即布置图与复制图长条在y2图5 根据图4所得的平面优化布置结果 Fig.5 2D optimum loading according to Fig.4 方向相交时，除应删除（8）式确定的物体外，还应从删除后的布置图长条末端位置水平向前，碰到布置图短条竖线开始，删除其多余物体；并以删除后的布置图短条为界，删除复制图长条多余物体，即： 由有序集{y, 2y, 3y,…, N2 × y}可求出i2，满足(i2 − 1)y < j1x≤i2y，得应删物体数[yi]sy(N2 − i2)； 由有序集{X − x, X − 2x, X − 3x, …, X − N1 × x}可求出j2，满足X − j2x≥i2y > X − (j2 + 1)x，得出应删物体数isy × (N1 − j2)。 因此，这种情况下实际装入的待布物体数为： 用类似式（7）—式（10）的过程，可求得K2，取 Kzz = max(K1, K2) （12） Gzz=Kzz×xy (12)′ XY此即为待布物体沿z方向以z为高度分布 [zs]s3层时平面矩形布局的优化结果。用同样过程，我们可求得沿各轴方向的各个矩形平面布局的优化结果，即可求得： K1=2k1−[yi]sy(N2−i1) −isy(N1−j1)−[yi]sy(N2−i2)−isy(N1−j2) ⎡Kxx⎢K=⎢Kyx⎢Kzx⎣KxyKyyKzyKxz⎤⎥Kyz⎥ （13） Kzz⎥⎦对应的分布层数为： =2k1−[yi]sy(2N2−i1−i2)−isy(2N1−j1−j2) （10） 计算结果示于图4、图5。 同样，令xj=X−jx，当xj≥0时，计算 y⎡Gxx⎢G=⎢Gyx⎢Gzx⎣GxyGyyGzyGxz⎤⎥Gyz⎥ （14） Gzz⎥⎦对应的装填率为： sx = max [(j × M1 + [xj] × M2), j = 0, 1, 2,…] 对应sx，有jsx、[xj]sx，可求得： k2 = jsx × M1 + [xj]sx × M2 （11） ⎡is1⎢L=⎢is2⎢⎣is3js1js2js3[zs]s1⎤⎥[zs]s2⎥ (14)′ [zs]s3⎥⎦ 20

集装箱单一规格物体装箱的优化算法 杨德荣

3 优化布局的计算步骤 Step1 令：W = 0，XYZ(1, 2, 3) = (X, Y, Z)，xyz(1, 2, 3) = (x, y, z) Step2 对于待布空间XYZ，求出矩阵（13）、（14）、（14）＇。由（14）＇，得： 6沿Z方向分布2层，再按图7沿Z方向分布3层，共装入148个物体，装箱率.853％，见图8。 y⎞⎛3⎟ KL(m)=max⎜K(i,j)L(i,j)i1,2,3×=⎟⎜∑⎠⎝j=1G(m,n)=max(G(m,j),j=1,2,3) 则： W = W + K(m, n) （15） Step3 XYZ(m) = XYZ(m) − xya(n) 如果 x图6 例1首选平面优化布置形式 Fig.6 The first form of 2D optimum loading of case 1 ⎧min(XYZ(1),XYZ(2),XYZ(3))≤ min(xyz(1),xyz(2),xyz(3))⎪⎨mid(XYZ(1),XYZ(2),XYZ(3))≤ mid(xyz(1),xyz(2),xyz(3)) ⎪max(XYZ(1),XYZ(2),XYZ(3))≤ max(xyz(1),xyz(2),xyz(3))⎩则转入step 2，否则，计算结束。 4 算 例 共计算三个例子，箱体尺寸为（5.9，2.388，2.352），物体尺寸取自文献[3]，计算结果如下： （1）(x, y, z) = (0.37, 0.9, 0.6)，计算结果为先按图 y x图7 例1第二次所选平面布置形式 Fig.7 The second form of 2D optimum loading of case 1 图8 例1优化布置结果 Fig.8 The optimum loading result of case 1 21

交通运输工程与信息学报 2007年 第2期

（2）(x, y, z) = (0.5, 0.78, 0.62)，计算结果为先按图9沿y方向分布1层，再按图10在剩余空间的z y x方向分布3层，共装入130个物体，装箱率94.875％，见图11。 yx图9 例2首选平面布置形式 Fig.9 The first form of 2D optimum loading of case 2 图10 例2第二次所选平面布置形式 Fig.10 The second form of 2D optimum loading of case 2 图11 例2优化计算结果 Fig.11 The optimum loading result of case 2 （3）(x, y, z) = (0.5, 0.78, 0.62)，计算结果为先按图12沿X方向分布3层，再按图13在剩余空间的Z yx方向分布5层，其中的方洞填进4个物体，共装入234个物体，装箱率94.995％，见图14。 yx图12 例3首选平面优化布置形式 Fig.12 The first form of 2D optimum loading of case 3 图13 例3第二次所选平面布置形式 Fig.13 The second form of 2D optimum loading of case 3 22

集装箱单一规格物体装箱的优化算法 杨德荣

图14 例3优化布置结果 Fig.14 The optimum loading result of case 3 5 结 论 （1）由于NP-完全问题特性只有当布局物体规格较多时才明显表现出来，对于单一规格情况，可以不予考虑。因此，单一规格装箱和多种规格装箱的算法是不同的，前者主要是数值算法，后者主要是选择搜 参考文献 [1] 查建中等．布局及布置设计问题求解自动化的理论与方法综述[J]．计算机辅助设计与图形学学报，2002，16（4）：705-712． [2] 王若恩等．三维空间最优装载模式的算法研究与实：6-13． 现[J]．工程图学学报，2005，26（5）[3] 刘嘉敏等．基于组合的三维集装箱装入启发式算法索路经。 （2）由于在平面布局时使用镜向复制方法，因此算法实际上在三维坐标方向均依序进行了严格的优化计算，能够保证求得问题的最优解。算例结果表明，算法效果显著。 ：22-25． 研究[J]．工程图学学报，2005，26（1）[4] 杨徳荣，杨 超．三维装箱布局的单向寻优搜索法[J]．工程图学学报，2007，28（2）：35-41． [5] 杨德荣．一类集装箱布局问题的优化计算[J]．物流：43-45． 科技，2006，29（8） 23