-
舰载机作为航空母舰(简称“航母”)的核心作战装备,其数量以及调运效率与航母综合作战能力紧密相关[1]。作为航母停放舰载机的主要地点,机库不仅需要尽可能布列更多数量的舰载机,同时布列方案需要合理满足舰载机出库调运需求。舰载机机库停放布列问题,即在二维机库平面内对不同种类舰载机(如战斗机、直升机、预警机等)进行站位划分,以提高机库停放的舰载机数量和保证舰载机调运效率。
目前,国内外学者针对机库布列问题开展了较多的研究。美国海军开发了航空数据管理与控制系统(Aviation Data Management And Control System,ADMACS)[2]和舰船综合信息系统(Integrated Shipboard Information System,ISIS),通过在舰载机上安装具有标识的GPS,提供实时显示位置状态信息,进而供相关人员手动调控站位,实现舰载机布列;李耀宇等[3]对舰载机甲板布列调运业务进行分析,总结了国内外相应的研究情况;胡玉龙等[4]对机库进行模糊建模以求解机库结构设计方案,其机库分段思想对布列问题很有帮助;张思[5]基于临界多边形(no fit polygon,NFP)与遗传算法,以舰载机数量为目标对该问题进行了求解;田大肥[6]将该问题转化成二维矩形装箱问题,以总调运路程为目标对问题进行了优化求解;Li等[7]通过对放置空间和飞机二维几何模型进行建模,开发了一种用于解决飞机布列问题的新型遗传算法。
从机库布列的两个优化目标(即舰载机数量更多与出动效率更高)出发,该问题可拆分为两个优化问题:空间利用率优化与考虑调运效率的空间布局优化。空间利用率优化也称装箱问题,属于一种NP难度问题。机库空间狭小,将舰载机轮廓凸化处理会导致舰载机间隙过大,机库空间利用不充分,故若想布列结果有实际使用价值,需要将机库布列问题转化为连续空间下二维凹多面体的装箱问题,面积利用率越高,则放置的舰载机数量越多。二维装箱问题解决方法很多,但目前在舰载机布列问题上应用不多。如Burke等[8]基于轨迹线建立临界多边形,可以为复杂二维图形排样提供多样化运算;Alvarez-Valdes等[9]基于分支定界算法实现了对二维不规则形状图形进行排样切割;这个问题与Kheirkhah等[10]在动态设施布局问题上的研究类似。考虑调运效率的空间布局优化对应于仓储、车库领域的车位排布问题。ABDELFATAH等[11]采用线性规划对车库停车容量进行了优化;徐涵喆等[12]提出一种基于规则的车位排布启发式算法,得到了车位数较多且实用的排布方案。
舰载机不仅具有空间轮廓属性,且有转运的业务需求。从现有的研究结果来看,一方面是弱化舰载机调度需求,以舰载机数量为唯一优化目标的布列优化研究已取得不错的成果,另一方面是简化舰载机轮廓和布列算法,以调运总路程为唯一目标的研究也成果颇丰,但这两方面都因优化目标单一,算法结果距离机库实际布列方案还有很大的距离。目前,同时结合这两优化目标的研究还处于空白。本文拟通过分析机库布列问题的特点和业务需求,建立基本空间组合关系库,计算可能的空间组合,基于遗传算法优化布列顺序,建立以最大化布列飞机数目与最大化紧急出动飞机数量为优化目标的多目标智能算法,优化机库甲板舰载机布列方案。
-
与飞行甲板相比,在机库甲板容纳更多舰载机的优化目标显得更为重要。机库甲板作为航母上空间最大的舱室,无起降跑道与舰岛等空间限制,布列自由度高,灵活性强,优化空间大。本文以“尼米兹”级航母作为参考对象,研究舰载机在机库甲板的布列问题。
“尼米兹”级航母机库甲板的形状约为矩形,长为208.5 m,宽为33 m。航母右舷有3部升降机,左舷有1部。升降机是舰载机在各层甲板之间转运的唯一途径。升降机的数量与位置,不仅影响甲板间转运效率,也必然会对机库内布列方案产生影响。在设计自动布列算法时应当考虑到升降机因素,以提高布列方案的转运效率与业务合理性。本文以升降机数量多的一侧——右舷的升降机为节点,以相邻升降机间隔中线为界限将机库划分为3个子舱室,分隔线同时也大致符合航母机库防火帘的位置[14],如图1所示。
通过将机库甲板划分成3个子舱室,每个子舱室仅将其相邻的升降机作为调运出口,设
$n$ 个单位的布列问题为${G_n}\left( x \right)$ ,划分成$m$ 个子舱室后,研究问题转化为如式(1)所示的问题:$${G_n}\left( x \right) \to m*{G_{\frac{n}{m}}}(x)$$ (1) 即
$n$ 架舰载机的布列问题转化为$m$ 个$\frac{n}{m}$ 架舰载机的布列问题。通过子舱室模型简化机库业务可以大大降低模型复杂度,同时贴近实际业务。 -
航母携带的舰载机数量多,种类也多。在美军进行的“高强度演习”中,“尼米兹”级共装载了F-14A战斗机、F/A-18C战斗/攻击机、EA-6B电子战机、S-3A反潜/加油机、E-2C预警机和SH-60直升机等多种飞机,机库内还放置了些许小艇,这些统称为布列单位。为保证每部升降机都能出动特定类型飞机,并保持升降机使用次数的均衡,本文将机库总布列需求分配至子舱室。
分配的规则为:
1)各子舱室布列的舰载机总数量不宜相差太大;
2)同一种类飞机不应过于集中。
根据上述规则,具体的分配算法流程如下图2所示:
上述流程图中,对各类舰载机数量进行判定后,先均匀分配布列需求,将无法均匀分配的剩余部分与其他数量少的布列单位合并为新的需求,进行第二次分配。
-
现有研究普遍采用以五边形为主的凸多边形甚至以矩形来简化舰载机轮廓,这导致诸如舰载机间距空间、舰载机机翼与机身所夹空间等空间资源可能出现浪费。本文中设计的算法对舰载机几何轮廓无要求,可以在同一方案内采用多种简化或原轮廓的图形来表示舰载机。如图3所示,分别为简化轮廓战斗机(折翼状态)、原轮廓战斗机(展翼状态)、原轮廓预警机、原轮廓直升机(折翼状态),这些轮廓都可通过2.1节中描述的布列算法进行布列。
在本文研究工作中,图形处理算法引用了Burke[8]的研究成果:基于移动碰撞算法,求解出临界多边形(No-Fit Polygon,NFP),从而实现二维排样。临界多边形是二维排样问题中关键的几何工具,可以被用来求解图形间最优靠接位置、重叠判断、定位等。根据内靠接NFP原理,基于最左最下原则(Bottom Left,BL)、最左最下填充原则(Bottom Left Fill,BLF)、最合适位置原则(Best Fit,BF)、最低重心原则等多种定位策略可以为布列单位选取比较有优势的布列位置。
-
舰载机在航母飞行甲板和机库甲板上的约束有许多差异。通过分析机库使用的特点,得出在机库划分舰载机站位时,需要考虑以下布列特点:
1)机库内舰载机调运全部靠牵引车实现,不需要考虑舰载机发动机尾焰对机尾朝向的影响。
2)单类型舰载机不应全部依赖于特定升降机转运,以防止在该升降机发生故障时无法出动该类型舰载机。
3)机库的主要功能是存储与维修,紧急出动的舰载机是用来替换飞行甲板上发生故障的舰载机。不需要紧急出动的舰载机无需考虑转运成本,这些飞机有足够的时间在机库内完成运动姿态的转换。
4)紧急出动的舰载机尾部应朝向升降机,紧急出动时由牵引车推入升降机,到飞行甲板指定保障站位进行保障。
5)紧急出动的舰载机不应被任何障碍物阻拦,即无需移动其他舰载机便可移动至升降机,且尽可能避免正反向行驶多次切换。
6)在不考虑飞行甲板使用的情况下,每部升降机都能用来紧急出动舰载机。
7)舰载机摆放在机库甲板规定的区域内。
8)舰载机不可互相重叠。
9)出于管理的方便与美观要求,舰载机划分的站位需要尽可能具有整齐划一、朝向有规律等特点。
-
对于如航母机库等自由空间下布列多类不规则轮廓物体的问题,巧妙地利用舰载机等单位不规则轮廓间的镶嵌,建立更紧密的组合关系是增加布列飞机数量、提高空间利用率的有效方法。舰载机的组合方式与业务强相关,涉及到管理、安全、美观等多个因素。本文依据实际业务以提取舰载机等物体常用的、可靠的组合方式为规则来建立基本组合关系库。
基本组合关系库中以类型为节点,记录各类型间是否存在推荐的组合关系。将可以相互组合的布列单位放入集合中,再基于以整数拆分思想为基础的搜索算法计算集合内可能存在的组合分配方案。同时基本组合关系库可以支持新机型的布列设计,使算法具有一定的可扩展性。
下面以“尼米兹”级航母的主要固定翼舰载机机型为例,说明组合关系的建模。主要考虑F-14A,F/A-18C,EA-2C等3种机型,可能的组合关系包括对式和齐头式,不同机型的组合关系如表1所示。
表 1 部分组合关系
Table 1. Partial combination relationship of aircrafts
机型 F-14A F/A-18C EA-2C F-14A 对式、齐头式 对式 — F/A-18C — 对式、齐头式 — EA-2C — — 对式 部分组合类型样式如图4所示。
以计算1架EA-2C与4架F-14A的组合方案结果集为例来介绍算法流程,流程图如图4所示,其结果集在表2中列出。
表 2 结果集
Table 2. The result set
结果集1-${{\rm{S}}_1}$ {(EA-2C*1)} 结果集2-${{\rm{S}}_2}$ {(F-14A*4),
(F-14A*3+F-14A*1),
(F-14A*2+F-14A*2),
(F-14A*2+F-14A*1+F-14A*1),
(F-14A*1+F-14A*1+F-14A*1+F-14A*1)}结果集3-${{\rm{S}}_3}$ {对式,齐头式} 总结果集-${\rm{S}}$ ${{\rm{S}}_{\rm{1}}} \times {{\rm{S}}_{\rm{2}}} \times {{\rm{S}}_{\rm{3}}}$ 多个布列单位组合成布列模块,算法2生成的结果确定各布列模块中布列单位的数量。表2中“F-14*4”为4架F-14组合摆放,为1个布列模块,“F-14A*1+F-14A*1+F-14A*1+F-14A*1”为4架F-14单独摆放,为4个布列模块。两者区别在于布列模块之间以最小包络矩形的形式堆叠,没有采用组合关系的4个布列模块堆叠导致相邻的“F-14”间隙空间不会被利用。提高面积利用率的唯一途径只有建立紧密的组合关系从而减少浪费面积来实现。
由于组合关系固定,基于同种组合关系组合成的布列模块内停机密度一定相等。
原问题为有限空间内多个不规则物体的二维连续排样问题,上述算法将该问题通过基本组合关系库离散化,将问题转化为组合优化问题。在转化过程中,尝试从有限的合理的组合关系来分析问题,将解空间由连续解空间离散化至可求解程度。被舍弃的解空间中不会存在满足业务需求的最优解。
-
根据前面的研究,舰载机布列方案有两个优化目标:布列数量更多与紧急出动舰载机数量更多。通过对布列资源进行分析,由搜索算法得出的结果集中包含了该布列资源下全部的组合方案。组合方案中的元素被命名为布列模块,在2.1节中已有介绍。通过为各模块编号,基于“LB(Left Bottom)”策略按编号顺序迭代摆放至机库空间即可实现一个完整的布列方案。“LB”策略意为将需要放置的模块先向左移动至边界,再向下移动至边界。通过该策略实现摆放定位。通常“LB”策略会造成很明显的元素分布不均匀问题,但在本文研究内容中由于布列模块内部停机密度固定、布列模块之间间隙基本相同,因此“LB”策略基本满足此时业务需求。
根据总体业务优化目标以及布列中的约束条件可得到优化问题的数学模型。
目标函数为:
$$\max F(x)=({f_1}(x),{f_2}(x))$$ (2) $${f_1}(x)=\sum {{S_i}} $$ (3) $${f_2}(x)=\sum {{B_t}} $$ (4) 约束条件为:
$${S_i} \cap {S_j}=\emptyset ,\forall i,j \in n$$ (5) $${S_i} \in S$$ (6) $$ i \ne j;i,j=1,2,3,\cdots,n$$ (7) 式中:
$S$ 为机库甲板总空间,${S_i}$ 表示编号为$i$ 的飞机所占空间,机库内布列单位不仅不可互相重叠,也不可超出机库空间;${f_1}(x)$ 为所有布列单位占用的面积,只与布列资源中布列单位数量有关;${B_t}$ 为$t$ 类型布列单位经路径规划模块判断后可直接出动的数量。飞机是否能够直接出动的判断逻辑是:单架舰载机在将其他布列单位视为障碍物且不超过边界的条件下,是否可以完成前往指定升降机的路径规划。在这种情况下,路径规划只需要回答“可以”或“不可以”。“可以”的数量与优化目标
${f_2}(x)$ 密切相关,而路径的长度优化从业务角度出发并无太大意义:机库内空间狭小,不同路径间长度差额的绝对值不大,不会对调运效率产生明显影响。本文基于Reed-Shepp算法实现路径规划进而完成判断逻辑。Reed-Shepp算法理论成熟,运算速度快,且具有考虑运动学约束等特点。对升降机附近的布列模型进行倒车路径判定可迅速评估布列方案的紧急出动能力。当布列资源确定时,机库甲板内面积利用率也可同时确定。两目标优化问题此时成为单目标优化问题,即锁定了布列资源后只需要对
${f_2}(x)$ 求解即可。此时,对于确定了布列资源后的模型,有
$$C=D \times E$$ (8) 式中:C为机库布列问题解空间;D为组合方案集解空间;E为布列顺序解空间。
-
基于搜索得出众多组合方案后,需要对每个组合方案最优布列进行优化求解。同一组合方案下各模块不同顺序的摆放会得到不同的结果,模块数决定了解空间大小。不同组合方案中模块数量
$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等[15]的研究成果,本文选取“顺序交叉(Order Crossover,OX)”规则对染色体进行交叉操作。第1步,随机选择一对染色体(父代)中几个基因的起止位置(两染色体被选位置相同);第2步生成一个子代,并保证子代中被选中的基因的位置与父代相同;随后,第3步先找出第1步选中的基因在另一个父代中的位置,再将其余基因按顺序放入上一步生成的子代中,如图5所示。突变选取常用的单点突变,随机选取要突变的基因位点,然后突变成与剩余的其它基因不同的基因。
通过对布列方案中的每架舰载机(只计算F-14A,F/A-18C等战斗机型,不计算预警机、救生艇、直升机等非战斗机型)遍历调用路径规划算法,计算可紧急出动舰载机数量,将其作为适应度值。
遗传算法流程图如图6所示。
在算法运行中,若某一编码对应的布列方案因机库空间几何约束导致空间不足而无法完成放置,则会放弃该编码。机库几何轮廓作为二维排样中的约束不断淘汰不合格的编码。
-
当机库内摆放一定数量舰载机时,通过遗传算法可以计算出最大紧急出动飞机数量及其对应的布列方案。本文为遗传算法设置适应度阈值,当达到阈值时提前终止遗传算法,使得机库完全能够满足该数量布列需求下对于紧急出动的业务需求。终止算法后,布列需求添加一架默认的战斗机型,如F-14A或F/A-18C,继续进行布列方案探究。迭代多次后,混合算法能够输出布列数量与最大紧急出动能力平衡的布列方案。
$m$ 个子舱室的满意解构成总机库的满意解。两目标迭代算法流程如下图7:
-
文献资料[14]中得到美军“尼米兹”级机库布列图,如图8所示。
本文设计了“尼米兹”级航母在类似战斗模式下机库的布列需求,对算法有效性进行验证。算法采用C++编程实现,运行在CPU为i5-6500(4核,3.2 GHz)、内存8 GB的计算机上。该布列需求包括7种布列单位,初始布列需求与美军方案保持一致,经过任务分配后得到具体子舱室的布列需求,如表3所示。
表 3 舰载机机库基本布列需求表
Table 3. Basic layout requirements of aircraft hangar
F-14A F/A-18C EA-6B S-3A E-2C SH-60 小艇 总计 总需求量 5 13 2 5 1 2 4 32 子舱室1 2 4 1 2 0 1 1 11 子舱室2 2 5 0 2 0 1 1 11 子舱室3 1 4 1 1 1 0 2 10 在本次算法运行中,设最大遗传代数
$Gen\max $ =100,种群空间$Pop\max $ =50,变异率${p_{\rm{m}}}$ =0.02,交叉率${p_{\rm{c}}}$ =0.6,设置阈值为$${E_k}=2 * {F_k}$$ (9) 其中,
${E_k}$ 为第$k$ 个舱室紧急出动的舰载机数量,${F_k}$ 为第$k$ 个舱室拥有的升降机数量。每个舱室单独求解。在算法运行过程中,优化算法表现出较好的收敛性,不同子舱室的求解时间接近,求解出的总布列方案如图9所示。
在计算美军布列方案利用率时,需将各舰载机占用面积替换为本文布列算法中同类型舰载机采用的轮廓的占用面积,以保证结果不受轮廓因素的干扰。经计算,得到美军布列方案面积利用率为36.54%。
在本文得出的方案中,各布列单位长、宽参数经过核对,符合实际尺寸。计算中,多次迭代加入F/A-18C来增加布列数量,使得机库总布列单位数量达到44架,其中F/A-18C为27架,面积利用率为53.46%,提高了16.92%。各升降机均保证了一定的紧急出动能力。考虑到可能因摆放规则出现的右上方区域利用率不够高的情况,可人工对生成的方案进行舰载机间距调整,使之分布均匀。
-
通过对机库环境进行分析,对舰载机常用摆放形式进行了归纳整理;通过对基本组合关系库进行组合关系搜索,实现布列资源预处理,得到了所有可能的布列区块组合;以布列面积利用率最大化与舰载机可直接出动数量最大化为目标,通过遗传算法对组合模块进行布列顺序优化,与美军布列方案对比验证了算法的有效性。通过研究,得到如下结论:
1)本文提出的布列算法能够应对不同类型机库、不同布列需求下同类问题的计算与优化;
2)基于基本组合关系库得到的组合方案使得布列结果具有较高的实用性、安全性与美观性;
3)启发式算法不仅能够尽可能提高机库存放舰载机数量,同时能够保证舰载机紧急出动能力;
4)可视化输出的布列结果,可以为机库管理员提供站位划分的辅助决策依据。
由于舰载机组合关系十分复杂,本文多以同类机型组合为主进行研究。基本组合关系库需要在后续的工作中继续丰富,同时组合的角度也可从离散化向连续化继续深入研究。目前,基本组合关系库需要用户手动输入,若能依据外形轮廓智能生成则更方便、更全面,更丰富的组合关系可以得到更优秀的布列方案。组合关系与舰载机实际业务密切相关,且不同战斗模式下机库对组合关系有不同的要求,特定区域对排样角度也有约束,需要建立更复杂的业务模型。此外,启发式算法的设计与优化空间巨大,与求解效率紧密相关,还需大量的研究工作。
A Layout Algorithm for Carrier-Based Aircrafts in Hangar based on Basic Spatial Combination Relationship
-
摘要:
目的 提出一种优化航空母舰机库甲板舰载机布列的算法。 方法 针对机库内舰载机混搭布列问题,基于基本空间组合关系,建立组合关系库,优化解空间,将有约束的二维排样问题转换为组合优化问题。再以最大舰载机数量与最大可紧急出动舰载机数量为目标,建立机库布列模型,并利用一种启发式算法来求解该模型。 结果 以“尼米兹”级航母作为案例进行求解,得到的机位排布方案能够在保证紧急出动舰载机数量的情况下最大化机库布列总数量,且布列方案满足实际业务约束与需求;与美军布列方案相比,面积利用率提高了16.92%。 结论 使用该算法可以有效地对舰载机机库布列问题进行求解。 Abstract:Objectives An algorithm for optimizing the layout of carrier-based aircrafts in hangar is proposed. Methods To solve the problem of mixed layout of aircrafts in hangar, based on basic spatial combination relationship, this paper sets up a combinatorial relationship library, optimizes the solution space, and converts the constrained two-dimensional nesting problem into a combinatorial optimization problem. With the purpose of the maximum number of aircrafts and the maximum number of aircrafts for emergency, the hangar layout model is established, and a heuristic algorithm is used to solve the model. Results By a case study of the "Nimitz" class aircraft carrier, The resulting layout scheme can maximize the total number of aircrafts while ensuring the number of carrier aircraft for emergency, and the result satisfies the actual business constraints and requirements. Compared with the US military layout scheme, the area utilization rate has increased by 16.92%. Conclusions The proposed algorithm can be used to effectively solve the layout problem of carrier-based aircrafts in hangar. -
表 1 部分组合关系
Table 1. Partial combination relationship of aircrafts
机型 F-14A F/A-18C EA-2C F-14A 对式、齐头式 对式 — F/A-18C — 对式、齐头式 — EA-2C — — 对式 表 2 结果集
Table 2. The result set
结果集1- ${{\rm{S}}_1}$ {(EA-2C*1)} 结果集2- ${{\rm{S}}_2}$ {(F-14A*4),
(F-14A*3+F-14A*1),
(F-14A*2+F-14A*2),
(F-14A*2+F-14A*1+F-14A*1),
(F-14A*1+F-14A*1+F-14A*1+F-14A*1)}结果集3- ${{\rm{S}}_3}$ {对式,齐头式} 总结果集- ${\rm{S}}$ ${{\rm{S}}_{\rm{1}}} \times {{\rm{S}}_{\rm{2}}} \times {{\rm{S}}_{\rm{3}}}$ 表 3 舰载机机库基本布列需求表
Table 3. Basic layout requirements of aircraft hangar
F-14A F/A-18C EA-6B S-3A E-2C SH-60 小艇 总计 总需求量 5 13 2 5 1 2 4 32 子舱室1 2 4 1 2 0 1 1 11 子舱室2 2 5 0 2 0 1 1 11 子舱室3 1 4 1 1 1 0 2 10 -
刘相春. 航空母舰舰机适配性技术体系[J]. 中国舰船研究, 2016, 11(3): 1–4, 10. doi: 10.3969/j.issn.1673-3185.2016.03.001 LIU X C. A technology system for the carrier/air vehicle integration[J]. Chinese Journal of Ship Research, 2016, 11(3): 1–4, 10 (in Chinese). doi: 10.3969/j.issn.1673-3185.2016.03.001 FEIN G. Navy expects to get ADMACS acquisition strategy approved this summer[N]. Defense Daily, 2009-06-23. 李耀宇, 朱一凡, 齐鸣, 等. 舰载机甲板布列调运优化方法研究[J]. 指挥控制与仿真, 2013, 35(2): 125–131. doi: 10.3969/j.issn.1673-3819.2013.02.029 LI Y Y, ZHU Y F, QI M, et al. An overview of aircraft allocation and transferring on carrier flight-deck[J]. Command Control & Simulation, 2013, 35(2): 125–131 (in Chinese). doi: 10.3969/j.issn.1673-3819.2013.02.029 胡玉龙, 黄胜, 侯远杭, 等. 航空母舰机库主尺度要素设计方法[J]. 上海交通大学学报, 2012, 46(8): 1184–1189. HU Y L, HUANG S, HOU Y H, et al. Research on design of principal dimension elements of hangar in aircraft carriers[J]. Journal of Shanghai Jiaotong University, 2012, 46(8): 1184–1189 (in Chinese). 张思. 舰载机自动布列方法的研究[D]. 哈尔滨: 哈尔滨工程大学, 2012. ZHANG S. Research on the automatic layout method of the aircraft[D]. Harbin: Harbin Engineering University, 2012 (in Chinese). 田大肥. 机库内舰载机的布置方法研究与实现[D]. 北京: 中国舰船研究院, 2014. TIAN D F. Research and realization of aircraft’s arrangement in hangar[D]. Beijing: China Ship Research and Development Academy, 2014 (in Chinese). LI X, WANG Z X, CHAN F T S, et al. A genetic algorithm for optimizing space utilization in aircraft hangar shop[J]. International Transactions in Operational Research, 2019, 26(5): 1655–1675. doi: 10.1111/itor.12642 BURKE E, HELLIER R S R, KENDALL G, et al. Complete and robust No-Fit Polygon generation for the irregular stock cutting problem[J]. European Journal of Operational Research, 2007, 179(1): 27–49. doi: 10.1016/j.ejor.2006.03.011 ALVAREZ-VALDES R, MARTINEZ A, TAMARIT J M. A branch & bound algorithm for cutting and packing irregularly shaped pieces[J]. International Journal of Production Economics, 2013, 145(2): 463–477. doi: 10.1016/j.ijpe.2013.04.007 KHEIRKHAH A, NAVIDI H, BIDGOLI M M. Dynamic facility layout problem: a new bilevel formulation and some metaheuristic solution methods[J]. IEEE Transactions on Engineering Management, 2015, 62(3): 396–410. doi: 10.1109/TEM.2015.2437195 ABDELFATAH A S, TAHA M A. Parking capacity optimization using linear programming[J]. Journal of Traffic and Logistics Engineering, 2014, 2(3): 176–181. 徐涵喆, 黄逸彬, 杨赫, 等. 基于规则的城市地下车库外圈车位排布启发式算法[J]. 北京邮电大学学报, 2019, 42(4): 102–108. XU H Z, HUANG Y B, YANG H, et al. Rule-based heuristic algorithm for parking spaces allocation in marginal area of urban underground parking lots[J]. Journal of Beijing University of Posts and Telecommunications, 2019, 42(4): 102–108 (in Chinese). 刘亚杰, 李忠猛, 谢君. 基于改进遗传算法的舰载机出库调度优化方法[J]. 火力与指挥控制, 2015, 40(6): 57–60, 65. doi: 10.3969/j.issn.1002-0640.2015.06.014 LIU Y J, LI Z M, XIE J. Optimized method of carrier-borne aircrafts exporting scheduling based on improved genetic algorithm[J]. Fire Control & Command Control, 2015, 40(6): 57–60, 65 (in Chinese). doi: 10.3969/j.issn.1002-0640.2015.06.014 ROBERT L D, HOWARD L B. Aircraft carrier flight and hangar deck fire protection: history and current status[R]. 2005. China Lake: Naval Air Warfare Center Weapons Division, 2005. ABDOUN O, ABOUCHABAKA J. A comparative study of adaptive crossover operators for genetic algorithms to resolve the traveling salesman problem[J]. International Journal of Computer Applications, 2011, 31(11): 49–57. -