基于混合启发式算法的货物空运装配策略

张游天 金辰禹 刘汉威 吴珊

[摘要]根据三维装箱问题的特点，考虑货物存在不同的摆放方式、集装箱剩余空间最大利用率等多项影响因素建立了货物空运装配多目标约束模型，采用以遗传算法和模拟退火算法为主的混合启发式算法运行求解，快速制定出货物的装载布局方案，有效解决了在多约束下的货物空运装配策略问题。

[关键词]三维装箱问题;模拟退火算法;遗传算法;货物装运;空运;装配策略

[中图分类号]F560.8[文献标识码]A[文章编号]1005-152X（2021）12-0070-08

Air Cargo Loading Strategy Based on Hybrid Heuristic Algorithm

ZHANG Youtian1，JIN Chenyu1，LIU Hanwei2，WU Shan3

（1. School of Economics & Management，Dalian Jiaotong University，Dalian 116028;

2. School of Mathematics & Computer Application Technology，Jining University，Jining 273199;

3. School of Transportation & Logistics Engineering，Wuhan University of Technology，Wuhan 430070，China）

Abstract：In this paper，according to the characteristics of the three-dimensional packing problem，and considering the various factors such as placement of goods，and the maximum utilization of the remaining space of the container，etc.，we established a multi- objective constraint model of air cargo loading，used a hybrid heuristic algorithm mainly consisting of the genetic algorithm and simulated annealing algorithm to solve it，and for the purpose to quicken cargo loading layout planning，effectively dealt with the problem of air cargo loading strategy under multiple constraints.

Keywords：three- dimensional packing problem;simulated annealing algorithm;genetic algorithm;cargo loading and shipment;air transportation;loading strategy

0引言

随着全球贸易自由化与物流业的快速发展，航空货运进入了蓬勃发展阶段。航空货运相对于集装箱运输的成本竞争力和可靠性有所提高，空运相对于海运的平均价格已大幅度下降。国际航空运输协会（IATA）日前发布的全球航空货运定期报告预测显示，货运强劲的表现将会持续。为满足不断增长的航空货运需求，实现高质量的集装箱装载是目前急需解决的问题。研究货物的装载优化问题，对提高空间效率、节约运费、规范作业等有着积极的现实意义。

货物空运装运策略问题属于三维装箱问题（Three Dimensional Container Loading Problem，3D- CLP），应用面广，专业性较强，同時也属于NP-hard问题[1]。根据提供的数据和要求不同，三维装箱问题可以分成箱柜装载问题、背包装载问题以及容器装载问题。而一般在运输过程中存在不同规格箱柜装载问题、柔性集装箱问题以及装运最佳利润问题等，所以三种问题均有涉及，模型程序较为繁琐，且不同种类的货物量较大，因此在有限的时间范畴内可以获得问题的最优近似解而难以获得精确解。

1问题描述

1.1航空货物运输策略描述

在航空货物运输的准备阶段，由于存在各类不同的机型以及内部构造，差异性较大，因此将该因素考虑在三维装箱问题范围内，视为规格不统一的箱柜装载问题。且由于货运飞机在空中飞行时受到力学因素的影响，前、中、后舱需要保持一定载重比例，为了方便计算，需把各机型的货舱分离开来，将同机型的货舱看为有一定比例关系的独立箱柜，因此需要考虑其存在的间隙以及是否超重。

由于货物形态多种多样且毫无规律，为了方便规划装配，假设将其包装为长方体，将货物视为长方体安排装配。货物为长方体，因此需要决策其摆放方式，选择将长宽面朝下、宽高面朝下或长高面朝下。此外，由于货舱之间存在着连接关系，货舱互相受到约束无法自由转动，所以需要货物的摆放转动来确定货物在货舱内的状态，因此货物的摆放状态有六种方式，如图1所示。

一般情况下货物会从某角落开始摆放，如图2所示，由于重力影响需要从下往上进行摆放，且需要考虑其重心的稳定性，其重心点要落在承重货物的上方而非悬空，如图3所示。

在该类问题中，为了提高装运货物的装卸空间效率、货物安全程度等，加入集装箱元素，集装箱作为装运容器可以很好的将小型货物整理入内并进行装运，以此提高货运飞机的整体效用。集装箱分为普通集装箱和柔性集装箱。增加集装箱后，需要集装箱内的小型货物也按照上述的规则进行排列[2]，考虑其摆放方式、重心位置等，需要先挑选出符合小体积条件的货物，在集装箱内部进行排样，装运完成后将集装箱看为整体再在货舱内继续按约束摆放，如图4所示。

在此基础上，考虑到货物的价值和效益问题，空运货物的费用较高，难以持续、及时的供应货物，因此存在着货运周期。为了适当降低组织货源数量带来的风险，供应商一般会设置可靠性，将其设置为固定的百分比数值，从而预测利润最大值以及选择合适的装运策略。

1.2问题假设

（1）货物装载顺序约束。考虑到重力的影响，货物需要从最底层开始装，不存在直接放置在悬浮状态或顶部，尽量呈垛型摆放。

（2）货物需要考虑其重心状况，以免出现重心悬浮等违反物理常识的现象，并设定所有货物均为质量均匀的长方体且不会变形。

（3）假定所有货物具有很强的承重能力。

（4）货物在装载完成后至重新开舱取货之前不会存在任何移动，即忽略飞机斜度、惯性、摩擦力减小等任何会让货物移动的情况。

（5）货物与飞机的货舱之间呈正交分布，即各边与相应的货舱面对应平行。

2问题分析及模型建立

2.1货运飞机内货舱的装运策略分析

假设某个进出口公司需要将货物运到目的地进行销售，该公司去航空公司求助运输业务。航空公司现有大、中、小三种类型的货运飞机，且每种货运飞机都分为前、中、后舱，每个货舱都可以装载一定的货物，但其容积和载重是有限制的。考虑到飞机飞行过程中的安全和平稳，三个货舱中的货物需要成一定比例来装载，以免出现“头重脚轻”等情况。不同类型的货运飞机的货舱情况不同，需要选择合适的装运策略以尽可能地提高各自的货舱空间利用率，且不考虑货物装完，只装入部分货物即可。本文考虑到货物存在不同的摆放方式，因此将各种类的所有货物进行编号，每一件货物都有其表达式，将各货舱的利用率之和作为目标函数，限制各个货舱的承重和体积，并考虑同一架货运飞机内各舱之间的载重尽量符合承重比率以维持稳定，并将误差设为0.1，建立相关模型。

为了方便更好地建立模型，将飞机各货舱进行分割，大、中、小三种类型飞机的前、中、后三个货舱分离并编号为p，其中p₁为大型货运飞机的前舱，p₉为小型货运飞机的后舱。具体货舱编号如图5所示。

设需要载运的货物共有N种，且每种货物的编号为第n₁，n₂，…，n_n件。

2.1.1目标函数。模型的目标是实现各类货物在三架飞机货舱内装载后的空隙尽可能小，即在三架飞机货舱的总空间利用率最大，因此构建如下优化模型：

2.1.2约束条件

（1）货物在货舱内的体积和质量约束。为了防止其货物在单个货舱内质量大于其货舱的载重量，或其货物的体积大于其货舱的最大容积，约束如下：

其中，M_p和V_p分别表示第p个货舱的最大承重量和容积。

式（4）表示x方向即长度的约束，式（5）表示y方向即宽度的约束，式（6）表示z方向即高度的约束。

（3）重心约束。为了确保货物的重心处于正常合理状态，引入横向容许偏移量、纵向容许偏移量和货物和重心最大允许高度[3]，约束如下：

其中，Δ_a表示横向容许偏移量，Δ_b表示纵向容许偏移量，Δ_c表示货物总重心最大允许高度。为了简化模型，货物在装载完成后至重新开舱取货之前不会存在任何移动，即忽略飞机斜度、惯性、摩擦力减小等任何会让货物移动的情况，因此现定

（4）保证飞机平稳的约束。三个货舱内载重的物品重量需要与其最大载重成比例，否则会影响飞机的平稳性。现约束如下：

其中，P₁，P₄，P₇分别为大、中、小型飞机的前舱，比例约束误差最大不超过0.1。

综上所述，貨运飞机内货舱的装运策略优化模型构建如下：

2.2增加集装箱元素的货运装配策略分析

加入集装箱因素后，将小体积货物装入集装箱，集装箱与中大型货物一起进行装运，同时要求集装箱和飞机货舱的利用率尽可能大，且需要选择合适的机型而不再同时选择多种机型。该问题中存在两个目标函数，即集装箱的最大空间利用率和飞机货舱的空间利用率[4]。因此需要先通过约束条件界定小体积货物和中大型体积货物，并需要满足无集装箱状态下货物装运的部分约束，通过比较三种类型飞机的最大空间利用率，以选择合适的机型，并求出该型号货运飞机装运货物所用的最少架次。由于要求集装箱和货运飞机货舱的空间利用率尽可能大，因此可以参考无集装箱状态下的部分目标函数和约束条件。y为集装箱的型号，K_M为飞机的型号，M=（1，2，3），（P₁，P₂，P₃）∈K₁，（P₄，P₅，P₆）∈K₂，（P₇，P₈，P₉）∈K₃。

2.2.1目标函数。首先考虑小型货物在集装箱内的空间利用率，目标函数如下：

其次考虑中大型货物和集装箱在各种飞机货舱的空间利用率，目标函数如下：

其中，S_y为第y种集装箱的数量，G₁，G₂，G₃分

别为需要出动的大、中、小型货运飞机架次数量。ω为三种飞机取各利用率之和最大的数据为目标。

2.2.2约束条件

（1）小型货物的约束。对货物进行分类，将货物分为小型货物和中大型货物，约束如下：

若货物的体积大于等于2时，被定义为中大型货物;若货物的体积小于2时，则被定义为小型货物。

（2）小型货物在集装箱内的约束。该约束可以参考2.1.2节中货物在各货舱内的体积和质量约束，载重物品将货物更换为小型货物，承载空间将货舱更换为集装箱，因此不再赘述。

（3）集装箱体积的约束。集装箱除了普通的航空集装箱之外还有柔性航空集装箱，由于其材质为塑料制品，且规定集装箱为长方体，因此定义在一定的高度范围内，集装箱内部货物总高度则为柔性航空集装箱的高度，具体约束如下：

普通的航空集装箱

柔性航空集装箱

（4）质量和体积的约束。除了小型货物的重量之外，集装箱本身也存在着一定的质量，因此其质量为：

（5）飞机数量的约束。

其中，G₁，G₂，G₃分别表示大型、中型和小型货运飞机的数量，要求所有中大型货物的体积与集装箱体积之和刚好小于所有可用架次飞机货运体积总量之和。

综上所述，带有集装箱因素的模型构建如下：

目标函数：

2.3考虑货物效益问题的可靠性分析

在加入集装箱因素的基础上继续增加经济效益因素，选择合适的装运策略以实现效益最大化，同时考虑到市场对产品的需求是不确定的，为达到公司希望得到可靠性为95%的最大利润值，降低货物销售量的平均值来组织货源的风险，重新利用时间序列法预测货物需求量，在满足最佳利润下，采用3D 装箱程序求解，得出新的装运策略[5]。

考虑到数据的特性，首先在置信区间为95%的估计误差下，利用时间序列预测法得出各货物的需求量，考虑到对于本文所要解决的问题，对本文研究的预测需求量问题采用指数平滑法模型解决。

然后将更精准的需求量代替之前用货物销售量来组织货源算出的货物需求量并代入问题3最大利润模型得出新的装运策略。

2.3.1时间序列预测法模型的建立。设货物需求量时间序列为y₁，y₂，…，y_t，α为加权系数，0<α<1，一次指数平滑公式为：

式（22）是由移动平均公式改进而来的，移动平均数的递推公式为：

将式（22）展开，有：

由于加权系数符合指數规律，又具有平滑数据的功能，故称之为指数平滑。以这种平滑值进行预测，就是一次指数平滑法[6]。预测模型为：

即：

得出以第t期指数平滑值作为t+1期的预测值，则为货物需求量n。

2.3.2最大利润货运装配模型的建立。按照用前50个周期各种货物销售量预测出的货物需求量n，调整货物装配方案，以达到最佳的利润，设置目标函数如下：

2.3.3约束条件。由于装配策略是在加入集装箱因素装配策略的基础上，希望能够得到在可靠性为95%下的最大利润值，因此目标函数一样，需更为精准的预测出各类货物的需求量，同样需要考虑其稳定性、易装载、易分拣等情况，因此约束条件与前面相同，在此不再赘述。

3混合启发式算法设计

在无集装箱因素时，货运飞机装配策略问题视为规格不统一的货物装载问题，并考虑到重心稳定性，货物有三种不同的摆放方法，长宽面朝下，宽高面朝下，长高面朝下。而且每个货物又有三种不同的排放方法，所以就可以将10种货物看成90个变量。采用启发式算法，主要是基于遗传和模拟退火算法求解目标函数的最大值和最优解。

算法流程如下：

算法一：解决货物摆放问题

step1：保留每个货物的（x，0，0）、（0，y，0）、（0，0，z）三个顶点;

step2：求出所有的不重复点;

step3：求步骤一和步骤二的交点;

step4：算出最前沿的这些点的位置即可。

算法二：分类打包程序算法

step1：对可能出现的超高货物进行处理;

step2：按照尺寸进行分类，记录分类结果，如果x，y，z相同则为同一类;

step3：对分类结果按照每类的个数大于1或等于1进行分离并且记录;

step4：对个数大于1的种类，调用同类装箱算法进行打包;

step5：对未达到优化目标的种类，更换摆放方式，即重新制定货物的长、宽、高之后，再次进行打包。

加入集装箱元素后，以装配体积为2m³以下的货物为例，先在集装箱内进行优化摆放，通过随机模拟来寻优，采用主装箱算法求解。

step1：打包，将体积在2m³以下的货物在集装箱内按照最优摆放方法摆放后打包;

step2：对打包后的集装箱和未打包的货物进行装运;

step3：解包，将最优化摆放方式解码;

step4：评价。

再增加经济效益因素，并选择合适的装运策略以实现效益最大化，同时考虑到市场对产品的需求是不确定的，采用3D装箱程序[7]。

step1：进行筛选，除去不满足约束的集装箱，最后将该集装箱放入surplus_box;

step2：如果PATH为空，设置初始PATH，并判断货物的高度是否超出货车的高度;

step3：若当前所有的箱子高度都超过舱位高度，则直接输出，或者当舱位被装满或是货物被装完，停止，统计未装运的集装箱;

step4：统计下一步可行的落脚点，统计所有货物的上顶点，用于判断支撑面积，如果支撑面积超过底面积的80%，保存新的箱子;

step5：进行解包以及评价。

4实例分析

进出口公司需要销售的货物共有WH1-WH10十种，每种货物都被简化为立方体形状，货物的属性，即尺寸、体积、重量、运输单价是已知的。收集公司之前的平均周期销售数量和销售价格，飞机货运成本为销售额的40%，具体见表1、表2。

一周期内貨物若没销售完，则剩余的货物按照其销售价的30%甩卖，且在加入集装箱元素后，小体积的货物（2m³以下）需要装在集装箱中，集装箱为长方体且有厚度5cm，需要选择合适的方法将小体积货物装进集装箱，再将集装箱与中大体积货物装运上货舱，集装箱的具体数据见表3。

根据所提出的模型和算法，利用matlab进行求解。考虑到实际情况，飞机货物装运货舱的承重比率存在一定的误差承受能力，无需严格按照比率精准配重，因此将符合承重比率设置为误差0.1。得出相应货物摆放方案见表4，且在加入集装箱因素后，选择使用飞机型号为大型货运飞机，且至少两架次，预估最大利润值为6 914 380元。

表4中，2号、6号、7号和10号货物经判定为小货物，需要装配至集装箱内进行运输。以在大型飞机的前舱为例，表示装运2号集装箱10个，3号集装箱9 个，5号集装箱20个，7号集装箱10个。

由于精度原因，考虑的每件货物和集装箱摆放方式不再列出，仅描述出该件货物和集装箱所在的位置。其中c1-c10为10种不同货物的数量，p11- p13为第一架大飞机前舱、中舱、后舱中装运各货物的数量和集装箱数量，p21-p23为第二架大飞机前舱、中舱、后舱中装运各货物的数量和集装箱数量，y1-y7为7种不同集装箱的数量。

5结语

本文根据三维装箱问题的特点，考虑货物存在不同的摆放方式、集装箱剩余空间最大利用率等多项影响因素，建立了多目标约束模型，采用多种算法结合求解，快速制定出货物的装载布局方案，有效求解三维装箱问题。本文通过编程方法，对具体不同问题给出了相应装运方案，为复杂三维装箱问题装载过程提供了智能的决策指导，同时模型考虑到诸多现实因素，可应用于飞机救援物资运送、工厂装箱等多项现实场景中。

本文在对三维装箱问题策略研究上仍存在一些问题，第一，仅考虑了部分约束条件，影响现有研究成果的实用性。第二，在假设前提下进行简化处理，得到优化后的模型，降低了三维装箱问题本身的复杂程度，但会造成改进后的模型出现失真的现象，使计算结果应有的实用性及可信性降低。第三，根据集装箱三维装载自身的复杂性和特殊性，不规则货物与不规则集装箱装载、更多目标与约束等问题有待进一步研究。针对上述问题，三维装箱问题在未来一段时间还有较大的研究价值。

[参考文献]

[1]王祎楼.基于货物组合的三维装箱启发式算法[J].物流工程与管理，2018，40（12）：73-75.

[2]张钧，贺可太.求解三维装箱问题的混合遗传模拟退火算法[J].计算机工程与应用，2019，55（14）：32-39，47.

[3]杜振，宫会丽.解决约束三维装箱问题的混合粒子群算法[J].计算机光盘软件与应用，2014，17（22）：115-116.

[4]张德富，彭煜，张丽丽.求解三维装箱问题的多层启发式搜索算法[J].计算机学报，2012，35（12）：2 553-2 561.

[5] YARU S，et al.A hybrid chemical reaction optimisation algorithm for solving 3D packing problem[J].International Journal of Autonomous and Adaptive Communications Sys- tems，2021，14（1-2）.

[6]谢英.基于时间序列和灰色预测的原煤产量预测[J].煤炭技术，2021，40（6）：221-224.

[7]张德富，魏丽军，陈青山，等.三维装箱问题的组合启发式算法[J].软件学报，2007（9）：2 083-2 089.