航空集装板组板优化问题的混合遗传算法

孙世峰，刘永军，张　俊

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

航空集装板组板优化问题的混合遗传算法

孙世峰，刘永军，张俊

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

在满足航空集装板组板优化问题的约束条件下，结合顺序及摆放方向的因素，提出了一种混合编码的遗传算法，构造了体积利用率和载重利用率共存的多目标适应度函数，并利用AForge.NET开源框架实现了遗传算法的编程。

航空集装板；空间搜索；遗传算法；组板优化

1　引言

目前对于航空集装板组板主要依靠操作习惯和经验，组板具有很大的不确定性。若组板超重超限，就必须拆箱重新装载，增加了组板的时间，直接影响了货运的效率和成本。

类似于集装箱装箱问题，航空集装板组板优化问题也是一个NP-hard问题［1］，直接利用传统方法进行求解会因为问题规模不断增大而产生时间维度过长。遗传算法（Genetic Algorithm，GA）作为一种模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解算法，其基本思想简单，运行方式和实现步骤规范，具有全局并行搜索、简单通用、鲁棒性强等优点，特别适合求解问题的近似最优解［2］。本文结合航空集装板实际组板过程中的一些约束条件，提出了应用混合编码［3］的遗传算法解决航空集装板组板优化问题的方法。

2　航空集装板组板优化问题描述

航空集装板组板类似于集装箱装载问题，根据货箱的不同分为3类：（1）是物资的规格完全相同，即单一尺寸的物资装载问题，这类问题被称为“同类”问题。（2）是物资有不同的规格，这类问题被称作“强异类”问题。（3）是物资只有少数的几类，但是每一类的数量较多，这类问题被称作“弱异类”问题［4］。本文应用一种物资摆放空间位置和其方向一一对应的编码方法，尤其适合于解决“强异类”问题。文中物资所占空间指“盒组”形式的空间即一个或两个以上呈立方体形式的空间。

2.1目标函数及约束条件

2.1.1目标函数.记符号Lj，Wj，Hj，Gj，k分别表示航空集装板的长、宽、高和最大装载质量、数量。Li，wi，hi，gi，n分别表示物资的长、宽、高和质量、数量。则目标可描述为：

式中μ为0-1的变量，当不考虑载重利用率时，μ= 1；当不考虑体积利用率时，μ=0。

2.1.2约束条件

（1）物资和航空集装板的数量和种类：物资的数量和种类为本次待运物资数量和种类，航空集装板数量和种类为航空公司根据待运物资数量、种类和质量而下发给本次货运任务使用的航空集装板的数量、种类和载重。

（2）物资的装载容积：装载的物资总容积之和不得大于可用之航空集装板的总可用容积。

（3）物资的装载质量：单个航空集装板上的物资总质量之和不得大于单个航空集装板可承受最大质量。

（4）物资的装载界限：组装好的物资界限不得超过航空集装板的最大外形限制，物资垂直边界不得超过卡网兜的孔。

（5）物资装载的方向：所有物资的边必须平行于航空集装板的边。

（6）物资悬空约束：物资不得悬空，物资上下层之间必须完全接触。

（7）物资的承载能力约束：在装载过程中，货物的承载能力由货物本身的性质和包装盒的结构航空货运飞机装载问题研究决定，货物码放时要做到重不压轻，大不压小。

（8）物资编组约束：相同大小的物资应当放在一起，方便集装板组板作业。

（9）货物的配置位置约束：有些特殊物资不可以侧放、倒放，有些特殊物资不能承担重压，这些物资必须单独设定它们的配置位置。

（10）“物资”：均设定为立方体。

2.2装载策略

2.2.1航空集装板的空间划分。先利用占角策略在全部空间的左下角放入“物资组”或者单个物资，之后将航空集装板的剩余空间划分为正上方剩余空间M，右方剩余空间R和前方剩余空间L，如图1所示。

图1　空间划分示意图

2.2.2航空集装板的空间搜索策略。在空间搜索前将每一种型号的物资编号，记录其大小，数量，质量，名称，是否容许侧放等信息，放入集合中，称为物资集合。将每一种型号的航空集装板编号，记录其可用面积，限高，数量，质量，名称，载重等信息，放入集合中，称为航空集装板集合。

根据2.2.1航空集装板的空间划分，选择当前物资所占空间作为三叉树的根节点，划分出L，M，R三个空间，分别作为根节点的三个子节点，依次搜索L，M，R放入物资，物资所占空间作为三叉树的新子节点，重复分割搜索空间，直到没有物资可以放入或者航空集装板没有可利用空间为止。

3　问题的遗传算法

3.1个体的编码及解码

结合航空集装板物资装载的空间搜索特性，本文选用了基于多参数交叉编码，排列编码和实数编码混合使用的编码方式。

个体的编码方法：每种装载方案对应一个字符串，长度为2n，即S=S1，S2，…，Sn，Sn+1，Sn+2，…，Sn+i，…，S2n。基因S1-S2由排列编码实现，对以物资总数为限的元素进行排列所得，表示每个物资在物资集合中的位置。基因Sn+i-S2n由实数编码实现，单个基因对应的数值用一定范围内的一个实数来表示，表示物资的放置方向编号。放置方向编号规定为：编号为1，则物资的放置方向为Lj// Lj，wj//Wj，hj//Hj；编号为2，则货物的放置方向为wj//Lj，lj// Wj，hj//Hj；编号为3，则货物的放置方向为hj//Lj，lj//Wj，wj//Hj；编号为4，则货物的放置方向为lj//Lj，hj//Wj，wj//Hj；编号为5，则货物的放置方向为wj//Lj，hj//Wj，lj//Hj；编号为6，则货物的放置方向为hj//Lj，wj//Wj，lj//Hj。

个体解码方法：基因S1-Sn和基因Sn+1-S2n之间具有一一对应的关系。比如现有物资A，B，C，D，E各一个，基因Si和S5+i（i∈｛1，2，3，4，5｝）即表示该物资在物资集合中的顺序和其放置方向。

3.2适应度函数

遗传算法通过适应度函数计算每一个个体的适应值来判断该个体的质量好坏。适应度的值越大，解的质量越好，该个体越有可能保留到子代种群中。在航空集装板的装载中，不仅要考虑集装板的体积利用率，还要考虑其载重利用率。因此，根据处理多目标优化的加权系数法［5］，本文提出的适应度函数同上述目标函数一致。

3.3停止准则

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

3.4遗传的操作过程

选择：在选择算子中选择Elitism算法［6］，Elitism算法的基本思想是当前群体中适应度最高的个体不参与遗传算法中的交叉、变异等操作，而是用它来替换交叉、变异等操作给新种群带来的适应值最低的个体。

交叉：本文采用一种改进的两点交叉算法。在交叉过程中，［1，2n］间随机生成两个整数a1和a2（a1＜a2）确定父代交换的位置。若a2≤n则交叉在两个父代的［a1，a2］间进行；若a1＞n则交叉在两个父代的［a1，a2］间进行；若a1≤n，a2＞n，则交叉在两个父代的［a1，n］，［n+1，a2］间进行。

变异：为了使遗传算法避免过早收敛而陷入局部最优解中，对遗传算法采取变异操作。本文的方法是在［n+1，2n］中随机数作为该染色体的变异位，并随机生成一个［1，6］的数来替换变异位上的数。

4　航空集装板组板优化问题的编程实现

本文主要利用Andrew Kirillov开发的AForge.NET开源框架中的进化算法库（Evolution algorithms library）来完成对遗传算法的实现。

4.1主程序

主程序是遗传算法的主要部分，负责实现算法的体系结构。包括创建初始种群，设置迭代次数，适应值比较等功能。

4.2Chromosome类

Chromosome类包括染色体的编码，创建新的染色体，克隆染色体以及染色体的交叉，变异等操作。在染色体的编码中，通过对染色体构造函数的重写，达到混合编码的目的。

4.3FitnessFunction类

FitnessFunction类包括染色体解码，适应值的计算。通过对染色体的解码，确定染色体各个基因对物资摆放空间位置确定的作用，通过构造目标函数，达到适应值计算的目的。

5　小结

本文针对航空集装板组板优化问题提出了一种基于混合编码形式的遗传算法，解决了简化模型下航空集装板组板的求解问题。同时利用开源的遗传算法框架提供了航空集装板组板优化问题的编程思路，有利于推广遗传算法在空间规划设计中的应用。

［1］周献中，郑华利，田卫萍，等.指挥自动化系统辅助决策技术［M］.北京∶国防工业出版社，2012.

［2］边霞，米良.遗传算法理论及其应用研究进展［J］.计算机应用研究，2010，27（7）∶2 425-2 434.

［3］余游明，刘玉树，阎光伟.遗传算法的编码理论与应用［J］.计算机工程与应用，2006，42（3）∶86-89.

［4］David Pisinger.Heuristics for the container loading problem［J］. European Journal of Operational Research，2002，141∶382-392.

［5］胡贵强.多目标优化的遗传算法及其实现［J］.重庆文理学院学报，2008，27（5）∶12-15.

［6］王曙霞，朱三元，涂俊英.基于Elitism的改进免疫遗传算法应用研究［J］.计算机仿真，2010，27（6）∶230-243.

Study on Hybrid Genetic Algorithm to Solve Aviation Pallet-building Optimization Problem

Sun Shifeng，Liu Yongjun，Zhang Jun
（Military Transportation Academy， Tianjin 300161， China）

In this paper， upon the precondition of satisfying the constraints in the aviation pallet-building optimization problem， and inconnection with the sequential and orientation considerations， we proposed a hybrid coding based genetic algorithm， established thesuitability function aimed at both bulk utilization and load utilization， and at the end， used the AForge.NET open- source framework toprogram the genetic algorithm proposed in this paper.

aviation pallet； spatial search； genetic algorithm； pallet-building optimization

TP18；F562

A

1005-152X（2016）03-0174-03

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

2016-02-19

国家自然科学基金资助项目（70371186）

孙世峰（1993-），男，新疆乌鲁木齐人，研究方向：军事物流；刘永军（1971-），男，湖北钟祥人，博士，研究方向：物流与供应链管理；张俊（1991-），男，浙江慈溪人，硕士研究生，研究方向：军事物流信息系统技术集成。