提高飛機使用效率的飛機維修路徑規劃方法

中圖法分類號：F253.9 文獻標志碼：A DOI： 10.13714/j.cnki.1002-3100.2025.09.013

Abstract：Inordertoensurethesafeoperationofcivilaireraft，eachaireraftnedstobemaintainedbeforereachingtherequired aircraftregular inspectionandmaintenanceinterval.AimingattheAircraftMaintenanceRouting Problem （AMRP），this paper takesthecumulativeflightdaysandaccumulatedflighthoursoftheircraftasthemaintenanceinterval，andstablishsamath maticalprogrammingmodelwiththegoalof minimizingtheremainingflighthoursbeforethemaintenancecheckofthefletair craft.TheCompressdAnnealingAlgorithm （CA）isusedtosolvetheproblem.Experimentalanalysisbasedonflightdataand comparison withthecommercialsolverCplexshowthattheCAalgorithmcanefectivelysolve the AMRP modelandcanobtaina satisfactory solution in a short time.

Keywords：airtransportation；aircraftmaintenancerouting;aircraftscheduling;mathematicalmodel;meta-heuristicalgorithm

隨著民航運輸業的快速發展，航空公司的機隊規模、航班數量以及航班密度等在逐漸上升，在此環境下，如何高效、快速地處理其運營調度問題是航空公司所面臨的巨大挑戰。最優的調度計劃對航空公司降低運營成本提高收益具有關鍵作用。針對AMRP，國外學者較早開始研究。Feoet al.1最早開始AMRP的研究，他們建立了考慮維修基地選址問題的AMRP模型，利用一種兩階段啟發式方法求解問題。Sriram et al.2拓展了Feoet al.提出的模型，同時考慮飛機A檢、B檢，并提出了一種啟發式算法求解；Taluri et al.3研究了滿足4天維修間隔的AMRP模型。Clarkeetal以最大化連接值（Through Value）為目標函數建立了相應的AMRP模型并利用拉格朗日松弛算法求解?；凇按钡木S修路徑模型最先被 Bamhart et al提出，他們以所選串的總成本最小化為目標函數，利用分支定價算法來求解該模型。Liang etal研究了航班任務每天重復的飛AMRP，并提出了基于時空網絡的輪轉路徑，時空網絡與相應的混合整數線性規劃模型，利用Cplex求解模型，但是模型忽略了飛機的維修需求。Basdereet al考慮飛機剩余飛行時間，建立了AMRP的整數規劃模型，利用Cplex和CA算法求解模型。近幾年研究中，Eltoukhy et al.8提出了一個考慮連接值的AMRP整數規劃模型，對比了三種元啟發式算法的求解效率。Ruan et alP將 AMRP建模作為一個馬爾科夫決策過程模型，并利用強化學習算法解決。Esmaeilzadeh et al考慮了調機飛行，建立了AMRP 雙目標混合整數規劃模型，并利用epsilon-constraint算法和NSGA-I算法解決。

我國AMRP研究起步較晚，最早的相關研究學者是都業富教授提出了航班串的概念。孫宏等是較早開始研究飛機路徑規劃的學者，他們提出了單樞紐航線結構下基于飛機調度、基于所需最小飛機數量、基于飛機使用均衡的飛機路徑規劃模型，模型復雜度較低，僅適用于小規模實例。肖東喜等[3研究了滿足3天維修間隔并以飛機維修機會最大化為目標的AMRP，利用列生成算法求解模型。李耀華等4研究了航班串的編制問題以及一體化AMRP問題5]。藍伯雄等對飛機進行任務環的指派，以最大化飛機維修前的累計飛行時間為目標，利用求解器Cplex對模型求解。郭潤夏等建立了以維修間隔利用率最優為目標的AMRP模型，并提出了基于強化學習的Q-Learning求解算法來求解問題。

現有AMRP研究大多考慮一種飛機維修間隔，對于同時考慮兩種或以上的研究較少?；诖?，考慮現有研究情況，改進原有優化模型，并提出了一個考慮飛機飛行天數限制與飛行時間限制的整數線性規劃模型，模型以最小化飛機維修前的剩余飛行時間為目標，同時考慮兩種飛機維修間隔限制，更加貼合實際情況。為了高效、快速求解問題，本文利用壓縮退火算法求解AMRP。

1問題描述及數學模型

1.1問題描述

AMRP的主要目的是在考慮航空公司機隊規模的情況下，為機隊中的飛機分配航班任務或航班任務串，并滿足民航規章和航空公司規定的飛機定檢類型與維修間隔，降低運營成本，以實現最優的資源配置。AMRP是短期內的決策問題，主要考慮飛機A檢。A檢是級別最低、期限最短的定期維修項目。它主要是把周期相同項目的檢查工作組合在一起形成成套維修。

1.2問題建模

在AMRP研究中，連接網絡是被應用最廣泛的底層結構之一。連接網絡包括源節點、匯節點、航段節點，連接網絡見圖1。航段節點見圖2，每個航段節點包含一次航段任務中的起飛機場、起飛時間、目的機場、降落時間。航段節點間的連接弧代表著航段間可以進行銜接。連接弧包含三種：（1）普通弧：若飛機連續執行航段i和 j ，并在航段 i 的降落機場未進行維修檢查，但在后續的飛行中進行了維修檢查，則航段 i 和 j 之間利用普通弧連接；（2）維修弧：若飛機連續執行航段 i 和 j ，并在航段i的降落機場進行維修檢查，則航段i和 j 之間利用維修弧連接；（3）非維修?。喝麸w機連續執行航段 i 和 j ，并在航段i 的降落機場未進行維修檢查，且在后續的飛行中也未進行維修檢查，則航段i和 j 之間利用非孤連接。

航段節點間的可行銜接需滿足地點（前一個航段的到達機場要與后一個航段的起飛機場相同）、時間約束（前一個航段的到達時間與后一個航段的起飛時間差應滿足飛機的周轉時間或維修時間要求）。若一架飛機在執行完某個航段任務后需要進行維修檢查，則需要滿足以下兩個條件：（1）飛機所在機場是維修機場，即具有維修能力的機場；（2）該飛機執行的下一個航段任務的起飛時間與剛執行完的航段任務的降落時間差應大于飛機維修時間與該飛機執行下次飛行任務的準備時間之和。

月了連根據飛機距離下次維修檢查的剩余飛行時間和剩余起落次數，將飛機劃分為三類 （K₁，K₂，K₃） ！ K_r 飛機的剩余飛行天數小于等于7天，必須在規劃期內進行維修檢查。 K₂ 飛機的剩余飛行天數大于7天，但其剩余飛行時間小于航段網絡中總持續飛行時間最長的一條路徑的總飛行時間 η^（L?） ，因此，不確定其是否需要進行維修檢查。 K₃ 飛機的剩余飛行天數大于7天，且剩余飛行時間大于 L ，因此 K₃ 飛機不需要考慮維修檢查。相應的集合、參數以及決策變量如表1所示。

基于以上論述，建立了如下AMRP優化模型：

min_k=K1∪K2（r_kR_k-Σ_i∈Id_i（Σ_j∈S（i）X_ijk+Σ_j∈S（i）Y_ijk））

式（1）為目標函數，表示最小化飛機維修前總的剩余飛行時間。式（2）為航段覆蓋約束，確保每個航段都被覆蓋。式（3）、式（4）確保每架飛機從源節點出發。式（5）保證每架飛機利用非維修弧連接匯節點結束于匯節點。式（6）、式（7）為K_r 、 K₂ 和 K₃ 飛機及其執行的航段間的銜接約束，式（6）表明：當一個航段由一架飛機利用維修前弧覆蓋時，下一個航段必須由該架飛機利用維修前弧或維修弧覆蓋；式（7）表明：當一個航段由一架飛機利用維修弧或非維修弧覆蓋時，下一個航段必須由該架飛機利用非維修弧覆蓋。式（8）為 K₃ 飛機的銜接約束。式（9）、式（10）為 K₁ ！ K₂ 飛機的飛行時間限制約束：式（9）保證 K₁ 和 K₂ 飛機在進行下次維修檢查之前的累計飛行時間不超過其剩余的飛行時間。式（10）表明：若在規劃期間對 K₂ 飛機進行維修檢查操作，則其在維修檢查之前的累計飛行時間要小于其剩余的飛行時間，若在規劃期間未對 K₂ 飛機進行維修檢查操作，則其飛行的整條路徑的總飛行時間要小于等于其剩余的飛行時間。式（11）和式（12）為 K_?1 ！ K₂ 飛機維修檢查限制。式（13）和式（14）為0＼～1決策變量。

2壓縮退火算法

AMRP已經被證明是一個NP-hard問題[8]，一些大型航空公司的航班規模以及飛機數量是很大的，利用求解器這類精確算法很難在合理時間內給出一個滿意方案。同時，一些不確定事件的發生很可能會中斷已制定的航班計劃，需要頻繁、快速地規劃飛機維修路徑。因此快速高效地解決AMRP至關重要。

基于模擬退火算法的壓縮退火算法（CA）被Ohlmann et al.19提出，CA算法具有較強的局部搜索能力，本文利用該算法求解問題。不同于模擬退火算法的是該算法會對不可行解添加一個變化“壓力”懲罰值，算法在迭代過程中，“溫度”與“壓力”同時變化。在算法的初始階段，“溫度”較高，“壓力”較小，對于不可行解的接受概率較高，所以算法會在可行與不可行解空間中充分搜索。隨著算法的迭代，“溫度”降低，“壓力”升高，對于算法搜索到的不可行解的接受概率逐漸降低，使算法在可行空間內進行搜索，最終收斂到最優。壓縮退火算法的溫度和壓力的變化趨勢如圖3所示，該算法流程圖如圖4所示。

初始解通過求解一個簡化的模型來獲得，在簡化的模型中，忽略目標函數以及飛機飛行天數和飛行時間限制，將每架飛機作為節點加入連接網絡中以降低模型復雜度，達到快速求得的目的。簡化的模型如下所示：

minO

在簡化的模型中，式（16）保證了每個飛機節點連接第一個執行的航段節點；式（17）保證每個航段被覆蓋一次；式（18）是航段間銜接約束，保證了路徑的連通；式（19）保證了每條路徑的完整性。

鄰域解的生成方法如下：隨機選擇兩架飛機（飛機1和飛機2）與其對應的航段序列，從飛機1中隨機選擇一對連續的航段 i 和航段 j ，檢查飛機2中是否存在一對連續的航段 χ_i 和航段 j ，使得 j^'∈S^（i^′） 1 ，若存在這樣的連續航段對，則交換航段 i 以及航段 i 的后續所有航段，若不存在則重復這個尋找過程。

3實驗與分析

本實驗所測試的航班數據由兩組不同規模的數據組成。第一組實驗數據由Case1＼～10組成，包含354個航段、8架飛機、22個機場和5個維修機場。第二組實驗數據由案例Case11＼～20組成，包含667個航段、20架飛機、36個機場和5個維修機場。對于所有Case，利用商業求解器 Cplex和CA算法分別求解，并對所有Case的實驗結果進行分析。利用求解器求解是在VS 2022環境下調用 Cplex12.10 實現，CA算法是在VS2022環境下 C++ 編程實現。所有實驗均運行在一臺操作系統Window11，16G內存，處理器i5-12460F 3.00 GHz的計算機。算法中的具體參數描述可以參考文獻[19]。

3.1實驗數據設置

第1組測試數據中，Case1＼～10包含3種飛機類型 K₁ ， K₂ ， K₃ 的數量分別為2、3、3。第2組測試數據Case11＼～20包含3種飛機類型的數量分別為5、7、8。每個Case中的飛機起始位置、飛機剩余飛行天數以及剩余飛行時間是不同并且是已知的。飛機連續執行兩個航段任務間的最小周轉時間設置為35分鐘，飛機定檢維修時間設置為8小時。求解器Cplex的求解時間設置為3 600秒。CA算法終止條件為：最優解在100次溫度變化內沒有改變則終止算法。另外，0是AMRP模型的最優解，所以，當前最優解解為0時同樣終止算法。

3.2實驗結果分析

表2展示了第1組實驗的結果，其中CA算法的平均最優值和平均求解時間為獨立運行10次后的取值。表3展示了第2組實驗的結果，由于規模較大，Cplex無法在表3時間內給出問題的可行解，所有表3僅展示了CA算法的結果。從第1組實驗結果可以看出，除了Case3、Case6、Case8以外，CA算法求得的平均最優值與Cplex求得的一致，對于其他Case，CA算法的平均最優值與Cplex求得的精確最優解也非常接近，算法穩定性較好。整體的平均最優值與Cplex 僅相差 2.18% 。從求解時間上來看，CA算法可以在 20秒內給出一個非常接近精確最優解的值。從第二組實驗結果可以看出，CA算法的整體平均值和整體平均求解時間分別為47.35s和 26.25s ，可以在短時間內給出較為滿意的解。

4結論與展望

本文以最優化飛機定檢維修前的使用效率為目標建立AMRP模型，根據飛機距離下次定檢維修前的剩余參數為其分配最優的航班任務從而提高飛機的使用效率，降低飛機維修成本。利用求解器、CA算法求解模型，算法對比結果表明，CA算法可以有效的求解AMRP模型，可以在更短時間內給出更為滿意的解。

對于未來的研究方向，一方面，航班延誤等因素也會影響飛機維修路徑規劃，所以未來研究重點之一是增強飛機維修路徑的魯棒性以應對不確定因素產生的影響。另一方面，其他的運營調度問題（如機型分配、機組分配等）影響著AMRP的最優性甚至可行性，所以，對于AMRP與其他調度問題的整合研究是未來的研究方向之一。

參考文獻：

[1]FEO TA，BARDJF.Flight schedulingandmaintenancebase planning[J].Management Science，1989，35（12）：1415-432.

[2]SRIRAMC，HAGHANIA.Anoptimizationmodelforaircraftmaintenanceschedulingandre-asignment[J].Transportation Research Part A， 2003，37（1）：29-48.

[3]TALLURI K T.The four-dayaireraft maintenance routing problem[J].Transportation Science，1998，32（1）：43-53.

[4] CLARKEL，JOHNSON E，NEMHAUSER G，et al. The aircraft rotation problem[J].Annals OR，1997，69：33-46.

[5]BARNHARTC，BOLANDNL，LLOYDW，etal.Flightstringmodelsforaireraftfletingandrouting[J].TransportationScience，1998，32（3）：208-220.

[6]LIANG Z，CHAOVALITWONGSEWA，HUANG H C，etal.Onanew rotational tour network model foraireraft maintenance routing problem[J]. Operations Research： Management Science， 2012，52（5/6）：485-486.

[7]BASDEREM，BILGEU.Operationalaircraftmaintenanceroutingproblemwithremainingtimeconsideration[J].Operations Research： Management science， 2015，55（5/6）：315-328.

[8]ELTOUKHY ABDELRAHMAN EE，CHAN FELIX T S，CHUNG SH，etal.Heuristicaproaches foroperationalaircraft maintenanceroutingproblemwithmaximumflying hoursandman-poweravailabilityconsiderations[J].IndustrialManagement amp;Data Systems，2017，117（10）：2142-2170.

[9]RUANJH，WANG ZX，CHANFELIX TS，etal.Areinforcementlearning-basedalgorithmfortheaireraftmaintenance routing problem[J]. Expert Systems With Applications，2021，169：114399.

[10]ESMAEILZADEH H，RASHIDI K A，KAZEMIPOOR H，et al.A bi-objective aircraft maintenancerouting problembasedon flying hours toeffcient useof available fleet[J]. Journal of Facilities Management，2O24，22（2）：325-344.

[11] 都業富.航班串優化方法[J].系統工程理論與實踐，1995（8）：75-80.

[12] 孫宏，杜文．飛機排班數學規劃模型[J].交通運輸工程學報，2004（3）：117-120.

[13] 肖東喜，朱金福．飛機排班中航班環的動態構建方法[J]：系統工程，2007（11）：19-25.

[14] 李耀華，譚娜，郝貴和.飛機排班航班串編制模型及算法研究[J]．系統仿真學報，2008，160（3）：612-615.

[15] 李耀華，譚娜．基于遺傳算法的飛機一體化排班優化方法[J].控制工程，2017，24（2）：435-440.

[16] 藍伯雄，王童妹．飛機維修短期計劃模型及其算法研究[J].運籌與管理，2016，25（3）：1-10.

[17] 郭潤夏，王一府．以維修間隔利用率最優為目標的飛機派遣方法[J]．系統仿真學報，2023，35（9）：1985-1999.

[18] BULBULKG，REFAILK.Augmentedlagrangianbased hybridsubgradient methodforsolvingaircraftmaintenancerouting problem[J]. Computersamp; Operations Research，2021，132：105294.

[19]OHLMANNJW，THOMASB W.Acompressedannealing heuristicforthetraveling salesmanproblem withtime windows [J].Informs Journal on Computing，2007，19：80-90.