基于遗传算法和启发策略的军用物资飞机装载优化

周柯雯，姚爱祥 （军事交通学院，天津 300161）

基于遗传算法和启发策略的军用物资飞机装载优化

周柯雯，姚爱祥 （军事交通学院，天津 300161）

以军用物资飞机装载为研究对象，在考虑实际应用中的一些约束条件下，构造了军用物资的装载优化模型，提出了一种基于启发策略的遗传算法。该算法考虑了装载容积、装载质量及装载密度等约束条件。最后对一个案例进行了计算，验证了该模型的有效性。

军用物资；遗传算法；启发策略

0 引 言

航空军事运输，是军队利用运输机和直升机等航空器，通过空中航线输送人员、物资和装备的一种运输方式[1]。装载，是航空军事运输实施的重要阶段和环节。搞好飞机的装载，对保证飞行安全，防止货损货差，充分利用飞机的载货能力，提高装卸效率和运输经济性，具有重要的意义。根据物资和载运工具的数量，装载问题可以分为两大类：一是载运工具足够多，而待装物资有限，要求使用的载运工具数目最少；二是载运工具有限，而待装的物资远远超过现有装载能力，要求充分利用容积和载重，使载运工具利用率最高。本文选取第二类问题为研究对象，建立相应的数学模型，设计实现高效的求解算法。

1 军用物资飞机装载问题的描述与建模

1.1 问题的描述

有若干件待运军用物资，要求合理安排物资的组合，包括物资的装载顺序、装载方向和装载位置，使货舱能装入更多的物资。

在建立模型之前，作出如下规定： （1）军用物资简化为长方体，且几何中心为其重心； （2）物资及其包装良好，可以支撑承重和多层装载，且都运往同一个目的地； （3）不考虑前后货舱重量对飞机平衡的影响，以及油重、温度等对货舱重量的制约； （4）必须横装火箭弹和已经安装引信的炮弹，而其他军用物资可以横、顺混装。

军用物资在飞机装运时应保证：物资的顶部或四周与飞机内部结构之间的最小间隙不得小于150mm；对于货舱中没有过道的飞机，应设置应急通道，要求保持有一个最小净空间，这个空间设置在顺航向左侧，其尺寸宽×高为355mm×1 830mm或762mm×1 220mm；对于有过道的飞机，在该通道上不能放置任何物资。

考虑到飞机的配重，实际摆放物资的顺序是先摆放靠近空机重心的区域，后摆放靠近机头或机尾的区域。

1.2 模型建立

设V为货舱的最大可用容积，G为飞机的最大业载量，vi为待装军用物资i的体积，gi为待装军用物资i的重量，n为待装军用物资总数，m为装入货舱的军用物资数量。

建立如下优化模型：

式中：k1,k2,k3为权重系数，根据部队执行任务的具体情况，由经验确定，且满足k1,k2,k3＞0，k1+k2+k3=1。式 （6）为货舱容积约束，即装入货舱的物资所占用的体积不能超过货舱的最大可用容积；式 （7）为飞机业载量能力约束，即装入货舱的物资总质量不能超过飞机的最大业载量。

为了使所装货物的体积重量达到最优，一方面，应该找出使货物的平均密度最接近标准密度 （货舱限重/货舱体积）的组合；另一方面，要避免最接近标准密度的货物组合的体积和重量远低于货舱的装载能力的情况，即：货物还没有装满，它们的平均密度已经是最优的了[2]。

2 基于遗传算法和启发策略的算法设计

遗传算法是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法。通过给解向量编码、形成初始群，然后用变异、交叉重组、自然选择等算子，进行并行迭代，进而求得最优解。

2.1 编码与解码

通常采用二进制编码，把待装军用物资按一定的顺序排列并编号，取串S={W1,W2,W3,W4,…,Wn}，其中Wi的取值是0或1，若Wi为1，则编号为i的军用物资被装载。若Wi为0，则不被装载。例如，对一组货物数为8的装载问题，若某一装载方案的编码方式为S={1,0,1,1,0,0,1,1 } ，则解码后对应的解码方案：编号1、3、4、7、8的物资被顺序装载。

2.2 适应度函数

遗传算法对一个解的好坏用适应度函数值的大小来评价，适应度的值越大，解的质量越好。为满足实际应用需要，缩短算法的搜索时间，选择适应度函数应遵循尽可能快的得到最优解的原则。因此，本文采用适应度函数等于目标函数。

2.3 遗传操作过程

2.3.1 初始种群的选取

一般的遗传算法随机选取多条染色体，然后依据适应度大小排序，取出适应度较大的作为初始种群。为了提高初始种群的质量，可以将几种由启发策略生成的染色体加入初始种群中。这些启发策略包括：

（1）设ci为待装的第i个军用物资的价值，其价值密度为将所有待运物资价值密度的值按降序排列，然后依次将物资装载，直至违反约束条件为止。

（2）从部队所担负的具体任务出发，根据对物资的需求程度不同，将物资按特需、急需、一般排序，然后依次装载。（3）定义物资的价值空间密度为，将价值空间密度的值按降序排列，然后依次将物资装载。这种策略兼顾了价值密度和承重约束[3]。

（5）除此之外，将一些已有的运输方案作为优胜染色体也加入初始种群。

其他初始种群的染色体则采取在不违反约束的条件下随机生成。

2.3.2 选择操作

一般采用轮盘赌、随机遍历抽样、局部选择法等进行选择。这里同时使用比例选择法和最优保存策略[4]。按照轮盘赌方法选择中间种群中适应度高的个体复制到下一代中，使用最优保存策略进化模型 （Elitist Model），使当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换掉本代群体中经过交叉变异等遗传操作后所产生的适应度最低的个体。这既能保证适应度较高的个体遗传到下一代，又能保证有较高的全局收敛性。

2.3.3 交叉、变异操作以及倒位操作

交叉操作：本文采用双点交叉的方式。双点交叉是指在个体编码串中随机设置了两个交叉点，然后再进行部分基因交换。

变异操作：为了在遗传操作过程中保持群体的多样性，避免算法早熟收敛甚至无法寻到全局最优解，对个体采取变异操作。在 [ 1,n ] 之间按均匀分布随机产生一个整数作为基因W1～Wn间的变异位，并将该位置基因值替换为相对应的整数0或1。

倒位操作：所谓倒位操作是指颠倒个体编码串中随机指定的二个基因座之间的基因排列顺序，从而形成一个新的染色体。其目的主要是为了能够使遗传算法更有利于生成较好的模式。

2.4 算法步骤描述

（1）初始化进化计数代数t=0，最大进化代数为T

（2）按一定启发策略产生初始种群

（3）以概率P1进行个体间的交叉操作

（4）以概率P2进行个体变异操作

（5）以概率P3进行个体倒位操作

（6）计算种群中个体适应值，并更新最优个体

（7）按比例大小将适应度高的个体选择到下一代

（8）进化T次后，停止计算，输出此时的最好解作为所求得的最优解

表1 军用物资尺寸

应用本文提出的遗传算法计算，各项初始参数取值分别为：群体规模n=80，最大进化代数T=200，交叉概率P1=0.9，变异概率P2=0.1，倒位概率P3=0.01。优化装载的结果为：A物资100箱，B物资130箱，C物资42箱，D物资5箱，共装载277箱。飞机的总装载质量为49 830kg，占最大业载量的99.7%；总装载容积为169.68m3，空间利用率为99.8%；偏离标准密度值0.27，物资装载后，其密度占标准密度的99.9%。为了防止军用物资破损，在实际装载过程中需要用木板、覆盖物之类的材料来填补货物之间的空隙。

3 应用举例

设有如下军用物资 （见表1）要装入某型运输机中 （见表2）。试确定充分利用运输机运输能力的合理装载方案。

表2 某型运输机主要参数

4 结束语

飞机货舱的利用率，是货物重量和体积共同作用的结果。货舱的限重除以体积为货舱标准密度，所装货物的平均密度越接近这个标准密度，效果越佳。

要搞好军用物资飞机装载作业，充分发挥航空运输的优势，除了要有良好的运输设备和装载设备外，还应该提高飞机的利用率。采用基于启发策略的遗传算法对这类问题进行求解，方法简单易行，其结果可为从事航空军事运输工作的单位和个人提供科学的决策依据，从而大大提高航空军事运输装载工作的效率。

[1] 葛同民.航空军事运输[M].天津：军事交通学院，2004.

[2] 张劼，衡红军，杨晓雪.航空货运装载问题算法设计与研究[J].计算机工程，2005(7):28-30.

[3] 徐贤胜，王帅.基于遗传算法和启发策略的舰船装载方案[J].军事运筹与系统工程，2008(6):40-44.

[4] 周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，1999.

Cargo-transport Plane Packing Optimization of Military Material Based on Genetic Algorithm and Developmental Strategy

ZHOU Ke-wen,YAO Ai-xiang (Academy of Military Transportation,Tianjin 300161,China)

This paper studies the problem of military material packing by cargo-transport plane.Considering multi-constraints in applications,an optimizing stowage model is set up,and a genetic algorithm based on developmental strategy is presented in this paper.The genetic algorithm takes account of loading capacity,loading mass,loading density and other constraints.Finally,the practical calculation shows the method is effective.

military material;genetic algorithm;developmental strategy

E234

A

1002-3100(2010)09-0122-03

2010-06-13

周柯雯（1985-），男，山东安丘人，军事交通学院硕士研究生，研究方向：军事运输；姚爱祥（1983-），男，江苏盐城人，军事交通学院军事硕士研究生，研究方向：作战后勤保障。