中圖法分類號(hào)：F253.9 文獻(xiàn)標(biāo)志碼：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

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

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

現(xiàn)有AMRP研究大多考慮一種飛機(jī)維修間隔，對(duì)于同時(shí)考慮兩種或以上的研究較少?；诖耍紤]現(xiàn)有研究情況，改進(jìn)原有優(yōu)化模型，并提出了一個(gè)考慮飛機(jī)飛行天數(shù)限制與飛行時(shí)間限制的整數(shù)線性規(guī)劃模型，模型以最小化飛機(jī)維修前的剩余飛行時(shí)間為目標(biāo)，同時(shí)考慮兩種飛機(jī)維修間隔限制，更加貼合實(shí)際情況。為了高效、快速求解問題，本文利用壓縮退火算法求解AMRP。

1問題描述及數(shù)學(xué)模型

1.1問題描述

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

1.2問題建模

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

航段節(jié)點(diǎn)間的可行銜接需滿足地點(diǎn)（前一個(gè)航段的到達(dá)機(jī)場(chǎng)要與后一個(gè)航段的起飛機(jī)場(chǎng)相同）、時(shí)間約束（前一個(gè)航段的到達(dá)時(shí)間與后一個(gè)航段的起飛時(shí)間差應(yīng)滿足飛機(jī)的周轉(zhuǎn)時(shí)間或維修時(shí)間要求）。若一架飛機(jī)在執(zhí)行完某個(gè)航段任務(wù)后需要進(jìn)行維修檢查，則需要滿足以下兩個(gè)條件：（1）飛機(jī)所在機(jī)場(chǎng)是維修機(jī)場(chǎng)，即具有維修能力的機(jī)場(chǎng)；（2）該飛機(jī)執(zhí)行的下一個(gè)航段任務(wù)的起飛時(shí)間與剛執(zhí)行完的航段任務(wù)的降落時(shí)間差應(yīng)大于飛機(jī)維修時(shí)間與該飛機(jī)執(zhí)行下次飛行任務(wù)的準(zhǔn)備時(shí)間之和。

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

基于以上論述，建立了如下AMRP優(yōu)化模型：

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

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

2壓縮退火算法

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

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

初始解通過求解一個(gè)簡(jiǎn)化的模型來獲得，在簡(jiǎn)化的模型中，忽略目標(biāo)函數(shù)以及飛機(jī)飛行天數(shù)和飛行時(shí)間限制，將每架飛機(jī)作為節(jié)點(diǎn)加入連接網(wǎng)絡(luò)中以降低模型復(fù)雜度，達(dá)到快速求得的目的。簡(jiǎn)化的模型如下所示：

minO

在簡(jiǎn)化的模型中，式（16）保證了每個(gè)飛機(jī)節(jié)點(diǎn)連接第一個(gè)執(zhí)行的航段節(jié)點(diǎn)；式（17）保證每個(gè)航段被覆蓋一次；式（18）是航段間銜接約束，保證了路徑的連通；式（19）保證了每條路徑的完整性。

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

3實(shí)驗(yàn)與分析

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

3.1實(shí)驗(yàn)數(shù)據(jù)設(shè)置

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

3.2實(shí)驗(yàn)結(jié)果分析

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

4結(jié)論與展望

本文以最優(yōu)化飛機(jī)定檢維修前的使用效率為目標(biāo)建立AMRP模型，根據(jù)飛機(jī)距離下次定檢維修前的剩余參數(shù)為其分配最優(yōu)的航班任務(wù)從而提高飛機(jī)的使用效率，降低飛機(jī)維修成本。利用求解器、CA算法求解模型，算法對(duì)比結(jié)果表明，CA算法可以有效的求解AMRP模型，可以在更短時(shí)間內(nèi)給出更為滿意的解。

對(duì)于未來的研究方向，一方面，航班延誤等因素也會(huì)影響飛機(jī)維修路徑規(guī)劃，所以未來研究重點(diǎn)之一是增強(qiáng)飛機(jī)維修路徑的魯棒性以應(yīng)對(duì)不確定因素產(chǎn)生的影響。另一方面，其他的運(yùn)營(yíng)調(diào)度問題（如機(jī)型分配、機(jī)組分配等）影響著AMRP的最優(yōu)性甚至可行性，所以，對(duì)于AMRP與其他調(diào)度問題的整合研究是未來的研究方向之一。

參考文獻(xiàn)：

[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] 都業(yè)富.航班串優(yōu)化方法[J].系統(tǒng)工程理論與實(shí)踐，1995（8）：75-80.

[12] 孫宏，杜文．飛機(jī)排班數(shù)學(xué)規(guī)劃模型[J].交通運(yùn)輸工程學(xué)報(bào)，2004（3）：117-120.

[13] 肖東喜，朱金福．飛機(jī)排班中航班環(huán)的動(dòng)態(tài)構(gòu)建方法[J]：系統(tǒng)工程，2007（11）：19-25.

[14] 李耀華，譚娜，郝貴和.飛機(jī)排班航班串編制模型及算法研究[J]．系統(tǒng)仿真學(xué)報(bào)，2008，160（3）：612-615.

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

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

[17] 郭潤(rùn)夏，王一府．以維修間隔利用率最優(yōu)為目標(biāo)的飛機(jī)派遣方法[J]．系統(tǒng)仿真學(xué)報(bào)，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.