多品种物资码垛方案生成算法设计及编程实现

刘振兴，吴兆东，张大鹏

（1.陆军军事交通学院 学员三大队，天津 300161；2.陆军军事交通学院 学员五大队，天津 300161；3.陆军军事交通学院 投送装备保障系，天津 300161）

1 引言

物资集装化运输是目前物流运输的主要形式之一，常见的集装容器有托盘、航空板、集装箱等。对托盘以及航空板而言，物资的码盘方式多数是依赖操作经验进行，这种方式对同一类物资或少品类近似物资比较适用，但对多品类物资，这种方法的不确定性增加，会产生重心不稳、空间利用率低等问题，进而影响了物流效率。

码盘优化算法一直都是集装化研究的热点问题。一个适用的算法，能够得到一个相对优化的组盘方案，节省时间，提高效率，为后续的物流环节做好铺垫。本文以航空板组板为例，研究多品种物资的组板问题，设计组板优化算法并通过java编程实现，得到自动堆码模型，为自动组板系统的研发提供思路。

2 航空板组板问题描述

多品种物资的航空组板问题可简化为以下描述：在一定大小的容器中，如何科学合理地码放物资，实现容器的空间利用率、载重利用率以及整体稳定性的最优化。

2.1 问题的数学抽象

将航空板视为具有一定载重量的立方体容器，其长、宽、高分别表示为Li，Wi，Hi（i=1,2,…），最大载重用Gi表示。待装物资视为立方体，长、宽、高、质量分别用lj，wj，hj，gj（j=1,2,3…）表示。以航空板的左上角为坐标原点，右方向和下方向为坐标轴正方向，表示物资的坐标。方案评价指标主要有空间利用率、载重利用率和重心偏移程度。

空间利用率函数：

载重利用率函数：

重心偏移程度函数：

分别给予上述评价指标α、β、θ的权重系数，取值在（0,1）之间，依据实际情况对码垛的要求进行取值。最后的考察函数为：

2.2 方案约束

其主要分为航空板约束和物资约束：

在航空板约束中，主要有以下约束：（1）空间约束，即一个航空板所装载的物资体积不得超过航空板的容量；（2）载重约束，一个航空板上所放物资的总质量不得超过航空板的承载能力。

在物资约束中，主要有以下约束：（1）码放位置，码放不得超出航空板的边缘；（2）码放方向，物资不得随意码放，仅考虑正确码放情况；（3）码放顺序约束，遵循大不压小，重不压轻的约束条件。

2.3 空间分割组合思想

2.3.1 空间分割。航空集装板作为容器，可视为一个空间。物资存放采用“占角原则”，放置在空间的左上角，并且可以形成3个独立的子空间，即右空间(R)、前空间(L)和上空间(M)。后续的物资均放入产生的子空间之中，并形成一个空间队列，如图1所示。

空间队列的排列顺序按照从下到上，从左到右进行排序，即摆放物资顺序是从下至上，从左至右，按层进行摆放。每放入一个新的物资时，则从空间队列中移出摆放物资的空间，并在空间队列中增加因加入新物资产生的新的空间。在码放下一个物资之前，先将队列空间按上述摆放物资的要求进行排序。

图1 航空板空间分割示意图

2.3.2 空间组合。在空间分割中存在部分相邻空间，如果仅仅考虑空间队列，则可能存在物资只有在跨空间的情况下才能够放得下。因此，在考虑队列空间的同时，在放不下物资的情况下，考虑空间的组合。主要分为空间浅组合和空间深组合。空间浅组合，就是将2个相邻且在同一水平面上的空间进行合并，如图2所示。空间深组合，是指多个相邻空间进行组合，组合出一个长条状的空间，如图3所示。

在进行空间组合之后，判断是否可以放得下物资，如果放得下，则更新队列空间，如果放不下，则取消更新，退出码放。因此，物资的码放流程如图4所示。

3 遗传算法设计及编程实现

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

3.1 方案的编码与解码

图2 空间浅组合示意图

图3 空间深组合示意图

个体的编码解码是将解空间和遗传算法能够处理的搜索空间相互转化的过程。这里将一组航空板和一批物资的组装方案视为一个个体。

3.1.1 编码。一个组装方案涉及待装物资编码、待用航空板编码、物资的摆放方向编码。编码预处理如下：

图4 物资码放流程图

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

（2）待用航空板编号：j=1,2,…,m；

（3）待装物资编号体现了堆码顺序，编号小的物资优先码放；

（4）物资码放方向编码采用1和2表示，1表示物资横向码放，即物资较长边平行于y轴，较短边平行于x轴。

依据方案设计可以得到一个编码长度为3×n的基因个体（S1，S2，S3，...Sn|Sn+1，Sn+2，...S2n|S2n+1，S2n+2，...，S3n），其中，前n个编码表示物资的码放顺序，取值在（1，n）之间，中间n个编码表示物资的摆放方向，取值为1或者2，后n个编码表示物资摆放在哪一个航空板上，取值在（1，m）之间。

3.1.2 解码。解码是将问题的可行解从遗传算法所能处理的搜索空间转化为实际方案，按照编码的逆操作进行。

（1）Si，Si+n，Si+2n表示一个物资以排序号Si，摆放方向为Si+n摆放在航空板编号为Si+2n的航空板上；

（2）物资i和物资j的Si+2n和Sj+2n相同时，表示两者在同一个航空板上，此时，比较基因Si和Sj来确定码放顺序；

（3）基因Si+n解码成物资在航空板上的码放方向；

（4）码放过程严格按照图4所示的流程进行。

3.2 遗传算法计算流程

遗传算法的计算过程基本上是不涉及到外部信息，只需要关注评价函数。在第二节中已经给出了评价函数，即式（4），作为遗传算法的适用度函数。

在解码过程中可能出现的不符合实际的情况增加适用度“惩罚”系数。一种情况是，当出现航空板所装物资超过了航空板的容积时，适用度函数z=z-10 000，通过这种方式剔除不合格的基因个体；另一种情况是所装物资超过航空板载重，适用度函数z=z-10 000。通过这样的方式在遗传算法中过滤掉不符合实际的情况。

个体基因遗传中，随机选择两个基因位置，其索引分别为a和b，将a和b之间的基因进行交换。基因突变，设置每次基因突变的位置个数，每个位置以概率p发生基因突变，对应的基因位置根据代表的编码意义，在对应的区间内随机变化。

为了确保算法收敛，将每一代产生的最优个体保存在下一代的种群中。

计算流程如图5所示。

图5 遗传算法流程图

3.3 编程及案例分析

3.3.1 编程实现。本文主要使用java语言，利用开发工具eclipseVE开发，根据上述算法，实现模拟航空组板的方案。在java编程中，将组板方案和遗传算法单独编程。待放物资用Good类表示，航空板用Plate类表示，空间用Space类表示。通过解码和编码将两者联系，并写一个工具类来计算组板方案和计算适应度。相关程序界面如图6所示。

图6 程序界面示意图

基于面向对象的设计思想，每个需要摆放的货物用Good类表示，集装板用Plate类表示，摆放货物的空间用Space类表示，最后生成的方案用PlanConcrete类表示，PGUtils类为遗传算法和具体摆放方案进行转换的工具类。

3.3.2 案例分析

（1）单一货物的堆码情况分析。利用单一货物，可以实现基本的堆码模拟生成。对于正方体形状的物资，码放的方式单一不用做多余工作。对于长方体物资，本文算法会考虑到物资的码放方向，进而优化前文所提到的规划目标，达到相对最优的情况。

以长0.5m，宽0.5m，高0.5m，数量为40的货物，航空板为PMC标准航空板为例，可以得到图7所示的组板方案，该图体现了算法的核心摆放顺序和摆放方式，即将航空板视为一个长方体，从左→右→上的顺序依次码放。

（2）多种货物、单一航空板堆码情况分析。对多种货物进行码放时，存在两种货物混合码放的情况。这里以宽和高相同、长度相差一倍的两种货物为例，具体如图8所示。可以看出，货物之间以相对规律的方式进行码放，并且存在混合的情况，基于遗传算法的特定，货物的码放方向存在一定的随机性。

（3）多种货物、多航空板情况。在本算法中，考虑了单个航空板容量不足，用多个航空板进行组板操作。案例数据见表1。

图7 单一货物的堆码模拟及数据示意图

图8 多种货物单一航空板堆码模拟及数据示意图

表1 多航空板、多物资部分组板数据

模拟结果与数据如图9所示。

因考虑整个组板方案的综合适应度，存在部分航空板空间利用率不够的情况。当存在此问题时，可以适当减少航空板的数量，再进行方案模拟。

图9 多航空板、多物资堆码模拟及数据示意图

在计算中，可根据实际情况调整重心、空间利用率和载重利用率的偏好，如对重心要求比较高时，可将计算适应度的公式中的重心部分的权重提高。该程序提供了数据输出功能，将计算结果，即每个物资对应的航空板及航空板上的坐标输出，向外提供接口。

4 总结与展望

本文基于遗传算法，探讨了多品种物资的码放问题，给出了3个评判指标和1个综合的适应度，并基于java语言编程实现，得出相对较优方案，为高适应的自动组板系统的操作提供数据支撑。但本文仅给出最后组盘方案，未考虑自动组盘系统中的物资输送顺序，也是下一步研究需要重点考虑的方向。