航季航班計劃飛機連線自動銜接模型

黃國輝

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

近年來，中國民航運輸業呈現快速發展趨勢，根據《2020年民航行業發展統計公報》[1]，截至2020年底，中國大陸已有64家運輸航空公司、3 903架運營飛機、5 581條執飛定期航班航線.對于各家航空公司而言，飛機是重資產、航權時刻是關鍵資源，企業核心目標是在飛機投入最小化的情況下，高效利用航權時刻資源，編排出最優的航線網絡，最終實現經營利潤最大化.因此，制定合理的航班計劃對提升航空公司市場競爭力有著重要作用.航季航班計劃編制是一項非常復雜而繁重的工作，操作難點在于飛機機型指派和飛機連線銜接[2-4].目前，國內大部分航空公司還是借助人工來完成這兩項業務，操作效率和編排質量都較低.行業主流的航班編排系統基本都被歐美公司壟斷，國內航空公司不得不高額采購引進這些系統，不僅維護成本極高，而且無法根據國內航空公司的實際業務優化系統功能，存在較大的應用局限性.Zhou[5]整理綜述了機型指派(FAP)、飛機路徑(ARP)和機組排班(CSP)等航空公司計劃和調度問題的解決方法，并指出航班調度仍是當前主要難題.都業富[6]在航班串優化的研究中提出航班銜接是評價航線調度優化效果的重要因素.肖東喜等[7]認為飛機連線問題是航班環構建的實際體現，飛機連線的自動銜接有助于降低航空公司構建航班環的難度，進而提高航線計劃的效率.于焯等[8]引入等圖的概念，構造航線調配狀態圖，將飛機航線調配問題等價為等圖的路徑査找問題.孫宏[9]用二部圖來描述航節銜接問題，并通過Ford Fulkerson算法進行求解.然而，當前研究主要用于解決單樞紐(或基地)航線網絡的航班銜接問題，無法完全滿足多樞紐、固定連線等復雜的實際需求.加權二部圖算法是在二部圖的基礎上，給邊賦予權重，以實現不同優先級別的目標實現[10]，張紹陽等[11]利用加權二部圖最優匹配算法研究了中文段落相似度的匹配查重問題，但該算法還比較少應用于解決航線優化問題.

綜合考慮機型指派、飛機路線問題，朱星輝等[12]建立了基于列生成算法的一體化飛機排班模型.但該模型是基于以天為單位的航班計劃(即每天的航班計劃都相同)，飛機數量和航班數量均較少.而在實際應用場景，國內中大型航空公司機隊數量達數百架，每周航班數量高達數千個，如果用一體化模型求解，建模和求解的復雜性將倍增，求解效率根本無法滿足航季航班計劃編制過程中快速模擬的需求.如Ahmed等[13]基于美國聯合航空公司的航班網絡，考慮航班計劃魯棒性，建立了綜合機型指派、連線銜接、機組排班等一體化的模型，該案例解決了超過200架飛機的航班排班問題，但需要數小時的求解時間；Sanchez等[14]利用啟發式算法建立了考慮飛機維修計劃的一體化飛機排班模型，該模型求解529架飛機的排班問題也需要2 h.結合相關領域的前沿算法，尋找有效的解決方案仍是目前亟待解決的一個重要難題.

由于國內民航市場規模大、變化速度快，且政府監管頻率較高，意味著航班優化調整的效率對航空公司而言極為重要.因此，本文以使用飛機數量最小化和收益貢獻最大化為目標，采取兩階段方式解決機型指派和連線銜接的問題.首先，利用時空網絡圖完成機型指派，明確最少的使用飛機數量，為飛機連線銜接確定機型基礎.其次，采用加權二部圖算法來解決航線銜接問題，根據連線銜接的目的不同，設計不同的銜接權重，求解滿足要求的銜接方案.為了與加權二部圖算法作對比，本文在第二階段加入二部圖、先進先出、后進先出等連線銜接算法，并通過橫向、縱向對比不同算法的可行性與適用性.

1 問題描述和數學建模

1.1 問題描述

在國內民航運輸業，每年分為兩個航季，即夏航季(每年3月的最后一個星期日至10月的最后一個星期日的前一天)和冬航季(每年10月的最后一個星期日開始到第二年3月的最后一個星期日的前一天).每次換季都要重新制定航班計劃，包括航班日期、航線、航班號、起降時刻、機型、連線編號等要素.其中：1) 航班日期是指每個航班在第一個起飛機場的起飛日期；2) 航線是指航空公司開展經營活動所運營的航班路線，比如，廣州-上海、廈門-舟山-北京；3) 航班號是一天中區分不同航班的唯一標識，比如，南航廣州-上海CZ3533；4) 起降時刻是指航班在起點機場、終點機場和經停機場的起飛及降落時刻；5) 機型指用于執飛該航班的飛機型號，比如波音B787、空客A321；6) 連線編號是指每架飛機執飛任務的編號，即同一架飛機執飛不同的航班，這些航班均屬于同一個連線編號，比如有3架A321飛機，那么這3架飛機連線編號為A321_01、A321_02、A321_03.

通常情況下，新航季航班計劃編制是在前一個同航季航班計劃的基礎上(比如2021年冬航季是基于2020年冬航季)，根據航空公司的機隊規劃、航權、時刻等資源情況和市場預期效益進行優化調整.因此，新航季會有部分航班是延續前一個同航季的航班計劃，但多數航班會根據市場和資源爭取情況做調整.這里的航季航班計劃是以周為單位制定，即只要編制出一周的航班計劃，再將其復制到后續周期，就可以形成整個航季的航班計劃.

在航班計劃編制過程中，第一步是機型指派.主要是滿足運行約束的前提條件下分配機型，使航班收益貢獻最大化.即考慮兩個因素：1) 運行限制.不同型號的飛機具有不同的飛行性能(如航程、最大起飛重量、發動機推力等)，不同性能的飛機決定了該機型可以執飛的航班.比如：B737、A320等短航程機型就不能執飛國內到洛杉磯等長航程的洲際航線.2) 預期效益.不同機型的運營成本存在差異，不同座艙布局的飛機載客能力也不同，同一架飛機執飛不同航班產生的收益貢獻也不同，故航班計劃編排也要綜合考慮預期效益.這里的收益貢獻是指航空公司從事經營活動所獲得的稅后收入減去使用某種機型執飛的變動成本，是衡量航班盈利能力的重要指標.

第二步是連線銜接.在確定每個航班的執飛機型后，兩個航班能實現銜接的前提是滿足以下兩條規則：1) 同機場，即前序航班的落地機場要與后續航班的起飛機場相同.2) 滿足最小過站時間，即前序航班降落與后續航班起飛之間在機場的停留時間要滿足最小過站時間標準.除了最基本的銜接原則外，航空公司在編制航班計劃時，也會根據實際業務需求增加航班銜接要求，常見的有3類：1) 保留原始銜接.航季航班計劃編排并不是完全從零開始，有部分航班計劃是延續上一個同航季的航班計劃，這些航班保留了部分銜接信息甚至機組排班信息.2) 保留往返銜接.往返航班銜接是指從出發地到達目的地，然后再從目的地返回出發地的兩個航班之間的銜接.這不僅利于機組排班，還可以減少機組在外站的過夜費用，對航空公司控制成本有重要意義.3) 緊湊銜接.航季航班計劃會盡可能用最少的飛機數量編排最多的航班，使整個航班計劃的飛機利用率最高.在此過程中，航空公司通常會將較短過站時間的兩個航班優先銜接，使得編排的航班計劃更為緊湊，可以集中利用空檔運力，有利于增加航班執飛量，提高飛機利用率.如圖1所示，假設最小過站時間為60 min，航班A、C的落地機場與航班B、D的起飛機場相同，圖1(a)中航班A與航班B的銜接過站時間為3 h，航班C與航班D的銜接過站時間為4 h，這兩個過站時間均較短，新增航班比較困難；但是，航班C與航班B的銜接時間最短且滿足最小過站時間，如圖1(b)，如果優先將航班C與航班B銜接，過站時間為1 h，剩余的航班A與航班D的銜接過站時間長達6 h，在這6 h的空余運力中新增航班就相對容易.

圖1 緊湊銜接航班計劃示意圖Fig.1Diagram of a tightly connected flight plan

A航空公司之前也是通過引進國外某系統來完成航季航班編排，但該系統只能在人工確定機型的前提下進行連線銜接操作，無法自動分配機型，自動化程度不高.為進一步提高航班計劃編排效率，確保航班收益最大化，經過長期的業務總結和技術研究，A公司已探索出滿足國內航司航季航班編排的解決方案.首先運用機型指派模型，在飛機數量最小化前提下確定每個航班執飛機型，使整體收益貢獻最大化；然后運用先進先出、后進先出、二部圖、加權二部圖等算法完成連線銜接.基于上述思路，本文列出以下假設條件：

1) 航季航班計劃是以周為單位，不同自然周的航班計劃均相同.因此，只需某個自然周的航班計劃進行連線自動銜接，其余周期的航班計劃重復銜接即可.

2) 航季航班計劃的飛機連線不涉及具體機號，只需根據具體型號的飛機數量給出對應數量的飛機連線即可.

3) 所有運行約束都只考慮機型維度的運行約束，不考慮機號維度的運行約束.

4) 每個航班用不同機型執飛所產生的收益貢獻為已知，貢獻大小僅與機型有關，與航班銜接無關.本文使用的預計貢獻是利用神經網絡模型根據歷史經營情況以及未來航班的銷售情況進行預計，文中不作詳述.

1.2 航班機型指派模型

機型指派模型以時空網絡為基礎.在時空網絡中，橫軸代表時間，縱軸代表機場，網絡由若干航班組成，能夠體現航班起飛、降落的時刻與機場.圖2所示為一周的時空網絡圖，xd,f,k等箭頭表示第d天用k機型執飛f航班，yd,a,k等節點表示第d天凌晨3:00時在A機場k機型的過夜數量(由于每天的航班計劃中，最遲降落的航班時刻可能超過24:00，故本文選取凌晨3:00作為過夜飛機數的統計節點).機型指派模型最核心的思想是當航班起飛時必須有一架飛機可供使用，例如：對于機型k，當x1,4,k準備起飛時，機場B初始的飛機有y1,b,k架，進港的飛機有x1,5,k、x1,2,k、x1,3,k，離港的飛機有x1,1,k、x1,6,k.因此，要使x1,4,k有k機型可用，就必須滿足y1,b,k+x1,5,k+x1,2,k+x1,3,k-x1,1,k-x1,6,k大于等于1.此外，為了航班計劃的銜接能夠循環延續，每個機場最終的機型數量分布要與該機場最初的機型數量分布一致，即需要圖中y8,a,1=y1,a,1.

圖2 時空網絡圖Fig.2Time-space network

1.2.1 參數設置

模型參數和變量設置如表1和2所示.

表1 模型參數

表2 模型變量說明

1.2.2 目標函數

對于航季航班分配機型通常考慮兩個目標：一是將現有航班用最少的飛機數編排；二是使航線網絡收益貢獻最大化.根據以上兩個目標可以得出目標函數(1)和(2)：

(1)

(2)

對于多目標決策，主要思路是將多目標降維成一系列單一目標進行優化，常見的有搶占式優化和加權優化.搶占式優化需要根據目標的重要性多次建立模型，而加權優化只需建立一次模型，通過設置加權系數的正負性保證加權目標函數最大化或最小化一致，其中系數絕對值大小體現目標的重要性，這樣就能減少建模次數，提高優化效率.在實際業務中，要優先保證以最小的飛機數排下所有航班，然后再調整機型增加貢獻.因此，本文采取加權優化，可以列出目標函數(3)，加權目標是求最大化的問題，所以β的系數為負.經過測試，當設α=1，β=-10 000時，求解的最小飛機數、最大貢獻與搶占式優化的結果一致.

(3)

1.2.3 約束條件

飛機連線的銜接要求覆蓋每個航班且每個航班只能被指派1種機型執飛，如式(4)：

(4)

每個航班在起飛前必須有1架飛機可供使用，即如果xd,f,k=1，則對于d天在fj航班的起飛機場的初始飛機數加上在fj航班起飛前進港的飛機數再減去在fj航班起飛前離港的飛機數后，在fj航班離港時至少有一架k機型的飛機可供其使用，如式(5)：

(5)

在每個機場，每天的初始飛機數加上該機場的所有進港飛機數再減去該機場的所有出港飛機數要等于該機場的最終的飛機數，如式(6)：

(6)

這里：?k∈K,?a∈A,?d∈D且d≠8.

機隊平衡約束，在優化周期內，每個機場的初始機隊分布要與最終的機隊分布一致，如式(7)：

y1,a,k-y8,a,k=0,?k∈K,?a∈A.

(7)

機隊規模約束，即每種機型在優化周期的初始機隊數量應在用戶設定的上下限之間，如式(8)和(9)：

(8)

(9)

每個機場對不同機型的保障能力不同，因此還需對每個機場每種機型允許過夜的飛機數量進行約束，如式(10)：

(10)

這里：?d∈D,?k∈K,?a∈A.

1.3 連線自動銜接優化

通過航班機型指派模型，只能確定在使用最少飛機數的前提下每個航班的執飛機型，并且能使總體貢獻最大化，但是機型指派模型并不能確定航班與航班間是如何銜接的.飛機連線的銜接本質是在每個機場為進港航班找到后續的出港航班，如圖3所示兩條飛機連線，實際上可以拆分成在杭州、廣州、海口、沈陽和蘭州機場的進港航班和出港航班的銜接.基于機場銜接思路，飛機連線的銜接算法主要有以下3種方法：先進先出、后進先出、加權二部圖最佳完美匹配算法.

圖3 飛機連線銜接本質示意圖Fig.3Aircraft routing schematic diagram

1.3.1 先進先出和后進先出算法

圖4 先進先出和后進先出算法Fig.4FIFO & LIFO algorithms

先進先出和后進先出算法如圖4所示.假設最小過站時間為60 min，先進先出算法(圖4(a))主要是在每個機場內，先進港的航班優先與滿足最小過站時間標準的先出港航班銜接；后進先出(圖4(b))算法主要是在每個機場內，將后進港的航班優先與滿足最小過站時間標準的先出港航班銜接.圖4中，08:10為第一個出港航班，無前序航班；12:00為最后一個進港航班，則無后續航班.先進先出的優點在于求解速度最快，飛機的過站時間分布較為均衡，過站時間相對較充足；后進先出的優點在于飛機的過站時間分布較為極端，可以集中體現飛機的空余運力.尤其在市場旺季區間，使用后進先出法可以快速發現空余運力，有利于旺季增加航班量，提高飛機利用率.

1.3.2 加權二部圖最佳完美匹配算法

每個機場的航班銜接實際上可以看作是一張二部圖的指派問題，即將機場的每個進港航班指派給該機場的每個出港航班，根據銜接目的不同可以對二部圖的邊(銜接)進行賦權，得到一張加權二部圖，再通過KM(Kuhn-Munkres)算法求得二部圖的最佳完美匹配，即可得到滿足要求的銜接方案.

連線銜接通常考慮保留原始銜接、往返銜接、緊湊型銜接3個因素.本文分別對原始銜接、往返銜接、緊湊銜接按0～100的不同得分賦值，其中：如果銜接為往返銜接(原始銜接)，往返銜接(原始銜接)得分即為100分，反之0分；對于緊湊銜接得分，采用指數函數y=100·ax(0

1.3.3 指派飛機連線編號

在每個機場都建立好銜接之后，需要將每個航班賦值機型連線編號.首先建立3個集合：初始航班集合P、前序-后續航班集合PF、終止航班集合F.對于先進先出、后進先出算法，如果未匹配航班屬于降落航班集合，說明該航班無后續航班銜接，屬于終止航班集合F；相反，如果未匹配航班屬于起飛航班集合，說明該航班無前序航班銜接，屬于初始航班集合P.對于加權二部圖求解的結果，邊權為-104的匹配在業務上是不合法的，在這些不合法的匹配中，將起飛的航班歸入初始航班集合，將落地的航班歸入終止航班集合.其次，遍歷初始航班集合P中的每個航班，通過該初始航班在前序-后續航班集合PF中不斷尋找后續航班，直到后續航班為終止航班，說明這些航班屬于同一條飛機連線，為其編號，以形成完整的連線銜接方案.具體的連線銜接流程如圖5所示.

2 實驗及分析

2.1 評價指標

使用不同算法和同一算法不同參數求得的連線銜接方案會有差異.本文結合航空公司實際業務，從飛機日利用率、往返航班銜接占比、原始銜接占比、空檔運力情況、過站時間裕度等指標，對比不同連線銜接方案的差異.

1) 飛機日利用率

飛機日利用率是從時間維度衡量飛機使用情況的重要指標，計算如式(11)所示.日利用率高說明在同等規模的機隊下，能夠充分利用主要固定資產，執飛更多的航班，為航空公司帶來更高收益.

(11)

2) 往返航班銜接占比

衡量往返航班銜接占比高低的指標，如式(12)所示.

往返航班銜接占比=

(12)

3) 原始銜接航班占比

衡量原始銜接占比高低的指標，如式(13)所示.

100%.

(13)

4) 空檔運力數量和時長

如前所述，空檔運力是指每天6:00—24:00時期間，連續6 h及以上沒有任何航班執行計劃的飛機數和時長.例如，圖1(a)中的空檔數量和時長均為0，圖1(b)中的空檔數量為1，空檔時長為6 h.

圖5 飛機連線銜接及編號流程圖Fig.5Aircraft routing flow chart

5) 過站時間裕度分布

過站時間裕度是指飛機實際過站時間與局方要求最小過站時間之差.過站時間裕度越小，說明航班銜接得越緊湊，有利于騰出空檔運力，但應對前序航班延誤情況的能力有限.過站時間裕度越大，說明航班銜接越寬松，不利于發現空檔運力，但能夠較好地應對前序航班延誤的情況，整個航班計劃的穩定性更好.本文中過站時間裕度不計過夜銜接的時間裕度.

2.2 實驗結果

本文選取A航空公司每周共3 876個航班進行實證分析.在這些航班中，1 317個航班延續了上個同航季的航班計劃，占總航班的34.0%；1 028個航班的銜接屬于往返航班銜接，占總航班的26.5%；其余航班均未指派機型且均未確定銜接情況.航班計劃共涉及4個主要基地、79個機場.

機型配置方面，本文應用cplex對機型配置模型進行求解，計算時間為16.3 s(cpu：i5-4570，主頻：3.0 GHz，內存：8 GB)；連線銜接方面，本文用Python程序求解，其中先進先出、后進先出算法求解時間不到1 s，加權二部圖的求解約3 s，實現了大規模航班飛機連線的快速模擬(表3).對比從國外引進的現有系統，雖在機型確定的前提下連線銜接僅需5 s，但還要考慮機型調整的時間，采用人工，則需要1～4 h，若采用本文機型配置結果，還要增加人工錄入時間.對比引言中提到的一體化模型需要數小時的求解時間，分階段的模式在求解效率上具有明顯的優勢，均在20 s以內.

通過第一階段機型指派模型結果(表4)可以得出，使用最少的飛機數為160架，飛機日利用率為8.40 h，貢獻22 602.8萬元，比現有系統編排結果增加收益貢獻232.8萬元/周，相當于1個航季可以增加收益貢獻7 200萬元.

為對比加權二部圖不同參數的效果，本文制定了3個方案，如表5所示.方案一側重往返銜接(簡稱“往返”)，方案二側重保留原始銜接(簡稱“原始”)，方案三側重緊湊銜接(簡稱“緊湊”).

在第一階段機型指派的結果上，分別運用先進先出、后進先出、二部圖、加權二部圖等算法進行連線銜接.從往返航班銜接占比(圖6)可以看出加權二部圖往返方案的占比最高，達82.0%，較初始航班計劃提高55.5個百分點，符合最初側重往返銜接的得分設置.從原始銜接航班占比(圖7)可以看出現有系統的占比最高，為33.7%，基本上保留了初始航班銜接的信息，其次為加權二部圖原始方案，占比31.7%，僅比現有系統少2個百分點.從空檔運力和時間(圖8、表6)可以看出后進先出和加權二部圖緊湊方案騰出的空檔運力最多，空檔運力數量達115個，比現有系統多4個，最高空檔時間達883 h，比現有系統多10%.從過站時間裕度分布(圖10)可以看出，后進先出和加權二部圖緊湊方案在0～5 min銜接裕度上數量最多，其余時間段均為最少，也可以說明這兩種算法傾向于緊湊型的銜接，而先進先出算法在20 min以上銜接裕度數量上均為第一，說明該算法傾向于較為寬松的銜接.對于二部圖算法，在各個指標上均不突出，實際上二部圖的結果只是求得一個可行解，并不能像加權二部圖一樣可以滿足不同的需求傾向.

表3 機型指派模型和連線銜接算法運行時間

表4 機型指派模型運行結果

表5 銜接算法中加權二部圖算法得分權重設置

圖6 各銜接算法對往返航班銜接占比的影響Fig.6The impacts on proportion of round-trip flights among different aircraft routing algorithms

圖7 各銜接算法對原始銜接航班占比的影響Fig.7The impacts on proportion of initial flights among different aircraft routing algorithms

圖8 各銜接算法對空檔運力數量的影響Fig.8The impacts on unused aircraft numbers among different aircraft routing algorithms

圖9 各銜接算法空檔運力時間的影響Fig.9The impacts on unused aircraft flight times among different aircraft routing algorithms

圖10 各銜接算法對過站時間裕度分布的影響Fig.10The impact of transit time distribution among different aircraft routing algorithms

3 結論和展望

航季航班編排關系到航空公司飛機利用率和整體經營效益.本文以使用飛機數量最小化和收益貢獻最大化為目標，通過運用機型指派模型，確定了新航季中每個航班的執飛機型，再運用先進先出、后進先出、二部圖、加權二部圖等算法，根據不同業務需求，求解滿足條件的連線銜接方案，實現航季航班編排的完整規劃.研究結果表明：

1) 先進先出算法傾向于寬松的銜接條件，在運力充足的情況下，采用此方法可以增加過站時間裕度，在發生航班延誤時，能提高整個航班計劃的穩定性.

2) 后進先出和加權二部圖緊湊方案算法在騰挪空檔運力方面效果顯著，在運力較為緊張時，可以通過緊湊型的銜接，發現空檔運力，有利于增加航班，提高飛機利用率.

3) 加權二部圖可以通過對不同需求設置差異化權重，實現往返航班銜接、保留原始航班銜接、騰挪空檔運力等方面的特定需求.特別是盡量做到往返航班銜接，并保留原始航班的銜接，更有利于機組排班等業務工作.

總結本文的研究創新點，主要有兩個方面：

1) 本文提出的模型更側重于航空公司的實際運營需要.采用現有系統編排航季航班，編排效率低、效果不理想；使用一體化模型求解，運行時間較長，較適用于航班計劃相對固定的國際航線編排，但國內民航市場的航班計劃每天都可能發生變動，對連線銜接的求解效率要求很高，如果采取一體化模型，求解效率將無法滿足實際需要.本文采用兩階段模型，可以快速求解滿足需求的連線銜接方案，20 s以內就能完成每周3 800班左右的航班編排.

2) 本文創造性將機型配置模型和加權二部圖算法結合應用.目前，二部圖在連線銜接上主要用于解決單樞紐(或基地)航線網絡的航班銜接問題，無法完全滿足多樞紐航線網絡的銜接，以及尋找運力空檔、往返銜接等不同銜接目標的復雜實際業務需求.本文運用加權二部圖，針對銜接目標不同進行差異賦權，在每個機場建立一張加權二部圖，再通過KM算法求得二部圖的最佳完美匹配，生成針對多樞紐航線網絡不同銜接需求的銜接方案，對比現有系統，航班編排收益貢獻可以提高232.7萬元/周，改善效果明顯.

本文以一個自然周的航班計劃作為研究樣本，通過重復單周的航班銜接方案，擴展至整個航季的航班計劃，可以適用于航季航班計劃的連線銜接優化.但到了航季中段，不同周期的航班計劃可能存在差異，需要編排的航班周期就會大于1周(比如暑運).面對這種情況，算法上計算量和計算時間就會有所增加，后續可以考慮啟發式算法等更加高效的優化算法，應用于優化長周期的航班計劃.