面向不规则集装箱的货物装载优化问题研究

张长勇 翟一鸣

(中国民航大学电子信息与自动化学院 天津 300300)

0 引 言

随着现代物流的飞速发展，航空货运已进入蓬勃发展的阶段。集装箱装载是航空货物运输中的重要环节，然而由于飞机机舱的特殊形状，除了用于大型飞机的货舱中的标准集装箱之外，通常要使用尺寸、体积和形状不同的非标准集装箱。目前常用的航空集装箱主要有AMF、AKE、AAU集装箱，它们都是非长方体的集装箱。因此，研究实用且高效的不规则集装箱的装载优化算法是非常必要的。

航空货物装箱问题本质上属于三维装箱问题，是NP问题。求解算法可以分为构造性算法和邻域搜索算法。

构造性算法用来生成初始装载布局方案，主要方法有极点法、砌墙法、中心骨架法、组合块、优条与优层、穴度法、三空间分割法。Crainic等[1]通过定义横纵交叉点生成关键点来放置货物；George等[2]首次提出了砌墙法，将三维装箱问题简化为一维问题进行求解；雷定猷等[3]根据实际装载经验，提出了先码放核心货物以构造骨架，再放置其他非核心的货物的中心骨架法；张德富等[4]将货物组合形成复合块，根据块选择算法确定每一步使用的块，再以固定方式装载块；刘胜等[5]采用箱子、优条、优层的顺序得到装载方案；何琨等[6]提出了每步选择一个货物将其放在箱子的某个位置，使其占用空间最小的穴度算法；张钧等[7]采用三叉树结构来表示空间的布局情况，通过空间搜索、分割与合并对货物进行装载。

装箱问题的计算结果是不可量化的，利用邻域搜索算法求解问题的近似最优解，主要有蚁群[8]、遗传[9-10]、树搜索[11-14]、模拟退火[15]、粒子群[16]、多元优化法[17]。利用构造性算法形成初始装载布局方案，用邻域搜索算法从多个可行解中选出目标函数最优的方案作为最终方案。为提高算法的全局搜索能力，可以两两相结合或者是对算法做出一些改进。构造性算法在结合邻域搜索算法后，其性能可得到些许的改进。

目前国内外学者研究的大多是规则的长方体箱子，而航空集装箱大都是不规则、非长方体的集装箱，为此需根据实际工程要求建立数学模型，研究相应算法来完成货物装载。本文研究航空货运背景下不规则集装箱的货物装载问题，在满足实际装载约束的条件下，提出一种将拟人与改进的遗传相结合的混合遗传算法。首先由拟人算法得到初始装载方案，然后通过改进的遗传算法从多组可行性方案中找到最优装箱方案。基于真实航空货物数据的结果分析比较，验证了该算法在空间利用率、载重利用率及求解时间上均优于传统遗传算法。最后，利用GUI设计了装箱软件，以方便指导实际应用中的装箱操作。

1 问题描述

虽然本文出发点是为不规则的航空集装箱提供装载布局方案，但目前航空集装箱类型较多，规格也不同，难以建立一套通用模型以适合所有不规则集装箱。针对目前广泛应用于航空运输的AKE集装箱展开研究，适载机型有747、777等。外形尺寸如图1所示。

图1 AKE集装箱外形尺寸

1.1 约束条件

不规则集装箱的货物装载问题可以描述为：给定AKE集装箱和一定数量的待装载航空货物B={b1,b2,…,bn}，在满足实际装载约束的前提下，得到使AKE箱空间利用率或者载重利用率最大的装载布局方案。考虑航空货物装载过程中的现实约束如下：

(1) 装载顺序约束：考虑航空货物装箱过程中的顺序装载，以适应实时装箱。

(2) 体积、质量约束：货物的总体积、质量不超过集装箱的最大装载体积、最大承载力。

(3) 重心约束：为保证垛形的稳定性，集装箱重心需要在合理的范围内。

(4) 不重叠约束：货物之间不能重叠。

(5) 承重约束：装载过程中，有必要充分考虑货物的载重能力，以免因过度挤压而损坏货物。

1.2 假设条件

由于实际装载过程中货物装箱问题的复杂性，为便于进行研究，做以下假设：

(1) 航空货物形状各异，考虑到大多复杂形状可拆分成几个小的长方体，故简化货物均为长方体。

(2) 货物密度均匀，其重心即为几何中心。

(3) 集装箱中货物的码放位置不受区域的限制。

(4) 货物因挤压产生的变形可忽略不计。

2 数学模型

2.1 符号说明

空间坐标系是通过将AKE集装箱的底面作为xy平面，垂直底面向上作为z轴，以其左、后、下角为原点建立的。以下是符号说明：

ηi为0/1变量，若货物i装入集装箱中则ηi=1，若未装入则ηi=0。

α是 0,1 之间的变量，以载重利用率最大为目标时α=0，以空间利用率最大为目标时α=1。

W1、W2、H、D、V、M是AKE集装箱的长(最大)、长(最小)、宽、高、体积及其最大载重量。

wi、hi、di、vi、mi、[gxi,gyi,gzi]是货物i的长、宽、高、体积、质量及其重心坐标。

Beari、BLi分别是货物所承受的重量及其最大承受力。

Bi、Ci是货物的顺序号、码放序号。

[conx1,conx2]、[cony1,cony2]、[0,conz]分别是x、y、z轴的重心安全区间。

2.2 模型建立

根据上述分析，建立航空货物堆码数学模型。式(1)表示优化目标为最大化集装箱空间利用率、载重利用率；式(2)、式(3)表示货物的总质量、总体积小于集装箱的最大承重量、体积；式(4)表示货物要与集装箱正交或者平行；式(5)表示货物需按照当前到来的顺序进行装载；式(6)表示货物垛形重心在合理的范围之内；式(7)表示货物承重约束，即货物所载全部上层货物总重量小于它的最大承重量；式(8)表示货物之间不能重叠。

Bi=Ci

(5)

3 算法设计

求解AKE集装箱装载优化问题的混合遗传算法包括拟人算法和改进的遗传算法两部分。利用拟人算法产生初始装箱方案，然后利用改进的遗传算法对多组可行方案寻优，得到目标函数最大的装载布局方案。其流程如图2所示。

图2 算法装载流程

3.1 基于拟人的构造性装箱算法

面对复杂的不规则集装箱装载问题，为使货物码放过程更加灵活，采用可放置点构建、规则设定、排序、参考线引入的拟人算法对货物进行装载，该算法的优点在于它不需要货物垛形满足特定的结构。将货物bi放置在点(xi,yi,zi)，会新增三个可放置点(xi+wi,yi,zi)、(xi,yi+hi,zi)、(xi,yi,zi+di)，如图3(a)所示。得到的可放置点通过设定规则并赋予一定的权重，对其进行排序。按照排好序的可放置点去判断货物bi是否满足装载条件，装载条件为该货物bi不能与其他货物以及集装箱相交，且满足x+wi≤Lx，z+di≤Lz，即不超过水平、垂直参考线(参考线如图3(b)和图3(c)所示)。

(a) 可放置点

(b) 水平参考线

(c) 垂直参考线图3 可放置点及参考线

规则及权重设定如表1所示，设定依据如下：规则1使货物从底层开始进行有序放置；规则2保证货物之间的接触率，使得垛形更加稳定；规则3为待装载货物提供更大的装载空间；规则4将放置的货物尽可能靠边，以装入更多的货物。根据对装载效果的影响，分别赋予权重0.5、0.2、0.2、0.1。为防止过拟合，添加了正则项以确保规则的合理性。表格规则可简化为：

式中：Q0是可放置点总数；qi是根据此规则i在总数中的排序个数；0.3μ为正则化项；r为每个可放置点的评价值，根据r值对可放置点进行排序。每次完成当前货物装载，同步更新可放置点序列和剩余货物信息。

表1 规则及权重

拟人算法步骤如下：

Step1输入AKE集装箱的尺寸、体积、最大载重量，以及待装载的货物序列B=(b1,b2,…,bn)。

Step2设定集装箱的左后下角为初始可放置点(0,0,0)，初始化水平、垂直参考线Lx=Lz=0。

Step3根据所设定规则对可放置点排序，按照排好序的可放置点依次检测货物。

Step4判断当前可放置点是否满足装载条件。若满足，装载当前货物，删除已用的可放置点；若不满足，返回Step 3。

Step5在所有的可放置点都不满足装载条件时，提高参考线。若Lx

Step6更新可放置点序列及剩余货物信息。

Step7判断货物是否装载完毕，若是，则输出装载布局方案；否则，返回Step 3。

3.2 改进的遗传算法

遗传算法在解决NP难题时具有快速随机的全局搜索能力，但收敛速度和局部搜索效果欠佳。为解决传统的遗传算法容易过早收敛的问题，加入适应度尺度变换、罚函数、最优解保存策略来对其进行改进。

3.2.1编码与解码

编码时，货物的每种装箱方案对应符号串S=(S1,S2,…,Si,…,Sn)，其长度为n，S1-Sn代表货物放置状态，每个货物有6种放置状态，分别用整数1、2、3、4、5、6表示；解码时，第i个待码放的货物按照基因Si代表的状态进行放置。

3.2.2适应度尺度变换与罚函数

适应度用来评价各装箱方案的好坏。把目标函数设为适应度函数，为提高个体间的竞争性，防止算法过早收敛，对适应度进行线性尺度变换。式(10)为原适应度函数，式(11)为变换后的适应度函数。

F1=aF+b

(11)

式中：a、b为变换系数；Fmin为F的最小值；Favg为F的平均值。

综合考虑垛形重心约束、不重叠约束、承重约束，对违反条件的个体给予相应的惩罚，使其被遗传到下一代种群的机会降低。式(12)为加入惩罚项的适应度函数；式(13)为垛形重心罚函数；式(14)为货物不重叠罚函数；式(15)为货物承重罚函数。

式中：H为货物装载的罚函数；k为惩罚因子。

H9=Beari-BLi

(15)

3.2.3遗传操作过程

对个体进行遗传操作，包括选择、交叉与变异。

选择：基于对个体适应度的评估，利用轮盘赌对个体进行选择。

交叉：决定了算法的全局搜索力，采用双点交叉法，通过随机产生两个交叉点进行基因交换。

变异：决定了算法的局部搜索力，利用顺序逆转变异，先在父代选择两个变异点，然后以相反的顺序在两个点之间对基因进行重新排列，以维持种群的多样性。

因为上述的操作有很大的随机性，可能会破坏适应度较好的个体。为使较好的个体尽可能多地遗传到下一代，采用最优解保存策略。即在每一代的进化中，前10%的个体被保留而不进行交叉、变异，并被直接复制到下一代种群中。

4 实例验证

在型号为Intel(R) Core(TM) i5- 7200U CPU 2.50 GHz的计算机上进行实验，运行环境Visual Studio 2010。

遗传算法的参数为：

{种群规模,交叉,变异概率,终止条件,测试次数}=

{50，0.6，0.1，200，10}

AKE集装箱参数如下：

{W1,W2H,D,M}=

{201 cm，156 cm，154 cm，163 cm，1 488 kg}

为验证混合遗传算法对不同种类货物的适应性与有效性，从某航空公司获取真实货物数据进行验证。本次实验采集了三组不同批次的货物数据，先后输入混合遗传算法中进行实验。限于篇幅，表2仅列出部分货物信息。

表2 航空货物信息

由于研究的是不规则航空集装箱的货物装载问题，且针对的是真实货物数据，暂未有可以直接使用作为比较的对象，所以本文算法仅与传统遗传算法产生的装载方案进行比较。其中，传统遗传算法由拟人结合改进前的遗传算法得到。两种算法独立运行20次，对比结果见表3。可以看出，混合遗传算法所产生的方案不仅有着较高的空间和载重利用率，货物码放更合理科学，而且其求解时间较短。究其根源，混合遗传算法加入适应度尺度变换、最优解保存策略之后，算法的局部、全局优化能力得以提高。对第三组货物数据得到的仿真结果做统计，得到适应度函数随迭代次数发生变化的对比效果图如图4所示，混合遗传算法迭代到77代得到全局最优解，而传统遗传算法迭代到149代才能获得全局最优解，且性能较差。结果表明混合遗传算法可在较短的时间收敛获得全局最优解，搜索速度明显优于传统遗传算法，说明混合遗传算法具有更好的收敛性。

表3 两种算法对比结果

图4 优化性能比较

图5所示为混合遗传算法得到的装载效果图，图5(a)、图5(b)、图5(c)分别为三组货物数据的装箱方案。由图5可见，航空货物垛形形状较为规则，满足不规则集装箱的空间约束。货物之间的接触面积较大，摆放紧凑，满足了货物装载过程中垛形稳定的要求。

(a) 第一组

(b) 第二组

(c) 第三组图5 装载效果图

因为在实际的货物装箱过程中，既要给出直观的装载效果图，又要给出待装载货物的基本信息、具体码放位置，才能给人工码放、机器码垛提供直接的参考，为实时装载决策提供基础。故使用MATLAB 2014中的GUI(图形用户界面)设计一个AKE集装箱装载布局软件，在进行装载前设置算法参数，装载完毕后得到装载效果图和货物码放位置表。装载效果图能直观地反映货物在箱内的码放位置，评估货物布局方案的可行性，并据此判断方案的好坏；货物码放位置表给出了货物在箱内的具体空间位置，反映不同货物的装箱情况。软件的输入界面、输出界面如图6所示。

(a) 输入界面

(b) 输出界面图6 装载软件界面

5 结 语

针对不规则集装箱的货物装载优化问题，在考虑实际装载过程中体积、质量、重心、不重叠等约束的前提下，提出一种将拟人算法与改进的遗传相结合的混合遗传算法。基于多组不同批次航空货物数据的结果分析比较，证明了混合遗传算法对强异构型货物有着较好的装载布局效果，能够将货物按照其装载顺序合理地装载至集装箱中，并提高集装箱的空间利用率和载重利用率，缩短程序的运行时间，为研究不规则集装箱装载优化问题提供了解决思路。同时，设计一款装箱软件，以证实算法的实用性与有效性。