基于基本空间组合关系的舰载机机库布列算法

徐柱国，余明晖*，吴靳，戴明强

1 华中科技大学 人工智能与自动化学院，湖北 武汉 430074

2 海军工程大学 电子工程学院，湖北 武汉 430033

3 海军工程大学 基础部, 湖北 武汉 430033

0 引 言

舰载机作为航空母舰（以下称“航母”）的核心作战装备，其数量以及调运效率与航母综合作战能力紧密相关[1]。作为航母停放舰载机的主要地点，机库不仅需要尽可能布列更多数量的舰载机，同时布列方案还需合理满足舰载机出库调运需求。因此，需对舰载机机库的停放布列问题，即在二维机库平面内对不同种类舰载机（如战斗机、直升机、预警机等）进行站位划分，以提高机库停放的舰载机数量并保证舰载机调运效率。

国内外学者针对机库布列问题开展了较多研究。美国海军开发了航空数据管理与控制系统（aviation data management and control system，ADMACS）[2]以及舰船综合信息系统（integrated shipboard information system，ISIS），通过在舰载机上安装具有标识的GPS，可实时显示其位置状态信息，进而供相关人员手动调控站位，实现舰载机的布列；李耀宇等[3]对舰载机甲板布列调运业务进行分析，总结了国内外相应的研究情况；胡玉龙等[4]对机库进行了模糊建模以求解机库结构设计方案，其机库分段思想对布列问题很有帮助；张思[5]基于临界多边形（no-fit polygon，NFP）与遗传算法（GA），以舰载机数量为目标对该问题进行了求解；田大肥[6]将该问题转化成二维矩形装箱问题，以总调运路程为目标对问题进行了优化求解；Li等[7]通过对放置空间和飞机二维几何模型进行建模，开发了一种用于解决飞机布列问题的新型遗传算法。

从机库布列的2个优化目标（即舰载机数量更多与出动效率更高）出发，该问题可拆分为两个优化问题，即空间利用率优化与考虑调运效率的空间布局优化。空间利用率优化也称装箱问题，属于一种NP难度问题。机库空间狭小，将舰载机轮廓凸化处理会导致舰载机间隙过大，机库空间利用不充分，故若想布列结果有实际使用价值，需要将机库布列问题转化为连续空间下二维凹多面体的装箱问题，面积利用率越高，则放置的舰载机数量越多。二维装箱问题解决方法很多，但目前在舰载机布列问题上应用不多。如Burke等[8]基于轨迹线建立临界多边形，可以为复杂二维图形排样提供多样化的运算；Alvarez-Valdes等[9]基于分支定界算法，实现了对二维不规则形状图形的排样切割；这个问题与Kheirkhah等[10]在动态设施布局问题上的研究类似。考虑调运效率的空间布局优化对应于仓储、车库领域的车位排布问题。Abdelfatah等[11]采用线性规划对车库停车容量进行了优化；徐涵喆等[12]提出一种基于规则的车位排布启发式算法，得到了车位数较多且实用的排布方案。

舰载机不仅具有空间轮廓属性，还有转运的业务需求。从现有的研究结果来看，一方面是弱化舰载机调度需求，以舰载机数量为唯一优化目标的布列优化研究已取得不错的成果，另一方面是简化舰载机轮廓和布列算法，以调运总路程为唯一目标的研究也成果颇丰，但这两方面都因优化目标单一，算法结果与机库实际布列方案还存在很大的差距。目前，同时考虑这2个优化目标的研究尚属空白。本文拟通过分析机库布列问题的特点和业务需求，建立基本空间组合关系库，计算可能的空间组合，然后基于遗传算法优化布列顺序，建立以最大化布列飞机数目与最大化紧急出动舰载机数量为优化目标的多目标智能算法，优化机库甲板舰载机布列方案。

1 机库布列问题描述

1.1 机库环境描述

与飞行甲板相比，在机库甲板容纳更多舰载机的优化目标显得更为重要。机库甲板作为航母上空间最大的舱室，无起降跑道与舰岛等空间限制，布列自由度高、灵活性强、优化空间大。本文将以“尼米兹”级航母作为参考对象，研究舰载机在机库甲板的布列问题。

“尼米兹”级航母机库甲板的形状约为矩形，长208.5 m，宽33 m。其右舷有3部升降机，左舷有1部。升降机是舰载机在机库甲板与飞行甲板之间转运的唯一途径，其数量与位置不仅影响甲板之间的转运效率，而且还会对机库内的布列方案产生影响。在设计自动布列算法时，应当考虑升降机的因素，以提高布列方案的转运效率与业务合理性。本文以升降机数量多的一侧-右舷的升降机为节点，以相邻升降机间隔中线为界限，将机库划分为3个子舱室，分隔线同时也与航母机库防火帘的位置大体一致[13]，如图1所示。

图 1 “尼米兹”级机库环境Fig.1 Hangar environment of USS Nimitz-class aircraft carrier

将机库甲板划分成3个子舱室后，每个子舱室仅将其相邻的升降机作为调运出口。设n个单位的布列问题为Gn(x)， 划分成m个子舱室后，研究问题转化为如式(1)所示的问题：

1.2 舰载机布列资源分配方法

航母携带的舰载机数量多，种类也多。在美军进行的“高强度演习”中，“尼米兹”级航母共装载了F-14A战斗机、F/A-18C战斗/攻击机、EA-6B电子战机、S-3A反潜/加油机、E-2C预警机和SH-60B直升机等多种飞机，机库内还放置了少许小艇，这些统称为布列单位。为保证每部升降机都能出动特定类型的飞机，并保持升降机使用次数的均衡，本文将机库总布列需求分配至子舱室。

分配的规则为：

1) 各子舱室布列的舰载机总数量不宜相差太大；

2) 同一种类飞机不应过于集中。

根据上述规则，具体的分配算法流程如图2所示。

图 2 舱室需求分配算法流程图Fig.2 The process of cabin requirement allocation algorithm

上述流程图中，在对各类舰载机数量进行判定后，先均匀分配布列需求，再将无法均匀分配的剩余部分与其他数量少的布列单位合并为新的需求，进行二次分配。

1.3 舰载机几何描述与布列原则

现有研究普遍采用以五边形为主的凸多边形，甚至以矩形来简化舰载机轮廓，这就导致舰载机间距空间、舰载机机翼与机身所夹空间等空间资源可能出现浪费。本文设计的算法对舰载机几何轮廓无要求，可以在同一方案内采用多种简化或原轮廓的图形来表示舰载机。如图3所示，分别为简化轮廓战斗机（折翼状态）、原轮廓战斗机（展翼状态）、原轮廓预警机和原轮廓直升机（折翼状态），这些轮廓均可通过2.1节中描述的布列算法进行布列。

图 3 部分舰载机轮廓图Fig.3 Outline drawing of some carrier aircrafts

在本文研究工作中，图形处理算法引用了Burke等[8]的研究成果：基于移动碰撞算法，求解出NFP，从而实现二维排样。NFP是二维排样问题中关键的几何工具，可以用于求解图形间最优靠接位置、重叠判断、定位等。根据内靠接NFP原理，基于最左最下原则（bottom left，BL）、最左最下填充原则（bottom left fill，BLF）、最合适位置原则（best fit，BF）及最低重心原则等多种定位策略，可以为布列单位选取比较有优势的布列位置。

1.4 舰载机机库布列特点

舰载机在航母飞行甲板和机库甲板上的约束有许多差异。通过分析机库使用的特点，得出在机库划分舰载机站位时，需要考虑以下布列特点：

1) 机库内舰载机调运全部靠牵引车实现，不需要考虑舰载机发动机尾焰对机尾朝向的影响。

2) 单类型舰载机不应全部依赖于特定的升降机转运，以防止在该升降机发生故障时无法出动该类型舰载机。

3) 机库的主要功能是存储与维修，紧急出动的舰载机是用来替换飞行甲板上发生故障的舰载机。不需要紧急出动的舰载机无需考虑转运成本，这些飞机有足够的时间在机库内完成运动姿态的转换。

4) 紧急出动舰载机的尾部应朝向升降机，以便紧急出动时由牵引车将其推入升降机，并牵引至飞行甲板指定保障站位进行保障。

5) 紧急出动舰载机的尾部不应被任何障碍物阻拦，即无需移动其他舰载机便可将其移动至升降机，且应尽可能避免正反向行驶多次切换。

6) 在不考虑飞行甲板使用的情况下，每部升降机都能用来紧急出动舰载机。

7) 舰载机摆放在机库甲板规定的区域内。

8) 舰载机不可互相重叠。

9) 为方便管理与摆放美观，舰载机划分的站位需尽可能具有整齐划一、朝向有规律等特点。

2 机库布列问题建模

2.1 基于基本空间组合关系的舰载机组合生成算法

对于如航母机库等自由空间下布列多类不规则轮廓物体的问题，巧妙利用舰载机等单位不规则轮廓间的镶嵌，建立更紧密的组合关系是增加布列飞机数量、提高空间利用率的有效方法。舰载机的组合方式与业务强相关，涉及管理、安全、美观等多个因素。本文依据实际业务，以提取舰载机等物体常用的、可靠的组合方式为规则来建立基本组合关系库。

在基本组合关系库中以类型为节点，记录各类型间是否存在推荐的组合关系。将可以相互组合的布列单位放入集合中，再基于以整数拆分思想为基础的搜索算法计算集合内可能存在的组合分配方案。同时，基本组合关系库可以支持新机型的布列设计，使算法具有一定的可扩展性。

下面，以“尼米兹”级航母的主要固定翼舰载机机型为例来说明组合关系的建模。主要考虑F-14A，F/A-18C，EA-2C这3种机型，可能的组合关系包括对式和齐头式，不同机型的组合关系如表1所示。

表 1 部分组合关系Table 1 Partial combination relationship of aircrafts

部分组合类型样式如图4所示。

图 4 部分组合结果Fig.4 Partial combination results

以计算1架EA-2C和4架F-14A的组合方案结果集为例来介绍算法流程，流程图如图5所示。图中，“*”后面的数字表示该机型的数量。

图 5 组合算法流程图Fig.5 The flow chart of combinatorial search

表 2 结果集Table 2 The result set

多个布列单位组合成布列模块，各布列模块中布列单位的数量如表2所示。表2中，“F-14A*4”表示4架F-14A组合摆放，为1个布列模块，“F-14A*1+F-14A*1+F-14A*1+F-14A*1”表示4架F-14A单独摆放，为4个布列模块。两者的区别在于布列模块之间以最小包络矩形的形式堆叠，没有采用组合关系的4个布列模块堆叠导致相邻的“F-14A”的间隙空间不会被利用。提高面积利用率的唯一途径在于建立布列模块之间紧密的组合关系，即通过减少浪费面积来实现。

由于组合关系固定，基于同种组合关系组合成的布列模块内停机密度一定相等。

原问题为有限空间内多个不规则物体的二维连续排样问题，上述算法将该问题通过基本组合关系库离散化，将问题转化为了组合优化问题。在转化过程中，尝试从有限的合理组合关系来分析问题，将解空间由连续解空间离散化至可求解程度。被舍弃的解空间中不会存在满足业务需求的最优解。

2.2 组合布列优化模型建立

根据前面的研究，舰载机布列方案有2个优化目标：布列数量更多与紧急出动舰载机数量更多。通过对布列资源进行分析，由搜索算法得出的结果集中包含了该布列资源下全部的组合方案。组合方案中的元素被命名为布列模块，这在2.1节中已有介绍。通过为各模块编号，基于LB（left bottom）策略，按编号顺序迭代摆放至机库空间即可实现一个完整的布列方案。LB策略意为将需要放置的模块先向左移动至边界，再向下移动至边界。通过该策略实现摆放定位。通常LB策略会造成很明显的元素分布不均匀问题，但在本文研究内容中，由于布列模块内部停机密度固定、布列模块之间间隙基本相同，因此LB策略基本满足此业务需求。

根据总体业务优化目标以及布列中的约束条件，可得到优化问题的数学模型。

目标函数为：

约束条件为：

式中：S为机库甲板总空间；Si为编号为i的飞机所占空间，在机库内布列单位不仅不可互相重叠，也不可超出机库空间；f1(x)为所有布列单位占用的面积，其只与布列资源中的布列单位数量有关；Bt为t类型布列单位经路径规划模块判断后可直接出动的数量。飞机是否能够直接出动的判断逻辑是：单架舰载机在将其他布列单位视为障碍物且不超过边界的条件下，是否可以完成前往指定升降机的路径规划。

在这种情况下，路径规划只需要回答“可以”或“不可以”即可。“可以”的数量与优化目标f2(x)密切相关，而路径的长度优化从业务角度来看并无太大意义：机库内空间狭小，不同路径间长度差额的绝对值不大，不会对调运效率产生明显影响。本文基于Reed-Shepp算法实现路径规划进而完成逻辑判断。Reed-Shepp算法理论成熟，运算速度快，且具有考虑运动学约束等特点。对升降机附近的布列模型进行倒车路径判定可迅速评估布列方案的紧急出动能力。

当布列资源确定时，机库甲板内面积利用率也可同时确定。两目标优化问题此时成为单目标优化问题，即锁定了布列资源后只需要对f2(x)求解即可。

此时，对于确定了布列资源后的模型，有

式中：C为机库布列问题解集；D为组合方案集解集；E为布列顺序解集。

3 机库布列的多目标启发式算法设计

3.1 启发式算法设计

基于搜索得出众多组合方案后，需要对每个组合方案的最优布列进行优化求解。同一组合方案下各模块不同顺序的摆放会得到不同的结果，模块数决定了解空间大小。不同组合方案中模块数量n并 不相同，解空间的大小为n!。本文基于遗传算法来求解该模型。

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，其求解过程不受搜索空间的限制，也不要求解具有连续性，在组合优化问题上具有很大优势。遗传算法具有很强的鲁棒性，能够面对不同的解空间保持较稳定的求解效率。

下面，具体说明为求解布列顺序设计的遗传算法内容。

本文采用十进制编码方式，染色体长度值为模块数量m值的2倍。每个模块具有2个变量：布列顺序与布列角度。所有的模块只考虑垂直与水平2种摆放形式。某含有9个模块的组合方案的染色体编码为[(2,0),(3,1),(4,0),(5,1),(1,0),(6,1),(7,0),(8,1),(0,0)]，其含义为布列顺序(2,3,4,5,1,6,7,8,0)，布列角度编码0代表水平摆放，1代表垂直摆放。基于Abdoun等[14]的研究成果，本文采用“顺序交叉”（order crossover，OX）规则对染色体进行交叉操作。第1步，随机选择一对染色体（父代）中几个基因的起止位置（两染色体被选位置相同）；第2步，生成一个子代，并保证子代中被选中基因的位置与父代相同；第3步，先找出第1步选中的基因在另一个父代中的位置，再将其余基因按顺序放入上一步生成的子代中，如图6所示。

图 6 编码流程Fig.6 Encoding process

变异选用单点突变，即随机选取要突变的基因位点，然后突变成与剩余的其他基因不同的基因。

通过对布列方案中的每架舰载机（只计算F-14A，F/A-18C等战斗机型，不计算预警机、救生艇、直升机等非战斗机型）遍历调用路径规划算法，计算可紧急出动的舰载机数量，将其作为适应度值。

遗传算法流程图如图7所示。

图 7 遗传算法求解流程Fig.7 Solving process of GA

在算法运行中，若某一编码对应的布列方案因机库空间几何约束导致空间不足而无法完成放置，则会放弃该编码。通过将机库几何轮廓作为二维排样中的约束不断淘汰不合格的编码。

3.2 迭代调用算法实现两目标优化

当机库内摆放一定数量的舰载机时，利用遗传算法可以计算出最大紧急出动飞机数量以及其对应的布列方案。本文为遗传算法设置适应度阈值，当达到阈值时提前终止遗传算法，以使机库完全能够满足该数量布列需求下对于紧急出动的业务需求。终止算法后，在布列需求中添加一架默认的战斗机型，如F-14A或F/A-18C，继续进行布列方案探究。迭代多次后，混合算法能够输出布列数量与最大紧急出动能力平衡的布列方案。m个子舱室的满意解构成总机库的满意解。

两目标迭代算法流程如图8所示。

4 仿真实验

由文献[13]，得到美海军“尼米兹”级航母机库的布列图如图9所示。

图 8 迭代算法流程Fig.8 Solving process of iterative algorithm

图 9 “尼米兹”级航母机库布列方案Fig.9 The hangar layout scheme of Nimitz-class aircraft carrier

本文设计了“尼米兹”级航母在类似战斗模式下机库的布列需求，并对算法有效性进行验证。算法采用C++编程实现，运行在CPU为i5-6500(4核，3.2 GHz)、内存8 GB的计算机上。该布列需求包括7种布列单位，初始布列需求与美军方案保持一致，经过任务分配后得到具体子舱室的布列需求如表3所示。

表 3 舰载机机库基本布列需求表Table 3 Basic layout requirements of aircraft hangar

在本次算法运行中，设最大遗传代数Genmax=100，种群空间Popmax=50，变异率pm=0.02，交叉率pc=0.6，设置阈值为

式中：Ek为第k个舱室紧急出动的舰载机数量；Fk为第k个舱室拥有的升降机数量。每个舱室单独求解。

在算法运行过程中，优化算法表现出较好的收敛性，不同子舱室的求解时间接近，求解出的总布列方案如图10所示。

图 10 最终布列结果Fig.10 The final layout result

在计算美军布列方案利用率时，需将各舰载机占用面积替换为本文布列算法中同类型舰载机采用的轮廓的占用面积，以保证结果不受轮廓因素的干扰。经计算，得到美军布列方案面积利用率为36.54%。

在本文得出的方案中，各布列单位长、宽参数经过核对，符合实际尺寸。在计算中，通过多次迭代加入F/A-18C来增加布列数量，使机库总布列单位数量达到44架，其中F/A-18C为27架，面积利用率为53.46%，与美军布列方案相比提高了16.92%。各升降机均保证了一定的紧急出动能力。考虑到可能会因摆放规则而出现右上方区域利用率不够高的情况，可人工对生成的方案进行舰载机间距调整，使之分布均匀。

5 结 论

本文通过对机库环境进行分析，对舰载机常用摆放形式进行了归纳整理；通过对基本组合关系库进行组合关系搜索，实现布列资源预处理，得到了所有可能的布列区块组合；以布列面积利用率最大化与舰载机可直接出动数量最大化为目标，通过遗传算法对组合模块进行布列顺序优化，与美军布列方案对比验证了算法的有效性。通过研究，得到如下结论：

1) 本文提出的布列算法能够应对不同类型机库、不同布列需求下同类问题的计算与优化；

2) 基于基本组合关系库得到的组合方案使得布列结果具有较高的实用性、安全性与美观性；

3) 启发式算法不仅能够尽可能提高机库存放舰载机数量，同时能够保证舰载机紧急出动能力；

4) 可视化输出的布列结果，可以为机库管理员提供站位划分的辅助决策依据。

由于舰载机组合关系十分复杂，本文多以同类机型组合为主进行研究。基本组合关系库需要在后续的工作中继续丰富，同时组合的角度也可从离散化向连续化继续深入研究。目前，基本组合关系库需要用户手动输入，若能依据外形轮廓智能生成则更方便、更全面，更丰富的组合关系可以得到更优秀的布列方案。组合关系与舰载机实际业务密切相关，且不同战斗模式下机库对组合关系有不同的要求，特定区域对排样角度也有约束，需要建立更复杂的业务模型。此外，启发式算法的设计与优化空间巨大，与求解效率紧密相关，还需进行大量的研究。