遺傳算法在機型配置中的應用

陳蓉

摘 ?要：航班機型配置關系到航空公司的行業競爭力，是航空公司長期關注的問題。針對航空運力過剩及機型比例失調等問題，考慮航班規模增加及機型配置需求增多對航空公司的影響，引入多重約束，建立基于航空收益最大化的航班機型配置優化模型。采用遺傳算法求解該模型，并設置算法中的選擇、交叉、變異等算子，獲得一段時間內機型配置連線最優方案。研究表明，提出的多重約束優化模型和遺傳算法，能夠提高航空公司機型配置時效性與科學性。

關鍵詞：機型配置;多重約束;航空收益;遺傳算法

中圖分類號：TP399 ? ? 文獻標識碼：A

Abstract： Fleet assignment， a long-term concern of airlines， has much to do with the competitiveness of airlines. Considering the impact of increased flight scale and increased fleet assignment demand on airlines， this paper introduces multiple constraints and establishes a fleet assignment optimization model based on maximizing aviation revenue， aiming at the problems of overcapacity and imbalance of aircraft types. The genetic algorithm is used to solve the model， and the selection， crossover， mutation and other operators in the algorithm are set to obtain the optimal solution for fleet assignment connection scheme within a period of time. Research shows that the proposed multi-constraint optimization model and genetic algorithm timely and scientifically improve fleet assignment model.

Keywords： fleet assignment; multiple constraints; aviation revenue; genetic algorithm

1 ? 引言（Introduction）

國內外航空市場競爭日益激烈，各航空公司為了提升競爭力，對增加航班規模、優化航班資源配置、精細化管理提出越來越多的要求。其中，機型配置是航空運輸中不可缺少的一部分，也是提升航空市場競爭力的一個有效方法。機型配置是航空公司在航班時刻表的基礎上進行現有機型的分配，它根據不同的機型具有的不同座位數、客運需求、最大空缺率、運行成本、最大耗油量等，配置不同的機型給設定好的航班，從而使航空公司獲得最大收益。此外，飛機座位是“易腐的”，在航班離港前沒有出售就會造成浪費，因此最理想的決策就是將“合適的座位數”以“合適的價格”提供給“合適的乘客”。本文主要從“合適的座位數”出發，優化航班的機型配置。

機型配置是一項長期研究的問題，過去的研究大多集中于機組任務問題上，定義一個便利且高效的目標函數[1]，開發高效算法來解決復雜的資源配置問題[2]，或者研究問題的動態性質[3]，也有研究問題的隨機性[4]、魯棒性[5]的。常見的機型配置問題可通過整數規劃建立數學模型或建立時空網絡圖[6]來解決，包括引入乘客需求、運營成本、票價、時間窗、航班頻率等因素[7-9]。

機型配置規劃中不同的機型及限制條件不同，模型算法有所不同。胡明華等提出改進的啟發式算法用于解決多元受限航班優化模型[10];李福娟等采用緊急搜索法對航空公司航線計劃優化模型進行求解，使利潤達到最大[11];WEI等采用一種原始的集成優化方法對機隊分配進行求解[8]。但當問題規模較大時，上述模型求解比較困難，因此，遺傳算法等智能搜索算法也被用于問題求解。

研究表明，機型配置規劃對航空運輸具有非常重要的意義，目前研究大多集中于某個因素或多個因素約束構成的綜合模型，或者對重大規模現有模型進行算法優化。本文在已有的理論上進行深入探究和發展，首先基于飛機座位數、尺寸、效率、成本、耗油量等因素建立以收益最大化為目標的多重約束機型配置模型;然后采用遺傳算法對其進行優化求解，使機型配置模型求得適應度最優的解;最后結合具體情況，驗證機型配置模型的可行性和有效性，以及遺傳算法用于解決機型資源配置的高效性。

2 ? 機型配置模型（Fleet assignment model）

2.1 ? 問題描述

機型配置是航班計劃的重要研究內容。我國現有航空公司中，每個航空公司不止一種機型，每種機型的飛機架數、座位容量、油耗、成本（維修成本及乘客溢出成本）等都是不同的，且在不同的航線上，不同的機型產生的運營成本也是不同的，故機型配置是為了確定每一條航線上使用的機型，并使得整體利益最大化。

要解決的問題及基本假設：

（1）機型配置要確定每一條航線應該使用哪一種飛機或機隊，使收入減運營成本最大化。

（2）航班時刻表是已知的，是一組具有指定起飛和到達時間的航班段。

（3）收入是細分市場需求，運營成本取決于飛機的尺寸和效率，以及航段的距離。

（4）機場必須有飛機可以飛行，且每個機場必須在一周開始和結束時分配相同的飛機。

（5）滿足覆蓋約束：確保每個單航程只分配一種機型;滿足計數約束：每個機型指定的飛機架數必須等于該機型在所有時間內可用的飛機總數;容量限制約束：分配到單一航程的所有乘客數量不能超過分配到該航程機型的容量;平衡約束：中轉服務飛行必須將兩個航段分配給相同的飛機;行程約束：機型分配航程時要注意機型路程類型，短途機不能分配給中長航段，中途機不可以分配給長航段。

2.2 ? 模型構建

2.2.1 ? 模型參數

機型配置模型所需參數及變量定義如表1所示。

其中，目標函數（5）是機型配置下運輸成本與收入的絕對值最大化，即使得收益達到最大。約束條件（6）確保每一次“真正”的飛行都有一架指定的飛機，即每一個航段都有一個機型來覆蓋。約束條件（7）確保每個機型的每架飛機只能從偽出發航班集及偽到達航班集起飛一次。約束條件（8）確保飛機必須在同一個地方開始和結束。約束條件（9）確保滿足最大座位空缺率，如果MS=0.1，航班的需求為100，則可溢出的乘客最多不超過10人，即必須使用座位容量大于90的機型。約束條件（10）強制在中轉飛行中，航段要使用相同的設備機型。約束條件（11）和（12）確保飛機必須在機場才能被分配給航段且機型相同，其中，對于將要

從某機場出發的航班，是在該機場航班可以銜接的到達航班集合，且滿足航班銜接的時間要求;，即在航班

前從該機場出發的航班集合。約束條件（13）和（14）確保機型與航班之間類型的兼容性，其中，即長途機型可以進行長、中、短途飛行;，即中途機型可以進行中、短途飛行，短途機型只能飛短途。

3 遺傳算法的應用（Application of genetic algorithm）

由于航空運輸規模的擴大，且機型配置模型是大規模數學組合模型，為了在短時間內得到最優解，本文采用遺傳算法對機組配置模型求解，采用適合的編碼方式及約束條件的處理方式，選取適應度函數和選擇、交叉以及變異方法，最后以某航空公司的數據為例，代入機組配置模型進行研究，計算使得機組航班資源最優的配置方案。

3.1 ? 編碼

采用遺傳算法對機組配置問題進行求解，需要編碼確定研究問題所表達的含義。本文采用直接編碼法對其進行編碼，其中機型編號為1—，航段為染色體上的基因位數，即為染色體長度。假設機型有3種，航段數為6，在進行編碼時3種機型的編號為1、2和3，規劃方式為36種選擇，假設一條染色體上基因的排列為（1，3，2，3，1，1），則解為：

3.2 ? 初始化數據

求解模型中所需的數據格式，確定交叉概率和變異概率，選擇一個機型配置結果作為初始群體，即為模型求解結果的假設集合，模型的最優解將通過這些初始解進化而求出。選擇初始解，可以采用隨機選取或優化算法選取，本文采用的是隨機選取。

選取初始群體后確定每個個體的適應度，適應度函數是根據目標函數來區分的。對每個航班所選擇的機型的編碼串進行解碼處理后得到個體的表現型，通過個體表現型可計算機出對應個體的目標函數值，根據機型配置模型的目標函數轉換出個體的適應度。

3.3 ? 選擇、交叉與變異

遺傳算法是一個優勝劣汰的尋優算法，選擇操作的目的是為了將不夠優的個體從群體中挑出，也就是在將機型分配給航段的個體中選擇適應度較高的個體進行演化。本文采用最佳保留選擇算法，按輪盤賭選擇方法執行遺傳算法的選擇操作，然后將當前群體中適應度最高的個體結構完整地復制到下一代群體中。

對于選中的用于演化的個體，隨機選擇兩個個體相同的位置進行交叉操作得到新的個體，然后根據變異算子的概率對某些個體的某些位置執行變異操作，增加全局優化特性，確保得到全局最優解。

4 ? 算列分析（Example analysis）

每條飛機連線上的航班視為一個航班塊，每一個航班塊包括序號、出發地和出發時間、目的地和到達時間、乘客需求及票價。決策變量為0—1的整數，即每一個決策變量只能取0或1。以表2和表3數據為例，涉及230個航班的3個機型，其中表2為航班塊集合（由于篇幅限制，僅展示部分信息），表3為機組信息集合。

根據表4、表5可以得出：（1）引進遺傳算法得到的最優解成本劣于混合整數線性規劃得到的最優解成本，但是隨著迭代次數的增大，GB也隨著減小，這證明了遺傳算法引入的有效性，且所提出的算法不受問題空間的限制，因此遺傳算法能在可接受時間內產生較優航空資源配置。（2）遺傳算法的引進增加了算法運行時間，但這個運行時間在成本取得較優的情況下可以忽略不考慮，且時間的增加在可接受范圍內。

5 ? 結論（Conclusion）

考慮到航空公司規模的不斷擴大，機型配置問題也愈發復雜，遺傳算法的引進解決了航班資源配置問題。首先，考慮乘客需求、運行成本、飛行距離、票價、耗油量等因素的影響，根據航班集合信息及機隊信息，建立收益最大化的機組配置優化模型;其次，考慮大規模問題，引進自適應遺傳算法，為調度、機組分配問題創建可行的初始解，設計制定遺傳算子，改進初始解，得到全局較優解;最后，以航空公司數據為例，將采用遺傳算法后的資源配置結果和最初的資源配置結果進行對比。結果表明，引進遺傳算法的優化模型可以得到全局最優解，實現了飛機停機調度約束的統一，通過對不同個體的適應度分析，得到全局效益最優解，且該優化模型靈活可變，方便后續相關約束的加入，能夠通過建立線性約束條件，較為方便地加入、修改、取消相關約束，進而實現約束的動態優化。

參考文獻（References）

[1] DUMAS J， AITHNARD F， SOUMIS F. Improving the objective function of the fleet assignment problem[J]. Transportation Research Part B： Methodological， 2009， 43（04）：466-475.

[2] YAN S Y， TANG C H， FU T C. An airline scheduling model and solution algorithms under stochastic demands[J]. European Journal of Operational Research， 2007， 190（01）：22-39.

[3] JIANG H， BARNHART C. Dynamic airline scheduling[J]. Transportation Science， 2009， 43（03）：336-354.

[4] CADARSO L， CELIS R D. Integrated airline planning： Robust update of scheduling and fleet balancing under demand uncertainty[J]. Transportation Research Part C： Emerging Technologies， 2017， 81（02）：227-245.

[5] JIANG H， BARNHART C. Robust airline schedule design in a dynamic scheduling environment[J]. Computers & Operations Research， 2013， 40（03）：831-840.

[6] HANE C A， BARNHART C， JOHNSON E L， et al. The fleet assignment problem： Solving a large-scale integer program[J]. Mathematical Programming， 1995， 70（02）：? ? ? 211-232.

[7] YAN S， TSENG C H. A passenger demand model for airline flight scheduling and fleet routing[J]. Computers and Operations Research， 2002， 29（11）：1559-1581.

[8] WEI K J， VAZE V， JACQUILLAT A. Airline timetable development and fleet assignment incorporating passenger choice[J]. Transportation Science， 2020， 54（01）：139-163.

[9] SERRANO-HERNANDEZ A， CADARSO L， FAULIN J.?? ? A strategic multistage tactical two-stage stochastic optimization model for the airline fleet management problem[J]. Transportation Research Procedia， 2020， 47（04）：473-480.

[10] 胡明華，朱晶波，田勇.多元受限的航班時刻優化模型與方法研究[J].南京航空航天大學學報，2003，35（03）：326-332.

[11] 李福娟，王魯平，劉仲英.航班計劃優化模型及其應用研究[J].計算機工程，2007，33（11）：279-281.

作者簡介：

陳 ? 蓉（1970-），女，碩士，經濟師.研究領域：航空公司數字化轉型及智能系統建設.