劉君強，張馬蘭，陳鵬超，謝吉偉，左洪福

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

CDM機制下的機場停機位一體化實時分配算法

劉君強，張馬蘭，陳鵬超，謝吉偉，左洪福

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

停機位是機場的核心資源，停機位實時分配算法是研究的熱點。本研究在協(xié)同決策（collaborative decision making，CDM）機制下，建立了多主體（機場、航空公司和旅客）最小延誤費用原則，研究了航班發(fā)生小規(guī)模延誤時的停機位實時分配模型，并借助混合集合規(guī)劃（mixed set programming，MSP）進行建模與求解。該模型能夠最小化航空公司滑行油耗成本和延誤旅客的中轉(zhuǎn)等待成本；實現(xiàn)各航空公司滑行油耗成本均衡化；以及在不影響航空公司利益的情況下有效保障延誤航班的航班波銜接。數(shù)據(jù)分析表明：該機位實時指派方法能夠有效實現(xiàn)機場與航空公司的協(xié)同決策，并能在節(jié)省算法運行時間的同時降低延誤產(chǎn)生的機位實時指派成本，對機場與航空公司的實際運行具有指導(dǎo)意義。

航班延誤；機位實時分配；航班波；協(xié)同決策；混合集合規(guī)劃

據(jù)2011年統(tǒng)計數(shù)據(jù)[1]，中國現(xiàn)有運輸機場175個，同時，許多大型機場正在改擴建，使得中國機場資源管理越來越復(fù)雜。針對機位實時指派問題，已有學(xué)者從機場、航空公司、旅客中的一方或兩方利益，基于航班特征值、機位特征值等建立模型，采用網(wǎng)絡(luò)仿真、規(guī)則庫、混合優(yōu)化等方法實現(xiàn)機位實時指派[2-6]。但綜合機場、航空公司和旅客多主體利益的機位實時分配仍有待深入研究。針對旅客利益，以往研究并未考慮樞紐機場航班波[7]延誤會大大影響旅客中轉(zhuǎn)等待時間。航班波是在一個時段安排進港航班，在緊接著的另一個時段安排出港航班，從而實現(xiàn)航班的有效銜接。合理的航班波要求機場、航空公司和空管協(xié)同決策（collab-orative decision making，CDM）[8]。而目前各種資源調(diào)度（如停機位指派和航班排班等）均由機場、航空公司和空管單獨完成，沒有達到CDM的要求。

傳統(tǒng)的機位實時分配中，航班延誤的信息是固定的[9]。由于航空公司與機場不協(xié)同，機場在基于給定延誤信息分配機位時可能產(chǎn)生機位分配困難和航班波銜接受影響等問題。本文所指的CDM機制下[10]：當延誤產(chǎn)生時，空管在獲得航班延誤信息后將為延誤航班提供新的時隙；航空公司在獲得時隙之后將時隙指派給延誤航班，此時的時隙指派方案并不是最終確定的方案，而是航空公司可選擇的時隙指派方案，簡言之，是時隙與延誤航班所有可能的組合；機場在獲得航空公司的可選時隙指派結(jié)果后進行實時機位分配，并比較各種可選時隙指派方案下對應(yīng)機位分配方案的經(jīng)濟性，將經(jīng)濟性最佳的機位分配方案所對應(yīng)的時隙指派方案反饋給航空公司；航空公司在得到機場反饋信息后再決定最終時隙指派方案?？梢?，航空公司與機場間的有效協(xié)同可讓機場在基本不影響航空公司利益的情況下，更合理地安排停機位。

在協(xié)同過程中需解決時隙指派和機位分配兩大問題。傳統(tǒng)的方法是進行分階段處理，先進行時隙指派，再進行機位分配。該方法需反復(fù)進行，十分耗時，而一體化的混合集合規(guī)劃方法可將時隙指派和機位分配統(tǒng)籌到一個算法當中，從而大大節(jié)省運算時間，提高算法性能。

因此，本文在協(xié)同決策機制下綜合考慮多主體利益，建立了以滑行油耗成本以及旅客中轉(zhuǎn)等待成本最小為目標、均衡各航空公司延誤油耗成本、并能保障延誤航班的航班波有效銜接的一體化機位實時分配模型。模型的建立與求解將借助混合集合規(guī)劃方法實現(xiàn)。

1 機位實時分配模型

1.1 符號定義

1）J為機位集合，j∈J；I為航班集合，i∈I；DI為延誤航班集合表示有航班波銜接的延誤航班，表示沒有航班波銜接的延誤航班表示并未產(chǎn)生延誤但是受到停機位分配影響的航班（根據(jù)文獻[8]確定調(diào)整范圍在50 min之內(nèi)的航班），DI?I，0＜J＜I；W為航班波集合，w∈W；M為機型集合，m∈M；N為航空公司集合，n∈N，NUM{N}，表示航空公司的個數(shù)；

2）Pmn為n公司m型飛機油耗增加占所有公司m型飛機油耗增加的百分比；ΔCOmn為n公司m型飛機由于延誤增加的油耗；

3）COi為航班i每分鐘的耗油量；

4）CTi、CTi＇分別為調(diào)整前后航班i滑行到其所?？繖C位所消耗的時間；

5）Y為每單位質(zhì)量航油的價格；C為每位旅客單位時間內(nèi)的中轉(zhuǎn)等待成本；

6）Pi為航班i的乘客數(shù)量；

7）Rij為航班i到達機位j的時刻；Lij為航班i離開機位j的時刻；

8）Gj表示機位j允許停放的最大機型，用相應(yīng)數(shù)字代表機位大小，數(shù)字越大，機位越大；

9）Qi表示航班機型大小，用相應(yīng)數(shù)字代表機型大小，數(shù)字越大，機型越大；Ω為一任意大的正數(shù)；

10）ΔT表示同一機位2架航班的最小間隔；Tidle表示所有機位空閑時間段集合

11）Xij的意義為：若航班i分配到機位j，則Xij為1，否則Xij為0；

12）K1j為機位j的空閑開始時間；K2j為機位j的空閑結(jié)束時間；

13）Zdw的意義為：若延誤航班id處于航班波w中，則Zidw為1，否則Zidw為0；

14）TPid為中轉(zhuǎn)旅客的人數(shù)，按照8%的中轉(zhuǎn)比例計算，一般平均中轉(zhuǎn)等待時間為90 min；

15）wp為延誤航班計劃所屬航班波；wa為延誤航班實際所屬航班波，wa≥wp；Ew為航班波w的波長，航班波一般波長為40 min。

1.2 目標函數(shù)分析

1）延誤產(chǎn)生的總成本最低：總成本包括滑行油耗成本和旅客中轉(zhuǎn)等待成本，即

其中：（CTi＇-CTi）表示航班i增加的滑行時間為延誤航班id中轉(zhuǎn)旅客等待的航班波數(shù)量。

2）最小化滑行時間為

3）最小化旅客中轉(zhuǎn)等待時間為

4）延誤油耗均衡為

1.3 綜合模型

算法綜合模型為

式（5）為目標函數(shù)，表示總成本最??；式（6）表示每個航班只指派一個機位；式（7）表示一個航班只屬于一個航班波；式（8）表示航班與航班波的對應(yīng)性；式（9）表示航班與被指派機位的唯一對應(yīng)性；式（10）要求機位與機型相匹配；式（11）要求機位的空閑時間大于最低安全間隔時間；式（12）要求機位空閑開始時間早于航班到港時間，并且機位空閑結(jié)束時間晚于航班離港時間；式（13）為有效性約束。

多目標不能同時達到最優(yōu)，因此對多目標進行了以下優(yōu)先次序的設(shè)定：為強調(diào)服務(wù)旅客的理念，旅客中轉(zhuǎn)等待時間最小化的優(yōu)先級最高；燃油成本是航空公司最直接的運行成本，故將滑行時間作為次優(yōu)先級目標；燃油均衡體現(xiàn)的是航空公司的公平性，應(yīng)是燃油成本最小化前提下的均衡，因此優(yōu)先級次于燃油成本；總成本最小化是對旅客中轉(zhuǎn)等待成本與航空公司油耗成本的綜合，因此優(yōu)先級放在最后。

2 算法

混合集合規(guī)劃[10-11]（mixed set programming，MSP）是以一階邏輯與集合推理為算法框架的邏輯求解系統(tǒng)，能系統(tǒng)地將集合推理與運籌學(xué)算法相結(jié)合，以集合變量為主進行問題建模，以基于集合推理的算法為核心進行模型求解。使用混合集合規(guī)劃能夠支持時隙分配與機位指派一體化的優(yōu)化策略，從而支持協(xié)同決策的目標。混合集合規(guī)劃主要算法介紹如下。

2.1 延誤航班的時隙分配

步驟1 將所有航班波按照計劃到達時刻的升序排序得到W（t）={w1，w2，…，wk}。

步驟2 定義uk=航班波wk包含的延誤航班數(shù)量/從t時刻（當前時刻）開始到完成航班波wk需要的時間；定義最大uk值對應(yīng)的航班波結(jié)束時刻為t1；定義t2為在t時刻未結(jié)束而在t2時刻結(jié)束的下一個航班波結(jié)束時刻，t2＞t；有τ=min（t1，t2）。

步驟3 將最大uk值對應(yīng)航班波wk內(nèi)的延誤航班id按可交換時隙的方式指派到τ時刻之前的時隙中。若延誤航班個數(shù)為r，則該步驟得到的時隙分配方式理論上應(yīng)有r!種，但航空公司在進行時隙交換時，有一定限制（如交換時隙的延誤航班所屬航班波應(yīng)盡量一致，交換時隙的延誤航班實際到達時刻應(yīng)晚于該延誤航班的計劃到達時刻，可進行時隙交換的航空公司限制等），因此實際需要計算的時隙分配方案遠遠小于r!種。

步驟4 將指派完成的航班波從集合W（t）中去除，重新進行航班波排序，重復(fù)步驟1、2、3，最終可輸出所有延誤航班的時隙分配方案。

2.2 停機位實時分配

步驟1 讀取集合I中所有航班的機位預(yù)分配結(jié)果，根據(jù)每個航班對應(yīng)的機位預(yù)分配信息，得到每個機位的可利用時間段

步驟2 分a）、b）兩種情況對延誤航班進行停機位分配：

步驟3 對于沒有航班延誤，但影響停機位分配的航班和步驟2中的b）部分得到的航班根據(jù)延誤費用原則以及機型Qi與機位Gj相匹配的原則進行停機位分配。

步驟4 綜合步驟2和步驟3，可以得到停機位分配結(jié)果。

在求解策略中，將算法和啟發(fā)式規(guī)則有機結(jié)合，使得約束條件得到嚴格滿足，確保解的可行性；并確保在求解過程中利用求解規(guī)則靈活控制搜索過程。啟發(fā)式規(guī)則包括：

1）假設(shè)原計劃航班所處的航班波是wk，則延誤航班分配時隙所屬的航班波必須≥wk。

2）航空公司進行時隙互換時，延誤航班所處航班波的數(shù)值應(yīng)盡量相同。

將上述兩個算法的求解規(guī)則同時植入深度優(yōu)先搜索算法中，一體化搜索時隙分配集合與機位指派集合，從而優(yōu)化延誤航班的時隙分配并確定滿足多目標的機位指派方案。

3 實驗結(jié)果及分析

采用某大型機場的42個航班數(shù)據(jù)，如表1所示。使用POEM軟件[9]建模與求解。

表1 航班計劃信息表Tab.1 Scheduled flight information

表1中，航班到達時間范圍為09：20—11：00，涉及國航、東航和南航，分別用C、E、S表示（算法中用1、2、3表示）；小、中、大機型分別用C、D、E表示（算法中用1、2、3表示）。7號和37號航班為特殊航班，調(diào)整前后的機位應(yīng)保持不變。該機場某一航站樓共有35個機位，空閑時間為[09：00，12：00]。機位信息如表2所示。

表2 機位信息表Tab.2 Airport gate information

延誤信息：13號航班10：05到達；17號航班11：00到達；37號航班11：00到達。根據(jù)文獻[8]選取09：50—10：50作為調(diào)整的時間段。機位預(yù)分配如表3所示，實時機位調(diào)整如表4所示。

表3 初始機位分配結(jié)果Tab.3 Original gate assignment

表4 機位實時分配結(jié)果Tab.4 Real-time gate assignment

為方便計算，設(shè)定各類機型油耗為：大型46kg/min，中型28 kg/min，小型12 kg/min。中轉(zhuǎn)等待的成本為1元/min。各種成本的計算結(jié)果如下。

1）旅客中轉(zhuǎn)等待成本：航班執(zhí)行前的原計劃指派方案為62 640元，發(fā)生航班延誤后的實時再指派方案為63 280元，增幅為1.02%。

航班延誤時，空管為3個延誤航班提供3個時隙，如表5所示。

表5 時隙信息表Tab.5 Slot information

13號、17號和37號航班分別屬于南航、東航和國航，這3個航空公司的時隙均可交換。結(jié)合啟發(fā)式規(guī)則，航空公司的可選時隙分配方案如表6所示，機場則根據(jù)表6做機位實時分配，不同的時隙分配將產(chǎn)生不同的成本。

表6 延誤航班的時隙分配Tab.6 Slot assignment for delayed flights

表6中，因為時隙1屬于航班波2，而37號、17號航班的預(yù)計到達時間是航班波3，延誤航班不能提前到預(yù)計時間以前，因此，方案3到方案6對應(yīng)的時隙分配是不可行的。

傳統(tǒng)模式下，航空公司可能隨機選擇方案1，但這種時隙分配方式下的機位指派方案并非最優(yōu)。時隙分配方案1和方案2對應(yīng)的旅客中轉(zhuǎn)等待成本增量分別為1 600元和960元，可見，根據(jù)機位指派結(jié)果，時隙分配方案2優(yōu)于方案1。所以，采用方案2進行時隙分配將有助于控制機場與航空公司的運行成本并使旅客滿意度最大化，同時也是CDM的體現(xiàn)。

2）油耗變化：航班執(zhí)行前的原計劃指派方案為9 758 kg，發(fā)生航班延誤后的實時再指派方案為9 980 kg，增幅為2.28%。油耗均衡性如圖1所示。

圖1 調(diào)整后各航空公司各類型飛機的滑行油耗Fig.1 Balanced fuel consumption

圖2表明，算法基本實現(xiàn)了各航空公司各類機型的油耗均衡。

3）總成本：航班執(zhí)行前的原計劃指派方案為130 946元；發(fā)生航班延誤后的實時再指派方案為133 469元，增加了2 514元，即1.92%。各部分成本變化如圖2所示。

圖2 延誤產(chǎn)生后機位實時分配方案下的各成本增量Fig.2 Increases of each cost in real-time gate assignment after delay

圖1中，油耗成本從68 306元增長為69 860元，增加了1 554元，漲幅為2.28%；旅客中轉(zhuǎn)等待成本從62 640元增長為63 600元，增加了960元，漲幅為1.53%。兩種方案的比較如表7所示。

表7 方法比較Tab.7 Comparison of traditional method and proposed method

表7說明，本文提出的方法一方面具備較好的經(jīng)濟性，因為其實現(xiàn)了航空公司與機場的協(xié)同決策；另一方面其運算速度更快，一體化的方法可借助啟發(fā)式規(guī)則實現(xiàn)快速目標篩選?？梢?，一體化優(yōu)化策略的采用使得機場與航空公司間的協(xié)同決策（CDM）得以實現(xiàn)。傳統(tǒng)的分階段優(yōu)化策略先進行時隙分配且缺少相關(guān)機位指派信息，所以比較費時，且總成本得不到有效控制；而一體化策略綜合考慮了機位指派對時隙分配的影響，采取了最佳機位指派方案對應(yīng)的時隙分配策略，從而能夠從全局層面同時協(xié)調(diào)時隙分配與機位指派，更好地實現(xiàn)航空公司間以及機場與航空公司間的協(xié)同決策。

4 結(jié)語

本文建立了基于CDM的一體化機位實時分配模型，使用混合集合規(guī)劃方法進行建模與求解。實驗分析證明，該機位實時分配方法實現(xiàn)了時隙指派與機位分配的一體化優(yōu)化以及機場與航空公司的協(xié)同決策；降低了航班延誤引起的航班延誤油耗成本、機位空閑成本和延誤航班旅客中轉(zhuǎn)等待成本；均衡了各航空公司的延誤油耗成本；保障了延誤航班的航班波銜接。因此，本文提出的方法在實際運行中是切實可行的。下階段將研究機場群條件下基于空管、機場、航空公司CDM機制的一體化機位分配問題。

[1]中國民用航空總局規(guī)劃發(fā)展司.從統(tǒng)計看民航2011[M].北京：中國民航出版社，2011.

[2]GILL C O，BADONI M，CHENG Y.A knowledge-based airport gate assignment system integrated with mathematical programming[J].Computers and Industrial Engineering，1997，32（4）：837-852.

[3]CHENG Y.A rule-based reactive model for the simulation of aircraft on airport gates[J].Knowledge-Based Systems，1998，10：225-236.

[4]WANG L.Optimized Assignment of Civil Airport Gate[C]//2010 International Conference on Intelligent SystemDesign and Engineering Application，2011：33-38.

[5]衛(wèi)東選，劉長有.機場停機位再分配問題[J].南京航空航天大學(xué)學(xué)報.2009，41（2）：257-261.

[6]李 雯.樞紐機場航班波構(gòu)建方法研究[D].南京：南京航空航天大學(xué)，2010.

[7]高 強，嚴 峻，朱金福.CDM機制下航空公司時隙分配優(yōu)化決策[J].交通運輸系統(tǒng)工程與信息，2010，11（5）：94-98.

[8]朱 博，朱金福，高 強.飛機和機組一體化恢復(fù)的約束規(guī)劃模型[J].交通運輸工程學(xué)報，2013，13（1）：77-83.

[9]ZHOU JY.A NoteonMixed Set Programming[C]//IEEE：the7thInternational Symposium on Operations Research and Its Applications.IEEE，2008：131-140.

[10]ZHOU J Y.Introduction to the constraint language NCL[J].The Journal of Logic Programming，2000，45（1/2/3）：71-103.

（責(zé)任編輯：黨亞茹）

Integrative real-time airport gate assignment algorithm based on CDM

LIU Jun-qiang，ZHANG Ma-lan，CHEN Peng-chao，XIE Ji-wei，ZUO Hong-fu
（College of Civil Aviation，Nanjing University of Aeronautics and Astronautics，Nanjing 210016，China）

Airport gate is one of the most primary resources of an airport，and real-time gate assignment has been paid more and more attention.To achieve appropriate real-time gate assignment under small-scale flight delays，a principle of minimum delay cost for multi-agent（airlines，airports and passengers）is established and an integrative real-time gate assignment model based on collaborative decision making（CDM）between airport and airlines is proposed.With mixed set programming（MSP）for modeling and optimization，not only the costs of ground taxiing of aircraft and the waiting of transfer passengers can be minimized，but also the increased fuel cost for the aircraft of the same type belonging to each airline can be balanced.Meanwhile，the flight banks of delayed flights can be connected effectively without adverse impacts on the interests of airlines.The illustrative example testifies that the collaboration between airport and airlines can be implemented，and the slot assignment as well as the gate assignment can be implemented through the integration of these algorithms in MSP，therefore both the operation cost and the computation time generated in the algorithm can be decreased.Analyses show that the proposed approach is qualified to serve as a guideline for practical operation of airport and airlines in air transportation.

flight delay；real-time gate assignment；flight bank；CDM；MSP

U8；V351

：A

：1674-5590（2014）06-0013-06

2014-04-22；

：2014-06-29

國家自然科學(xué)基金項目（61232002；60939003）；中國博士后面上基金項目（2012M521081）；中國博士后基金特別資助（2013T60537）；中央高?；究蒲袠I(yè)務(wù)費專項（NS2014066）；江蘇省博士后基金項目（1301107C）

劉君強（1978—），男，山東威海人，講師，博士，研究方向為交通信息管理.