航線網(wǎng)絡規(guī)劃中的時刻配置優(yōu)化方法

張 寧

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

1 引言(Introduction)

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

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

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

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

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

2.1 問題求解框架

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

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

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

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

2.2.1 繁忙機場時刻價值量化

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

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

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

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

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

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

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

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

2.3 構建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 問題模型

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

3 數(shù)據(jù)實驗(Data experiment)

3.1 實驗設計

本文模型既可用于單機場航線網(wǎng)絡優(yōu)化，也可用于多機場航線網(wǎng)絡優(yōu)化。為了檢驗模型在求解本文問題上的有效性，基于某航空公司的數(shù)據(jù)設計了實驗。使用同樣的量化后的主協(xié)調機場時刻價值、同樣的航權和繁忙機場時刻資源，將上同航季的紅頭航班計劃和優(yōu)化后的航班計劃作對比。

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

以某夏航季為例，將以對應上同航季的紅頭航班計劃和航權作為優(yōu)化的基礎數(shù)據(jù)。因為某航空公司在北京首都和北京大興都是單場運行，所以將這兩個機場設為一組。以不同的優(yōu)化機場和固定機場作為實驗參數(shù)，分為單優(yōu)化機場和多優(yōu)化機場兩類。單優(yōu)化機場是指只有一個機場設置為優(yōu)化機場，其余機場設置為固定機場。多優(yōu)化機場是指有2 個或更多機場設置為優(yōu)化機場，其余機場設置為固定機場。一共設計了19 組實驗方案如表1所示。

表1 實驗方案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的計算機上實現(xiàn)。

3.2 實驗結果與分析

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

表2 單優(yōu)化機場實驗結果Tab.2 Experimental results of single optimized airport

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

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

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

表3 多優(yōu)化機場實驗結果Tab.3 Experimental results of multiple optimized airports

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

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

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

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

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

4 結論(Conclusion)

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