运输机群货物装载方案生成方法

刘宁君 王立新 潘文俊

（北京航空航天大学 航空科学与工程学院，北京100191）

随着航空运输的快速发展以及运送物资的大型化与多样化，空运任务的强度也在不断增大.对于一个同时使用多种型号运输机的航空运输机群，如何合理地安排机群的货物装载方式，有效地利用有限的运输资源并节约运输成本，成为当前迫切需要研究解决的难题.国内目前主要采用人工规划的方法进行装载，这一方面费时费力，另一方面也难以得到特定优化指标下的最佳装载方案.若采用自动算法来生成机群的装载方案，则可极大地提高机群运输的效率.

由于国内刚开始关注这类问题的研究，尚检索不到相关的研究成果文献.国外可参考的装箱算法有“最佳舱段适应法”（BFL，Best Fit Level）［1］、“宽度排序试验法”（CLS）［2］以及“双边插入法”（FC，Floor－Ceiling）［2］等.但这些参考文献均未给出上述算法的完整介绍，且方法仅限于单机货物的装载，也未考虑如何进行货物重心位置的调整，以保证运输机的飞行稳定性与安全性等具体问题.针对现有研究工作中尚存在的这些问题，本文开展了运输机群货物的装载方法研究：首先确定了机群货物装载的顺序，其次，生成了各架飞机货物装载的初步方案，然后对货物的重心位置进行了纵向和横向的调整，最后按照特定的优化指标，优选出运输机群的最优装载方案，从而形成了一种较系统的运输机群货物装载方案生成的新方法.

1 机群货物装载方案

为机群装载货物时，需先将货物分类，再依次为单架运输机分别进行装载.通过改变机群的装载顺序，并对不同的装载顺序进行预装载，可以生成各种不同的装载预案.对所有得到的装载预案进行分析、比较和筛选，可最终优选出满足给定指标的运输方案.

1.1 货物的分类

为了方便阐述，本节假设运输机群由甲型、乙型和丙型3种运输机组成，且无论从可运送货物的体积还是重量来说，它们的运载能力都存在甲型＞乙型＞丙型的关系.在装载之前，先按照机型的运载能力，把待运的k件货物归纳到如下几个集合中：

式中任意一个不等式不满足，则意味着货物大小超过货舱尺寸或者重量超过运输机载重上限，因此这件货物不能列入相应的集合.

若S所有＝S甲型（即不存在机群中最大运输机都无法运送的待装货物），就可以对货物进行分类，生成货物集合S1，S2，S3.仅可由机群中最大的运输机运送的货物归入S1中；可以由机群中最大和第2大（但不能由第3大）运输机运送的货物归入S2中；仅可由第3大运输机运送的货物归入S3中，即：

当运输机群包含的运输机型号多于3种时，可同理生成S1，S2，S3，…，Sn（n为型号总数）.

1.2 机群装载顺序的确定

采用不同的装载顺序，在进行预装载之后即可产生不同的装载预案.在生成装载顺序时，应注意以下两点：

1）不同顺序的总数要合适.数量过大会使得计算时间过长，过小会导致最终优选出的运输方案不接近实际最佳方案；

2）不同顺序之间不能过于相似，否则生成的不同装载预案也会比较相似，不利于比较和优选.

一般来说，随机生成足够数量的装载顺序即可满足以上要求.生成顺序的数量应按计算能力和机群组成情况具体分析；运输机型号和数量越多，顺序数也应越大.

1.3 不同装载预案的生成

装载顺序确定后，就可以对每个装载顺序按照如下的方法进行程序预装载，以生成相应的装载预案：

1）按照装载顺序选定需装载的运输机；

2）从前面生成的S1，S2，…，Sn中选择其中能装入当前运输机的所有货物集合；

3）在2）中选择的一个或多个集合中，优先选择货物较大的集合，并装载其中的货物.装载时，应将一个集合中的货物按照长度递减的顺序逐件尝试地装入运输机，每件货物的具体装载方法在第2节详细介绍.若此件货物能被成功装入，则将它从所属集合中去除；

4）运输机装满后，需要对机舱货物进行重心位置的调整.调整过程中需要从运输机货舱中去除的货物，应将其重新归入其原属的集合（即S1，S2，…，Sn其中一个）中（具体调整方法和步骤在第3节中介绍）；

5）如果重心位置调整失败，则说明该装载顺序不可行，不能产生有效的装载预案.这时可以对下一个装载顺序进行预装载.如果所有货物都已装载完毕，则表明这个装载顺序已经顺利完成，成功产生了一个装载预案.

1.4 最终运输方案的生成

生成了不同装载预案后，每个预案中所有飞机装载的货物重量也就随之确定，这时就可根据设定的优化指标计算出机群在执行任务时耗费的成本.一般使用机群的总耗油或总耗时作为优化指标，二者分别体现了机群执行空运任务中的燃油成本和时间成本.耗油或耗时量指标即为机群中各架运输机的耗油或耗时量之和，每架运输机在不同指标下的优化航迹和飞行成本算法在参考文献［3］中已详细阐述.

确定不同装载预案各自耗费的成本后即可确定成本最低的为最优预案.最优预案的货物装载方式和各架运输机相应的航迹可用于确定最终的运输方案.

2 单机货物装载算法

在飞行条件下，运输机舱内的货物一般不能多层堆叠［2］，但可以在地板上自由排列.这意味着运输机货物装载是一个需要考虑货物重心位置安排的特殊二维装箱问题.本文提出的单机货物装载算法是在综合BFL装箱算法［2，4］和CLS装箱算法［2，5］二者优点的基础上加以改进而形成的，前者对尺寸相差较大的货物都适用，后者能通过对货物按宽度排序而节约空间.其大致思路为对运输机货舱每个舱段使用FC法［2］装入货物，并在装入过程中将货物按宽度排序，以尽量节省空间.对一件待装的货物（总重应小于运输机的载重上限），具体装载步骤如下：

1）为装入货舱的第1件货物建立一个舱段，并将其靠在货舱左边装入，见图1a；

2）将后续装入的货物放置在舱段后方（朝机尾的方向）已置货物的右边，见图1b.如果空间不够，就将货物翻转90°放置在舱段右前角［4－5］，见图1c.如果右前角已放有货物，可将要装入的和右前角已有的货物按照宽度递增的顺序从左到右排列，如图1d所示；

图1 装载方法示意图

3）如果步骤2）中还无法装入货物，就建立一个新舱段，如图1e所示，后续货物可以往这个新的舱段内装载.如果运输机货舱的剩余空间不足以容纳新的舱段，即货舱空间已被用尽，则待装货物无法装入此运输机.

由于传统的BFL和CLS算法都没有考虑舱段位置的安排，可能会出现货物纵向总重心位置大幅度偏离允许范围的情况，如图2a所示.这个问题可通过结合人工装载中常用的“金字塔装载法”［6］来解决.具体做法为：在建立第1个舱段时，将其布置在纵向重心最佳位置处，而之后的舱段则在这个舱段前后两边交替建立；此外，有新的货物要装入时，优先考虑将其装入靠近纵向重心最佳位置处的舱段中；如果不能实现，再考虑距离稍远的舱段.这样操作之后，生成的舱段安排如图2b所示.

图2 不同的装载算法对舱段生成的影响

3 舱内货物重心位置调整

为了保证空运飞行的安全，运输机舱内货物的总重心位置在机身的纵、横两个方向都必须处于限定的范围之内［7－8］.本文采用的重心调整方法为先调整机身纵向（x方向，如图1左边所示的坐标系中）的重心位置，之后再调整横向（y方向，见图1）的重心位置.这是因为在调整纵向重心位置时，有可能需要去除货舱内的某些货物，这对货物的总体横向重心位置会有影响，而调整横向重心位置时无需去除货物，因此不会引起纵向重心位置的改变.

3.1 纵向重心位置调整方法

如果将所有的舱段前后无间隙排列形成一个“大舱段”（见图3），通过前后移动“大舱段”就可非常有效地调整纵向重心的位置.此外，通过卸除部分货物也可以调整重心的位置.具体调整方法如下：

1）使所有舱段前后连在一起，形成一个“大舱段”，然后将大舱段在货舱内前后移动，如图3所示，直至货物重心调整至合适位置；

2）如果上一步操作还不能调整好重心位置，就选取位于重心位置偏离方向上最末端的舱段，在舱段中逐件卸除重量最小的货物，直到货物总重心位置满足要求为止.

图3 大舱段前、后移动的情况

3.2 横向重心位置调整方法

横向重心位置的调整方法是对某些舱段进行左右翻转（如图4所示），这一调整对纵向重心位置无影响.一个舱段左右翻转后产生的滚转力矩是原来的负值.通过左右翻转部分舱段，可使得所有舱段产生的滚转力矩之和尽量接近0，从而消除或减小货物产生的不对称滚转力矩，以保证飞行的稳定性和安全性.

图4 舱段左右翻转示意图

消除或减小货物在货舱内产生的不对称滚转力矩即是使L取最小值，具体步骤如下：

1）找出所有Lp为负值的舱段并将其翻转，这样所有Lp都变为正值；

2）将Lp按从大到小的顺序交替放入两个数列和中，再将｛cn｝倒序接在｛bn｝之后，组成数列｛dn｝.这样｛dn｝应该有“两头大，中间小”的特征；

3）将｛dn｝从中间某位置分成两个子数列，使二者包含的滚转力矩元素之和尽量相近，然后将其中任意一个子数列中元素的对应舱段进行翻转.

通过以上步骤可使L取得最小值，即货物在

设待调整运输机在装载时被分成了q个舱段，其中第p个舱段产生的滚转力矩为Lp，其值的正负代表力矩产生向右或向左滚转运动的趋势.这样所有舱段产生的滚转力矩之和为货舱内产生的不对称滚转力矩最小，这样就完成了横向重心位置的调整.

4 算例与分析

本文对一个典型的运输任务，采用机群耗油总量作为优化指标进行了计算分析.任务中的航程为1 008km，机群组成为 Y－7，Y－8，IL－76各3架，货物信息如表1所示.

表1 货物信息

经过试算，算例中一共随机生成了115种不同的装载顺序，在此装载顺序数时计算效率较高.经过比较选出的最优方案使用了一架IL－76、两架Y－8和一架Y－7运输机，装载顺序为IL－76→Y－8→Y－8→Y－7.在装载每架运输机时，各货物的装载优先级别按照其长度递减排序，即为卡车→货箱1→小车→货箱2→货箱3→货箱5→货箱4→散货.各架运输机的耗油量和载重量见表2.

表2 运输机耗油量和载重量

在装载计算过程中，对Y－7和IL－76运输机内的货物进行了纵向重心位置调整，调整后货物紧凑地排列在货舱中部；对所有运输机都进行了货物横向重心位置调整，调整后各运输机内货物在横向分布比较均匀（如图5所示）.由于使用了金字塔装载法，每架运输机中较大、较重的货物相对更靠近货舱中部.

图5 最优方案中各运输机的装载图

采用文献［3］给出的计算方法，图6给出了不同装载预案飞行用油总量的分布.从图中可以看出，不同的装载预案之间耗油量相差很大，有约55%的预案的用油量比最优方案多近20t，几乎为最优方案用油量的1.5倍.由此可见，本文提出的货物装载生成方法能有效地对不同装载预案进行优化，节省可观的运输资源，极大地降低运输成本.

图6 不同装载预案飞行用油总量分布

5 结 论

本文较系统地提出了一种运输机群货物装载方案生成的新方法，可实现的主要功能有：

1）自动将待运货物分配到运输机群的各架飞机内，并按照指定的优化指标（一般为耗油量或者耗时量）生成接近最佳的运输方案；

2）快速、自动地生成货物在运输机货舱内的排列方式，生成的排列方式空间利用率较高、货物重心位置易处于允许范围内；

3）在货物重心位置处于允许范围之外时，能够在纵向及横向调整货物重心位置，使其移至允许范围之内，从而可保证飞机空运飞行的稳定性与安全性.

（

）

［1］Mongeau M，Bès C.Optimization of aircraft container loading［J］.IEEE Transactions on Aerospace and Electronic Systems，2003，39（1）：140－150

［2］Heidelberg K R，Parnell G S，James E Ames IV.Automated air load planning［J］.Naval Research Lagistics，1999，45（8）：751－768

［3］周堃，王立新.大型军用运输机的飞行航迹优化［J］.北京航空航天大学学报，2010，36（9）：654－658 Zhou Kun，Wang Lixin.Vertical flight trajectory optimization of heavy military airlift aircraft［J］.Journal of Beijing University of Aeronautics and Astronautics，2010，36（9）：654－658（in Chinese）

［4］Gehring H，Menschner K，Meyer M.A computer－based heuristic for packing pooled shipment containers［J］.European Journal of Operational Research，1990，44（2）：227－228

［5］Lodi A，Martello S，Vigo D.Neighborhood search algorithm for the guillotine non－oriented two－dimensional bin packing problem ［C］／／Voss S.Meta－Heuristics：Advances and Trends in Local Search Paradigms for Optimization.Boston：Kluwer Academic Publishers，1998：125－139

［6］Lodi A，Martello S，Vigo D.Heuristic and metaheuristic approaches for a class of two－dimensional bin packing problems［J］.Informs J Comput，1999，11（4）：345－357

［7］Kaluzny B L，David Shaw R H A.Optimal aircraft load balancing［J］.International Transactions in Operational Research，2009，16（6）：767－787

［8］Heidelberg K R.A bin packing algorithm for cargo conveyance systems［M］.Virginia：Virginia Commonwealth University，1995