基于多Agent的通航运力资源协同调度

张红颖，周子林，李 彪

(中国民航大学a.电子信息与自动化学院；b.航空工程学院，天津300300)

0 引 言

随着近年来跨区域经济联系的日益密切，通航业务规模稳步增长，行业市场化程度不断提升，对通航运输能力提出了更高的要求.传统资源调度方法多建立在点对点的单向任务需求基础上，应对并行多任务、多资源的规模化协同调度问题能力不足[1]，难以保障日益增长的运力需求，因此如何建立有效的、多位一体的通航运力资源协同调度方法成为国内外研究的热点问题，国内外学者主要利用启发式算法和智能体算法进行研究.启发式算法方面，袁建国等[2]提出多目标自适应快速人工蜂群算法处理调度决策片面性的问题；王坚浩等[3]提出一种基于入侵杂草蝙蝠混合算法的双子群任务规划方法.但启发式算法迭代次数多，求解速率偏慢的问题并未完全解决.Rolka 等[4]采用智能体算法，建立基于黑板模式的分布式多Agent控制网络任务调度模型，引入联合约束惩罚算子强化底层Agent的效用值增益函数，提升了分配方案的计算速率；为增强系统调度能力，王冲[5]设计了相邻Agent的信息协议增益矩阵，改善了调度模型耦合度，但智能体算法存在系统资源占用过多的问题，随着并行任务数量的增加，计算时间呈指数级上升趋势[6].

上述国内外资源调度方法依然存在求解多任务模型速度较慢的不足之处，故本文提出一种基于多Agent的通航运力资源协同调度方法，建立生产任务与运力资源匹配模型以提升并行任务处理效率，在匹配性结果的基础上设计资源调度数学模型及其求解算法，最后进行仿真实验，验证该方法的合理性和有效性.

1 通航运力资源协同调度框架

提出一种多级通航运力资源协同调度框架，将问题分解为系统级并行任务与运力资源的匹配过程，与分系统级运力资源协同调度过程分别建模求解.

系统级匹配模型以运力资源作业效率最大化为目标，设计招标式多Agent协商算法求得并行生产任务与通航运力资源的匹配性结果.

分系统级资源调度模型以匹配性结果为主体，依据对应的目标函数及约束条件，构建数学模型并求解，实现分系统内资源协同调度过程.整体运力资源协同调度模型框架如图1所示.

图1 基于招标式多Agent 协商的协同调度算法基本框架Fig.1 Basic frame of collaborative schedule algorithm based on bidding multi-Agent negotiation

2 系统级多Agent运力匹配模型

2.1 模型架构

针对通航并行任务与运力资源的匹配过程，建立如图2所示的系统级Agent 模型.嵌入基于招投标机制的多Agent 协商模块，设立中央调度Agent作为招标管理者，完成竞标资源层与招标任务层的信息交换，实现任务与运力资源之间的匹配性关系.

图2 系统级多Agent 运力匹配模型Fig.2 Matching model of system-level multi-Agent

整体模型中，各运力资源Agent拥有均等机会发布自身属性信息的竞标模式决定着该协商算法能够同时访问多类候选资源，并依据判决条件选取任务的最佳执行者，即最优解.该方法在算法机制上提升了协同调度多类资源匹配并行任务的处理能力.

2.2 任务招标

定义任务Agent 集合为{T1,T2,…,Tn} ，集合中共有n个任务Agent 元素；航空器Agent 集合为{P1,P2,…,Pi} ，集合中共有i个航空器Agent元素；机组Agent 集合为{C1,C2,…,Cj} ，集合中共有j个机组Agent元素.任务Tn向中央调度Agent广播招标书并申请资源Pi和Cj，招标书向量Xn=(tn,Vn,An,Sn,Mn,Qi,Wj)，其中，tn为任务作业需求时间，Vn为任务需求速率，An为任务海拔得分，Sn为任务坡度得分，Mn为任务气象得分，Qj、Wj分别为0-1二值化航空器、机组状态变量，变量为0表示处于适航状态，变量为1 表示处于不适航状态.以上数据信息存储于状态知识库中，在本文讨论范畴中视为已知条件.

2.3 运力资源竞标

中央调度Agent接收招标书Xn后转发至运力资源层中的各Pi；满足数据变量An、Sn与Mn且状态变量Qi为0 的Pi，向状态知识库查询机型对应且状态变量Wj为0 的Cj，向中央调度Agent 返回包含机组、航空器编号与作业速率的竞标书向量xn=(Pi,Cj,vij)；否则返回竞标书为空.

2.4 任务评标

接收竞标书应答的中央调度Agent 筛选满足任务需求速率Vn的最大值vij，宣布对应的竞标单位Pi、Cj中标，完成任务Tn与航空资源的匹配成组过程.任务资源匹配性算法流程图如图3所示.

图3 任务资源匹配算法流程图Fig.3 Workflow of tasks matching with resources

求解系统级匹配模型所得到的匹配性结果包含在任务Agent单元内输出，便于资源调度分系统继承对应数据.

3 分系统级多Agent运力资源调度模型

3.1 模型设计

分系统级多Agent 资源调度模型如图4所示，以任务Tn为主体，所匹配运力资源Pi、Cj为被控对象，在继承对应匹配性结果的条件下，建立资源调度数学模型并求解最优解.

图4 分系统级资源调度模型Fig.4 Model of subsystem resource scheduling

3.2 设定目标函数

通航实际电力巡检作业过程中，机组作业质量与作业时长具有正相关性，因此选取参数单机日利用率作为分系统n优化目标.定义分系统n中单机日利用率Dn向量表达式为

式中：tn为任务Tn的需求作业时间值，总计天数为t；Bk为长度为t的机组飞行时长向量，元素bk表示第k天机组的作业时长(h).

单机日利用率Dn是对向量Bk元素求和所得总飞行时长与tn的比值，反映了任务Tn中航空资源Pi和Cj的使用效率.实际作业过程中，天气、管制等外界因素造成的客观不适航性对航空资源指派造成一定的影响，需要对分系统目标函数作规划调整.定义航空器适航矩阵Zn为

式中：矩阵Zn为t×t的对角线矩阵，主对角线元素为第t天航空器的适航性，适航则元素为1，不适航则元素为0.将适航矩阵右乘飞行时长矩阵Bk后结合式(1)可得到修正后的目标函数为

3.3 构建约束条件

分系统数学模型约束条件源自航空运输业的规章条例，从安全因素与任务计划两方面对运力资源实现约束.

安全因素约束体现在航空器与机组劳动强度均受到客观条件限制：航空器各机型续航时间不超过m1h，机组的工作时长不可超过m2h以避免疲劳生产，m1、m2具体数值可查阅相关规章条例，安全因素约束为

式(4)表示飞行时长向量Bk中的每个元素均小于等于m1，即航空器日均作业时长受到限制；式(5)表示飞行时长向量Bk中值不为0的元素不超过m2，即保证机组的工作天数在正常范围内.

任务计划约束体现在每日需完成基础均摊任务量，方可保证按期完成生产任务.任务量约束条件为

式(6)表示机组每日结算的总作业里程数均满足总任务量的进度要求，即保证可按计划完成任务需求.

3.4 改进遗传算法求解

遗传算法处理并行任务能力强，稳定性高[7]，适合求解包含并行多任务的资源调度模型，但需针对传统遗传算法后期收敛速度慢的缺点进行改进.轮盘赌选择算子根据个体适应度来分配选择概率，具有精英保留的特点，在此方法上加入基于进化代数的催熟机制，提升后期种群的选择压力以保证后期收敛速度，改进后的轮盘赌选择算子个体被选概率表达式为

式中：Pind为种群个体被选概率；Find为个体适应度值；o为当前第r代的种群大小，e为当前进化代数，E为总进化代数.

式(7)保证适应度值越高的个体被选中的概率越大，且随着进化代数的增加，优秀个体的权重也获得提高，从而在保留适应度值高的个体的同时加速了后期算法收敛.改进遗传算法求解资源调度模型主要步骤如下：

Step 1以Bk向量为实数编码形式随机生成n个分系统的初始种群.

Step 2以式(3)为种群适应度值评价函数进行计算.

Step 3依据式(4)～式(6)进行个体淘汰，未淘汰个体依据式(7)进行选择操作，适应度值较高的个体组成新种群.

Step 4对并行n个种群进行变异交叉操作生成下一代完整种群.

Step 5若进化代数达到终止进化代数，算法结束，输出结果；否则重复Step 2～Step 4.

求解算法流程图如图5所示.求解资源调度模型所得结果Bk通过调度Agent 发送至Pi和Cj来指导通航资源的作业时长.

图5 资源调度模型求解算法流程示意图Fig.5 Flow chart of resource scheduling model

4 算例分析

4.1 仿真平台及先验数据

本文所提出的通航运力资源协同调度方法基于java/JADE(version1.8)平台进行开发测试，硬件配置为Intel Core i7 CPU，内存16 G.首先，在JADE平台创建任务、航空器、机组Agent与中央调度Agent模型；其次，开发实现所设计的Agent协作法则；最后，导入表1和表2所示国内某大型通航公司实时运行数据，以及表3所示由气象、管制等限制因素形成的适航属性表.

表1 任务数据信息Table1 Task data

表2 运力资源数据信息Table2 Transport resources data

由表1～表3可得任务、航空器、机组状态知识库具体数据，以及任务招标书Xn与航空器适航矩阵Zn具体表达形式，查阅民航局所发布CCAR-121部条例可得m1、m2值，以便仿真模型计算求解.

4.2 仿真结果及分析

4.2.1 系统级运力匹配性结果

仿真所得系统级运力匹配结果如表4所示.将匹配性结果与实际生产运行数据进行对比，如表5所示.

表3 航空器适航性Table3 Airworthiness of aircraft

实验所含数据信息表如图6所示。对比结果可得：使用协同调度算法所得匹配性结果同比实际运行结果在平均机组作业速率上提升1.6 km/h，运力资源作业能力更强；单任务计算求解模型时间控制在2.3 s 内，求解速率受并行任务数量影响较小，体现出较好的并行多任务处理能力.

表4 系统级运力匹配结果Table4 System-level matching results

图6 匹配性结果与实际运行数据对比Fig.6 Comparisons between matching results and actual operation data

4.2.2 运力资源调度结果

5 类并行任务运力资源调度结果如表6所示，限于篇幅，此处给出整个作业周期(30 d)内部分日期的机组作业时长.

由表6中资源调度数据可得，本文所提出的调度方法求得每日作业小时数结果均优于实际运行数据.

为验证本文方法的资源调度能力，选取单机日利用率和作业时长均方差两类关键参数，与文献[3]中人工蜂群算法、文献[4]中分布式多Agent调度网络模型实验结果进行对比，所得仿真对比数据如表7所示.

由表7中数据可得协同调度算法资源调度结果在单机日利用率方面相比人工蜂群算法调度结果平均提升0.27 h/d，相比分布式多Agent 调度网络模型调度结果平均提升0.19 h/d，有效增加了运力资源作业时长.

针对参数作业时长均方差进行分析，本文提出算法在作业时长均方差方面相比人工蜂群算法调度结果平均降低0.12 h，相比分布式多Agent 调度网络模型调度结果降低0.03 h，证明本文算法提升了作业稳定性.

表6 并行多任务运力资源调度结果Table6 Capacity resources scheduling results of parallel multi-task

表7 仿真参数对比结果Table7 Comparison of simulation parameters

为验证本文提出方法的计算效率，将资源调度算法与传统遗传算法及文献[5]中所提出的多Agent 耦合算法计算时间数据绘制如图7所示，其中遗传算法的种群迭代次数设为50代.

图7 求解计算时间对比Fig.7 Comparisons of calculating time

由图7可得，本文提出的资源调度算法因加入了基于进化代数的催熟机制，相比传统遗传算法求解速率提升了26.1%；而与多Agent 耦合算法相比，对于单个任务的计算时间虽然有所增加，但随着并行任务数量的增长，在计算速度方面的优势逐渐显著.

结合对比仿真实验结果可以看出，所提出的基于多Agent 通航运力资源协同调度算法通过细化运力匹配流程、建立资源调度模型与综合考量各类限制条件等方法，有效提升了多任务通航资源作业质量与稳定性，并能在较快时间内完成求解过程.

5 结 论

针对并行式多任务通航资源调度问题，建立基于多Agent协商的运力资源协同调度模型，在运力匹配环节设计基于招投标机制的求解模型算法以提高处理并行任务的匹配能力与效率；设计并行式资源调度分系统模型继承匹配性结果，并提出相应的目标函数与约束检验规则进行求解.仿真结果证明，所提出的基于多Agent的通航运力资源协同调度方法能有效求解通航运输业并行多任务资源调配问题.