CDM機(jī)制下的機(jī)場停機(jī)位一體化實(shí)時(shí)分配算法

劉君強(qiáng)，張馬蘭，陳鵬超，謝吉偉，左洪福

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

CDM機(jī)制下的機(jī)場停機(jī)位一體化實(shí)時(shí)分配算法

劉君強(qiáng)，張馬蘭，陳鵬超，謝吉偉，左洪福

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

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

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

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

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

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

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

1 機(jī)位實(shí)時(shí)分配模型

1.1 符號(hào)定義

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

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

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

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

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

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

7）Rij為航班i到達(dá)機(jī)位j的時(shí)刻；Lij為航班i離開機(jī)位j的時(shí)刻；

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

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

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

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

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

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

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

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

1.2 目標(biāo)函數(shù)分析

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

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

2）最小化滑行時(shí)間為

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

4）延誤油耗均衡為

1.3 綜合模型

算法綜合模型為

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

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

2 算法

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

2.1 延誤航班的時(shí)隙分配

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

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

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

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

2.2 停機(jī)位實(shí)時(shí)分配

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

步驟2 分a）、b）兩種情況對(duì)延誤航班進(jìn)行停機(jī)位分配：

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

表1 航班計(jì)劃信息表Tab.1 Scheduled flight information

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

表2 機(jī)位信息表Tab.2 Airport gate information

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

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

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

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

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

航班延誤時(shí)，空管為3個(gè)延誤航班提供3個(gè)時(shí)隙，如表5所示。

表5 時(shí)隙信息表Tab.5 Slot information

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

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

表6中，因?yàn)闀r(shí)隙1屬于航班波2，而37號(hào)、17號(hào)航班的預(yù)計(jì)到達(dá)時(shí)間是航班波3，延誤航班不能提前到預(yù)計(jì)時(shí)間以前，因此，方案3到方案6對(duì)應(yīng)的時(shí)隙分配是不可行的。

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

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

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

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

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

圖2 延誤產(chǎn)生后機(jī)位實(shí)時(shí)分配方案下的各成本增量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)濟(jì)性，因?yàn)槠鋵?shí)現(xiàn)了航空公司與機(jī)場的協(xié)同決策；另一方面其運(yùn)算速度更快，一體化的方法可借助啟發(fā)式規(guī)則實(shí)現(xiàn)快速目標(biāo)篩選?？梢姡惑w化優(yōu)化策略的采用使得機(jī)場與航空公司間的協(xié)同決策（CDM）得以實(shí)現(xiàn)。傳統(tǒng)的分階段優(yōu)化策略先進(jìn)行時(shí)隙分配且缺少相關(guān)機(jī)位指派信息，所以比較費(fèi)時(shí)，且總成本得不到有效控制；而一體化策略綜合考慮了機(jī)位指派對(duì)時(shí)隙分配的影響，采取了最佳機(jī)位指派方案對(duì)應(yīng)的時(shí)隙分配策略，從而能夠從全局層面同時(shí)協(xié)調(diào)時(shí)隙分配與機(jī)位指派，更好地實(shí)現(xiàn)航空公司間以及機(jī)場與航空公司間的協(xié)同決策。

4 結(jié)語

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

[1]中國民用航空總局規(guī)劃發(fā)展司.從統(tǒng)計(jì)看民航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ī)場停機(jī)位再分配問題[J].南京航空航天大學(xué)學(xué)報(bào).2009，41（2）：257-261.

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

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

[8]朱 博，朱金福，高 強(qiáng).飛機(jī)和機(jī)組一體化恢復(fù)的約束規(guī)劃模型[J].交通運(yùn)輸工程學(xué)報(bào)，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é)基金項(xiàng)目（61232002；60939003）；中國博士后面上基金項(xiàng)目（2012M521081）；中國博士后基金特別資助（2013T60537）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)（NS2014066）；江蘇省博士后基金項(xiàng)目（1301107C）

劉君強(qiáng)（1978—），男，山東威海人，講師，博士，研究方向?yàn)榻煌ㄐ畔⒐芾?