基于合作博弈论的多机场终端区协同航班调度

吴　艺，王　湛

（南京航空航天大学民航学院，南京211100）

基于合作博弈论的多机场终端区协同航班调度

吴艺，王湛

（南京航空航天大学民航学院，南京211100）

针对多机场进离场航班协同调度问题，以协同决策（CDM）理念为基础，结合合作博弈论相关理论建立协同航班调度模型.模型主要分析机场、航空公司以及空管部门的效用函数和拒绝性函数，通过计算各航班拒绝性值和选择性值分析进离场航班次序.实例仿真表明，基于博弈论的协同航班调度优化模型有较好的准确性和实用性，有助于解决机场终端区的航班调度问题，较公平地兼顾了机场、航空公司和空管部门之间的利益.

调度公平性；多机场航班调度；合作博弈论；协同决策

随着我国民用航空运输业不断发展，空中交通需求量持续增大，需求量较高的地区通常都集中在运行具有一定相关性的多机场终端区［1］.该区域机场布局密集、空域结构复杂，引起航班延误发生，影响运行效率，因此需要对该区域航班进行优化调度，使终端区进离场航班有序进行.

地面等待程序（GDP）和空中等待程序（AHP）是解决该类问题的有效途径［2］.传统的GDP和AHP的运行基于空管部门、航空公司以及航空公司之间信息互换，很难有效地利用时空资源.协同决策理念（CDM）起源于美国FAA，是在航空公司、机场和空管部门之间引入协同决策的思想，致力于安全、高效和公平地调整交通需求与供给［3］.多机场终端区起降航班协同调度涉及多个机场之间进离场航班的运行，将综合考虑机场、航空公司、空管部门三方利益优化各航班起降次序，合理运用GDP、AHP，提高终端区资源利用率.

博弈论是应用数学的一个分支，主要适用于有限资源分配的问题.根据博弈假设的环境的不同，可分为合作博弈和非合作博弈，前者以团体利益为目标，后者分析参与者存在冲突与合作的决策模型，使自己利益最大化［4］.多机场终端区航班调度参与主体主要包括机场、空管部门以及航空公司，其中机场主要以最大化容量利用率为目标，提高机场资源使用效率；空管部门将安全高效调度进离场航班运行，合理运用GDP和AHP，使终端区有效运行；航空公司作为航班承运人，以延误最小化为目标降低运营成本为目标.但上述三方均可在机场终端区高效运行的环境下实现各自的目标，因此本文利用合作博弈论的理论，根据多机场终端区各决策部门目标，建立效用函数和拒绝性函数，构建系协同航班调度模型，合理调度多机场终端区进离场航班.模型相关参数和定义如表1所示.

表1　变量定义表

1　协同决策效用函数分析

协同决策理论（DME）是协同航班调度的基础，本质是多方参，以控制总延误的情况下兼顾空管部门、航空公司和机场三方利益为目标，因此建立的效用函数.

1.1空管部门效用函数

空中交通管制服务的目的是确保空中交通安全、高效运行，因此需合理利用GDP和AHP，缓解空中交通拥堵问题.

1）拥塞效用函数

空域饱和能力N（x）描述给定扇区x可容纳飞机数量的最大值.当给定扇区x内飞机数量达到扇区容量的100%时，称扇区x是饱和的.而当给定扇区x内飞机数量达到扇区容量的80%时，称扇区x是拥挤的［5］.变量c是扇区x可以支持不造成拥堵的最大飞机数量，具体计算如下：

其中，［N（x）×0.8］是计算N（x）×0.8时的整数部分，dec是计算N（x）×0.8时的小数部分.dec给定如下：

函数Cs（x）给出了在每个扇区x的拥塞程度：

2）延误效用函数

空管部门应用地面等待程序（GDP）减少进入终端区的飞机数量，从而缓解空中交通拥堵.然而，由于空中的飞机需要在机场着陆，并最终进入停机位，应用这一措施会引发地面空间不足，从而造成飞机空中等待，导致空中延误.因此需衡量地面延误和空中延误值：

航空器地面延误计算如下：

航空器空中延误计算如下：

终端区内航空器总延误计算如下：

1.2航空公司效用函数

1）延误效用函数

航班的运营需要公司投入大量的成本，协同航班调度的措施需尽可能减少航班延误，降低运营成本.空中交通管制单位采取不同的限流措施，则会产生不同的航班调度，即不同的航班次序，各航空公司原有的航班排序被打乱，产生不同的延误分布，延误分布的影响如式（7）所示.

2）成本效用函数

航班延误会导致空公司将产生额外的财务费用，如飞机的运营成本，额外的燃料消耗，增加的机组小时以及航班取消和乘客赔偿等间接成本等.由延误导致的财务费用的影响表现为：

综上所述，航班调度对航空公司的效用影响如下：

1.3机场效用函数

机场作为航空飞行的起点和终点，在流量管理体系中发挥着不可替代的作用.对于机场单位来说，任意给定时刻t，最好的状态就是机场机降能力可以满足场内飞机起降运行.机场起降能力可以使用可用跑道数和可用停机位数衡量.任意给定时刻t可用跑道数如下：

任意给定时刻t机场可用停机位数如下：

基于上述方程，任意给定时刻t机场起降能力可用式（12）表示.

2　基于博弈论的协同决策拒绝函数分析

给定可选决策集合U，为了找到满意的决策，计算每个选项u的选择性值和拒绝性值.程度是很重要的.其中，选择性可以被理解为支持u∈U过程具有的成功度；拒绝性表示在决定支持u∈U过程中，获得成功的资源消耗的程度或参与决策的风险程度［6］.

2.1空管拒绝性模型

考虑空管的偏好方程，终端区x不允许飞机数量大于饱和容量N（x），由饱和容量N（x）决定的终端区拥堵程度的最大值为Csmax（x）.Csmax（x）的计算如式（13）所示.

GDP决策时，空中交通管制单位的拒绝性和Csmax（x）值相关.因此，初始ATC拒绝性的值可以由拥堵Csmax（x）得到，具体如下：

为了空中交通安全，理想情况是减少AHP程序的时间.终端区x飞机的空中延误计算如下：

因此，AHP决策时，空中交通管制单位的拒绝性值也由式（16）得到：

其中：dAhp（x）是当前空中延误，dAhp（u）是空中总延误.Δahp（x）为终端区x的AHP时间变化，定义如下：

具体计算流程如图1.

图1　管制单位拒绝性值计算流程图

2.2航空公司拒绝性模型

根据航空公司的偏好方程，mt0，t是t0到时间段终端区x内延误飞机之间累积的延误分布平均值，计算如下：

GDP程序中，当航班延误值增加并超过mt0，t时，航空公司会产生拒绝性，并且与延误分布平均值mt0，t有关.所以，航空公司初始的拒绝性值可由式（19）得到：

飞机执行AHP程序时，会产生额外的燃油消耗，将对航空公司造成额外的经济损失，因此产生经济拒绝值.空中等待最大值为D（f），由燃油储量决定，航班取消前的地面等待最大值为C（f）.一架飞机最多可以延误C（f）和D（f）中的最低值，将这些时间按分钟计算，航班延误最大值dAthmax（f）如式（20）所示.

执行AHP决策时，航空公司的拒绝性值：

计算流程如图2.

图2　航空公司拒绝性值计算流程图

2.3机场拒绝性模型

当机场着陆能力饱和时，GDP拒绝会产生；否则，不产生拒绝值.因此机场拒绝性值可由式（22）得到：

计算流程如图3：

图3　机场拒绝性值计算流程图

3　选择性函数

当终端区空域出现拥堵，将无法接受更多的飞机起飞进入空域，地面等待GDP程序就会执行.因此，地面等待GDP对应的初始选择性值可由下式得到：

当越来越多航班执行GDP程序，则机场起降能力越低，即地面拥堵程度越严重，空中等待AHP程序决策选择性越强.所以PSahp（u）的选择性值可由下式得到：

根据上述分析，对终端区内航班进行起飞降落分析，采用以下计算流程选择GDP程序或者AHP程序计算其拒绝性值和选择性值.见图4.

图4　选择性值计算流程图

4　案例分析

本文主要分析对上海虹桥机场和浦东机场的机场航班调度进行仿真模拟.虹桥机场，有3个可用起降空间，和浦东机场，无起降空间.终端区x模拟分析数据：饱和容量N（x）=20，当前空中飞机数V（x）=18.12架离场飞机，其中7架在进行地面等待程序；6架飞机在空中申请着陆在虹桥或浦东机场，其中3架飞机已经在空中等待程序中.18架飞机对应的航班基础数据如表1所示，Cf（min）指航班允许的地面等待最大值（按分钟计算），Df（min）指航班允许的空中等待最大值（按分钟计算）.

根据博弈模型，计算GDP决策的结果值如表2、3所示.

表2　航班基础数据

表3　虹桥机场离场航班

表4　浦东机场离场航班

根据表3、4的选择性和拒绝性，以及给定的决策权限，有利于航班而不考虑机场的偏好，我们可以得到航班起飞序列：F6≺F4≺F10≺F7≺F12≺F1≺F2≺｛F3∨F5∨F8∨F9∨F11｝.若给定的决策权限有利于机场而不考虑航空公司的偏好，航班起飞序列则是：｛F7∨F8∨F9∨F10∨F11∨F12｝≺｛F1∨F2∨F3∨F4∨F5∨F6｝.对于空管单位，模型返回较低的拒绝性值，即终端区还有可用空间给新航班起飞.

任意的地面等待5 min的决策，选择性比率都保持0.5.另一方面，起飞航班也保持相同比率.所以，得到的适配CDM机制参与者的满意起飞序列是：F10≺F7≺F12≺｛F8∨F9∨F11｝≺F6≺F4≺F1≺F2≺｛F3∨F5｝.

空中等待程序（AHP）计算的进场航班选择性和拒绝性值如表5所示.

表5　两机场进场航班

表5中，AHP程序空管的拒绝性保持固定值不变，然而，进场航班需要机场的起降空间，因此机场的拒绝性值不稳定.所以，考虑航班的进场序列是：｛F13∨F14∨F15｝≺F18≺｛F16∨F17｝.计算结果表明浦东机场的飞机在空中等待直到该机场解除饱和状态.

5　结语

本文以协同决策（CDM）理念为基础，分析终端区内机场、航空公司、空管部门对进离场航班调度的效用函数，并以此为依据，结合合作博弈论相关理论建立协同决策拒绝性模型.通过分析进离场航班GDP和AHP程序的选择，计算该航班机场、航空公司和空管部门三方的拒绝性值，分析航班进离场次序，给决策三方建立参考.研究表明：基于博弈论的协同航班调度优化模型有较好的准确性和实用性，有助于解决机场终端区的航班调度问题，较公平地兼顾了机场、航空公司和空管部门之间的利益.之后可考虑多机场进场航班各机场之间、各航空公司之间调度的公平性问题，进一步改善多机场终端区机场航班的运行.

［1］IDRISH.Queuing analysis of interdependencies between multiple-airport system operations［C］//South Carolina：9th AIAA Aviation Technology，Integration，and Operations（ATIO）Conference，2009.

［2］张洪海.机场终端区协同流量管理关键技术研究［D］.南京：南京航空航天大学，2009.

［3］SARAF A P，LATER G L.An efficient combinatorial optimization algorithm for optimal scheduling of aircraftarrivals at congested airports［C］//［s.n.］：IEEE Aerospace Conference，2006.

［4］SOOMER M J，RANX G J.Scheduling aircraft landings using airlines’preferences［J］.European Journal of Operational Research，2008，190（1）：277-291.

［5］张妍.多机场终端区排序方法研究［D］.南京：南京航空航天大学，2014.

［6］RIBEIRO V F，WEIGANG L.Collaborative decision making with game theory for slot allocation and departure sequencing in airports［C］//Bergamo：17th Air Transport Research Society World Conference，2013.

Research on collaborative flight scheduling based on cooperative game theory in multi-airports term inal area

WU Yi，WANG Zhan
（Department of Civil Aviation，Nanjing University of Aeronautics and Astronautics，Nanjing 211100，China）

To solve the collaborative scheduling problem for arrival and departure aircrafts in multi-airports terminal，a collaborative flight schedulingmodelwas builtbased on the cooperative game theory and the Collaborative Decision Making（CDM）.The preference functions and the reject-ability functions for airports airlines and ATC weremainly analyzed by themodel.Then the reject-ability and the select-ability were calculated to analyze the sequence of the arrival and departure aircrafts.The simulation experiment indicated that the collaborative flight schedulingmodel based on the cooperative game theory was accurate and practical，and itwas helpful to solve the flight scheduling problem in terminal area，balance the fairness among airports，airlines and ATC.

scheduling fairness；aircrafts scheduling in multi-airports；cooperative game theory；CDM

V355

A

1672-0946（2016）02-0237-05

2015-06-12.

江苏省自然科学基金（Bk20130821）

吴艺（1990-），女，硕士，研究方向：空域规划与管理.