航空物流运输物资组板堆码模型生成

李 欣，张 俊,王爱嘉，石红霞

（军事交通学院，天津 300161）

航空物流运输物资组板堆码模型生成

李 欣，张 俊,王爱嘉，石红霞

（军事交通学院，天津 300161）

以航空转运物资集装为背景，针对航空集装板物资堆码（组板）问题，运用空间分解与组合思想对堆码策略进行设计，利用自适应遗传算法完成堆码策略的数学实现和堆码模型的生成，并通过实例进行验证，为航运物资集装辅助决策系统和自动组板系统的研发提供技术支撑。

航空物流；物资组板；堆码策略；堆码模型

1 引言

航空物流是以航空运输为主要运输形式，借助现代信息技术，连接供给主体和需求主体，使原材料、产成品及相关信息从起点至终点有效流动的全过程。它将运输、仓储、装卸、加工、整理、配送、信息等方面进行有机结合，形成完整的服务供应链，为用户提供多功能、一体化的综合性服务［1］。其快速、高效、机动的特点，使其在战略投送、应急物资转运、急件运输等领域得到越来越广泛的应用。

航空货物运输主要采用全货机、客机或客货机三种运输工具，使用全货机和客货机转运物资时，一般都要使用航空集装器集装物资，如何将物资合理地集装码放到航空集装器上，是影响航空物流作业效率和生产效益的关键要素，也是航空货运处理的重要作业环节。目前，航运物资集装主要还是依靠人工经验作业，物资码放随意性较大、工作过程忙乱、劳动强度高，尤其在军事物流、应急物流中转运大批量物资时，这一问题更加突出。本文以航空集装板物资集装为例，研究物资堆码（组板）问题，拟建立物资自动堆码模型，为航运物资集装辅助决策系统和自动组板系统的研发奠定基础。

2 航运物资组板堆码问题描述

航运物资组板堆码问题可简化描述为：在一定约束条件下，研究待运物资如何在航空集装板上进行科学、合理、规范的堆码，使航空集装板空间、载重利用率最大，堆码物资重心偏移量最小，最终确定所需各类航空集装板数量及各航空集装板上物资的堆码模型。

2.1 堆码问题目标函数建立

记符号li、wi、hi、gi、vi分别表示待运物资的长、宽、高、重量和体积；Lj、Wj、hj、Gj、Vj分别表示航空集装板 j（j=1,2,…,m）的长、宽、高、最大载重和最大装载容积；xi、yi分别表示待运物资i的重心位置沿航空集装板长度方向和宽度方向距离航空集装板中心轴的偏差量。

航空集装板空间利用率函数为：

航空集装板载重利用率函数为：

航空集装板重心考察函数为：

因此，综合航空集装板空间利用率函数（1）、载重利用率函数（2）以及重心考察函数（3），根据多目标优化的加权系数法，定义本问题目标函数为：

式中，λ、β、γ分别为航空集装板空间利用率、载重利用率以及重心偏移量的权重系数，均为0-1变量，且λ+β+γ=1。当认为上述三者同等重要时，可令λ=β=γ=1/3。目标函数值越大，则堆码方案越优。

2.2 堆码问题约束条件分析

本问题的约束条件可分为两大类：第一大类为航空集装板的属性约束，是指与航空集装板装载空间和最大载重相关的约束条件，可分为航空集装板空间约束和载重约束；第二大类为物资堆码约束，是指为满足航空运输要求，物资堆码过程必须满足的约束条件，可分为物资码放位置约束、物资码放方向约束、物资堆码顺序约束以及物资重心约束。

航空集装板属性约束：

（1）航空集装板空间约束：各块航空集装板上物资总容积不得大于航空集装板的最大装载容积。

（2）航空集装板载重约束：各块航空集装板上物资的总重量不得超过航空集装板的最大载重。

物资堆码约束：

（1）物资码放位置约束：物资边界不得超过航空集装板装载空间限制，并且上层物资悬空部分不得超过其体积的1/3。

（2）物资码放方向约束：部分物资不可侧放或倒置，必须对这些物资进行码放方向约束。

（3）物资堆码顺序约束：物资堆码的顺序应该遵循从大到小、从重到轻的顺序，做到大不压小，重不压轻。

（4）物资堆码重心约束：物资堆码后，应该使整体的重心位于航空集装板中心或其附近允许的范围内。

3 基于空间分解和组合思想的堆码策略设计

为方便起见，将航空集装板装载空间近似看作为长方体，以航空集装板一角为坐标原点建立三维直角坐标系，以宽度方向作为x轴，以长度方向作为y轴，以高度方向作为z轴，如图1所示。

图1 航空集装板三维装载空间示意图

3.1 物资堆码顺序总原则

在航空集装板装载空间内进行物资堆码遵循以下原则：（1）依次沿左侧至右侧方向（即y轴方向）放置每一行；（2）然后沿从后往前方向（即x轴方向）放置每一列；（3）最后沿从下到上方向（即z轴方向）放置每一层。

3.2 航空集装板三维装载空间分解和组合

待运物资在航空集装板装载空间内平行于三维直角坐标系各轴放置，当第一个物资或物资组利用“占角原则”放入航空集装板装载空间后，该航空集装板装载空间被分解为右空间R、前空间L、上空间M这3个空间（除自身所占用空间外），如图2所示。被划分后的空间在子空间队列中排队等待，每次去除子空间队列中的一个元素作为当前的填充空间，按照后空间、前空间、上空间的顺序进行堆码作业，子空间队列如图3所示。

同理，每个子空间进行物资堆码的过程中，在摆放物资后同样被分解为3个子空间。这时，我们把原先3个子空间从空间队列中替换掉。对于不能摆放物资的子空间，则将其改命名为间隙。逐层考虑，当间隙满足以下条件，则间隙与同层剩余空间进行组合：

图2 航空集装板三维装载空间分割示意图

图3 子空间队列

（1）间隙与同层剩余空间左右相邻，且在同一水平面上，间隙X轴方向厚度（长度）小于等于同层剩余空间X轴方向厚度，则该间隙与同层剩余空间组合。

（2）间隙与同层剩余空间前后相邻，且在同一水平面，间隙Y轴方向厚度小于等于同层剩余空间Y轴方向厚度，则该间隙与同层剩余空间组合。

（3）同一层中多个间隙相邻，则令这些间隙组合构成长条形空间。

3.3 基于“层”空间分解和组合的“同类”物资堆码策略设计

这里的“同类”物资指单一品种、规格、包装形式的物资。对“同类”物资在航空集装板上进行堆码作业，空间搜索时以“层”为一个基本搜索单位，按照对“层”空间分解和组合展开，如图4所示。航空集装板装载空间按照待运物资类型规格划分为若干层，对每一层物资，改变物资摆放方向，通过2.1所给出的堆码优化问题目标函数考量此堆放方案的优劣，逐层考虑，直至航空集装板剩余装载空间中无法放入新的物资。

3.4 基于“块”空间分解和组合的“弱异类”物资堆码策略设计

“弱异类”物资指不同品种、规格、包装形式的物资，且类别不超过5种。由于“弱异类”物资中同样存在较多相同品类的物资，因此它的堆码策略可以借鉴“同类”物资堆码策略，但因其特性实际操作过程中也有一定差异。

“弱异类”物资堆码前，首次将待运物资分类排序，将同一品类物资分为一组，同时按照体积、重量以及耐压程度将各组排序，排序越小，越先堆码。首先，对排序第一的物资组按“同类”物资堆码策略进行堆码，完成堆码作业后再对剩余空间搜索时以“块”为一个基本搜索单元，按照对“块”空间分解和组合展开，如图5所示。由于下一组物资内部同样也是“同类”物资，因此这样的空间分解和组合方法保证了策略的有效性。重复上述步骤，直至航空集装板剩余装载空间中无法放入新的物资。

3.5 基于“三叉树”空间分解和组合的“强异类”

物资堆码策略设计

“强异类”物资指不同品种、规格、包装形式的物资，且类别超过5种。这类物资的堆码相比较前两类要复杂的多。本文借鉴“三叉树”空间分解和组合思想，对“强异类”物资堆码策略进行设计，如图6所示。

将当前物资所占空间作为三叉树的根节点，根据上文3.2航空集装板三维装载空间对航空集装板三维装载空间分解方法，得到R、L、M三个子空间作为三叉树的子节点，依次搜索R、L、M三个子空间摆放物资，新物资所占空间作为三叉树的新根节点，再次根据三维装载空间分解方法得到新根节点下的三个子节点，重复上述步骤，直至航空集装板剩余装载空间中无法放入新的物资。

图4 “同类”物资堆码策略

4 堆码策略的数学实现及堆码模型的生成

遗传算法是一种基于达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模拟，是一种通过模拟生物界自然进化过程寻找最优解的方法。遗传

算法与传统非智能算法相比较，具有运算简易、搜索过程灵活、搜索能力高以及隐含并行性等优点，因此被广泛应用于人工生命、自动控制、机器学习、生产调度、机器学习、组合优化等领域。

但是，在经典遗传算法中，交叉和变异操作采用固定的概率，不能很好地反映生物种群的进化过程，同时随着问题规模的不断增大，容易产生时间维数的灾难问题，不能比较简便有效地对大规模的航空转运物资组板堆码问题进行优化求解。本文中采用一种自适应遗传算法，使交叉概率和变异概率随群体的适应度自动改变［2］，使群体中优良个体得到有效保护，从而提高了进化速度，是解决航运物资组板堆码问题行之有效的方法。

图5 “弱异类”物资堆码策略

图6 “强异类”物资堆码策略

4.1 自适应算式设计

自适应遗传算法中交叉概率Pc、变异概率Pm随着群体的适应度而自动改变。当种群个体的适应度趋于局部最优或者趋于一致时，应该使Pc和Pm增加，以跳出局部最优；而当群体适应度较为分散时，应该使Pc和Pm减小，以保护优良个体的生存。同时，对适应度高于群体平均适应度的个体，应该选择较小的Pc和Pm，使优良个体得到保护，对适应度低于群体平均适应度的个体，选择较大的Pc和Pm，以提高新个体产生速度。这种调节方法能有效保护优良个体，提高算法的搜索效率。

同时，又为了避免某些适应度较大的优良个体之间的交叉概率过小而导致进化过程中根本不产生变化或变化过小，致使整个算法出现“早熟”现象，本文设计的交叉和变异概率的自适应算式如下：

其中：favg表示每代群体的平均适应度值，fmax表示群体中最大的适应度值，f'表示要交叉的2个个体中较大的适应度值，f表示要变异的个体的适应度值，pc1=0.95，pc2=0.6，pm1=0.15，pm2=0.01。

4.2 个体的编码及解码

个体的编码与解码是将问题的可行解在解空间与遗传算法所能处理的搜索空间相互转换的过程［3］，它们的实现是遗传算法应用成功与否的关键。

4.2.1 个体编码方法。编码是将问题的可行解从解空间转换到遗传算法所能处理的搜索空间的操作。正式编码前，首先对待运物资、航空集装板、堆码顺序编号以及放置方向进行如下的编码预处理：

（1）待运物资编号i=1,2,…,n；

（2）航空集装板编号j=1,2,…,m；

（3）堆码顺序编号按照自然数序列规定待运物资的堆码顺序，同一编号表示对应的物资之间无堆码顺序要求；

（4）物资码放方向编号，定义物资码放方向编号为1，如果物资码放方向为li//Li、wi//Wi、hi//Hi；定义编号为2，如果物资的码放方向为wi//Li、li//Wi、hi//Hi；定义编号为3，如果物资的码放方向为hi//Li、li//Wi、wi//Hi；定义编号为4，如果物资的码放方向为li//Li、hi//Wi、wi//Hi；定义编号为5，如果物资的码放方向为wi//Li、hi//Wi、li//Hi；定义编号为6，如果物资的码放方向为hi//Li、wi//Wi、li//Hi。

编码时应该考虑物资码放方向约束、物资堆码顺序约束和航空集装板的编号，每种堆码方案对应着一个编码长度为3n（n为待运物资的件数）的符号串个体

4.2.2 个体解码方法。解码是将问题的可行解从遗传算法所能处理的搜索空间转换还原至解空间的操作，按照编码的逆过程进行。

（1）基因si、sn+i、s2n+i之间具有一一对应关系，即基因si表示的具有某堆码顺序的物资i按照基因sn+i表示的码放方向堆码至基因s2n+i表示的集装箱中。

（2）si取值不同时，小编号值对应物资先堆码，大编号值对应物资后堆码，而同一取值对应的物资之间无堆码顺序要求。

（3）基因sn+i表示的物资码放方向按照编码预处理进行解码。

（4）物资在航空集装板上装载严格按照3.1物资堆码顺序总原则进行。

4.3 评价函数及停止准则

遗传算法在搜索空间进行搜索过程中基本不需要外部的信息，只需要以评价函数（适应度函数）为依据，通过个体适应值大小评价群体中个体所对应堆码方案的优劣。因此，适应度函数的选取就非常重要，将会直接影响到遗传算法的收敛速度以及能否准确找到问题的最优解。同时，我们通过适应度函数值的大小来评价解的优劣，适应度值越大，则得到的解越优。根据2.1所述，航空转运物资组板堆码优化不仅要求航空集装板空间利用率最大，同时还要考虑载重利用率最大以及重心位置等多个因素。本文为保证研究的完整性，将上述三者同时纳入考量范围，因此适应度函数为：

同时，对于违反航空集装板空间约束、航空集装板载重约束以及物资堆码重心约束的个体，在求解其适应值的过程中要给予相应的“惩罚”以确保符合条件的优良个体具有较大的生存机会。第gen代中个体的适应值计算如下：

上式中，pengen（q）为物资堆码“惩罚”函数；式（9）为物资堆码总体积惩罚函数；式（10）为物资堆码总重量惩罚函数；式（11）-式（15）为物资堆码重心惩罚函数；（xi,yi,zi）为航空集装板上物资i的重心坐标为待运物资在航空集装板上堆码后的重心坐标且限定范围分别为区间边界值；cgen为惩罚因子；μij为0-1变量，若物资i码放在航空集装板 j上，μij=1，否则μij=0。

本文以算法迭代到预定的最大次数M后终止，取种群中适应值最大的个体作为最优解。

4.4 自适应遗传操作过程

在本算法中，对种群中每一个体实行的遗传操作过程包括复制操作过程、交叉操作过程和变异操作过程。

（1）复制操作。在复制过程中可采用轮盘赌法或者最优个体保存法复制N个个体。

最优个体保存法基本思想是：父代种群内最优个体直接替代子代中最差个体，利用这一方法，能够保证遗传算法以1的概率收敛［5］。

（2）交叉操作。交叉操作是指在父代种群中以概率Pc对2个相互配对的个体（染色体）以约定方式相互交换部分基因，从而形成2个新的个体。为了确保物资码

放方向基因在遗传操作过程中的有效性，在交叉过程中采取基因s1-sn保持不变，基因sn+1-s3n参与交叉的策略，交叉操作如下所示：

（3）变异操作。为了在遗传操作过程中保证种群的多样性，避免算法“早熟”收敛甚至无法寻到全局最优解，对种群中个体采取变异操作。变异操作是将个体染色体编码串中的某些基因以概率Pm用其他的等位基因来替换，从而形成新的个体。对个体变异操作如下：在内按照均匀分布随机产生一个整数作为基因的变异位，并将该位的基因替换成对应物资码放方向编号间随机产生的一个编号值；在内同样也按照均匀分布随机产生一个整数作为基因的变异位，并将该位的基因替换为对应航空集装板编号间随机产生的一个编号值。

5 实例分析

某航空货运站有1 200件物资需要进行航空运输前的组板作业，物资在航空集装板上允许重心范围为物资码放方向任意。备选航空集装板型号如图7所示，部分待运物资相关特征数据如图8所示。

图7 备选航空集装板型号

图8 部分待运物资相关数据

应用本文提出的自适应遗传算法，群体规模N=100。最大进化代数为300。每代种群中个体平均适应度值与进化代数之间的变化关系如图9所示。

图9 平均适应度值与进化代数之间的变化关系

可见，自适应遗传算法总共迭代了300次，但是在迭代到第189次时便已经收敛到全局最优点。根据计算，共需要航空集装板11块，其中P6P板5块，P1P板3块，PLA板3块。其中，P6P板型第1块板物资堆码模型如图10所示。

图10 P6P板型第1块板物资堆码模型

6 总结

本文以航空转运物资集装为背景，针对航空集装板物资堆码（组板）问题，运用空间分解与组合思想对堆码策略进行设计，利用自适应遗传算法完成堆码策略的数学实现和堆码模型的生成，并通过实例进行验证。本文的研究结果可以为航运物资集装辅助决策系统和自动组板系统的研发提供技术支撑。

［1］魏然.航空物流服务链的特征及现状［J］.物流技术,2008,（1）.

［2］许光泞,肖志勇,俞金寿.应用自适应遗传算法解决集装箱装载问题［J］.控制与决策,2007,（11）：80-85.

［3］Pisinger D.Heuristics for the container loading problem［J］.European J of Operational Research,2002,141（2）：382-392.

［4］Mukhacheva E A,Mukhacheva A S.The rectangular packing problem：Local optimum search methods based on block structure［J］.Automation and Remote Control,2004,65（2）：248-257.

［5］Lipnitskii A A.Use of genetic algorithms for solution of the rectangle packing problem［J］.Cybernetics and Systems Analysis, 2002,38（6）：943-946.

Generation of Pallet Building and Piling Model in Aviation Logistics Transportation

Li Xin,Zhang Jun,Wang Aijia,Shi Hongxia
（Military Transportation Academy, Tianjin 300161, China）

In this paper, against the background of material containerization in airway transportation and in view of the pallet buildingand piling problem in the aviation logistics process, we designed the piling strategy following the principle of space decomposition andcombination, used the adaptive genetic algorithm to realize mathematically the piling strategy and generate the piling model, and at the end,validated the process in connection with an empirical case.

aviation logistics； material pallet building； piling strategy； piling model

F562；F259.2

A

1005-152X（2016）09-0085-06

10.3969/j.issn.1005-152X.2016.09.019

2016-08-09

李欣（1964-），男，天津蓟州人，教授，研究方向：军事物流；张俊（1991-），男，浙江慈溪人，硕士研究生，研究方向：军事物流信息系统与技术集成；王爱嘉（1994-），男，河北保定人，硕士研究生，研究方向：军事物流信息系统与技术集成；石红霞（1978-），女，河北保定人，讲师，研究方向：军事物流。