趙晉芳，趙喬洋，周松，殷奧博
（沈陽航空航天大學 a.民用航空學院，b.機電工程學院，沈陽 110136）
航空公司機組排班問題是非確定性多項式（nondeterministic polynomially，NP）的整數規劃問題。在民航運輸業發展初期，由于航班少、機型單一、運行軟件落后等問題，通常由人工完成排班操作，從而導致機組值勤超時、航班銜接不合理、航班延誤等諸多問題。隨著航空公司運力規模的擴大，國內民航事業的競爭也愈發激烈，因此合理運用計算機技術進行機組排班對提升航空公司的飛行運作效益和飛行管理水平具有重要意義。
目前，國外實際應用的機組排班軟件主要分為兩類，即公平性系統（equitability system）和競標系統（bidding system）。Zeghal等［1］將機組排班問題分解為機組配對問題和工作制度建設問題，采用二進制和不完全分割問題的方法簡化該問題，將其轉化為整數線性規劃問題。Anbil等［2］針對機組排班問題設計了TRIP算法，該算法通過三階段分層求解并重復計算的方法滿足約束條件。Kornilakis等［3］針對機組排班問題采用集合覆蓋公式建模，并采用遺傳算法求解。Kasirzadeh等［4］將個性化問題考慮到機組排班問題中，采用列生成算法進行求解。Fahle等［5］、Jiao等［6］、Antonova 等［7］采用列生成技術解決大規模優化的機組排班問題。
國內學者亦對機組排班問題開展了一些工作。范永俊等［8］提出了基于分支定界法解決飛機排班問題的方案。李耀華等［9］將車輛路徑問題模型應用到航班串排班問題上，并利用單親遺傳算子的免疫算法對模型進行求解，得出VRP模型滿足優化航班串排班問題。此外，李耀華等［10］在利用遺傳算法解決排班問題時，還提出了通過控制染色體交叉和變異的概率快速求得優化可行解的方法。陶世群等［11］采用編碼策略以及適應度函數將非平衡指派問題轉化為組合優化問題，提出了一種基于遺傳算法的多級目標非平衡指派問題的求解方法。張米［12］針對機組排班問題設計了可求解大規模機組排班問題的啟發式列生成算法，并通過數值實驗對算法的有效性進行了驗證。潘海洋［13］采用罰函數法解決了機組排班問題中無初始解的情況，探索出高質量的初始列并用啟發式搜索輸入給列生成法，實現了對算法求解質量的優化。李青等［14］提出了排班問題的多目標優化模型，并應用改進的基于信息熵的自適應遺傳算法求解該模型的最優解。邵俊［15］、王文璨等［16］、董宇楠等［17］針對機組任務配對問題，提出利用遺傳算法和啟發式搜索算法，高效產生可行的機組任務配對，充分考慮到機組任務配對中的排班法規和運營成本因素。
雖然國內諸多學者對機組排班問題開展了一些研究，但我國民航排班問題復雜，排班工作量較大，直接應用國外的排班軟件會與國內的運行規范產生沖突，影響機組排班效率，因此需要根據我國實際情況對機組排班問題進行簡化。為解決航班和機組人員匹配所面臨的大規模決策問題，本文考慮將航班聚合形成航班環，將與機組人員形成匹配的基本單位由航班轉變為航班環，即實現由航班—機組人員匹配向航班環—機組人員匹配的轉變，將問題的決策單元確定為航班環和機組的匹配，以降低問題的基本決策單元維度，縮減決策空間。研究可分為兩個階段：第一階段為航班環構建階段，該階段以獲得可行的航班環集合為目標，將一個可行航班計劃的生成過程轉化為滿足要求的航班環的搜索過程；
第二階段為航班環—機組人員匹配階段，該階段的目標為將現有駐地的飛行員與可行航班環相匹配，使得當日計劃航班完成率最高。
1.1 問題描述
航空公司排班問題即對機組人員進行航班環的指派問題，需要在滿足民航規章、公司運行規范的前提下，為機組指派到合適的航班環，并盡可能少地取消航班及盡量減少置位的次數。由于航空公司實際運營管理十分復雜，本研究規定問題中機長和副駕的資質均滿足航班對機長和副駕駛要求、飛機型號均滿足航班需求，且已明確航班、機組機長、副駕駛數量。
1.2 問題假設
（1）每個機組人員有一個固定駐地，以所在地機場表示；
（2）機組人員還可以執行置位任務，置位任務是指機組人員乘坐正常航班從一個機場擺渡到另一機場去執行飛行任務。
2.1 目標函數
主要集合、參數和變量定義如表1所示。欲建立航班環模型，將原問題簡化為航班環p與機組人員k的匹配問題，簡稱問題Q。問題Q的具體定義為：需要將滿足配置的機組與某天的航班環集合P中的航班環p匹配。其中航班環p由多個航班（f1，f2，…，fn）組成，每段航班為一段接續鏈條，機組配置由一名機長i和一名副駕駛j組成。本文用a表示有滿足配置的機組和航班環匹配，其定義式如式（1）所示。用決策變量xa表示a是否啟用，啟用取1，否則取0。
表1 集合、參數和變量定義
其中，目標函數需依編號次序滿足：（1）盡可能多的航班滿足機組配置；
（2）盡可能少的總體置位次數。由此可知，兩個目標函數具有不一樣的優先級，且第一優先級的目標是使盡可能多的航班滿足機組配置。
首先針對目標（1），運用決策變量yf來控制不能起飛的航班，若不能起飛為1，否則取0，可用式（2）表示最小化不能起飛的航班數
其次針對目標（2），要求盡可能少的機組置位次數，因此對所有匹配a的置位航班進行求和，為此定義了Fa即匹配a中的航班f集合，則總置位次數最小化表達如式（3）所示
考慮到?f∈Fa，均有恒定的xa，且da fnf為常數。因此，式（2）可寫為
由于問題Q為多目標函數優化問題，結合大M法理念［18］，為兩個目標函數添加加權系數m1＞＞m2，將多目標問題轉化為單目標優化問題。因此問題P表達如式（5）所示
2.2 約束條件
機組排班問題主要分為空間與時間的銜接約束和航班與機組的屬性約束。
2.2.1 航班任務未完成的松弛約束
因機組排班的核心任務是完成每個航班任務，應有約束如式（6）所示
但由于式（6）引入判斷是否滿足機組配置的yf，式（6）可以被松弛為式（7），同時與目標函數式（5）中第一項協同控制，使得不能起飛的航班數最小化。
2.2.2 航班空間銜接約束
對于兩段連續的航班f，將前段到達航班索引定義為h，后段離港航班索引定義為l。此外，定義前段航班到達機場時間為，后段離港航班出發時間為。由于航班的空間連貫關系，前段航班到達機場時間必須為后段航班離港時間。因此航班的空間銜接約束定義如式（8）所示
2.2.3 航班始發與終點空間約束
由于每個機組人員需從初始駐地出發并最終回到初始駐地，因此，在航班環建模中，針對所有從駐地始發的航班，都需與本文構造的虛擬起點相連接；
同樣的，針對所有終點到達駐地的航班，都需與本文構造的虛擬終點相連接。此外，針對機組人員的虛擬起點與終點必須是同一個機場。
定義一條航班環中最早的航班為f_min，最晚的航班為f_max。因此，該類約束表達如式（9）所示
2.2.4 最小過站時間約束和最長過站時間約束
由于民航局對最小過站時間有所規定，在此定義該最小過站時間標準為50 min）。此外，為避免飛機過站時間過長造成資源浪費，定義最長過站時間=100 min）。定義前段航班的到達時間為，后段航班的離港時間為。因此，航班最小過站時間約束和最長過站時間約束如式（10）和式（11）所示
2.2.5 航班—機組人員對應唯一性約束
由于置位情況的存在，為確保航班和機組唯一確定，定義航班f在航班環集P中出現次數為δf，則航班f的執飛次數用置位次數表達，如式（12）所示
因此有唯一性約束表達如式（13）所示
2.2.6 值勤時間約束
為保證航班的飛行安全，設置最大飛行值勤小時數為h值勤，飛行時間為h飛行，因此需引入約束如式（14）、（15）所示
2.2.7 航班約束
因最大航班受值勤小時數h值勤約束，因此需引入約束如式（16）所示
2.3 模型約簡
綜上所述，可以將原問題Q的模型總結如式（17）所示
由于問題Q仍然是組合爆炸問題，因此，定義兩類機組人員的上限分別為εI、εII，每一個匹配a中兩類機組人員出現的個數分別為φI、φII，因此需引入新約束如式（18）、（19）所示
3.1 算例設置
本文研究的是某民營航空分公司機組某日的排班問題，其測試算例航班如表2所示。在本算例中，共有飛行機組人員24人，其中12人為機長資質，12人為副駕駛資質。飛行機組駐地為A、B兩地和C、D、E 3個過站機場。其中A駐地共有機組人員12人，其中6人為機長資質，6人為副駕駛資質。B駐地共有飛行機組人員12人，其中6人為機長資質，6人為副駕駛資質。根據CCAR121手冊查詢出h值勤max=14 h，h飛行max=9 h，根據h值勤max可得pmax=4。
表2 測試算例航班
首先，為獲取航班環集合P，將提供的航班信息轉換成一個有向圖，如圖1所示，其中每個節點代表不同的航班，每個節點包含有航班的起止機場與時間信息。每根連接線都代表節點與節點之間的合法連接，需要滿足包括時間、地點等的約束。如圖1所示，3個航班樹相互連接，形成了一個航班網絡結構。航班1的可合法連接航班包括1-2、1-3、1-4以及1-5，航班2的合法連接包括2-3、2-4及2-5；
航班5則能夠與航班6及航班3合法連接。通過搜索可從航班1的航班樹連接航班5的航班樹，從而派生出1-5-6和1-5-3兩個合法的任務環。其余航班樹同理。
圖1 深度優先搜索算法網絡
其次，必須構建一個啟發式函數，以評估航班環的品質。該啟發式函數涵蓋以下考慮因素：最大值勤時間h值勤max、航班環P所包含的城市數Cp以及航班環P所包含的航班數Np。選定一個起始城市作為出發點。從起始城市出發，深度優先搜索所有可能的航班路徑DFS，通過遞歸方式，針對每個可能的下一個航班進行以下步驟：
（1）若滿足啟發式函數的品質要求，則將當前航班加入航班環中；
（2）遞歸嘗試下一個城市，持續搜索可能的航班。
每當形成一個航班環（至少包含起始城市），將其儲存為一個可行解，并納入航班環集合P之中。若無法找到適宜的下一個航班，或已經構建出航班環，將回溯至前一個城市，繼續搜索其他路徑。在搜索過程中，采用不同的起始城市，通過多輪迭代以找出更多的航班環。搜索完成后，輸出所獲得的航班環集合P。
利用匿名指派法，將NP難問題進行降維處理，根據資質要求和駐地對φI、φII、φIII名飛行機組成員區分為nc個機組。最后由于約束條件式（16）限制，其nc個機組最多可完成pmaxnc個航班，若不采用pmax航班環，其最多完成(pmax-1)nc個航班，因此若選用pmax航班環為起始點的目標函數值大于(pmax-1)nc，則不討論選用pmax-1航班環為起始點的可行解。
本文選用pmax個航班的航班環為起始航班環，通過貪心算法進行機組排班。貪心算法本質上是一種啟發式方法，它通過局部最優選擇來構建解決方案。本文通過建立STn篩選算法完成模型求解，其算法流程圖如圖2所示。
圖2 STn篩選算法流程圖
STn篩選算法應用如下：創建一個空集合來存儲已選擇的航班環，開始時為空。對于每個航班環，計算它是否與已選航班有交集。從尚未選擇的航班環中選擇無交集的最大航班數的航班環，并將其添加到已選擇航班環中，形成新的集合。以此類推直至選擇12個航班環或沒有更多航班環可供選擇為止。
3.2 計算結果
由表3機組排班結果可知，該航班有3個航班未完成，其序號為5、24、34，是由飛行時長、空間和時間約束限制造成的，因此可以在做航班計劃時去掉這3個航班，滿足機組配置航班百分比為92.86%。飛行小時數總計79.08 h，飛行小時數利用率為73.22%，總飛行值勤時長為107.75 h，飛行值勤時長利用率為64.14%，該算例共置位一組機組從駐地A搭乘2號航班飛往駐地B完成27-20的飛行計劃。由結果可知該排班結果留有一定余度，但相對于機組每月總飛行時長100 h略偏高，因此該算法更適用于航空旺季，可以合理安排機組人員使航空公司利用最大化。由于飛行機組人數不同，會引起最終航班完成程度的差異，因此進行靈敏度分析，以該航班計劃表為例找到最優飛行機組人數配比。
表3 貪心算法機組排班結果
3.3 實驗對比
為了驗證文中算法的可靠性和高效性，本文將遺傳算法與貪心算法進行比較，利用遺傳算法的機組排班結果如表4所示，兩種算法比較結果如表5所示。可以明顯看出，在迭代次數一定的情況下，由于貪心算法易于實現并且算法高效，使得它在問題規模相對較小、計算資源有限的情況下，能夠快速地找到一個可行的排班方案。并且由于貪心算法逐步地選擇最優的步驟，因此可以在實時環境中快速地生成排班。這對于需要頻繁更新排班的場景，如應對突發事件或變動具有優勢。由于機組排班問題可能沒有太多的約束條件或變數，使得遺傳算法在迭代次數有限的情況下，計算結果反而沒有貪心算法精確。
表4 遺傳算法機組排班結果
表5 兩種算法計算結果對比
3.4 靈敏度分析
靈敏度分析是研究一個模型輸出項對系統參數敏感程度的方法，在建模中經常利用靈敏度分析來研究原始數據發生變化時最優解的穩定性。此外，靈敏度分析還可以度量參數對模型的影響水平。在一次執飛任務中，航班必須由飛行機組人員操作；
換言之，機組人員數量是制約實飛航班數量的關鍵約束之一。本文選取機組人員數量作為靈敏度分析指標，對機組排班優化模型進行靈敏度分析。由于本算例中機長、副駕駛比例為1：1，可以最大限度提高機組作業效率，因此，在靈敏度分析實驗中，機長、副駕駛各占總人員的50%。
結合算例情景，使機組人員總數量在［0，36］區間內等步長增加，循環調用Groubi對模型進行優化求解，輸出未滿足及滿足配置的航班數量（實飛班次數量）如表6所示。對靈敏度分析結果進行可視化，如圖3所示。隨著機組人員總數量的增加，滿足機組配置的航班數量由0提升至41，未滿足機組配置的航班數量自42開始逐漸減少至1，之后不再變動，滿足配置的航班數量增加呈現邊際效應遞減。在圖3中標記（1）、（2）兩處區域，滿足機組配置的航班數增長曲線斜率出現了明顯的變化。據此可將機組人員數量增加對航班數的影響過程劃分為4個階段：
圖3 機組排班任務靈敏度分析可視化
表6 機組排班任務靈敏度計算結果
第一階段：機組人員數量從0增加到8，該階段航路基本閑置，機組人員數量是制約實飛航班數的主要因素，隨著機組人員數量的增加，實飛航班數快速增長；
第二階段：機組人員數量從8增加到20，該階段部分航路開始出現競爭，但是由于機組人員基數較少，實飛航班數隨機組人員數量增加仍有顯著提升；
第三階段：機組人員數量從20增加至28，此時航路數量開始出現較多競爭，實飛航班數增長趨勢明顯放緩；
第四階段：機組人員數量自28開始繼續增加。此時，航路數量取代機組人員數量，成為制約航班數的關鍵約束，機組開始出現一定比例的人員空閑，僅提升人員數量無法再提高實飛航班數量。
綜上，機組人員數量對實飛航路數量的增長呈現邊際效應遞減，而機組人員數量控制在20左右是兼顧成本與實飛航班數的較好方案。
本文通過構建航班環對飛行計劃和機組排班計劃進行優化處理，剔除不合理的航班，保證了航班計劃的可行性，同時還降低了因置位飛行員所帶來的額外成本。在滿足航班連續性的約束下完成了航班計劃與機組排班計劃。
（1） 針對航空公司的排班現狀及航班環選擇問題的復雜性和優化結果不滿意等問題，提出基于航班環的指派思路，構建優化模型。
（2） 本文通過深度優先搜索算法和貪心算法，得出局部最優航班計劃。對于未完成的航班依照目標函數的權重大小進行飛行員置位處理或放棄該飛行計劃處理，該值主要受加權系數m1、m2控制，可以通過當日實際情況更改加權系數使其選擇不同的處理方法。
（3） 對于沒有航班環與機組匹配的航班，本文進行受限主問題模型的松弛處理，將未完成航班加入受限主問題中再次進行求解，如此迭代，直到無法尋找到可使目標函數優化的變量，得到松弛問題的最優解。
（4） 本文進行了靈敏度分析，評估了模型對輸入參數變化的響應程度，了解模型未完成航班yf如何隨著機組總人數K的變化而變化，從而幫助決策者更好地理解系統的行為和性能，做出更準確的決策。
本文將NP多目標問題進行降維并簡化，驗證了其合理性，極大地提高了飛行計劃和機組排班的效率。在飛行機組成員選擇上，利用靈敏度分析得出機組人數最佳方案，為后續制定最終飛行計劃做好基礎。
猜你喜歡 機組人員航班約束 全美航班短暫停飛環球時報(2023-01-12)2023-01-12山航紅色定制航班金橋(2021年10期)2021-11-05藍色起源將實現世界首次全大眾太空飛行 最小機組人員僅十八歲海外星云(2021年9期)2021-10-14山航紅色定制航班金橋(2021年8期)2021-08-23山航紅色定制航班金橋(2021年7期)2021-07-22“碳中和”約束下的路徑選擇加油站服務指南(2021年4期)2021-07-21約束離散KP方程族的完全Virasoro對稱數學年刊A輯(中文版)(2020年1期)2020-05-19印度航空公司125名機組人員因超重遭停飛奧秘(2016年1期)2016-02-24適當放手能讓孩子更好地自我約束人生十六七(2015年6期)2015-02-28不等式約束下AXA*=B的Hermite最小二乘解上海理工大學學報(2012年3期)2012-03-20