基于合作博弈論的多機(jī)場終端區(qū)協(xié)同航班調(diào)度

吳　藝，王　湛

（南京航空航天大學(xué)民航學(xué)院，南京211100）

基于合作博弈論的多機(jī)場終端區(qū)協(xié)同航班調(diào)度

吳藝，王湛

（南京航空航天大學(xué)民航學(xué)院，南京211100）

針對多機(jī)場進(jìn)離場航班協(xié)同調(diào)度問題，以協(xié)同決策（CDM）理念為基礎(chǔ)，結(jié)合合作博弈論相關(guān)理論建立協(xié)同航班調(diào)度模型.模型主要分析機(jī)場、航空公司以及空管部門的效用函數(shù)和拒絕性函數(shù)，通過計(jì)算各航班拒絕性值和選擇性值分析進(jìn)離場航班次序.實(shí)例仿真表明，基于博弈論的協(xié)同航班調(diào)度優(yōu)化模型有較好的準(zhǔn)確性和實(shí)用性，有助于解決機(jī)場終端區(qū)的航班調(diào)度問題，較公平地兼顧了機(jī)場、航空公司和空管部門之間的利益.

調(diào)度公平性；多機(jī)場航班調(diào)度；合作博弈論；協(xié)同決策

隨著我國民用航空運(yùn)輸業(yè)不斷發(fā)展，空中交通需求量持續(xù)增大，需求量較高的地區(qū)通常都集中在運(yùn)行具有一定相關(guān)性的多機(jī)場終端區(qū)［1］.該區(qū)域機(jī)場布局密集、空域結(jié)構(gòu)復(fù)雜，引起航班延誤發(fā)生，影響運(yùn)行效率，因此需要對該區(qū)域航班進(jìn)行優(yōu)化調(diào)度，使終端區(qū)進(jìn)離場航班有序進(jìn)行.

地面等待程序（GDP）和空中等待程序（AHP）是解決該類問題的有效途徑［2］.傳統(tǒng)的GDP和AHP的運(yùn)行基于空管部門、航空公司以及航空公司之間信息互換，很難有效地利用時空資源.協(xié)同決策理念（CDM）起源于美國FAA，是在航空公司、機(jī)場和空管部門之間引入?yún)f(xié)同決策的思想，致力于安全、高效和公平地調(diào)整交通需求與供給［3］.多機(jī)場終端區(qū)起降航班協(xié)同調(diào)度涉及多個機(jī)場之間進(jìn)離場航班的運(yùn)行，將綜合考慮機(jī)場、航空公司、空管部門三方利益優(yōu)化各航班起降次序，合理運(yùn)用GDP、AHP，提高終端區(qū)資源利用率.

博弈論是應(yīng)用數(shù)學(xué)的一個分支，主要適用于有限資源分配的問題.根據(jù)博弈假設(shè)的環(huán)境的不同，可分為合作博弈和非合作博弈，前者以團(tuán)體利益為目標(biāo)，后者分析參與者存在沖突與合作的決策模型，使自己利益最大化［4］.多機(jī)場終端區(qū)航班調(diào)度參與主體主要包括機(jī)場、空管部門以及航空公司，其中機(jī)場主要以最大化容量利用率為目標(biāo)，提高機(jī)場資源使用效率；空管部門將安全高效調(diào)度進(jìn)離場航班運(yùn)行，合理運(yùn)用GDP和AHP，使終端區(qū)有效運(yùn)行；航空公司作為航班承運(yùn)人，以延誤最小化為目標(biāo)降低運(yùn)營成本為目標(biāo).但上述三方均可在機(jī)場終端區(qū)高效運(yùn)行的環(huán)境下實(shí)現(xiàn)各自的目標(biāo)，因此本文利用合作博弈論的理論，根據(jù)多機(jī)場終端區(qū)各決策部門目標(biāo)，建立效用函數(shù)和拒絕性函數(shù)，構(gòu)建系協(xié)同航班調(diào)度模型，合理調(diào)度多機(jī)場終端區(qū)進(jìn)離場航班.模型相關(guān)參數(shù)和定義如表1所示.

表1　變量定義表

1　協(xié)同決策效用函數(shù)分析

協(xié)同決策理論（DME）是協(xié)同航班調(diào)度的基礎(chǔ)，本質(zhì)是多方參，以控制總延誤的情況下兼顧空管部門、航空公司和機(jī)場三方利益為目標(biāo)，因此建立的效用函數(shù).

1.1空管部門效用函數(shù)

空中交通管制服務(wù)的目的是確?？罩薪煌ò踩?、高效運(yùn)行，因此需合理利用GDP和AHP，緩解空中交通擁堵問題.

1）擁塞效用函數(shù)

空域飽和能力N（x）描述給定扇區(qū)x可容納飛機(jī)數(shù)量的最大值.當(dāng)給定扇區(qū)x內(nèi)飛機(jī)數(shù)量達(dá)到扇區(qū)容量的100%時，稱扇區(qū)x是飽和的.而當(dāng)給定扇區(qū)x內(nèi)飛機(jī)數(shù)量達(dá)到扇區(qū)容量的80%時，稱扇區(qū)x是擁擠的［5］.變量c是扇區(qū)x可以支持不造成擁堵的最大飛機(jī)數(shù)量，具體計(jì)算如下：

其中，［N（x）×0.8］是計(jì)算N（x）×0.8時的整數(shù)部分，dec是計(jì)算N（x）×0.8時的小數(shù)部分.dec給定如下：

函數(shù)Cs（x）給出了在每個扇區(qū)x的擁塞程度：

2）延誤效用函數(shù)

空管部門應(yīng)用地面等待程序（GDP）減少進(jìn)入終端區(qū)的飛機(jī)數(shù)量，從而緩解空中交通擁堵.然而，由于空中的飛機(jī)需要在機(jī)場著陸，并最終進(jìn)入停機(jī)位，應(yīng)用這一措施會引發(fā)地面空間不足，從而造成飛機(jī)空中等待，導(dǎo)致空中延誤.因此需衡量地面延誤和空中延誤值：

航空器地面延誤計(jì)算如下：

航空器空中延誤計(jì)算如下：

終端區(qū)內(nèi)航空器總延誤計(jì)算如下：

1.2航空公司效用函數(shù)

1）延誤效用函數(shù)

航班的運(yùn)營需要公司投入大量的成本，協(xié)同航班調(diào)度的措施需盡可能減少航班延誤，降低運(yùn)營成本.空中交通管制單位采取不同的限流措施，則會產(chǎn)生不同的航班調(diào)度，即不同的航班次序，各航空公司原有的航班排序被打亂，產(chǎn)生不同的延誤分布，延誤分布的影響如式（7）所示.

2）成本效用函數(shù)

航班延誤會導(dǎo)致空公司將產(chǎn)生額外的財務(wù)費(fèi)用，如飛機(jī)的運(yùn)營成本，額外的燃料消耗，增加的機(jī)組小時以及航班取消和乘客賠償?shù)乳g接成本等.由延誤導(dǎo)致的財務(wù)費(fèi)用的影響表現(xiàn)為：

綜上所述，航班調(diào)度對航空公司的效用影響如下：

1.3機(jī)場效用函數(shù)

機(jī)場作為航空飛行的起點(diǎn)和終點(diǎn)，在流量管理體系中發(fā)揮著不可替代的作用.對于機(jī)場單位來說，任意給定時刻t，最好的狀態(tài)就是機(jī)場機(jī)降能力可以滿足場內(nèi)飛機(jī)起降運(yùn)行.機(jī)場起降能力可以使用可用跑道數(shù)和可用停機(jī)位數(shù)衡量.任意給定時刻t可用跑道數(shù)如下：

任意給定時刻t機(jī)場可用停機(jī)位數(shù)如下：

基于上述方程，任意給定時刻t機(jī)場起降能力可用式（12）表示.

2　基于博弈論的協(xié)同決策拒絕函數(shù)分析

給定可選決策集合U，為了找到滿意的決策，計(jì)算每個選項(xiàng)u的選擇性值和拒絕性值.程度是很重要的.其中，選擇性可以被理解為支持u∈U過程具有的成功度；拒絕性表示在決定支持u∈U過程中，獲得成功的資源消耗的程度或參與決策的風(fēng)險程度［6］.

2.1空管拒絕性模型

考慮空管的偏好方程，終端區(qū)x不允許飛機(jī)數(shù)量大于飽和容量N（x），由飽和容量N（x）決定的終端區(qū)擁堵程度的最大值為Csmax（x）.Csmax（x）的計(jì)算如式（13）所示.

GDP決策時，空中交通管制單位的拒絕性和Csmax（x）值相關(guān).因此，初始ATC拒絕性的值可以由擁堵Csmax（x）得到，具體如下：

為了空中交通安全，理想情況是減少AHP程序的時間.終端區(qū)x飛機(jī)的空中延誤計(jì)算如下：

因此，AHP決策時，空中交通管制單位的拒絕性值也由式（16）得到：

其中：dAhp（x）是當(dāng)前空中延誤，dAhp（u）是空中總延誤.Δahp（x）為終端區(qū)x的AHP時間變化，定義如下：

具體計(jì)算流程如圖1.

圖1　管制單位拒絕性值計(jì)算流程圖

2.2航空公司拒絕性模型

根據(jù)航空公司的偏好方程，mt0，t是t0到時間段終端區(qū)x內(nèi)延誤飛機(jī)之間累積的延誤分布平均值，計(jì)算如下：

GDP程序中，當(dāng)航班延誤值增加并超過mt0，t時，航空公司會產(chǎn)生拒絕性，并且與延誤分布平均值mt0，t有關(guān).所以，航空公司初始的拒絕性值可由式（19）得到：

飛機(jī)執(zhí)行AHP程序時，會產(chǎn)生額外的燃油消耗，將對航空公司造成額外的經(jīng)濟(jì)損失，因此產(chǎn)生經(jīng)濟(jì)拒絕值.空中等待最大值為D（f），由燃油儲量決定，航班取消前的地面等待最大值為C（f）.一架飛機(jī)最多可以延誤C（f）和D（f）中的最低值，將這些時間按分鐘計(jì)算，航班延誤最大值dAthmax（f）如式（20）所示.

執(zhí)行AHP決策時，航空公司的拒絕性值：

計(jì)算流程如圖2.

圖2　航空公司拒絕性值計(jì)算流程圖

2.3機(jī)場拒絕性模型

當(dāng)機(jī)場著陸能力飽和時，GDP拒絕會產(chǎn)生；否則，不產(chǎn)生拒絕值.因此機(jī)場拒絕性值可由式（22）得到：

計(jì)算流程如圖3：

圖3　機(jī)場拒絕性值計(jì)算流程圖

3　選擇性函數(shù)

當(dāng)終端區(qū)空域出現(xiàn)擁堵，將無法接受更多的飛機(jī)起飛進(jìn)入空域，地面等待GDP程序就會執(zhí)行.因此，地面等待GDP對應(yīng)的初始選擇性值可由下式得到：

當(dāng)越來越多航班執(zhí)行GDP程序，則機(jī)場起降能力越低，即地面擁堵程度越嚴(yán)重，空中等待AHP程序決策選擇性越強(qiáng).所以PSahp（u）的選擇性值可由下式得到：

根據(jù)上述分析，對終端區(qū)內(nèi)航班進(jìn)行起飛降落分析，采用以下計(jì)算流程選擇GDP程序或者AHP程序計(jì)算其拒絕性值和選擇性值.見圖4.

圖4　選擇性值計(jì)算流程圖

4　案例分析

本文主要分析對上海虹橋機(jī)場和浦東機(jī)場的機(jī)場航班調(diào)度進(jìn)行仿真模擬.虹橋機(jī)場，有3個可用起降空間，和浦東機(jī)場，無起降空間.終端區(qū)x模擬分析數(shù)據(jù)：飽和容量N（x）=20，當(dāng)前空中飛機(jī)數(shù)V（x）=18.12架離場飛機(jī)，其中7架在進(jìn)行地面等待程序；6架飛機(jī)在空中申請著陸在虹橋或浦東機(jī)場，其中3架飛機(jī)已經(jīng)在空中等待程序中.18架飛機(jī)對應(yīng)的航班基礎(chǔ)數(shù)據(jù)如表1所示，Cf（min）指航班允許的地面等待最大值（按分鐘計(jì)算），Df（min）指航班允許的空中等待最大值（按分鐘計(jì)算）.

根據(jù)博弈模型，計(jì)算GDP決策的結(jié)果值如表2、3所示.

表2　航班基礎(chǔ)數(shù)據(jù)

表3　虹橋機(jī)場離場航班

表4　浦東機(jī)場離場航班

根據(jù)表3、4的選擇性和拒絕性，以及給定的決策權(quán)限，有利于航班而不考慮機(jī)場的偏好，我們可以得到航班起飛序列：F6?F4?F10?F7?F12?F1?F2?｛F3∨F5∨F8∨F9∨F11｝.若給定的決策權(quán)限有利于機(jī)場而不考慮航空公司的偏好，航班起飛序列則是：｛F7∨F8∨F9∨F10∨F11∨F12｝?｛F1∨F2∨F3∨F4∨F5∨F6｝.對于空管單位，模型返回較低的拒絕性值，即終端區(qū)還有可用空間給新航班起飛.

任意的地面等待5 min的決策，選擇性比率都保持0.5.另一方面，起飛航班也保持相同比率.所以，得到的適配CDM機(jī)制參與者的滿意起飛序列是：F10?F7?F12?｛F8∨F9∨F11｝?F6?F4?F1?F2?｛F3∨F5｝.

空中等待程序（AHP）計(jì)算的進(jìn)場航班選擇性和拒絕性值如表5所示.

表5　兩機(jī)場進(jìn)場航班

表5中，AHP程序空管的拒絕性保持固定值不變，然而，進(jìn)場航班需要機(jī)場的起降空間，因此機(jī)場的拒絕性值不穩(wěn)定.所以，考慮航班的進(jìn)場序列是：｛F13∨F14∨F15｝?F18?｛F16∨F17｝.計(jì)算結(jié)果表明浦東機(jī)場的飛機(jī)在空中等待直到該機(jī)場解除飽和狀態(tài).

5　結(jié)語

本文以協(xié)同決策（CDM）理念為基礎(chǔ)，分析終端區(qū)內(nèi)機(jī)場、航空公司、空管部門對進(jìn)離場航班調(diào)度的效用函數(shù)，并以此為依據(jù)，結(jié)合合作博弈論相關(guān)理論建立協(xié)同決策拒絕性模型.通過分析進(jìn)離場航班GDP和AHP程序的選擇，計(jì)算該航班機(jī)場、航空公司和空管部門三方的拒絕性值，分析航班進(jìn)離場次序，給決策三方建立參考.研究表明：基于博弈論的協(xié)同航班調(diào)度優(yōu)化模型有較好的準(zhǔn)確性和實(shí)用性，有助于解決機(jī)場終端區(qū)的航班調(diào)度問題，較公平地兼顧了機(jī)場、航空公司和空管部門之間的利益.之后可考慮多機(jī)場進(jìn)場航班各機(jī)場之間、各航空公司之間調(diào)度的公平性問題，進(jìn)一步改善多機(jī)場終端區(qū)機(jī)場航班的運(yùn)行.

［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］張洪海.機(jī)場終端區(qū)協(xié)同流量管理關(guān)鍵技術(shù)研究［D］.南京：南京航空航天大學(xué)，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］張妍.多機(jī)場終端區(qū)排序方法研究［D］.南京：南京航空航天大學(xué)，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.

江蘇省自然科學(xué)基金（Bk20130821）

吳藝（1990-），女，碩士，研究方向：空域規(guī)劃與管理.