問 濤，張 穎，田 文，張曉潔

(南京航空航天大學(xué) 國家空管飛行流量管理技術(shù)重點實驗室，南京 211106)

近年來我國民航運(yùn)輸業(yè)持續(xù)高速發(fā)展，日益增長的空中交通需求不斷沖擊有限的空域容量資源，為繁忙機(jī)場的正常運(yùn)行帶來巨大挑戰(zhàn).因此，如何進(jìn)一步緩解擁擠和延誤問題，是新形勢下推動民航高質(zhì)量發(fā)展的重要課題之一.一方面，我國正擴(kuò)建、新建機(jī)場，加強(qiáng)民航基礎(chǔ)設(shè)施建設(shè)，直接有效地增加系統(tǒng)容量；另一方面，可以采取流量管理策略，通過控制空中交通需求的時空分布，在中短期內(nèi)改善機(jī)場容量短缺和航班延誤現(xiàn)象[1].

航班時刻優(yōu)化策略是一種戰(zhàn)略規(guī)劃階段實施的流量管理策略，它通過科學(xué)、合理地分配航班時刻實現(xiàn)改善對機(jī)場容量的使用，以減少空中交通沖突，增加飛行流量，提高社會效益[2].在眾多文獻(xiàn)中， 航班時刻優(yōu)化策略問題有多種說法， 包括時隙分配問題、 時隙調(diào)度問題等，它們的本質(zhì)是一樣的.

世界多國研究者針對航班時刻優(yōu)化策略問題進(jìn)行了相關(guān)研究.例如，2017年，Jacquillat等提供的優(yōu)化方法在傳統(tǒng)效率目標(biāo)外，提出了如何度量時刻可靠性、公平性等其他種類的目標(biāo)[3].2017年，Pellegrini等研究了機(jī)場網(wǎng)絡(luò)在多種時刻調(diào)整量優(yōu)化目標(biāo)下的時隙分配[4].2018年，Zografos等提出了考慮時刻計劃可接受度的雙目標(biāo)優(yōu)化模型[5].2018年，Ribeiro等研究了基于優(yōu)先級的多目標(biāo)時刻分配模型及計算方法，使得優(yōu)化更加貼近實際規(guī)則[6].2018年，裔田園探究了一種基于航路走向的航班時刻優(yōu)化方法[7].總體上，已有成果主要集中于對確定型問題的研究，對不確定性問題的研究則相對較少.2013年，Churchill等從宏觀排隊系統(tǒng)的角度建立了容量不確定性下優(yōu)化機(jī)場時刻安排水平的模型[8].2014年，Corolli等研究了不確定容量下機(jī)場網(wǎng)絡(luò)的航班時刻優(yōu)化模型[9].2014年，曾奇初步探索了單個機(jī)場的魯棒性航班時刻優(yōu)化[10].2019年，亓堯、岳仁田等研究了只考慮一個運(yùn)行日的容量不確定性的航班時隙分配[11-12].

確定型航班時刻優(yōu)化問題假設(shè)空域系統(tǒng)是理想、靜態(tài)的，不受外界環(huán)境的影響，沒有考慮實際每日運(yùn)行過程中機(jī)場容量受天氣等因素影響下的隨機(jī)性，得到的航班時刻在機(jī)場實際運(yùn)行時若遇到較低的容量會產(chǎn)生較多的航班延誤.因此，有必要對不確定型航班時刻優(yōu)化問題進(jìn)行研究，將航班時刻的戰(zhàn)略協(xié)調(diào)規(guī)劃與實際運(yùn)行可能的環(huán)境條件相互關(guān)聯(lián)，得到潛在航班延誤更少的時隙分配結(jié)果.

本文則在前人研究的基礎(chǔ)上，建立了能夠考慮多個機(jī)場多個運(yùn)行日的容量不確定性的兩階段隨機(jī)規(guī)劃時隙分配模型，模型增加了對機(jī)場進(jìn)離場容量的優(yōu)化選擇決策，彌補(bǔ)了既有研究將機(jī)場進(jìn)場容量、離場容量和總?cè)萘抗铝⒖紤]的不足，并設(shè)計使用了樣本均值近似方法對具有大量場景的大規(guī)模實例進(jìn)行求解計算.

1 問題描述

在航空運(yùn)輸系統(tǒng)的實際運(yùn)營中，為適應(yīng)季節(jié)變化，每年要制定兩次航班計劃，分為冬春航季和夏秋航季，每個航季的航班時刻均要在航季開始前幾個月提前協(xié)調(diào)好.由于天氣這一主要不確定性因素的存在，由航班時刻協(xié)調(diào)人在航季開始前協(xié)調(diào)分配好的航班時刻在機(jī)場實際運(yùn)行時往往會受到機(jī)場容量等條件的隨機(jī)變化的影響而不能正常如期執(zhí)行，此時需要實施地面等待等戰(zhàn)術(shù)流量管理策略來處理發(fā)生的交通沖突.本文采用兩階段隨機(jī)規(guī)劃方法來考慮容量不確定性，時刻協(xié)調(diào)人根據(jù)未來機(jī)場網(wǎng)絡(luò)運(yùn)行時一系列可能的容量場景做出最佳的協(xié)調(diào)決策.

如圖1所示，本文不確定性問題的優(yōu)化依據(jù)包括兩個階段—協(xié)調(diào)階段和運(yùn)行階段.第一階段為協(xié)調(diào)階段，協(xié)調(diào)人根據(jù)協(xié)調(diào)規(guī)則配置航班時刻；第二階段為航班時刻在不同容量場景下的戰(zhàn)術(shù)運(yùn)行過程，航班根據(jù)機(jī)場網(wǎng)絡(luò)容量場景施行戰(zhàn)術(shù)流量管理.本文中機(jī)場容量指機(jī)場在單位時間能夠執(zhí)行的航空器架次.關(guān)于容量場景，單個機(jī)場一天的典型容量場景及其發(fā)生概率可以通過分析長期的歷史容量數(shù)據(jù)得到[8]，本文假設(shè)機(jī)場之間的天氣是相互獨立的，暫不考慮它們之間的相關(guān)性，因此，機(jī)場網(wǎng)絡(luò)的一個場景是各機(jī)場各運(yùn)行日容量場景的一種組合[9].

圖1 航班時刻協(xié)調(diào)與運(yùn)行過程

兩階段隨機(jī)規(guī)劃是處理含有不確定性參數(shù)的優(yōu)化問題的常用方法之一，通過陳列展開不確定性場景，即可以得到其等價的確定性問題.兩階段隨機(jī)規(guī)劃模型的一般形式和確定型等價形式可見文獻(xiàn)[13].本文針對航班時刻分配問題建立的優(yōu)化模型如下.

2 兩階段隨機(jī)規(guī)劃航班時刻優(yōu)化模型

2.1 模型假設(shè)

本文建立的考慮容量不確定性的航班時刻優(yōu)化模型為方便起見，做出如下假設(shè)：

1)以天氣為主的隨機(jī)因素只對機(jī)場空側(cè)容量造成影響，帶來不確定性；

2)運(yùn)行階段對交通沖突采取的戰(zhàn)術(shù)流量管理手段均為地面等待策略；

3)暫不考慮本地機(jī)場的航班延誤傳播以及來自上游機(jī)場的航班延誤傳播.

2.2 決策變量

2.2.1 協(xié)調(diào)階段決策變量

根據(jù)航班計劃制定規(guī)則，協(xié)調(diào)后的航班時刻t必須為5 min的整數(shù)倍時間點，一個時刻t對應(yīng)的是一個5 min長度的時間片，一天24 h共為288個時間片.

2.2.2 運(yùn)行階段決策變量

不同于一般的考慮不確定性的時隙分配模型，本文將進(jìn)離場服務(wù)率也作為決策變量.

2.3 目標(biāo)函數(shù)

本文建立的考慮容量不確定性的航班時刻優(yōu)化模型的目標(biāo)函數(shù)為

MinZ=CST+W·COP

(1)

其第一部分為協(xié)調(diào)階段航班時刻調(diào)整成本CST，第二部分為權(quán)重系數(shù)W和運(yùn)行階段航班延誤期望成本COP的乘積.權(quán)重系數(shù)的取值范圍為W≥0，本文將其定義為對運(yùn)行延誤的控制程度，用來權(quán)衡協(xié)調(diào)成本和運(yùn)行期望成本之間的關(guān)系.當(dāng)W=0時，即等價于確定型航班時刻優(yōu)化模型，航班時刻協(xié)調(diào)人不考慮不確定性帶來的潛在運(yùn)行延誤.當(dāng)W>0時，協(xié)調(diào)人開始考慮整個機(jī)場網(wǎng)絡(luò)容量的不確定性，W取值越大，則越重視控制運(yùn)行延誤期望的大小，越傾向于安排更多的時刻調(diào)整以減少運(yùn)行延誤期望成本.其中：

(2)

(3)

式(2)表示協(xié)調(diào)成本為總航班調(diào)整時間量，其中daysf為航班f的計劃運(yùn)行天數(shù)，deptf為航班f申請的計劃起飛時刻，arrtf為航班f申請的計劃降落時刻.式(3)表示運(yùn)行成本為各容量場景的總航班運(yùn)行延誤時間的數(shù)學(xué)期望，其中p(ω)為機(jī)場網(wǎng)絡(luò)容量場景ω的發(fā)生概率，ck為機(jī)場k延誤一個航班估計所需的時間成本.

2.4 約束條件

2.4.1 戰(zhàn)略協(xié)調(diào)約束

1)航班時刻分配約束

保證每一個航班的起飛和降落申請都分配到時刻，即：

(4)

(5)

2)機(jī)場額定容量約束

保證機(jī)場計劃的起飛、降落和總航班數(shù)量不超過對應(yīng)的機(jī)場額定容量，即：

?k∈K,r∈R,t∈T,h∈H

(6)

?k∈K,r∈R,t∈T,h∈H

(7)

?k∈K,r∈R,t∈T,h∈H

(8)

3)飛行時間約束

保證所有航班的計劃飛行時間不變，即：

(9)

其中：lf為航班f的計劃飛行時間.

4)周轉(zhuǎn)時間約束

保證對于銜接航班，前一個航班的降落操作與后一個航班的起飛操作之間的時刻間隔不小于所需的最小周轉(zhuǎn)時間，即：

(10)

其中：qff′為銜接航班對(f,f′)∈P的允許最小周轉(zhuǎn)時間，f對應(yīng)降落航班，f′對應(yīng)起飛航班.

2.4.2 戰(zhàn)術(shù)運(yùn)行約束

1)運(yùn)行延誤定義約束

定義起飛延誤、降落延誤航班數(shù)量分別為超出進(jìn)場和離場服務(wù)能力的航班架次，即

?k∈K,r∈R,t∈T,h∈H

(11)

?k∈K,r∈R,t∈T,h∈H

(12)

2)進(jìn)離場服務(wù)率優(yōu)化選擇約束

機(jī)場運(yùn)行時可達(dá)到的進(jìn)場服務(wù)率和離場服務(wù)率之間存在一定的關(guān)系，即：

(13)

圖2 進(jìn)離場服務(wù)率優(yōu)化選擇原理圖

機(jī)場跑道既要用于起飛，又要用于降落，研究表明，機(jī)場進(jìn)離場率之間存在包絡(luò)線形狀的制約關(guān)系，該包絡(luò)線表征了機(jī)場運(yùn)行容量，其形狀、大小取決于跑道配置和天氣條件[14]，如圖2所示.根據(jù)容量的定義，機(jī)場運(yùn)行過程中，能夠執(zhí)行的航班量應(yīng)該是在包絡(luò)線范圍之內(nèi)，圖2中圓點表示某機(jī)場假想的一些計劃航班量，實線包絡(luò)線表示該機(jī)場某時段假想的容量，在該容量情況下，包絡(luò)線內(nèi)的計劃需求完全可以滿足，對于包絡(luò)線外的計劃需求，機(jī)場實際運(yùn)行時管制員會決定合適的服務(wù)率，只執(zhí)行部分航班，以實現(xiàn)容流平衡，如圖2中箭頭所示.

不同于一般的考慮不確定性的時隙分配研究將進(jìn)離場運(yùn)行容量孤立開來列寫約束，忽略了它們之間固有的關(guān)系，本文在模型中加入進(jìn)離場服務(wù)率優(yōu)化選擇約束，使得模型能夠根據(jù)容量場景ω下各時段容量包絡(luò)線情況、機(jī)場總的航班計劃量，優(yōu)化選擇每個時段最適宜的進(jìn)離場率的組合，實現(xiàn)進(jìn)離場率的動態(tài)平衡優(yōu)化，更加符合機(jī)場實際運(yùn)行操作.

2.5 求解計算方法

上述模型為整數(shù)線性規(guī)劃模型.本文使用強(qiáng)大的商業(yè)數(shù)學(xué)規(guī)劃求解器CPLEX求解.然而機(jī)場網(wǎng)絡(luò)多運(yùn)行日的容量場景數(shù)量一般呈指數(shù)型增加，往往使得模型的規(guī)模異常龐大，對此，本文在求解中采用一種運(yùn)用統(tǒng)計近似的簡單、快速的計算方法—樣本均值近似.

樣本均值近似是一種基于蒙特卡洛仿真的外部采樣方法，它通過隨機(jī)抽取部分容量場景，使用樣本運(yùn)行延誤成本的算術(shù)平均作為總體運(yùn)行延誤成本期望的近似值，并通過多次采樣縮小近似解的范圍.根據(jù)文獻(xiàn)[9]和[15]，結(jié)合本文問題，具體求解計算步驟設(shè)計如下：

1)確定采樣次數(shù)M和樣本大小N；

3)根據(jù)容量場景ω的發(fā)生概率按照輪盤賭規(guī)則抽取樣本；

4)M組容量場景樣本分別代入樣本均值近似模型使用CPLEX求解，得到各組樣本的目標(biāo)函數(shù)值Lm；

3 算例實驗

3.1 實例參數(shù)

采用我國北京首都機(jī)場(ZBAA)和廣州白云機(jī)場(ZGGG)一周的預(yù)先飛行計劃數(shù)據(jù)進(jìn)行模擬計算.

兩場所構(gòu)成的機(jī)場網(wǎng)絡(luò)如圖3所示，機(jī)場網(wǎng)絡(luò)考慮在ZBAA和ZGGG起降的航班，其中ZBAA和ZGGG考慮容量約束，外圍機(jī)場假設(shè)容量為無窮大.本算例ZBAA和ZGGG的容量約束類型均選取為整點小時容量約束，戰(zhàn)略協(xié)調(diào)階段使用民航局頒布的協(xié)調(diào)機(jī)場容量標(biāo)準(zhǔn)作為額定總?cè)萘浚?具體ZBAA為86架次/h，ZGGG為69架次/h；戰(zhàn)術(shù)運(yùn)行階段機(jī)場進(jìn)離場容量，即進(jìn)離場服務(wù)率，使用后文假設(shè)的運(yùn)行容量場景.

圖3 機(jī)場網(wǎng)絡(luò)示意圖

以ZBAA和ZGGG為目標(biāo)機(jī)場選取2018年3月5日～2018年3月11日的預(yù)先飛行計劃如表1所示，共計航班申請4 502條.其他機(jī)場參數(shù)包括：選擇優(yōu)化的時段為各計劃日的12:00～18:00；兩機(jī)場的航班延誤時間乘子ck粗定為5 min/架次.

表1 預(yù)先飛行計劃(部分)

3.2 容量場景

由于沒有機(jī)場歷史運(yùn)行容量數(shù)據(jù)來源可用于分析，本文采用假設(shè)的機(jī)場網(wǎng)絡(luò)容量場景.為方便起見，假設(shè)兩機(jī)場的容量場景和發(fā)生概率相同，各場景每個小時的容量也相同，且容量包絡(luò)線均為如圖2中間所示的三段，αb、βb為0或1，γb值具體如表2所示.7個運(yùn)行日則機(jī)場網(wǎng)絡(luò)共得到2.68億個容量場景.

表2 機(jī)場假設(shè)容量場景

3.3 結(jié)果與分析

為了考察運(yùn)行延誤控制程度對時刻協(xié)調(diào)成本的影響，對前述模型采用不同的權(quán)重系數(shù)W進(jìn)行計算，得到戰(zhàn)略協(xié)調(diào)成本與戰(zhàn)術(shù)運(yùn)行期望成本之間的關(guān)系.所有算例樣本均值近似初始樣本大小N和N′分別定為100和500，初始采樣次數(shù)M定為10，優(yōu)化間隙限定為3%.最終結(jié)果如表3和圖4所示.Z*下界計算用時均在1 h左右，上界計算用時均在28 min左右.

表3列出了不同權(quán)重系數(shù)下目標(biāo)函數(shù)最優(yōu)值的上下界和標(biāo)準(zhǔn)差，最佳近似解的兩階段成本以及最佳近似解下同W=0時相比運(yùn)行期望成本優(yōu)化的程度.通過表3可知，下界和上界都非常接近，表明近似結(jié)果精確度高；上下界的標(biāo)準(zhǔn)差都相對較小，說明實驗選擇的樣本大小、數(shù)量合理，所取樣本點分布均勻.

表3 求解計算結(jié)果

圖4顯示了戰(zhàn)略協(xié)調(diào)成本和運(yùn)行期望成本的帕累托前沿.首先，W=1和W=0時的結(jié)果一樣，說明W=1時模型還不足以產(chǎn)生隨機(jī)優(yōu)化的效果，這是由于本文暫時省略了對波及延誤的計算；戰(zhàn)略協(xié)調(diào)成本為0，這是因為預(yù)先飛行計劃由民航局審批后得到，本身已基本滿足公布容量約束.接著，隨著權(quán)重W的遞增，戰(zhàn)略協(xié)調(diào)成本在隨之增加，而運(yùn)行延誤期望成本在不斷減小，且隨著運(yùn)行期望成本的減小，戰(zhàn)略協(xié)調(diào)成本增加得越快.結(jié)合表3，戰(zhàn)略協(xié)調(diào)成本增加435 min，運(yùn)行延誤期望成本即減少22.61%，驗證了模型能夠幫助減少運(yùn)行階段預(yù)期的不確定性延誤，航班時刻協(xié)調(diào)人可以根據(jù)需求和能夠接受的水平對協(xié)調(diào)成本和運(yùn)行期望成本做出權(quán)衡.

圖4 戰(zhàn)略協(xié)調(diào)成本與運(yùn)行期望成本的帕累托前沿

4 結(jié) 論

1)本文建立了基于兩階段隨機(jī)規(guī)劃的航班時刻優(yōu)化模型，模型能夠處理考慮多個機(jī)場多個運(yùn)行日的容量不確定性；

2)所建模型將進(jìn)離場服務(wù)率也作為決策變量，在戰(zhàn)術(shù)運(yùn)行階段加入了進(jìn)離場率優(yōu)化選擇約束，更加貼近機(jī)場運(yùn)行操作實際；

3)結(jié)合模型設(shè)計總結(jié)的樣本均值近似方法簡單快速，使得具有大量場景的實例能在有效時間內(nèi)求解計算得到滿意的結(jié)果；

4)結(jié)合實際數(shù)據(jù)驗證了模型的有效性，同時分析了航班時刻戰(zhàn)略協(xié)調(diào)成本與運(yùn)行期望成本之間的關(guān)系，可以輔助航班時刻協(xié)調(diào)人根據(jù)能夠接受的運(yùn)行延誤期望水平做出合適的時刻協(xié)調(diào)決策；

5)下一步可進(jìn)行的研究包括：尋找可行的間接方法得出我國機(jī)場真實的典型容量場景；研究延誤波及的計算從而得到更精確的運(yùn)行延誤期望等.