基于动态信誉的飞机推出时隙分配Stackelberg博弈*

刘丽华 张亚平 王明辉 邢志伟

(河南城建学院土木与交通工程学院1) 平顶山 467036) (哈尔滨工业大学交通科学与工程学院2) 哈尔滨 150090)(江苏省苏州市吴江区公安局3) 苏州 215200) (中国民航大学航空地面特种设备研究基地4) 天津 300300)

0 引 言

高峰时段的场面拥堵及航班延误是国内外机场面临的共性问题，不仅降低机场运营效率，也给航空公司带来巨大损失.依靠基础设施扩建已无法满足场面需求的增长，场面运行管理至关重要.场面运行管理涉及推出管理、路径优化[1]等，传统先到先服务(first come first serve，FCFS)推出管理下，推出需求在时间上集中、极易引发拥堵，而合理的推出管理能分散推出需求，大幅降低拥堵和地面成本.

Fornés[2]分析了推出率控制的停机位等待约束.杨双双等[3]提出基于场面监视雷达系统的滑行推出许可决策启发式控制方法.张亚平等[4]从机场场面滑行容量的角度对飞机推出时段进行了研究.实际推出过程中，如果飞机未按约定时刻推出，按照现行的FCFS分配原则，该飞机将延迟较长时间推出，航空公司(以下简称公司)不会因违约受到惩罚，不但浪费推出资源，对未违约公司也不公平.现代博弈论认为解决违约行为最有效方法是给违约一方足够严厉的惩罚，邢志伟等[5]在飞机除冰研究中提出浮动优先级算法对违约公司进行了惩罚.

违约行为下的推出时隙分配需要先确定飞机-时隙对，然后求解最优推出时刻.本文首先设计基于动态信誉优先的飞机推出时隙分配混合决策流程得到飞机-时隙对，接着利用Stackelberg博弈建立双层规划模型，并设计改进的人工鱼群算法求解最优推出时刻，最后将其应用于新郑机场飞机推出研究，验证模型及算法性能.

1 基于动态信誉的飞机推出时隙分配混合决策

1.1 动态信誉优先概念

①为了让更多小公司公平参与竞争，信誉优先级仅考虑履约与否；②优先级最高的公司享有优先权，若选定飞机按时推出，该公司优先级保持不变；若违约，优先级降低；③参与申请但优先级较低没有获得资源的公司，下次分配中适当提高其优先级，作为对失去资源的补偿；④没有参与资源争夺的公司信誉不受影响.

1.2 基于动态信誉和FCFS的混合决策算法行为规则

1.3 推出时隙分配混合决策

对于每一个时隙依次执行如下步骤：确定待选飞机、公司集合，利用混合决策算法确定飞机-时隙对，根据是否违约进行决策，直到所有时隙分配完算法结束，决策流程见图1.

注：虚线框内是决策过程公司信誉优先级的动态变化图1 基于动态信誉的飞机推出时隙分配混合决策流程

(1)

2 信誉机制下的飞机推出Stackelberg博弈模型

2.1 Stackelberg博弈建模

2.2 上层机场收益

i=1,2,…,n

(2)

(3)

2.3 下层公司收益

将公司收益转换为最小化本公司单架飞机平均地面成本

i=1,2,…,nl,l=1,2,…,u

(4)

(5)

(6)

3 改进人工鱼群算法

3.1 算法步骤

为了加快求解速度和保证精度，本论文对AFSA邻域中心及最优解选择进行改进.

步骤2计算初始鱼群各个体适应值，取最优AF状态及其值赋给公告板.

步骤3个体依次进行追尾、觅食、聚群行为(若超过try_number次后仍无明显进步就加入随机行为)，生成新鱼群.

步骤4评价所有个体.若某个体优于公告板，则γ将公告板更新为该个体.

步骤5公告板上最优解满足收敛准则，算法结束，否则转步骤3.

3.2 邻域中心

为了避免求解过程陷入局部最优，设计新的邻域中心[7]计算方法：将y的Visual邻域AF按照目标函数值y由小到大排列；取y值较小的前50%条组成新的集合U，在U中选择新的状态tv；如果(ys-yv)/ys<γ(为误差，考虑到成本加权值变化程度不大，令γ介于10%～20%)，接受，这些U0组成新的集合U0(U0∈U).若U0非空，则在U0中任选一个作为y，否则将y作为中心.

3.3 面向未违约公司的最优解

AFSA最优解可能并不唯一：y相等状态y不同.在y相同情况下考虑未违约公司利益：至少有一家未违约公司平均成本低于违约公司，选择能够使某未违约公司平均成本最小的结果.

4 仿真分析

4.1 数据准备

表1 计算相关数据

注：资料来源河南省机场集团有限公司.

假设飞机编号f8，f10违约，由式(2)及表1得到飞机-时隙对见表2(无违约和违约下飞机f1～f7、f15～f16、f21～f29的分配对fi-sj中编号一致，不再列出).

f8、f10与后续飞机顺序均下滑，下滑程度随a值变大而明显，体现了违约惩罚.a=2时，PN在f8之后的飞机未受影响，惩罚力度不够；a=6时波及到f10之后的第6架，导致惩罚过重.综上a=[3,5].

表2 飞机-时隙分配对

4.2 仿真设计

图2 AF搜索过程(a=3，横、纵坐标x、y为鱼在水域中位置)

图3 AFSA收敛过程(a=3)

AF经过45次迭代由分散到集聚，两个目标函数达到最优4.87 min/人、447元/架.

4.3 结果分析

表3 仿真结果

图4 每架飞机地面成本

图5 单架飞机滑出时间

5 结 束 语

本文研究违约行为下的推出时隙分配优化，提出动态信誉优先理论及混合决策算法；将推出时刻优化的非合作博弈描述为双层规划问题，考虑因素更加全面；并对人工鱼群算法进行改进，以加速找到全局最优. 仿真结果表明本方法既能对违约公司适度惩罚，又能兼顾各方利益，同时降低滑出时间和地面运行成本.

[1] 董莹,安然.机场航空器地面滑行时间优化研究[J].交通运输系统工程与信息,2011,11(5):141-146.

[2] FORNÉS MARTINEZ H. Analysis of potential implementations of pushback control at LaGuardia Airport[D]. Boston: Massachusetts Institute of Technology,2015.

[3] 杨双双,朱华庆.航空器推出决策的优化研究[J].武汉理工大学学报(交通科学与工程版),2014,38(1):227-231.

[4] 张亚平,刘丽华,郝斯琪,等.基于弹性滑行容量的飞机有效推出时隙研究武汉理工大学学报(交通科学与工程版),2016,40(6):937-942.

[5] 邢志伟,乔晓辉.飞机地面除冰运行的非合作博弈研究[J].系统仿真学报,2011,23(3):433-437.

[6] 刘丽华,张亚平,邢志伟,等.基于离散差分进化的飞机推出决策优化[J].交通运输系统工程与信息,2016,16(6):196-203.

[7] 王飞.地面等待策略中的时隙分配模型与算法研究[D].南京:南京航空航天大学,2010.