基于多智能体航空公司航班恢复协同决策方法.pdf

第 55 卷第 5 期2023 年 10 月Vol.55 No.5Oct.2023南 京 航 空 航 天 大 学 学 报Journal of Nanjing University of Aeronautics&Astronautics基于多智能体航空公司航班恢复协同决策方法季灵，吴薇薇，吴思韵，高强，刘硕（南京航空航天大学民航学院，南京 211106）摘要：航空公司进行航班延误恢复时，各种资源之间会通过航班计划产生间接关联，此时各决策单元若独立地考虑本领域内的资源恢复问题，将难以保证恢复方案的整体可行性和全局优化性。为探究航空公司航班恢复过程中各决策部门的决策模型及其协同关系，本文提出了基于多智能体技术的航班恢复协同决策仿真方法。首先，基于航空公司实际组织架构构建了航班恢复多智能体决策系统框架；其次，对部门间协同决策的动态过程进行了分析，将延误恢复的全过程分为了预恢复、可行解协商、均衡解协商 3个阶段，构建了三阶段协同决策机制；最后，根据不同资源的恢复特性建立各决策部门的核心决策模型与部门间自动协商模型，并基于多智能体系统进行仿真。仿真结果显示，基于多智能体的协同决策方法能够在 3.8 s的极短时间内针对 1天中包含 3架飞机和 12个航班的航班计划做出完整的延误恢复方案，并且能够在保障航空公司整体效益的情况下一定程度地平衡各决策主体的自身利益。关键词：航空运输；延误恢复；协同决策；多智能体；仿真系统中图分类号：V355.2 文献标志码：A 文章编号：10052615（2023）05086810Multiagent Based Collaborative Decision Making Approach for Airline Flight RecoveryJI Ling，WU Weiwei，WU Siyun，GAO Qiang，LIU Shuo（College of Civil Aviation，Nanjing University of Aeronautics&Astronautics，Nanjing 210016，China）Abstract:In the case of airlines recovering from flight delays，resources are indirectly linked to each other through the flight plan，and it is difficult to ensure the overall feasibility and global optimization of the recovery solution if each decisionmaking department considers the recovery of resources in its own area.This paper proposes a multiagent simulation method for flight recovery in order to investigate the decision models of the departments and their collaborative relationship in the airline flight recovery process.Firstly，the framework of flight recovery multiagent system is constructed based on the actual organizational structure of the airline.Then，the whole process of delay recovery is divided into three stages：Prerecovery，feasible solution negotiation and balanced solution negotiation，and a threestage collaborative decisionmaking mechanism is constructed.Finally，the core decision model of each department agent is developed according to the recovery characteristics of different resources，and the multiagent autonegotiation model is established based on the collaborative decision mechanism.The simulation results show that the multiagent based collaborative decisionmaking method can produce a complete delay recovery plan in 3.8 s for a flight schedule consisting of three aircrafts and twelve flights in one day，and it can balance the local interests of each decision maker to a certain extent while safeguarding the overall benefits of the airline.DOI：10.16356/j.10052615.2023.05.013基金项目：国家自然科学基金（U2033205，U1933118）。收稿日期：20220225；修订日期：20220708通信作者：吴薇薇，女，教授，博士生导师，Email：。引用格式：季灵，吴薇薇，吴思韵，等.基于多智能体航空公司航班恢复协同决策方法 J.南京航空航天大学学报，2023，55（5）：868877.JI Ling，WU Weiwei，WU Siyun，et al.Multiagent based collaborative decision making approach for airline flight recovery J.Journal of Nanjing University of Aeronautics&Astronautics，2023，55（5）：868877.第 5 期季灵，等：基于多智能体航空公司航班恢复协同决策方法Key words:air transportation；flight delay recovery；collaborative decisionmaking；multiagent；simulation system科学的航班延误恢复策略是航空公司平稳有序运行的重要保障，不仅能够显著降低航空公司的经济损失，而且能够帮助其提高市场信誉度。实际进行航班延误恢复的过程中，各种资源并非独立存在，而是会通过航班计划产生关联关系，由此形成各个决策部门间的相互影响与制约。因此，航班恢复是一个多任务、需要多方参与协作的复杂过程。目前航空公司进行航班延误恢复的协作流程如图 1所示，可以看到该流程的主体是一种自上而下的顺序恢复模式，上游部门提出备选方案，下游部门只能被动地接受并传递，若遇到机组合法性约束不满足的情况才能向上反馈。在这种运作模式下，信息的单向传递很容易导致方案的不可行，同时，下游决策部门的诉求被极大程度地忽略。因此，有必要寻求一种更加科学的恢复策略，综合各个决策部门的意见，在保证多资源有效恢复的同时兼顾各部门的自身利益。当前，学术界对于延误恢复的研究多侧重于单一资源恢复或部分资源整合恢复，少数学者对于多资源协同恢复展开了探索。对于单一资源恢复的研究，Nissen等1使用了一个基于分支定价的解决方法在对延误进行重新排班的情况下进行各种方案 的 测 试，每 一 种 情 况 都 得 到 多 个 不 同 方 案；Chang2取消列生成步骤，开发了一个具有动态航段绑定机制的基于职责的 GA 模型来解决机组人员的恢复；Hwmv等3提出了一个动态建模框架来解决航班计划表的恢复问题即以动态的方式处理航班计划表的中断，该解决方法基于一个有效的飞机选择算法和一个平行飞机特定时空网络的线性编程模型的综合使用并实例验证其可行性；Liang等4考虑了具有机场容量限制和维修灵活性的飞机恢复问题，并提出了一个列生成算法来求解这一问题；Vink等5提出一种使用启发式方法迭代解决航空公司机队恢复的问题，每当延误发生就会找到一个恢复性的方案，随后的延误则根据之前所得到的解决方案进行解决；Zhu 等6建立了两阶段随机规划模型来处理实时航班时刻表恢复和乘客重新安排问题，并提出样本平均近似和启发式相结合的算法框架计算出航班恢复问题的 5%左右最优间隙的解；Ji等7提出一种内置的航班可行性验证算法，从而改进延误航班重新编排的算法。在部分资源整合恢复研究方面，Sinclair 等8提出了一个大型邻域搜索启发式方法，在延误恢复期产生一个包括飞机路径和旅客行程的可行的计划表；Le 等9建立了飞机、机组一体化恢复模型，使用配对存储树来获取可行的飞机、机组配对路径，将可行配对作为输入来求解模型；Zhang等10提出了一个两阶段的启发式算法来解决飞机和机组的一体化恢复问题；Hu 等11考虑了飞机航线和旅客的综合恢复问题，提出基于航班连接网络和旅客重分配关系的数学模型，并采用启发式算法解决该问题；朱博12 构建了飞机和机组关联的一体化恢复模型，并在确定性问题的基础上加入随机扰动因素，设计贪婪模拟退火算法求解；Sinclair 等13将飞机和乘客的联合恢复问题建模为一个混合整数规划模型，并提出了一个基于列生成算法的启发式方法进行求解；Cadarso 等14开发了一个旅客反应模型，在恢复航空公司的时刻表、飞机路径和旅客行程的同时内生化航空公司的决策对旅客补充和旅客反应的影响。在多资源协同恢复的研究方面，Bratu 等15率先整合了飞机资源、机组人员和乘客行程恢复问题，但其在机组恢复部分仅考虑了使用备份机组的方法；Petersen 等16整合了延误恢复中涉及的 5 个关键子问题，并使用 Benders 分解法求解该问题，虽然求解质量较高但求解速率很低；Stephen17建立了多资源一体化恢复模型并使用了行列生成法来求解；Vink等18将航班计划进行分割，基于一组平行的时空网络建立线性规划模型并动态求解，最后再检验恢复计划对飞机维修、旅客行程以及机组排班的可行性，虽然简化了模型求解但整体计算效率也不高；乐美龙等19提出了飞机和机组一体化恢复的数学模型，通过构建飞机恢复和机组恢复的可行路径和可行配对作为输入，对建立的优化模型进行优化求解，以使其在合理的时间内，获得整合恢复的优化解；吴刚等20分析了由飞机资源短缺造成的航班不正常情况，将该问题视为带有容量约束的多个商品的整数最小费用流问题，建立了多商品网络流数学模型并采用列生成算法框架求解该图 1 航空公司现行航班恢复流程Fig.1 Current process of flight recovery of airlines869第 55 卷南 京 航 空 航 天 大 学 学 报大规模整数规划问题，通过算例验证了该方法的正确性和有效性。由于规模庞大且约束众多，多资源恢复问题的建模和求解非常困难，几乎没有研究能够在短时间内完全解决该问题21，而且现有研究并未对资源恢复的公平性作详细考虑，多以成本最低或效益最大化为求解目标。本文摒弃了以往建立大规模数学规划模型的策略，基于分开求解、协商整合的思路，提出了一种基于多智能体技术的协同恢复方法。该方法改进了当前部门间的协作模式，建立了一套更加标准、更加公平的三阶段协同决策机制，在决策过程中充分考虑了每个决策部门的限制和要求。该协同决策机制通过多智能体仿真技术来实现，能够在短时间内求解出一套完整的解决方案。1 航班恢复多智能体系统1.1多智能体系统智能体（Agent）22是一种具有感知、学习能力、问题求解能力并且能够与系统中其他的 Agent进行交互、协商，从而完成一个或者多个功能的软件实体，其作用机理如图 2所示。而多智能体系统（Multiagent system，MAS）则是由一系列相互作用的智能体构成，内部的各个智能体之间通过相互通信、合作和竞争等方式，完成单个智能体不能完成的大量而又复杂的工作。使用 MAS 进行仿真具有以下优势：（1）智能体能够在不同的环境下进行自主决策，仿真一些难以用数学公式表达的复杂行为；（2）智能体能够实现完全自主的通信与协商，无需人为干预；（3）单个智能体的计算复杂度能够保持在较低的水平，且不同智能体能够实现分布式计算，大大提高了系统的整体计算效率。1.2航班恢复 MAS上节已简要介绍过航空公司当前进行延误恢复时的部门间协作模式，本节基于该模式进行改进，建立如图 3 所示的航班延误恢复 MAS 架构。该系统的主体部分由延误恢复相关决策部门的工作人员构成，将部门内的工作人员分别设置为Agent，并根据工作性质将其进一步划分为通信层Agent和业务层 Agent。系统的外部触发条件为造成航班延误的事件；系统的输出为一套完整的恢复方案，包括调整后的航班计划、飞机排班、机组排班以及旅客行程恢复方案。系统的底层数据库包括航班计划、机场信息、旅客订票信息、机组人员信息、成本数据以及系统运行的历史数据。通信层采用集中式体系结构，它由4个智能体组成：AOCManager、CrewManager、PassengerManager 和 MarketManager，它们分别代表了与延误恢复工作相关的 4个部门的部门经理，是延误恢复方案的最终决策者，主要负责部门之间的通信协商以及方案选择。业务层由 4 个专家智能体组成，AOC Specialist、CrewSpecialist、PassengerSpecialist 和 MarketSpecialist，它们分别代表了不同部门的业务专员，负责根据模型求解具体的资源恢复问题，为本部门的 Manager提供可选的资源恢复方案。1.3航班恢复 MAS构成要素AOCManager：代表航空公司运控部的部门经理，它是延误恢复活动的组织者，同时也是协同决策的参与者。相比其他通信层Agent，它还需额外负责异常事件的实时监控，并在异常发生后根据情况组织其余 Agent进行协同恢复，此外，它在协商过程中对于方案的可行性具有关键的判别作用。除了组织延误恢复，它还需要选择合适的飞机重排方案，在保证当天航班运行顺畅、不影响次日航班正常运行的基础上，尽量减少总延误时间、降低取消率。CrewManager：代表航空公司飞行部的部门经理。它负责选择合适的机组重排方案，尽可能降低机组对于新飞行任务的不满意度。PassengerManager：代表航空公司地服部的部门经理。它负责选择合适的旅客行程恢复方案，尽可能降低航班被取消的旅客的不满意度。MarketManager：代表航空公司市场部的部门图 2 智能体作用机理Fig.2 Operating mechanism of agents图 3 航班延误恢复 MAS架构图Fig.3 Architecture diagram of flight delay recovery based on MAS870第 5 期季灵，等：基于多智能体航空公司航班恢复协同决策方法经理。它负责选择合适的航班计划，尽可能减少航空公司在本次延误事件中的经济损失。Specialists：Specialists 统 一 接 受 Managers 的调度，它是 Managers 的智囊团。当 Managers 接收到具体的资源恢复问题时，将相关信息发送给Specialists，它们根据问题的规模选择合适的算法求解单一资源恢复模型。在求解过程中 Specialists间 通 过 信 息 共 享 使 结 果 更 加 精 确，例 如，MarketSpecialist 在计算恢复计划收益时，可以从CrewSpecialist和 PassengerSpecialist处及时获取机组人员成本和旅客行程恢复成本。2 多智能体协同决策机制根据上文搭建的 MAS 框架，协同决策主要发生在通信层 Agent 之间。本文对航空公司延误恢复时部门间的常规协商流程进行改进，将其协商过程根据不同任务阶段进行划分，构建如图 4所示的三阶段协同决策机制。如图 4所示，Agent间通过标准会话进行通信，从而实现信息共享与沟通协商。每一次会话包括5个元素，可表示为Conversation=(ConversationID，MessageType，Sender，Receiver，Ontology)（1）式 中：ConversationID 表 示 会 话 序 号；MessageType 表示消息类型，本文中包括 5 种，分别为请求方案、接受方案、拒绝方案、提出方案和方案生成失败；Sender 表示消息的发送方；Receiver 为消息的接收方；Ontology 为消息本体，其中包含消息的具体内容。Agent 将自己的需求或决策以会话消息的形式发送给其余协商参与者，又从接收的会话消息中提取信息进而调整决策，经过多轮会话，最终达成协商一致。下面对每一阶段作具体阐述。2.1预恢复方法在预恢复阶段，AOCManager 首先捕获造成延误的异常信息，例如恶劣天气、飞机故障以及机组缺勤等，然后通过分析识别出即将受到干扰的资源，并要求对应部门的 Agent 给出解决方案，尽快恢复异常。如果收到请求的 Agent 能够独立解决资源恢复问题（例如在机组缺勤时找到备用机组），而不影响航班计划的正常运行，则结束协商流程，AOCManager 返回监控状态，否则进入可行解协商阶段。通过预恢复可以将异常限制在一定范围内，尽量避免改变航班计划、影响其他部门的正常运行。2.2可行解协商机制由于受扰Agent无法依据原航班计划独立恢复受扰资源，因此在这一阶段，AOCManager需要调整航班计划，以帮助资源受扰的 Agent完成恢复工作。AOCManager首先以受扰资源为约束生成多个航班计划恢复方案，然后将这些备选方案发送给其他部门的Manager，要求其生成相应的配套方案。在这一过图 4 三阶段协同决策机制Fig.4 Three-stage collaborative decision-making mechanism871第 55 卷南 京 航 空 航 天 大 学 学 报程中，CrewManager由于机组合法性约束众多很可能难以完成任务，因此，需要与AOCManager进行反复协商，根据机组资源和飞机资源进一步调整航班计划，详细协商规则如图5所示。在可行解协商的过程中，CrewManager 分析当前无法形成可行解的原因，并与 AOCManager进行信息共享，使其能够有方向性地调整航班计划和调配飞机资源，避免在错误的尝试中浪费时间。通过可行解协商，Managers 得到了多方公认的可行解集合。2.3均衡解自动协商模型均衡解协商的目标是从可行解集合中选出兼顾各部门利益的解，由于资源之间通过航班计划相互关联，因此，均衡解协商的本质是对于航班计划恢复方案的协商。在本文设计的均衡解自动协商过程中，Agent仿真人类协商谈判中的行为模式，从满足自身利益的角度分别提出建议，同时针对其他 Agent提出的建议给出反馈。由于利益冲突，各决策 Agent可能无法得到一致解，此时，Agent 需要根据协商进程和其他智能体的行为动态地调整期望、重新决策。经过反复地协商调整，团队内部最终达成一致。将上述动态协商过程表示为Model=(q，Agent1，Agenti，T)（2）式中：q=uAOC，upassenger，ucrew，umarket 表示协商议题，即各 Agent 的效益值，对应于各部门的优化目标；T=t|t=1，2，k 表示协商轮次集合，k为协商轮 次 上 限；Agent1，Agenti为 参 与 协 商 的Agent，可以将其建模为Agenti=(M，-E，-E，U，v，S，)（3）式 中：M=propose，accept，reject，quit 为 Agent的行动策略集，包括提出方案、接受方案、拒绝方案、退出协商；-E 表示 Agent的效益期望值；-E表示Agent 的效益底线值；U 表示效益评估函数，与下文中 Specialists 决策模型中的目标函数计算方法一致；v表示对其他 Agent所提方案的满意度计算函数，即v=Ut-E-E-E(t-1k)1（4）表示满意度参数，越高表示 Agent 对于协商达成一致的态度越迫切。令S表示 Agent 给出的提议，本文假设 Agent采用时间让步策略生成每轮的提议23S=-E+(-E-E)()t-1k1（5）令i表示 Agent的决策规则，AOCManger和其他 Manager的决策规则略有不同，它还需判别可行解集合中是否存在解满足当前所有 Agent 的期望值组合图 5 可行解协商机制Fig.5 Negotiation mechanism for feasible solutions872第 5 期季灵，等：基于多智能体航空公司航班恢复协同决策方法others=quitt kacceptvt reject&proposevtkacceptvtreject&proposevt or no solutions（7）其中 表示 Agent接受提议的平均满意度。3专家智能体资源恢复模型在 MAS 中，各专家智能体负责根据具体模型求解单一资源的恢复问题，本节将简要介绍这些关键模型。由于单一算法不能在限制时间内动态地解决所有类型的问题，本文充分利用多 Agent系统的并行性，使各个专家 Agent分布式求解延误恢复模型，竞争地为管理员 Agent 提供解决方案，以提高延误恢复方案的优化性能。飞机恢复团队中配有列生成算法专家智能体和遗传算法专家智能体，机组和旅客恢复团队中均配有分支定界算法专家智能体和模拟退火算法专家智能体。由于这些算法都是比价经典且为人熟知的算法，本文不作赘述。3.1飞机路径恢复模型AOCSpecialist 首先基于剩余航班为每一架飞机构建不正常航班调度的时空网络24，然后基于时空网络搜索可行的飞机路径，可行的飞机路径需满足航班时空衔接约束、机场宵禁约束以及飞机日利用率约束，最后构建飞机路径恢复模型求解优化的飞机路径组合。引入以下符号：（1）集合。F 为航班集合；A 为机场集合；K 为可用飞机集合；T1为机场通航时间段集合；P 为飞机路径集合。（2）参数。tj为路径j上的延误时间；tcan为取消一架航班的惩罚因子，取较大值；aij：如果路径j中包含航班i，则为 1，否则为 0；bja：如果路径j的终点机场为a，则为 1，否则为 0；ha：机场a的过夜飞机数；Tj：路径j的飞机执飞时间；c(t)ja：若路径j上有航班在时刻t起降于机场a，则为 1，否则为 0；C(t)a：机场a在时刻t的剩余容量。（3）变量。x(k)j为 01 变量，表示飞机k是否选择路径j；yi为 01变量，表示航班 i是否取消。基于以上符号，建立模型min Z=k Kj Ptjx(k)j+j Ftcanyi（8）s.t.k Kj Paijx(k)j+yi=1 i F（9）k Kj Pbjax(k)j=ha a A（10）j Px(k)j 1 k K（11）j Pk Kc(t)jax(k)j C(t)a t T1，a A（12）x(k)j=0，1 j p，k K（13）yi=0，1 i F（14）式（8）为目标函数，表示总的延误时间最少；式（9）为航班覆盖约束；式（10）为过夜飞机数量约束；式（11）表示每架飞机至多被指派一次；式（12）为机场容量约束，式（13，14）为变量取值约束。3.2机组任务恢复模型CrewSpecialist 首先基于调整的航班计划为每一个机组构建机组调度的时空网络24，然后基于时空网络搜索可行的机组任务串，可行的机组任务串需满足航班任务时空衔接约束、机组返回基地约束以及执勤时间合法性约束，最后建立机组任务恢复模型求解优化的任务串组合。引入以下符号：（1）集合。F为调整后的航班集合；Crew 为机组集合；P为机组任务串集合。（2）参数。ak：如果机组k为调休机组则为 1，否则为 0；uj=djfj，即任务串j的执勤时间与飞行时间的比值，与任务效率成反比；：各机组航班串任务执勤时间的标准差，反映任务分配的公平性；aij：如果任务串j中包含航班i，则为 1，否则为 0；si：航班i的加机组数。（3）变量。x(k)j为 01 变量，表示机组k是否执行任务串j。基于以上符号，建立模型min Z=k Crewj P(ak+uj)x(k)j+（15）s.t.k Crewj Paijx(k)j-si=1 i F（16）j Px(k)j 1 k Crew（17）xkj=0，1 k Crew，j P（18）式（15）为目标函数，表示机组的不满意度最低，机组满意度从 3 个方面进行衡量：（1）工作效率，指机组实际飞行时间与总执勤时间的比值，比值越低说明机组的无效工作时间越长，机组满意度越低；（2）是否存在临时调休，这里是指临时指派休假机组执行航班任务，这会大大增加机组的不满情绪；（3）机组任务的变动率，调整后的机组任务与原任务相比变动越多，机组的满意度越低。式（16）为航班覆盖约束；式（17）表示每个机组只可指派一个任务串；式（18）为变量取值约束。3.3旅客流恢复模型航班计划的变动会导致单航段旅客行程被取消以及多航段旅客行程无法衔接。由于中国主要873第 55 卷南 京 航 空 航 天 大 学 学 报航空公司航班的客座率一般在 70%80%，每个航班都有可用的剩余座位，如果充分利用这些剩余座位，可以实现受扰旅客的行程重排。PassengerSpecialist首先根据调整的航班计划为受扰旅客构建旅客行程网络图，然后基于网络图搜索可行的旅客流恢复路径，可行的旅客流恢复路径需满足起止点与原计划相同、出发时间不早于原计划时间，最后建立旅客流恢复模型求解优化的恢复路径组合。引入以下符号：（1）集合。P 为受扰旅客流集合；R 为旅客流恢复路径集合。（2）参数。d(p)f为旅客流p选择路径f的不满意度，d(p)f=*(tA-tE)，其中为系数，为旅客行程结构变化系数，若旅客行程结构不变则为 1，若由直达变中转取 1.5，若由中转变直达，取 0.6，tA表示旅客实际到达时间，tE为旅客计划到达时间；d(p)can为旅客流p取消的惩罚因子，取较大值；W(p)为旅客流p包含的旅客人数；uf为路径f上的剩余座位数。（3）变量。x(p)f为受扰旅客流p分配在路径f上的旅客人数；y(p)为旅客流p的取消人数。min Z=p Pf Rd(p)fx(p)f+p Pd(p)cany(p)（19）s.t.f Rx(p)f+y(p)=W(p)p P（20）p Px(P)f uf f R（21）x(p)f，y(p)N（22）式（19）为目标函数，表示旅客的不满意度最低；式（20）为旅客覆盖约束；式（21）为恢复路径上的容量约束；式（22）为变量取值约束。3.4收益评估函数MarketSpecialist根据以下收益评估函数计算恢复方案的盈利水平，有Rtotal=R-Caircraft-Ccrew-Cpassenger（23）式中：Rtotal表示一体化恢复方案的总盈利；R表示收入；Caircraft表示飞机运行成本；Ccrew表示机组人工成本；Cpassenger表示旅客延误损失。其中R=fticket+fairline+fovernight（24）Caircraft=Cdepreciation+Cmaintain+Cfule（25）Ccrew=Cduty+Cfly（26）Cpassenger=p P tp（27）式（24）表示收入的计算方式，收入等于最终成行的旅客机票收入fticket、航线补贴fairline和飞机过夜补贴fovernight之和；式（25）表示飞机运行成本的计算方式，为飞机折旧成本Cdepreciation、飞机维修成本Cmaintain和燃油成本Cfule之和；式（26）表示机组人工成本的计算方式，为机组执勤工资Cduty和机组飞行工资Cfly之和；式（27）表示乘客延误损失的计算方式，tp为旅客p的延误的时间；为行程结构变化因子，根据旅客不同行程段的两种行程结构所消耗旅客行程时长的平均数值设置行程结构变化因子的值，若行程由直达变为中转，=1.5，若由中转变为直达，=0.6，否则为 1。4 算例分析4.1算例设计本节设计算例验证航班延误恢复多智能体系统的可行性。算例的假设情景为：某航空公司有 3架 A320飞机，某日的航班计划表包括 3架 A320飞机的机尾号、计划执行的航班号及对应的起降机场、计划起降时间和执行机组，如表 1 所示。旅客行程信息包括旅客的行程类型、航段的旅客数、航班票价，如表 2所示。仿真情景设置为因天气影响，南京禄口机场8：0014：00 关闭，导致航班延误，成都双流机场13：0019：00繁忙，无法接受临时起降航班，且所有机场 0：006：00宵禁。为保证次日航班正常运行，在恢复期末成都双流机场至少需有2架飞机停场，航空公司无备份飞机可用。A320 飞机的座位数为180，飞机的最小过站时间为40 min。南京禄口机场有 1名备用飞行员驻场，到岗时间为早上 8：00，其余机组的执勤时间起始于首个航班任务起飞前30 min且无休假机组可用。原计划机组均为二人制机组，机组的执勤时间不得超过14 h，实际飞行时间不得超过8 h。为保证航班有效衔接，旅客中转时间不得少于40 min，旅客中转行程最多由两段航班构成。基于上述算法和仿真情景，使用 JADE 平台开发 航 班 延 误 恢 复 多 智 能 体 系 统，并 建 立 Sniffer 表 1 原航班计划表Table 1 Original flight schedule机尾号B2435B2436B2437航班号MU2941MU2942MU2943MU2944MU2945MU2946MU2947MU2948MU2949MU2950MU2951MU2952起飞机场NKGCTUPEKNKGNKGCTUPEKCTUCTUNKGPEKNKG降落机场CTUPEKNKGCTUCTUPEKCTUNKGNKGPEKNKGCTU计划起飞时间07：50：0011：50：0015：50：0018：50：0008：40：0012：40：0016：40：0020：40：0009：00：0013：00：0016：10：0019：10：00计划降落时间10：50：0014：50：0017：50：0021：50：0011：40：0015：40：0019：40：0023：40：0012：00：0015：00：0018：10：0022：10：00执行机组122231144433874第 5 期季灵，等：基于多智能体航空公司航班恢复协同决策方法Agent 监 控 系 统 内 各 Agent 间 的 协 商 过 程，将Agent 及其协商过程以 UML 顺序图的形式展现，如图 6 所示。图 6 最上方方框中为参与协商的Agent，各个 Agent的职能在第一章中已详细介绍，最左边一列数字表示协商会话的轮次，图中的横向箭头表示会话消息的收发过程，箭尾表示会话消息的发送方，箭头指向会话消息的接收方，箭头上方的文字表示会话消息中的动作类型。得到调整后的航班时刻表如表 3 所示。调整后的航班时刻表中包含航班出发时刻和到达时刻的调整方案，以及每架飞机待执行的新航班任务，被取消的航班不显示方案详情。恢复方案共取消3架航班，其余 9架航班正常运行。旅客行程恢复方案如表 4 所示。旅客行程恢复方案中包含受扰旅客流的原行程信息和新行程信息。由于座位数限制，同一受扰旅客流可能需要分配到不同的恢复路径上去，在实际落实中，需要地服人员有序协调。旅客行程恢复方案共计取消旅客 214 人，恢复旅客 162 人，为航空公司挽回了43%的客源。4.2结果分析本节将 MAS的恢复性能与人工恢复和一体化恢复数学模型12进行对比。需要声明，航空公司人工调整延误航班的策略是将受扰航班依次顺延，若有航班时间超出恢复期则根据经验取消部分航班。本算例的硬件环境是 Intel双核 P8700处理器、2 GB 内存 PC 机的 Windows 操作系统。算例使用32位的 eclipse编程软件运行 Java语言程序，并调用表 2 旅客行程信息表Table 2 Passenger itinerary information form行程编号12345678910111213141516171819行程类型直达直达直达直达直达直达直达直达直达直达直达直达中转中转中转中转中转中转中转航段 1MU2941MU2942MU2943MU2944MU2945MU2946MU2949MU2950MU2948MU2947MU2951MU2952MU2942MU2943MU2949MU2951MU2942MU2943MU2950航段 2MU2943MU2944MU2950MU2952MU2951MU2952MU2947旅客数/人1201251261241051491221271341361391221081510131214票价/元8407507901 0407807509701 800600700790890540650650570600550600图 6 Agent及其协商流程示意图Fig.6 Schematic diagram of agents and its negotiation process875第 55 卷南 京 航 空 航 天 大 学 学 报CPLEX 求解器进行求解。仿真结果显示，MAS在3.8 s内完成了152次协商会话，最终得到了一致解，可见，使用 MAS 仿真技术实现协同决策机制大大缩减了人工协商成本。除了求解效率显著提高，MAS方法在恢复效果上也得到了很大提升。如图7所示，相对于人工恢复方法，协同决策方法的延误水平降低了 26.63%，并在收益水平、旅客满意度和机组满意度等方面均得到显著优化，表 5展示了多智能体协同恢复方法与航空公司人工协同恢复方法、一体化恢复整数规划模型的对比，多智能体系统生成的延误恢复方案在延误成本、机组不满意度以及旅客不满意度 3个方面均有大幅下降，验证了本文所提出方法的可行性和优越性。在本算例中，一体化恢复数学模型的运行时间为 5.2 s，而 MAS由于采用了分布式计算、协商整合的方法，运行效率更高，总运行时间仅 3.8 s，运行效率提高了接近 20%。在现实意义方面，本系统运行效率的提高将促进 AOCC协同恢复的工作效率，在一定程度上解放了人工劳动力，同时系统运行节省的时间也将会节约航空公司相关的运营成本。在优化效果上，一体化模型恢复方案的经济效益更高，但MAS方法在各方面的优化效果更为均衡。根据上述分析可知，基于多智能体技术的航班恢复协同决策方法可以在短时间内得到兼顾各方利益的均衡解，更符合航空公司生产运营的实际需求。5 结 论本文研究工作的创新性和先进性主要体现在两个方面：（1）从多部门协同决策的角度研究航班延误恢复策略，构建了标准化的部门间协同决策机制，着重解决了部门协同过程中因合法性约束和利益冲突造成的矛盾。（2）从系统仿真的角度研究航班延误恢复方案的求解方法，大大提高了延误恢复方案的求解效率。本文基于多智能体技术对主体间协同决策机制进行了仿真，构建了一个虚拟的AOCC，它能够代替人工完成异常监控以及协同恢复工作，在短时间内生成完整的延误恢复方案，为航空公司提供了一个即时辅助决策工具。本文侧重于多智能体恢复系统的框架搭建和协商逻辑构建，在有效性验证方面还有许多需要完善的地方。首先，由于时间关系，本文仅设计了小规模算例验证方法的可行性，对于