编辑推荐：
针对NP难的航母飞行甲板调度问题，本研究提出融合图神经网络（GNN）与深度强化学习（DRL）的新框架。通过将问题建模为马尔可夫决策过程（MDP），利用GNN捕捉任务依赖与资源约束关系，显著提升调度效率与质量，决策时间从分钟级降至秒级，满足实时需求。
作者列表：李长久|韩伟|李海旭|刘杰|王新伟|张勇|苏希超
中国山东省烟台市264001，海军航空大学
摘要
飞行甲板操作调度是一个NP难组合优化问题，传统方法在计算效率和解决方案质量之间存在关键权衡。为了解决这一挑战，我们提出了一个结合图神经网络的深度强化学习框架来优化这一过程。该问题被构建为一个马尔可夫决策过程，允许调度代理直接从环境状态生成调度方案。我们的分析表明，结合折扣因子1.0的softmax探索策略为通用性提供了稳健的配置。实验结果表明，该代理在解决方案质量方面优于传统的优先调度规则。与元启发式算法相比，我们训练有素的代理在小规模问题上表现出了竞争力，并在大规模实例上展示了更强的搜索能力。值得注意的是，该代理将元启发式算法所需的几十分钟决策时间缩短到了几秒钟，同时产生了满足实时操作需求的高质量解决方案。
引言
基于航母的飞机出动能力是现代海上战争的基石，是海军编队投射战斗力的主要手段。这一能力的有效性取决于飞行甲板操作的高效执行——这需要物流人员、甲板资源和指挥决策的复杂协调。随着未来冲突对强度、精确度和效率提出前所未有的要求，优化这些操作的调度不仅仅是一个改进措施，更是提高航空母舰战斗准备状态和效能的战略要求。
然而，当前的飞行甲板调度范式存在严重局限性。现有操作主要依赖于指挥官基于经验的判断，导致调度方案往往缺乏灵活性、最优性和适应性。这种手动方法经常面临协调不精确、资源利用低和操作瓶颈等问题，从而危及飞行操作的安全、秩序和节奏。随着全球向多类型飞机舰队和智能支持系统发展的趋势，协调高节奏出动的规模和复杂性使得传统的经验驱动方法变得不可行。迫切需要转向敏捷和智能的调度技术。
这一挑战的核心在于基于航母的飞机飞行甲板操作调度问题（CAFDS）的复杂性。从根本上说，CAFDS是一个高维组合优化问题，其特征是空间-时间约束紧密耦合。有限的甲板空间（空间约束）、有限人员和设备的竞争（资源约束）以及严格的操作优先级（程序约束）共同构成了一个计算上极具挑战性的搜索空间。低效的调度可能导致延误，显著降低出动率并危及操作安全。这一内在难点成为本研究的核心动机：开发一种新的调度范式，以应对CAFDS的复杂性，提供实时的高质量解决方案。
为了解决这个问题，我们转向了人工智能（AI）技术领域，特别是深度强化学习（DRL），它为在复杂和动态环境中学习最优决策策略提供了强大的框架。然而，将DRL应用于CAFDS面临两个重要且具体的挑战：
首先是表示挑战：标准的DRL代理通常处理扁平化的状态向量，这种格式不适合捕捉调度问题中固有的丰富关系和拓扑结构。CAFDS中复杂的任务依赖性和资源约束网络在这种表示方式下丢失，导致代理无法做出真正有根据的、具有上下文意识的决策。
其次是效率与质量的权衡：虽然传统的元启发式算法可以生成高质量的调度方案，但其高昂的计算成本使其不适用于飞行甲板的实时动态环境。相反，如果DRL代理未能理解问题的底层结构，它可能会快速做出决策，但牺牲了关键的解决方案质量。
为了克服这些挑战，我们引入了一个将图神经网络（GNN）与DRL相结合的新框架。通过明确建模问题的结构，我们可以克服上述挑战。具体来说，我们利用GNN的力量来学习操作状态的丰富、结构感知的嵌入。这使得DRL代理能够理解复杂的依赖关系。同时，DRL框架促进了端到端的策略学习，确保可以在几秒钟内做出高质量决策，从而解决了效率与质量的权衡问题。
本工作的主要贡献和创新有三方面：
首先是理论建模创新：我们将CAFDS问题形式化为一个马尔可夫决策过程（MDP），为应用强化学习（RL）提供了数学基础。通过系统地定义状态空间、动作空间和基于核心MDP元素的奖励函数，我们将一个静态优化问题转化为一个适合基于学习的动态决策过程。
其次是方法论创新：我们引入有向无环图（DAG）来表示CAFDS中的优先级约束和资源依赖关系。然后使用GNN从这个图结构中学习深度特征嵌入。这种基于图的表示方法比传统的DRL方法有显著的方法论进步，因为它使代理能够明确地理解关系信息，从而制定出智能且具有远见的调度策略。
第三是实际应用价值：我们开发并实现了一个基于优势演员-评论家（A2C）算法的调度器，该算法与我们的GNN架构集成。全面的实验验证了其实际效用。我们的代理不仅超越了传统的调度规则，而且在大规模实例上实现了更优的解决方案质量。最重要的是，它将决策时间从元启发式算法通常所需的几分钟缩短到了几秒钟，凸显了其在复杂操作环境中进行实时高性能调度的巨大潜力。
本文的结构如下：第2节回顾了相关工作。第3节概述了CAFDS问题的背景及其具体挑战。第4节介绍了我们的MDP建模和增强型GNN DRL算法。第5节讨论了实验设置并分析了性能结果。最后，第6节总结了工作并指出了未来的研究方向。
章节片段
CAFDS的发展
为了提高飞行甲板操作的效率，美国军方自20世纪70年代以来开发了航空数据管理和控制系统。其中一个系统是电子灵应板（Electronic Ouija Board），以及目前安装在航空母舰上的航空数据管理和控制系统（ADMACS）。这些系统提供了跟踪飞行计划和提供起飞及回收操作视觉记录的工具，显著增强了飞行甲板操作的能力
问题陈述
为了确保舰队保持必要的系统安全性和作战效能，以便在直接出动和重新出动准备阶段将飞机从机库或回收轨道运输并停靠在指定的服务停车位，以支持航空作业，航空后勤支持人员将执行一系列后勤操作，包括加油、液压供应、气体填充等
方法论
本研究通过引入一个基于GNN的集成DRL算法来解决CAFDS中的复杂性，该算法被称为“代理”。该代理使用A2C算法来训练神经网络的参数。以下部分将详细解释算法的技术方面，包括MDP的组成部分、神经网络架构的设计、SGS的选择过程以及A2C训练算法的工作流程。
案例实验
本节将描述为评估所提出的CAFDS优化能力而创建的仿真实例。首先，我们将概述DRL训练阶段的每个步骤。接下来，我们将确定几种有效的PDR、元启发式算法以及最近在RCPSP领域发布的DRL算法。这些将作为评估训练模型有效性和泛化能力的基准参考
管理洞察
这项研究为指挥官提供了一种将飞行甲板操作调度转变为敏捷执行能力的途径。通过将AI应用于这一复杂且响应迅速的领域，我们不仅提高了理论性能，更重要的是，提供了一种平衡效率与灵活性的决策支持工具，适用于实际操作。
结论
在这项工作中，我们根据航空后勤支持服务的过程元素和约束条件设计了一个基于MDP的模型，其中包括状态空间、动作策略、状态转换和CAFDS的奖励函数。我们提出了一个结合GNN网络的DRL算法来解决这一调度挑战。所提出的算法经过预训练和“端到端”部署后，可以生成高质量的CAFDS调度方案
CRediT作者贡献声明
李长久：撰写——审阅与编辑、撰写——原始草稿、可视化、验证、监督、资源管理、项目管理、资金获取。韩伟：调查、资金获取。李海旭：调查、数据整理。刘杰：调查。王新伟：形式分析、数据整理、概念化。张勇：资金获取、形式分析、数据整理。苏希超：方法论、形式分析、数据整理、概念化。
利益冲突声明
作者声明他们没有已知的可能会影响本文所述工作的竞争性财务利益或个人关系。
