張 寧

(廈門航空有限公司，福建 廈門 361006)

1 引言(Introduction)

航線網(wǎng)絡(luò)是航空公司賴以生存和發(fā)展的基礎(chǔ)。構(gòu)建布局合理、符合市場需求的航線網(wǎng)絡(luò)會增強(qiáng)航空公司的競爭力，提升航空公司的經(jīng)營效益，也將對后續(xù)運(yùn)營產(chǎn)生有利且深遠(yuǎn)的影響。

關(guān)于航空公司的航線網(wǎng)絡(luò)規(guī)劃研究，國外研究開展較早且較為深入，這與國外發(fā)達(dá)國家較早開放民航市場和航線網(wǎng)絡(luò)模型研究發(fā)展歷程有較大的關(guān)系。YAN等[1]以O(shè)&D(Original and Destination，始發(fā)地和目的地)為基礎(chǔ)對需求建立模型，從零開始構(gòu)建完整的航季航班計劃，并采用拉格朗日松弛法、次梯度法、網(wǎng)絡(luò)單純形法等算法求解算法模型。CADARSOA等[2]將航線網(wǎng)絡(luò)規(guī)劃各個階段的工作整合到一個單一的模型中，加強(qiáng)其魯棒性，降低決策之間的不兼容性，盡量避免錯失旅客，模型使用Cplex軟件求解算法模型。CADARSOA等[3]擴(kuò)展了自己在2011 年提出的算法模型，將指定必須包含的航班列表和最低平均飛機(jī)利用率的因素考慮在內(nèi)，模型使用Cplex軟件求解算法模型。PITA等[4]考慮機(jī)場擁堵的實(shí)際問題，提出了一個混合整數(shù)線性優(yōu)化模型，該模型將飛機(jī)和乘客延誤成本考慮在內(nèi)并使用Xpress軟件求解算法模型。

近年來，國內(nèi)航空管制水平顯著提升，航空公司業(yè)務(wù)快速發(fā)展。張伯生等[5]設(shè)計了一個在一定的時間范圍、航線班次前提下，含有隨機(jī)變量的航線貢獻(xiàn)最大化的動態(tài)規(guī)劃模型，首先使用MonteCarlo(蒙特卡羅)方法仿真確定隨機(jī)變量的值，將模型轉(zhuǎn)化為非線性的整數(shù)規(guī)劃，然后使用動態(tài)規(guī)劃中資源分配算法求解模型最優(yōu)解。鄧亞娟等[6]提出一種需求不確定且有容量限制的樞紐輻射式航線網(wǎng)絡(luò)模型，并使用基于隨機(jī)模擬的遺傳算法求解模型。牟德一等[7]設(shè)計了一種航線決策方法，首先求解出可選航線集合，然后使用多屬性決策方法篩選被選航線，進(jìn)而獲得在資源有限的情況下最優(yōu)的航線網(wǎng)絡(luò)。于焯等[8]在滿足飛機(jī)檢修維護(hù)計劃、最小飛機(jī)數(shù)、航班覆蓋等約束的基礎(chǔ)上，以飛機(jī)運(yùn)營成本最小化和飛機(jī)使用均衡為目標(biāo)，建立一個多目標(biāo)的0—1整數(shù)線性規(guī)劃模型，并使用Lingo軟件求解算法模型。楊新湦等[9]設(shè)計了航線網(wǎng)絡(luò)和航班時刻的雙層優(yōu)化模型，確定航班頻率、執(zhí)飛機(jī)型和航班時刻，并使用Matlab軟件仿真求解。樊瑋等[10]針對不同城市的特性，使用改進(jìn)的淘汰選擇算法篩選候選樞紐城市集，提出一種基于優(yōu)先級無容量限制多分配p樞紐定位的多目標(biāo)優(yōu)化模型，然后使用Cplex軟件對模型分步求解。

上述文獻(xiàn)為航線網(wǎng)絡(luò)規(guī)劃研究打下基礎(chǔ)，但存在國內(nèi)外民航業(yè)差異較大且算法模型復(fù)雜，研究成果無法較好應(yīng)用的局限性，鑒于無法有效地在當(dāng)下航空公司的實(shí)際業(yè)務(wù)場景中應(yīng)用，提出航線網(wǎng)絡(luò)規(guī)劃中的時刻配置優(yōu)化方法。

2 問題分析與建模優(yōu)化(Problem analysis and modeling optimization)

2.1 問題求解框架

本文研究的繁忙機(jī)場航線網(wǎng)絡(luò)優(yōu)化問題屬于航線網(wǎng)絡(luò)規(guī)劃領(lǐng)域的問題。對于繁忙機(jī)場，時刻和航權(quán)資源相對固定，不容易新增資源數(shù)量。在時刻和航權(quán)資源不變的情況下，可以通過交換和調(diào)整航班時間對航線網(wǎng)絡(luò)進(jìn)行優(yōu)化。例如，航班A為北京大興T1—上海虹橋T2，可以將北京大興T1的時刻交換給航班B北京大興—武漢使用。在符合局方規(guī)定的航段標(biāo)準(zhǔn)飛行時長及其浮動區(qū)間的情況下，可以適當(dāng)調(diào)整航班的計劃飛行時長。

本文算法將以運(yùn)籌學(xué)中的最優(yōu)化理論為基礎(chǔ)，以貢獻(xiàn)最大化為目標(biāo)，使用0—1整數(shù)規(guī)劃構(gòu)建問題模型，以求解優(yōu)化航線網(wǎng)絡(luò)。具體建模求解框架如圖1所示。

圖1 時刻優(yōu)化問題求解框架Fig.1 Time optimization problem solving framework

2.2 方案與參數(shù)初始化

2.2.1 繁忙機(jī)場時刻價值量化

對于歷史航季的成行航班，可計算出航班的收入，再扣除成本，加上補(bǔ)貼、機(jī)場優(yōu)惠等金額，繳納一定的稅額，即可計算出航班的貢獻(xiàn)；然后用航班的貢獻(xiàn)除以執(zhí)飛飛機(jī)的座位數(shù)和飛行小時，就能得出航班的座小時貢獻(xiàn)。

按照供需關(guān)系，機(jī)場可分為主協(xié)調(diào)機(jī)場、輔協(xié)調(diào)機(jī)場和非協(xié)調(diào)機(jī)場。由于主協(xié)調(diào)機(jī)場的市場流量大且運(yùn)力投放多，這類機(jī)場的航班時刻和航權(quán)資源供不應(yīng)求，成為各大航空公司競相爭搶的優(yōu)質(zhì)資源。在量化繁忙機(jī)場時刻價值時，可以將航班貢獻(xiàn)全部分?jǐn)偟街鲄f(xié)調(diào)機(jī)場時刻上。對于某個航班多個時刻屬于主協(xié)調(diào)機(jī)場時刻，比如北京首都機(jī)場至廣州白云機(jī)場的航班，則要按照一定的規(guī)則分?jǐn)偂?/p>

以各整點(diǎn)時刻前后半小時的區(qū)間范圍，將一天24 h分為24 個時刻區(qū)間，如某機(jī)場8:00的時刻，對應(yīng)區(qū)間為[7:30，8:30)。同樣的時刻，可用做航班起飛和航班降落，或者將其用于不同的航線，其價值可能是不一樣的。冬航季和夏航季運(yùn)行環(huán)境有較大差異，因此也要進(jìn)行區(qū)分，可以根據(jù)時刻區(qū)間、時刻起飛/降落性質(zhì)及航線對機(jī)場時刻進(jìn)行分類。在計算新航季的繁忙機(jī)場航班計劃時，使用上同航季或上同多個航季的時刻價值作為計算航班貢獻(xiàn)的基礎(chǔ)數(shù)據(jù)。

2.2.2 繁忙機(jī)場航班計劃優(yōu)化

經(jīng)過多年的運(yùn)行，每個航空公司都形成一定的戰(zhàn)略布局和相對穩(wěn)定的航線網(wǎng)絡(luò)，通常使用上同航季的航班計劃作為基礎(chǔ)，對航班編排進(jìn)行優(yōu)化，進(jìn)而形成新航季的航班計劃。

境外航班相對固定，因此優(yōu)化的空間有限。主協(xié)調(diào)機(jī)場中的前十大機(jī)場的時刻緊缺且時刻價值高，屬于航班計劃的優(yōu)化重點(diǎn)。對于前十大機(jī)場的相關(guān)航線，經(jīng)營許可量很難有較大的改變，航班頻率相對固定，因此以優(yōu)化航班的時刻為主。

以時刻、航權(quán)為基礎(chǔ)，按照航段標(biāo)準(zhǔn)飛行時長、航段浮動區(qū)間、機(jī)型過站時間、往返航班為一組的原則組建新的航班往返組合。按照量化時刻價值的規(guī)則，使用量化后的主協(xié)調(diào)機(jī)場時刻價值，反向計算新航班往返組合的貢獻(xiàn)。將這些新航班往返組合作為算法模型的備選航班集合。

以方案的形式使用算法，不同方案間互不影響。算法使用步驟如下。一是新建方案。二是設(shè)置方案參數(shù)：①優(yōu)化航季；②優(yōu)化機(jī)場，這些機(jī)場的時刻是優(yōu)化的對象，將重新編排到航班計劃中；③固定機(jī)場，這些機(jī)場的時刻只能使用提供的時刻資源；④基礎(chǔ)航班計劃，使用上同航季(2022 年冬航季的上同航季為2021 年冬航季)的紅頭航班計劃作為基礎(chǔ)航班計劃，抽取基礎(chǔ)航班計劃的航班時刻作為基礎(chǔ)時刻資源，可根據(jù)實(shí)際情況修改時刻資源，增加時刻起飛/降落限制；⑤航權(quán)，可根據(jù)實(shí)際情況修改航權(quán)資源，設(shè)置每條航線的班次上限、下限；⑥航段運(yùn)行時長，每個航段在不同航季、不同機(jī)型條件下的標(biāo)準(zhǔn)飛行時長；⑦航段浮動區(qū)間，不同標(biāo)準(zhǔn)飛行時長可設(shè)置上浮和下浮時間，比如航段飛行時長為125—180 min，可上浮15 min或下浮10 min；⑧機(jī)型過站時間，每個機(jī)場可設(shè)置過站時間下限和上限；⑨起飛時間間隔，每條航線可設(shè)置起飛時間間隔，比如同一天的廈門—上海的航班，需要間隔60 min以上，避免優(yōu)勢航線航班過密，浪費(fèi)資源。三是初始化輸入數(shù)據(jù)。四是輸入加工算法數(shù)據(jù)。五是構(gòu)建并求解算法模型，以貢獻(xiàn)最大化為目標(biāo)，使用0—1整數(shù)規(guī)劃構(gòu)建模型，并求解算法模型。六是輸出算法數(shù)據(jù)，得到優(yōu)化機(jī)場相關(guān)的往返航班計劃。七是輸出加工算法數(shù)據(jù)，計算指標(biāo)。八是輸出方案結(jié)果，至此算法結(jié)束。

2.3 構(gòu)建0—1整數(shù)規(guī)劃模型

2.3.1 模型變量和數(shù)據(jù)集合

2.3.2 模型參數(shù)

2.3.3 決策變量

Xi為往返航班組合i是否被選中，Xi=1表示選中，否則Xi=0。

2.3.4 問題模型

模型以繁忙機(jī)場時刻相關(guān)航班的總航班貢獻(xiàn)最大化為優(yōu)化目標(biāo)(1)，并對不屬于上同航季的紅頭航班的航班組合進(jìn)行懲罰，使得當(dāng)航班貢獻(xiàn)不變且滿足各類限制條件時，傾向于使用上同航季紅頭航班對應(yīng)的組合。約束(2)對應(yīng)固定時刻用全約束。固定時刻屬于繁忙機(jī)場時刻，對應(yīng)的價值高，要求全部使用；約束(3)對應(yīng)航權(quán)資源數(shù)量約束，保證選中的航班組合使用的航權(quán)資源滿足數(shù)量上下限要求；約束(4)對應(yīng)可行航班唯一約束，保證每一個可行航班最多只被使用一次；約束(5)對應(yīng)航段起飛間隔約束，保證每個航段的航班起飛時刻間隔滿足對應(yīng)航段的最小間隔時間的要求；約束(6)為變量取值。

3 數(shù)據(jù)實(shí)驗(yàn)(Data experiment)

3.1 實(shí)驗(yàn)設(shè)計

本文模型既可用于單機(jī)場航線網(wǎng)絡(luò)優(yōu)化，也可用于多機(jī)場航線網(wǎng)絡(luò)優(yōu)化。為了檢驗(yàn)?zāi)Ｐ驮谇蠼獗疚膯栴}上的有效性，基于某航空公司的數(shù)據(jù)設(shè)計了實(shí)驗(yàn)。使用同樣的量化后的主協(xié)調(diào)機(jī)場時刻價值、同樣的航權(quán)和繁忙機(jī)場時刻資源，將上同航季的紅頭航班計劃和優(yōu)化后的航班計劃作對比。

選擇旅客吞吐量在3，000萬(含)人次以上的境內(nèi)機(jī)場，包含北京首都(PEK)、北京大興(PKX)、上海浦東(PVG)、廣州白云(CAN)、成都雙流(CTU)、深圳寶安(SZX)、昆明長水(KMG)、西安咸陽(XIY)、上海虹橋(SHA)、重慶江北(CKG)、杭州蕭山(HGH)，將這些最繁忙的國內(nèi)機(jī)場納入優(yōu)化機(jī)場和固定機(jī)場的范圍。

以某夏航季為例，將以對應(yīng)上同航季的紅頭航班計劃和航權(quán)作為優(yōu)化的基礎(chǔ)數(shù)據(jù)。因?yàn)槟澈娇展驹诒本┦锥己捅本┐笈d都是單場運(yùn)行，所以將這兩個機(jī)場設(shè)為一組。以不同的優(yōu)化機(jī)場和固定機(jī)場作為實(shí)驗(yàn)參數(shù)，分為單優(yōu)化機(jī)場和多優(yōu)化機(jī)場兩類。單優(yōu)化機(jī)場是指只有一個機(jī)場設(shè)置為優(yōu)化機(jī)場，其余機(jī)場設(shè)置為固定機(jī)場。多優(yōu)化機(jī)場是指有2 個或更多機(jī)場設(shè)置為優(yōu)化機(jī)場，其余機(jī)場設(shè)置為固定機(jī)場。一共設(shè)計了19 組實(shí)驗(yàn)方案如表1所示。

表1 實(shí)驗(yàn)方案Tab.1 Experimental scheme

在本文“2.3 部分”的0—1整數(shù)規(guī)劃模型使用C++語言和Cplex軟件編碼，使用Visual Studio 2015工具編譯，在硬件環(huán)境為Intel Core i5-7200U CPU/2.50 GHz/8 GB/Windows 10的計算機(jī)上實(shí)現(xiàn)。

3.2 實(shí)驗(yàn)結(jié)果與分析

針對19 組實(shí)驗(yàn)方案，使用本文方法建模、初始化參數(shù)，輸入Cplex數(shù)據(jù)規(guī)劃求解器求解。首先，對比單優(yōu)化機(jī)場實(shí)驗(yàn)方案結(jié)果，即編號為1—10的實(shí)驗(yàn)方案，對應(yīng)的實(shí)驗(yàn)結(jié)果如表2所示。

表2 單優(yōu)化機(jī)場實(shí)驗(yàn)結(jié)果Tab.2 Experimental results of single optimized airport

通過柱形圖可更直觀地對比不同實(shí)驗(yàn)方案的優(yōu)化提升比率結(jié)果，單優(yōu)化機(jī)場實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 單優(yōu)化機(jī)場優(yōu)化提升比例Fig.2 Optimized proportion of single optimized airport

接下來，對比多優(yōu)化機(jī)場實(shí)驗(yàn)方案結(jié)果，即編號為11—19的實(shí)驗(yàn)方案，并將同樣包含成都雙流(CTU)的實(shí)驗(yàn)方案10也進(jìn)行對比，對應(yīng)的實(shí)驗(yàn)結(jié)果如表3所示。

表3 多優(yōu)化機(jī)場實(shí)驗(yàn)結(jié)果Tab.3 Experimental results of multiple optimized airports

同樣通過柱形圖直觀展示對比實(shí)驗(yàn)結(jié)果，多優(yōu)化機(jī)場的優(yōu)化提升比率如圖3所示。

圖3 多優(yōu)化機(jī)場優(yōu)化提升比率Fig.3 Optimized proportion of multi optimized airports

綜合上述實(shí)驗(yàn)結(jié)果可知：(1)不同機(jī)場的優(yōu)化提升比率差別較大，最小為3.8%(深圳寶安機(jī)場)，最大為115.6%(重慶江北機(jī)場)；(2)本文所提優(yōu)化方法可在一定程度上提升整體的航班貢獻(xiàn)，多優(yōu)化機(jī)場實(shí)驗(yàn)方案的平均優(yōu)化提升比率為28.6%。

航空公司根據(jù)其戰(zhàn)略規(guī)劃，一般會以一個或若干個機(jī)場為主基地，多個機(jī)場為過夜機(jī)場，以此為基礎(chǔ)，考慮可用飛機(jī)數(shù)和時刻、航權(quán)資源等因素，隨航線網(wǎng)絡(luò)進(jìn)行布局。在不同的機(jī)場，航空公司可獲得的時刻、航權(quán)資源質(zhì)量和數(shù)據(jù)存在較大差異。對于繁忙機(jī)場，供小于或接近于求，時刻、航權(quán)資源緊張，只有在新增機(jī)場跑道數(shù)量或開放更多空域等情況下，才能提供更多的時刻、航權(quán)資源。對于非繁忙機(jī)場，時刻和航權(quán)資源相對充足，供大于求，可選空間大，則可根據(jù)實(shí)際需求靈活申請匹配的資源。因此，對于繁忙機(jī)場，航空公司每個航季可獲得的時刻、航權(quán)資源相對固定，資源數(shù)量一般不會出現(xiàn)較大波動。在航權(quán)資源數(shù)量變化不大的情況下，可通過調(diào)整航班的時刻，建立新的航班，從中選擇更優(yōu)的航班計劃。

對于單優(yōu)化機(jī)場的場景，如果航空公司擁有該機(jī)場的時刻、航權(quán)資源較多，則可組合出更多的新航班，擁有更多調(diào)整空間，則可優(yōu)化的空間較大；如果航空公司擁有該機(jī)場的時刻、航權(quán)資源較少，則只能組合出較少的新航班，擁有的調(diào)整空間較小，則可優(yōu)化的空間有限。對于多優(yōu)化機(jī)場的場景，將綜合各個優(yōu)化機(jī)場的資源，組合出新航班集合，在滿足約束條件的情況下，可以根據(jù)目標(biāo)函數(shù)從整體上提升航班總貢獻(xiàn)。

4 結(jié)論(Conclusion)

時刻、航權(quán)資源是航空公司的重要資源，也是構(gòu)建航線網(wǎng)絡(luò)的基礎(chǔ)。由于市場需求大且供求關(guān)系緊張，繁忙機(jī)場的時刻和航權(quán)資源更為寶貴。本文算法可以量化繁忙機(jī)場時刻價值，運(yùn)用運(yùn)籌優(yōu)化理論，滿足時刻、航權(quán)、航段標(biāo)準(zhǔn)運(yùn)行時長、航段浮動區(qū)間、機(jī)場過站時間、航段起飛間隔等限制條件，使用0—1整數(shù)規(guī)劃算法優(yōu)化繁忙機(jī)場時刻配置，進(jìn)一步優(yōu)化繁忙機(jī)場航線網(wǎng)絡(luò)布局，以此為基礎(chǔ)，搭建完整的新航季航班計劃。單優(yōu)化機(jī)場和多優(yōu)化機(jī)場實(shí)驗(yàn)結(jié)果表明，本文算法能提升繁忙機(jī)場時刻相關(guān)航班的整體貢獻(xiàn)，能夠?yàn)楹娇展镜暮骄€網(wǎng)絡(luò)規(guī)劃提供指導(dǎo)。未來將深入研究，不斷優(yōu)化算法并推廣至所有機(jī)場使用，以周為單位構(gòu)建完整的航季航線網(wǎng)絡(luò)。