Chinese Journal of Ship Research
Layout algorithm for carrier aircraft in hangar based on basic spatial combination relationship
引用格式：徐柱国, 余明晖, 吴靳, 等.基于基本空间组合关系的舰载机机库布列算法 [J]. 中国舰船研究, 2021, 16(3): 9–16. XU Z G, YU M H, WU J, et al. Layout algorithm for carrier aircraft in hangar based on basic spatial combination relationship[J]. Chinese Journal of Ship Research, 2021, 16(3): 9–16.
徐柱国1，余明晖*1，吴靳2，戴明强3 1华中科技大学人工智能与自动化学院，湖北武汉 430074 2海军工程大学电子工程学院，湖北武汉 430033 3海军工程大学基础部,湖北武汉 430033
摘 要:［目的］提出一种优化航空母舰机库甲板舰载机布列的算法。［方法］针对机库内舰载机混搭布列问题，基于基本空间组合关系，建立组合关系库，优化解空间，将有约束的二维排样问题转换为组合优化问题。然后，再以最大舰载机数量与最大可紧急出动舰载机数量为目标，建立机库布列模型，并利用一种启发式算法求解该模型。［结果］以“尼米兹”级航空母舰作为案例进行求解，得到的机位排布方案能够在保证紧急出动舰载机数量的情况下最大化机库布列总数量，且布列方案满足实际业务约束与需求；与美军布列方案相比，机库甲板的面积利用率提高了16.92%。［结论］使用该算法可以有效地对舰载机机库布列问题进行求解。关键词：舰载机；航母机库；空间组合关系；混搭布列；启发式算法中图分类号: U674.771文献标志码:A DOI：10.19693/j.issn.1673-3185.01954
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所示。