民機(jī)機(jī)隊(duì)航班指派與維修調(diào)度聯(lián)合優(yōu)化策略

丁雨童,郭晉之,邢雪琪,鄭美妹,夏唐斌+,奚立峰

(1.上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院,上海 200240;2.中國(guó)商飛上海飛機(jī)客戶服務(wù)公司 運(yùn)行支持技術(shù)研究所,上海 200241)

0 引言

民航工業(yè)的迅速發(fā)展給航司機(jī)隊(duì)維修調(diào)度帶來(lái)了巨大挑戰(zhàn)[1]。作為飛機(jī)適航性保證,維修活動(dòng)要求飛機(jī)在維修基地較長(zhǎng)時(shí)間停場(chǎng)產(chǎn)生的維修機(jī)會(huì)中,執(zhí)行覆蓋飛機(jī)部件循環(huán)往復(fù)維修需求的大量維修任務(wù)。維修成本可達(dá)航司運(yùn)營(yíng)總成本的30%[2-4],因此機(jī)隊(duì)維修調(diào)度需在滿足飛機(jī)適航性的前提下,優(yōu)化機(jī)隊(duì)飛機(jī)各項(xiàng)維修任務(wù)的執(zhí)行時(shí)間與地點(diǎn)方案,以降低維修成本,提升航司收益[5]。

目前,航司維修調(diào)度主要遵循獨(dú)立于飛行路徑規(guī)劃的定檢模式,在最大定檢間隔約束下,自上而下地首先確定各飛機(jī)的定檢日程,然后進(jìn)行定檢中的維修任務(wù)分配[6],現(xiàn)有研究相應(yīng)聚焦于定檢方案的優(yōu)化。首先,定檢日期與地點(diǎn)的決策往往以維修資源可用性與最大維修間隔為依據(jù),在航班運(yùn)營(yíng)規(guī)劃前優(yōu)先確定飛機(jī)在維修基地的停場(chǎng)日程。DENG等[7]考慮機(jī)位與人工時(shí)等資源可用度及航空淡旺季運(yùn)維需求差異,面向機(jī)隊(duì)的單一維修基地定檢日期進(jìn)行決策優(yōu)化。將定檢決策問(wèn)題抽象為馬爾可夫決策過(guò)程,基于動(dòng)態(tài)規(guī)劃方法貫序輸出定檢方案。在此基礎(chǔ)上,文獻(xiàn)[8-9]進(jìn)一步考慮天氣條件、突發(fā)故障等不確定性干擾,建立魯棒優(yōu)化模型,最大限度減少已有定檢方案的變動(dòng)。為解決定檢決策過(guò)程中的維數(shù)災(zāi)難問(wèn)題,ANDRADE等[10]提出一種基于強(qiáng)化學(xué)習(xí)的優(yōu)化框架,在保障飛機(jī)利用率的前提下顯著提升求解速度。在定檢日程決策的基礎(chǔ)上,多屬性、大規(guī)模的機(jī)隊(duì)維修任務(wù)被分配于定檢活動(dòng)中形成最終的維修調(diào)度方案。LI等[11]針對(duì)單架飛機(jī)設(shè)計(jì)了基于屬性相似度權(quán)重的維修任務(wù)聚類(lèi)方法,通過(guò)將相似度高的維修任務(wù)組合執(zhí)行,有效降低定檢規(guī)劃復(fù)雜度。WITTEMAN等[12]基于定檢日程輸入,將機(jī)隊(duì)的維修任務(wù)分配問(wèn)題抽象為裝箱問(wèn)題,并設(shè)計(jì)了基于任務(wù)優(yōu)先級(jí)的啟發(fā)式算法輸出維修任務(wù)分配方案。ZHANG等[13]針對(duì)資源受限且高度不確定維修環(huán)境下的艦載機(jī)隊(duì)維修任務(wù)分配問(wèn)題提出了完全與部分重調(diào)度算法,以提高維修計(jì)劃抗干擾能力。此外,定檢的具體執(zhí)行還需與維修人員、工具、備件等要素匹配[14],QIN等[15]根據(jù)給定維修計(jì)劃進(jìn)行多技能維修人員的調(diào)配優(yōu)化以降低維修成本。

以上文獻(xiàn)針對(duì)定檢維修的關(guān)鍵環(huán)節(jié),考慮維修資源、不確定擾動(dòng)等因素進(jìn)行了較全面的研究。然而,機(jī)隊(duì)維修方案的實(shí)施需要飛行路徑規(guī)劃支撐,使飛機(jī)能夠在維修執(zhí)行日期抵達(dá)預(yù)定維修基地。因此,部分學(xué)者針對(duì)融合預(yù)定定檢方案或間隔約束的機(jī)隊(duì)飛行路徑規(guī)劃與航班指派問(wèn)題進(jìn)行研究[16-17]。LIANG等[18]將定期抵達(dá)維修基地的約束納入機(jī)隊(duì)飛機(jī)飛行路徑規(guī)劃中,獲得滿足適航性的飛行路徑方案。MAHER等[19]針對(duì)短期維修資源不確定情況下的航班指派問(wèn)題,提出一種靈活的前瞻調(diào)度方法,在保障次日維修需求前提下隱式地滿足后續(xù)兩天的維修需要,最大限度降低失修風(fēng)險(xiǎn)。此外,CUI等[20]針對(duì)飛機(jī)延誤概率對(duì)考慮維修約束的飛行路徑影響建立了魯棒優(yōu)化模型,在滿足維修間隔約束前提下降低了飛機(jī)延誤成本。

綜上,定檢模式下機(jī)隊(duì)維修調(diào)度問(wèn)題已得到廣泛研究,但相關(guān)文獻(xiàn)大多局限于維修方案制定的單一環(huán)節(jié),與機(jī)隊(duì)運(yùn)營(yíng)與維修調(diào)度實(shí)踐仍存在差距。首先,飛機(jī)抵達(dá)維修基地僅產(chǎn)生維修機(jī)會(huì),而維修任務(wù)的分配則是維修調(diào)度最終方案[21]。每架飛機(jī)都有大量維修任務(wù),由于維修歷史差異,飛機(jī)個(gè)體維修需求存在較大區(qū)別。機(jī)隊(duì)維修需在飛機(jī)個(gè)體大規(guī)模維修任務(wù)分配層面進(jìn)行調(diào)度,而僅關(guān)注群體普遍定檢間隔的停場(chǎng)決策忽略了飛機(jī)維修個(gè)性化需求。此外,由于維修活動(dòng)只在維修基地進(jìn)行對(duì)航班指派全局規(guī)劃的限制,及飛機(jī)個(gè)體維修方案執(zhí)行對(duì)適航性的影響,局限于單一維修基地的維修任務(wù)分配易導(dǎo)致維修計(jì)劃與航班運(yùn)營(yíng)沖突。航班指派與維修調(diào)度需進(jìn)行協(xié)同規(guī)劃,僅以定檢間隔為約束的飛行路徑難以實(shí)現(xiàn)飛行路徑與維修調(diào)度方案的全局優(yōu)化考慮。最后,維修基地有限的維修資源由多架飛機(jī)共享,維修機(jī)位、人工時(shí)等差異化的資源能否匹配飛機(jī)個(gè)體維修需求,也將很大程度影響維修基地選擇與維修任務(wù)分配決策[22-25]。

規(guī)劃粗放的定檢模式易導(dǎo)致過(guò)度維修、飛機(jī)利用率低、維修與飛行路徑?jīng)_突等問(wèn)題,其經(jīng)濟(jì)性較低[26-27]。因此,國(guó)內(nèi)外航司已開(kāi)始探索利用飛機(jī)日常夜間維修基地停場(chǎng)執(zhí)行維修任務(wù),形成維修任務(wù)日常執(zhí)行(Maintenance Task Daily Execution,MTDE)模式。該模式能夠突破定檢局限,大幅減少飛機(jī)日間維修停場(chǎng)時(shí)間,正逐步應(yīng)用于實(shí)踐,但也為維修調(diào)度優(yōu)化提出更高要求。在上述建模難點(diǎn)的基礎(chǔ)上,航班指派方案不局限于與定檢方案匹配,而需主動(dòng)為每架飛機(jī)提供充足維修機(jī)會(huì),進(jìn)一步提升了問(wèn)題復(fù)雜度。因此,有必要針對(duì)MTDE模式開(kāi)展機(jī)隊(duì)航班指派與維修調(diào)度聯(lián)合優(yōu)化,以彌補(bǔ)定檢模式下維修調(diào)度經(jīng)濟(jì)性的不足。

本研究面向MTDE模式下機(jī)隊(duì)維修調(diào)度的優(yōu)化目標(biāo),綜合考慮飛機(jī)個(gè)體維修任務(wù)層面維修需求和機(jī)隊(duì)整體航班運(yùn)營(yíng)與維修資源共享約束,圍繞聯(lián)合調(diào)度方案經(jīng)濟(jì)性提升,提出一種新的航班指派與維修調(diào)度聯(lián)合優(yōu)化策略(Collaborative Optimization Policy of Tail Assignment and Maintenance Scheduling,COPTAMS)。為應(yīng)對(duì)耦合飛行路徑與維修方案建模難點(diǎn),借助飛行路徑中涵蓋的維修機(jī)會(huì)的交互樞紐作用,通過(guò)引入維修機(jī)會(huì)節(jié)點(diǎn)定義,創(chuàng)新改進(jìn)了常用于航班指派問(wèn)題的連接網(wǎng)絡(luò)模型框架以統(tǒng)籌考慮航班分配與維修調(diào)度,并將問(wèn)題抽象為多商品網(wǎng)絡(luò)流問(wèn)題建立了整數(shù)規(guī)劃模型。針對(duì)大規(guī)模模型的求解困難,將問(wèn)題進(jìn)行分解并建立了高效的兩階段求解方法,基于滿足運(yùn)營(yíng)約束且提供充足維修機(jī)會(huì)的航班指派方案生成,依據(jù)維修任務(wù)剩余可用間隔對(duì)維修任務(wù)在維修機(jī)會(huì)中進(jìn)行合理分配,相較航司人工排程現(xiàn)狀,在較短時(shí)間內(nèi)獲得經(jīng)濟(jì)性顯著提升的航班指派與維修調(diào)度方案。COPTAMS能夠改善航班運(yùn)營(yíng)與維修計(jì)劃的脫節(jié),支持航司在MTDE模式的調(diào)度實(shí)踐,有效降低機(jī)隊(duì)運(yùn)維成本。

1 問(wèn)題描述

本文面向一支執(zhí)飛國(guó)內(nèi)航線的機(jī)隊(duì),開(kāi)展航班指派與維修調(diào)度的聯(lián)合優(yōu)化,該機(jī)隊(duì)事先將被分配規(guī)劃期內(nèi)需執(zhí)飛的日間航班任務(wù)。航班運(yùn)營(yíng)保證所有航班均指派給機(jī)隊(duì)中的飛機(jī),且同一飛機(jī)連續(xù)執(zhí)飛的航班序列滿足時(shí)間與路徑的連續(xù)性。由于機(jī)齡、燃油消耗等運(yùn)行特征的差異,同一航班指派給不同飛機(jī)的成本有所區(qū)別。飛機(jī)需通過(guò)執(zhí)行大量維修任務(wù)確保適航性要求。各項(xiàng)任務(wù)在相應(yīng)維修間隔約束下循環(huán)往復(fù)執(zhí)行,每次執(zhí)行將會(huì)消耗對(duì)應(yīng)維修成本。飛機(jī)維修活動(dòng)受限于飛行路徑規(guī)劃,只有在飛機(jī)抵達(dá)維修基地停場(chǎng)產(chǎn)生的維修機(jī)會(huì)中,維修任務(wù)才得以在基地資源承載能力內(nèi)進(jìn)行分配。故機(jī)隊(duì)航班指派與維修調(diào)度聯(lián)合優(yōu)化方案需在滿足航班全覆蓋與執(zhí)飛連續(xù)性的運(yùn)營(yíng)約束、飛機(jī)適航性要求與維修資源承載限制的維修約束前提下,為每架飛機(jī)指派航班任務(wù),并提供機(jī)隊(duì)所有維修任務(wù)在維修基地的分配執(zhí)行計(jì)劃。本文主要符號(hào)說(shuō)明如表1所示。

表1 主要符號(hào)說(shuō)明表

傳統(tǒng)定檢維修模式規(guī)劃復(fù)雜度低,但整體方案經(jīng)濟(jì)性較差。首先,飛機(jī)長(zhǎng)時(shí)間日間停場(chǎng)維修需支付場(chǎng)地費(fèi)用且無(wú)法執(zhí)飛航班,飛機(jī)利用率及運(yùn)營(yíng)收益由此下降;而維修任務(wù)只能局限分配到固定的定檢日程中,易導(dǎo)致維修任務(wù)過(guò)度提前執(zhí)行,增加長(zhǎng)期維修成本;同時(shí),定檢方案制定獨(dú)立于飛機(jī)路徑,易導(dǎo)致航班指派與維修調(diào)度沖突,出現(xiàn)成本高昂的航班取消或空載飛行狀況。而MTDE模式的應(yīng)用能夠改善定檢模式的不足,通過(guò)航班指派方案為飛機(jī)提供日常夜間停場(chǎng)的維修機(jī)會(huì),維修任務(wù)分配靈活且飛機(jī)利用率顯著提升。

COPTAMS旨在優(yōu)化MTDE模式下聯(lián)合調(diào)度方案的經(jīng)濟(jì)性指標(biāo),包括航班指派成本與維修成本。航班指派成本即所有航班由相應(yīng)飛機(jī)執(zhí)飛的成本之和。為對(duì)維修方案經(jīng)濟(jì)性進(jìn)行長(zhǎng)遠(yuǎn)考量,維修成本包括維修提前成本與維修額外執(zhí)行成本。規(guī)劃期內(nèi)維修任務(wù)實(shí)際執(zhí)行總成本為所有任務(wù)各自執(zhí)行次數(shù)與對(duì)應(yīng)成本乘積的總和,從長(zhǎng)遠(yuǎn)看,經(jīng)濟(jì)性較高的維修方案應(yīng)在適航性要求下,盡量減少過(guò)度提前維修。不同維修任務(wù)分配方案可能對(duì)應(yīng)相同執(zhí)行次數(shù),因此應(yīng)用維修提前成本dc將維修提前程度納入優(yōu)化模型中。對(duì)于飛機(jī)a的維修任務(wù)m,其實(shí)際執(zhí)行日期越接近下一執(zhí)行期限,維修提前程度越低,在第d(d∈D)天執(zhí)行對(duì)應(yīng)的維修提前成本dcamd計(jì)算如下:

(1)

而當(dāng)維修任務(wù)已達(dá)執(zhí)行期限且基地剩余人工時(shí)無(wú)法滿足其執(zhí)行需求時(shí),需通過(guò)維修資源與人員調(diào)配付出額外成本執(zhí)行任務(wù)以保證適航性。

2 改進(jìn)連接網(wǎng)絡(luò)模型框架及聯(lián)合優(yōu)化模型建立

2.1 改進(jìn)連接網(wǎng)絡(luò)模型

航班指派與維修調(diào)度聯(lián)合優(yōu)化的關(guān)鍵在于突破協(xié)同考慮飛行路徑與維修調(diào)度障礙并進(jìn)行統(tǒng)籌規(guī)劃。由于維修任務(wù)僅能在維修基地執(zhí)行,飛行路徑中涵蓋的維修機(jī)會(huì)即成為了二者間交互樞紐。本節(jié)通過(guò)引入維修機(jī)會(huì)節(jié)點(diǎn),創(chuàng)新改進(jìn)了常用于航班指派問(wèn)題的連接網(wǎng)絡(luò)(Connection Network,CN)模型框架,實(shí)現(xiàn)了航班指派與維修調(diào)度在同一框架中的統(tǒng)籌規(guī)劃。

CN框架是由航班節(jié)點(diǎn)V與連接弧E構(gòu)成的有向網(wǎng)絡(luò)G(E,V)。航班節(jié)點(diǎn)代表待執(zhí)飛的航班任務(wù),其節(jié)點(diǎn)屬性包括航班的起落時(shí)間、起落機(jī)場(chǎng);節(jié)點(diǎn)間的連接弧則代表兩個(gè)航班能否由同一飛機(jī)連續(xù)執(zhí)飛的判斷:假設(shè)航班節(jié)點(diǎn)i,j被一條弧連接且弧由i指向j,則航班i,j必須滿足:航班i的降落機(jī)場(chǎng)與航班j的起飛機(jī)場(chǎng)相同,航班i的降落時(shí)間早于航班j的起飛時(shí)間且二者之間留有基本航前準(zhǔn)備時(shí)間。此外,網(wǎng)絡(luò)中還包括源(Source)和匯(Sink)兩個(gè)虛擬節(jié)點(diǎn),表示所有飛機(jī)的起點(diǎn)和終點(diǎn)?；贑N框架,航班指派方案將CN中所有航班節(jié)點(diǎn)分配給各架飛機(jī),每架飛機(jī)分配的節(jié)點(diǎn)由弧順序連接,形成由源到匯的可行路徑。相較航班指派問(wèn)題其他模型框架,CN以較少元素進(jìn)行問(wèn)題完整表示,進(jìn)而減小問(wèn)題規(guī)模,因此采用CN作為模型構(gòu)建的基礎(chǔ)框架。

然而,CN框架僅含航班元素,在指派航班時(shí)忽略了適航性要求,故需要對(duì)CN進(jìn)行調(diào)整?；贑N框架應(yīng)用于航班指派的思想,通過(guò)在網(wǎng)絡(luò)結(jié)構(gòu)中將維修活動(dòng)納入考慮,即可實(shí)現(xiàn)機(jī)隊(duì)的航班指派與維修調(diào)度的聯(lián)合規(guī)劃。根據(jù)飛機(jī)的維修活動(dòng)僅能在維修基地進(jìn)行的約束,飛機(jī)在執(zhí)飛目的機(jī)場(chǎng)為維修基地的航班后,便擁有能夠在當(dāng)前維修基地進(jìn)行當(dāng)日過(guò)夜維修決策的機(jī)會(huì),即維修機(jī)會(huì)。將飛機(jī)各個(gè)維修任務(wù)在維修機(jī)會(huì)是否執(zhí)行進(jìn)行決策,即可形成最終的維修調(diào)度方案。因此,維修機(jī)會(huì)作為飛行路徑與維修方案的關(guān)鍵交互樞紐,本文將其抽象為維修機(jī)會(huì)節(jié)點(diǎn)并納入CN網(wǎng)絡(luò)結(jié)構(gòu)中,形成了改進(jìn)連接網(wǎng)絡(luò)(Modified Connection Network,MCN)模型。一個(gè)維修機(jī)會(huì)節(jié)點(diǎn)表示一個(gè)維修基地在當(dāng)天夜晚為各飛機(jī)提供的過(guò)夜維修機(jī)會(huì),其屬性包括所在機(jī)場(chǎng)、維修起止時(shí)間、維修機(jī)位數(shù)、可用人工時(shí)。類(lèi)似地,其與航班節(jié)點(diǎn)的連接代表二者能否由同一飛機(jī)連續(xù)執(zhí)行的判斷:若航班節(jié)點(diǎn)i與維修機(jī)會(huì)節(jié)點(diǎn)j連接且由i指向j,則i,j應(yīng)滿足:i的降落機(jī)場(chǎng)與j所在的機(jī)場(chǎng)相同,且i的降落時(shí)間不晚于j的維修開(kāi)始時(shí)間;若由j指向i,則i的起飛機(jī)場(chǎng)與j所在的機(jī)場(chǎng)相同,且i的起飛時(shí)間不早于j的維修終止時(shí)間。

下面通過(guò)示例展示CN與MCN的應(yīng)用及區(qū)別?？紤]表2航班時(shí)間表及維修機(jī)會(huì)信息,涉及兩天往返A(chǔ)、B兩機(jī)場(chǎng)的航班,B為維修基地。其中:a+,a-,a分別為航班起降機(jī)場(chǎng)、維修機(jī)會(huì)所在機(jī)場(chǎng),t+,t-分別為航班起飛或維修開(kāi)始時(shí)間、航班降落或維修結(jié)束時(shí)間,D1,D2分別表示第一、二天,航前準(zhǔn)備時(shí)間為30 min。

表2 航班時(shí)間表與維修機(jī)會(huì)信息示例

圖1 CN與MCN框架示例

2.2 整數(shù)規(guī)劃模型建立

基于MCN框架,建立COPTAMS整數(shù)規(guī)劃模型如下:

(2)

(3)

?j∈N/{sink,source};

(4)

i=source,i′=sink;

(5)

(6)

(7)

(8)

?a∈A,?i∈N,?j∈B;

(9)

?a∈A,?m∈M,?d∈D;

(10)

xaij∈{0,1},?a∈A,?i,j∈N;

(11)

yami∈{0,1},

?a∈A,?i∈B,?m∈M。

(12)

該模型的決策變量包括xaij與yami,輔助變量包括eamd及dcamd,其余均為模型的輸入?yún)?shù)。目標(biāo)函數(shù)(2)表示最小化聯(lián)合調(diào)度方案的經(jīng)濟(jì)性指標(biāo)。約束(3)為航班覆蓋約束,即每個(gè)航班均需指派給機(jī)隊(duì)中的一架飛機(jī)。約束(4)～約束(6)為MCN網(wǎng)絡(luò)流平衡約束,其中約束(4)表示網(wǎng)絡(luò)中除源和匯所有節(jié)點(diǎn)的出入流量相等;約束(5)表示離開(kāi)源與進(jìn)入?yún)R的流量相等;約束(6)表示每架飛機(jī)須從源節(jié)點(diǎn)出發(fā),且各飛機(jī)首個(gè)執(zhí)飛航班從其初始機(jī)場(chǎng)起飛。約束(7)～約束(10)為維修調(diào)度約束,其中約束(7)與約束(8)表示維修機(jī)位與可用人工時(shí)限制;約束(9)表示維修任務(wù)只能在飛機(jī)到達(dá)維修機(jī)會(huì)節(jié)點(diǎn)時(shí)進(jìn)行;約束(10)定義中間變量eamd。約束(11)與約束(12)為決策變量取值范圍。通過(guò)在小規(guī)模問(wèn)題上的精確求解,驗(yàn)證了模型的有效性與可靠性。

3 聯(lián)合調(diào)度方案兩階段求解方法

2.2節(jié)建立了機(jī)隊(duì)航班指派與維修調(diào)度的聯(lián)合優(yōu)化模型,而由于模型同時(shí)涵蓋航班指派與維修任務(wù)執(zhí)行決策變量,模型規(guī)模過(guò)大,直接使用Gurobi等商業(yè)求解器耗時(shí)過(guò)長(zhǎng),難以滿足實(shí)踐需求。為在可接受時(shí)間內(nèi)得到質(zhì)量較高的調(diào)度方案,本節(jié)基于對(duì)原問(wèn)題的分解,設(shè)計(jì)了COPTAMS兩階段求解方法,具體如下。

3.1 階段一:維修機(jī)會(huì)導(dǎo)向的航班指派優(yōu)化

借助維修機(jī)會(huì)在航班指派與維修調(diào)度的交互樞紐作用,首先考慮飛機(jī)個(gè)體維修需求,生成滿足運(yùn)營(yíng)約束且包含充足維修機(jī)會(huì)的航班指派方案,以進(jìn)行后續(xù)維修任務(wù)層面分配。為此,第一階段求解建立維修機(jī)會(huì)導(dǎo)向的航班指派優(yōu)化模型如下。

(13)

s.t.

式(3)～式(7),

?k∈K,?d∈D;

(14)

xaij∈{0,1},?a∈A,?i,j∈N。

(15)

該模型的決策變量為xaij,不包含輔助變量,其余均為模型的輸入?yún)?shù)。航班指派成本(13)為優(yōu)化目標(biāo),航班運(yùn)營(yíng)、網(wǎng)絡(luò)流平衡、維修機(jī)位約束(3)～約束(7)得到保留,其余維修約束被調(diào)整為維修機(jī)會(huì)分配需求約束(14):對(duì)于任一飛機(jī)任一類(lèi)型的維修任務(wù),將該類(lèi)任務(wù)維修間隔最小值設(shè)為時(shí)間窗長(zhǎng)度,飛機(jī)須在時(shí)間窗內(nèi)至少一次經(jīng)過(guò)具備該類(lèi)任務(wù)維修能力的維修基地,通過(guò)時(shí)間窗在規(guī)劃期內(nèi)的滾動(dòng),保證了飛機(jī)個(gè)體維修任務(wù)要求,航班指派方案能使其擁有對(duì)應(yīng)維修能力的充足維修機(jī)會(huì)。約束(15)為決策變量取值范圍。該模型僅包括節(jié)點(diǎn)分配(包括航班與維修機(jī)會(huì)節(jié)點(diǎn))決策變量xaij,在模型簡(jiǎn)化基礎(chǔ)上保證了基本維修需求,求解速度顯著提升。

3.2 階段二:維修任務(wù)分配高效啟發(fā)式算法

基于第一階段的航班指派與維修機(jī)會(huì)方案,第二階段綜合考慮飛機(jī)個(gè)體維修任務(wù)執(zhí)行狀態(tài)與維修資源共享機(jī)制,將維修任務(wù)在各維修機(jī)會(huì)進(jìn)行擇優(yōu)分配與狀態(tài)更新交互,求解經(jīng)濟(jì)性較優(yōu)的維修調(diào)度方案。

首先,滿足維修間隔且維修提前成本最低的方案應(yīng)將維修任務(wù)在其期限日期執(zhí)行。由于維修機(jī)會(huì)日期、維修資源限制,維修任務(wù)大多無(wú)法恰好分配在期限日期,而使任務(wù)分配盡可能接近期限日期則能降低維修提前成本。因此,在每個(gè)維修機(jī)會(huì),通過(guò)判斷各維修任務(wù)的剩余可用間隔,其中在當(dāng)前維修機(jī)會(huì)已到期、即將在下一維修機(jī)會(huì)前到期的維修任務(wù)優(yōu)先執(zhí)行,若人工時(shí)消耗完畢則調(diào)配額外維修資源;對(duì)于剩余維修任務(wù),計(jì)算其剩余可用間隔并據(jù)此由小到大排序,設(shè)置剩余間隔閾值,大于該閾值的任務(wù)無(wú)需在當(dāng)前維修機(jī)會(huì)過(guò)早執(zhí)行,將其從備選執(zhí)行序列中剔除;若維修基地仍有可用人工時(shí),則順次執(zhí)行排序后的維修任務(wù),直至人工時(shí)使用完畢。隨后更新各任務(wù)執(zhí)行狀態(tài),計(jì)算下一執(zhí)行期限,在后續(xù)維修機(jī)會(huì)重復(fù)上述判斷步驟直至規(guī)劃期結(jié)束。上述方法的機(jī)理保證了飛機(jī)適航性要求,同時(shí)任務(wù)剩余間隔得到了充分利用,緩解了過(guò)度維修,有效降低長(zhǎng)期維修成本。

3.3 算法評(píng)價(jià)

第一階段應(yīng)用Gurobi求解器進(jìn)行成本最優(yōu)的航班指派方案精確求解,因此針對(duì)本階段的算法評(píng)價(jià)以模型規(guī)模為標(biāo)準(zhǔn)。由于模型規(guī)模可以由決策變量與約束的數(shù)目衡量[28],相較于2.2節(jié)建立的機(jī)隊(duì)航班指派與維修調(diào)度的聯(lián)合優(yōu)化模型(決策變量數(shù)目為|A|×CO+|A|×|M|×|B|,約束數(shù)目為|F|+|A|×[|N|×(1+|B|)+|M|×|D|+1]+|B|×(|K|+1)),該模型僅包括節(jié)點(diǎn)分配(包括航班與維修機(jī)會(huì)節(jié)點(diǎn))決策變量xaij(數(shù)目為|A|×CO),且約束數(shù)目減少為|F|+|A|×(|N|+|K|×|D|+1)+|B|。由于機(jī)隊(duì)飛機(jī)數(shù)目|A|較少發(fā)生變動(dòng),機(jī)隊(duì)航班指派與維修調(diào)度聯(lián)合優(yōu)化的問(wèn)題規(guī)模變化主要來(lái)自于規(guī)劃期時(shí)長(zhǎng)|D|、航班任務(wù)數(shù)|F|及維修任務(wù)數(shù)|M|。而在維修實(shí)踐中,每架飛機(jī)維修任務(wù)可達(dá)百余項(xiàng),對(duì)于問(wèn)題規(guī)模影響最為顯著。本階段模型保留的決策變量xaij數(shù)目遠(yuǎn)小于yami數(shù)目,同時(shí)維修相關(guān)約束數(shù)量大幅降低,因此在處理大規(guī)模問(wèn)題時(shí)將不受維修任務(wù)數(shù)目增長(zhǎng)影響,實(shí)現(xiàn)成本最優(yōu)的航班指派方案快速生成。

在第二階段,算法執(zhí)行時(shí)間僅隨著輸入的總維修任務(wù)數(shù)與規(guī)劃期天數(shù)變化而線性變化,其時(shí)間復(fù)雜度可表示為O(n)。機(jī)隊(duì)維修調(diào)度問(wèn)題本身具有大規(guī)模特性,而本階段所提方法即使面對(duì)規(guī)劃期長(zhǎng)、機(jī)隊(duì)規(guī)模大、維修任務(wù)數(shù)量多的維修任務(wù)分配問(wèn)題,也能夠?qū)崿F(xiàn)較快的求解速度,滿足機(jī)隊(duì)維修調(diào)度實(shí)踐需求。

3.4 航班指派與維修調(diào)度聯(lián)合優(yōu)化求解步驟

綜合上述求解過(guò)程,COPTAMS求解步驟如下所示:

步驟1獲取航班時(shí)間表、維修基地信息、機(jī)隊(duì)維修任務(wù)、飛機(jī)初始位置等參數(shù),構(gòu)建MCN框架,建立維修機(jī)會(huì)導(dǎo)向的航班指派優(yōu)化模型。

步驟2對(duì)模型精確求解,得到規(guī)劃期內(nèi)機(jī)隊(duì)航班指派方案及維修機(jī)會(huì),即各飛機(jī)在MCN中的節(jié)點(diǎn)路徑。

步驟3從規(guī)劃期第一天開(kāi)始,尋找當(dāng)日MCN中飛機(jī)經(jīng)過(guò)的維修機(jī)會(huì)節(jié)點(diǎn)。若當(dāng)日所有維修機(jī)會(huì)節(jié)點(diǎn)均無(wú)飛機(jī)經(jīng)過(guò),則直接進(jìn)入次日繼續(xù)尋找。

步驟4從當(dāng)日首個(gè)維修機(jī)會(huì)節(jié)點(diǎn)開(kāi)始,獲取抵達(dá)該節(jié)點(diǎn)飛機(jī)的維修任務(wù)信息,計(jì)算各任務(wù)剩余可用間隔及執(zhí)行期限,按剩余可用間隔由少到多順序排列。進(jìn)一步獲取該節(jié)點(diǎn)各飛機(jī)下一維修機(jī)會(huì)節(jié)點(diǎn)日期,判斷各項(xiàng)任務(wù)執(zhí)行期限是否在規(guī)劃期內(nèi),若不在規(guī)劃期內(nèi)則停止對(duì)該任務(wù)的決策;若在規(guī)劃期內(nèi)且早于所屬飛機(jī)的下一維修機(jī)會(huì)節(jié)點(diǎn)日期,則將該任務(wù)于當(dāng)前維修機(jī)會(huì)節(jié)點(diǎn)執(zhí)行,消耗相應(yīng)人工時(shí)。

步驟5根據(jù)剩余間隔閾值進(jìn)行任務(wù)剔除,對(duì)剔除并排序后的任務(wù),從首個(gè)任務(wù)開(kāi)始,判斷當(dāng)前維修機(jī)會(huì)節(jié)點(diǎn)的剩余可用人工時(shí)能否執(zhí)行此任務(wù)。若是,則安排該任務(wù)在當(dāng)前維修節(jié)點(diǎn)執(zhí)行;否則不執(zhí)行該任務(wù),進(jìn)行下一任務(wù)的判斷,直至所有任務(wù)判斷完畢;轉(zhuǎn)步驟4進(jìn)行下一維修節(jié)點(diǎn)的任務(wù)分配決策過(guò)程,直至當(dāng)日所有維修節(jié)點(diǎn)決策完畢。

步驟6獲取當(dāng)日所有執(zhí)行的維修任務(wù)進(jìn)行狀態(tài)更新,轉(zhuǎn)步驟3搜索次日維修機(jī)會(huì)節(jié)點(diǎn),直至規(guī)劃期內(nèi)所有維修節(jié)點(diǎn)搜索完畢。COPTAMS求解步驟示意如圖2所示。

圖2 COPTAMS示意圖

4 實(shí)例分析

為驗(yàn)證本研究提出的COPTAMS方法,選取一組國(guó)內(nèi)某航司10架客機(jī)組成的機(jī)隊(duì)實(shí)例進(jìn)行分析,各實(shí)例信息及成本相關(guān)參數(shù)如表3和表4所示。各實(shí)例在問(wèn)題規(guī)模、航班任務(wù)、維修起始狀態(tài)、規(guī)劃時(shí)長(zhǎng)、維修基地方面均有所差異,全面驗(yàn)證優(yōu)化方法應(yīng)用性能。本章所有實(shí)例分析計(jì)算均使用MATLAB R2020b以及Gurobi 9.1.2進(jìn)行,PC處理器為Intel(R) Core(TM) i7-10510U CPU @ 1.80 GHz,內(nèi)存大小為4 GB。

表3 機(jī)隊(duì)運(yùn)營(yíng)實(shí)例信息

表4 成本相關(guān)參數(shù)設(shè)置

表5 實(shí)例求解結(jié)果

由表5可知,大部分實(shí)例求解時(shí)間均值與極大值均在10 min內(nèi),實(shí)例3、12的航班任務(wù)與維修基地?cái)?shù)據(jù)較復(fù)雜,但仍可在30 min內(nèi)生成聯(lián)合調(diào)度方案。而與本研究合作的航司維修調(diào)度部門(mén)目前仍采用人工定檢排程的方式,進(jìn)行相同規(guī)模機(jī)隊(duì)15天內(nèi)航班指派與維修任務(wù)規(guī)劃耗時(shí)約2 h,而若規(guī)劃時(shí)長(zhǎng)進(jìn)一步擴(kuò)大至30天需耗費(fèi)超過(guò)3 h。此外,為驗(yàn)證本研究所提維修任務(wù)分配方法的競(jìng)爭(zhēng)性,基于階段一的最優(yōu)節(jié)點(diǎn)分配方案,選取文獻(xiàn)[12]中提出的相關(guān)算法進(jìn)行效果比較如表6所示。該文獻(xiàn)研究機(jī)隊(duì)在單一維修基地、固定維修間隔下的維修任務(wù)分配問(wèn)題,依據(jù)裝箱問(wèn)題基礎(chǔ)求解思想“worst-fit”,僅據(jù)任務(wù)間隔計(jì)算各任務(wù)分配優(yōu)先級(jí),構(gòu)建啟發(fā)式求解算法進(jìn)行維修任務(wù)在維修活動(dòng)中的分配。在聯(lián)合優(yōu)化場(chǎng)景下,本研究中維修任務(wù)分配方法能夠全面考慮后續(xù)維修機(jī)會(huì)間隔靈活變動(dòng)及任務(wù)執(zhí)行狀態(tài)更新,具有更優(yōu)的維修經(jīng)濟(jì)性表現(xiàn)。故COPTAMS方法可高效得到機(jī)隊(duì)飛機(jī)的航班與維修計(jì)劃,滿足機(jī)隊(duì)調(diào)度需求。

表6 維修任務(wù)分配算法成本對(duì)比

而為驗(yàn)證MTDE模式相較傳統(tǒng)定檢模式的經(jīng)濟(jì)性優(yōu)勢(shì),將定檢模式的航班指派與維修調(diào)度同樣應(yīng)用于本章的實(shí)例進(jìn)行總成本對(duì)比。在定檢模式下,機(jī)隊(duì)各架飛機(jī)每間隔vkmin天需要抵達(dá)具有k類(lèi)維修任務(wù)能力的維修基地進(jìn)行日間停場(chǎng)維修。根據(jù)航司實(shí)際情況,運(yùn)營(yíng)人需為日間停場(chǎng)支付停場(chǎng)費(fèi)用以及飛機(jī)利用率降低的懲罰成本。每次定檢執(zhí)行維修任務(wù)決策依據(jù)僅為維修間隔要求,即下次定檢之前到期的維修任務(wù)均在當(dāng)前定檢執(zhí)行,其他任務(wù)則不執(zhí)行。各實(shí)例計(jì)算得到的優(yōu)化航班指派成本obj1、維修成本obj2以及維修調(diào)度原因?qū)е潞桨嗳∠臄?shù)量q如表7所示,表中定檢模式下的obj1包括了航班取消的收入損失,obj2包括了日間停場(chǎng)維修場(chǎng)地費(fèi)用。總成本TC柱狀圖如圖3所示。

圖3 兩種維修模式的總成本對(duì)比圖

表7 兩種維修模式的成本對(duì)比

由表7和圖3可知,MTDE模式下航班指派成本、維修調(diào)度相關(guān)成本均優(yōu)于定檢模式:

(1)航班指派方面 定檢模式需要飛機(jī)在指定日期抵達(dá)維修基地的約束破壞了航班指派全局最優(yōu)性,且機(jī)隊(duì)中多架飛機(jī)同時(shí)定檢會(huì)導(dǎo)致部分航班無(wú)法執(zhí)飛而產(chǎn)生高昂的航班取消懲罰成本;MTDE模式避免了飛機(jī)的日間維修停場(chǎng),機(jī)隊(duì)運(yùn)營(yíng)部門(mén)能夠靈活調(diào)配飛機(jī)執(zhí)飛航班,使所有航班均被覆蓋,因此相較定檢模式,在航班指派成本上具有優(yōu)勢(shì),平均節(jié)省2%航班指派成本。

(2)維修調(diào)度方面 固定的定檢日程局限了維修任務(wù)分配方案,且分配決策依據(jù)僅為適航性要求,易導(dǎo)致過(guò)度維修,同時(shí)日間停場(chǎng)也需為占用維修機(jī)位而支出費(fèi)用;而MTDE模式下,綜合考慮飛機(jī)路徑及維修需求能靈活安排維修機(jī)會(huì)以分配維修任務(wù),在保證適航性前提下兼顧維修經(jīng)濟(jì)性指標(biāo),從而得到成本更低的維修調(diào)度方案,同時(shí)避免日間停場(chǎng)費(fèi)用支出,平均節(jié)省51%維修成本。

從總成本的視角看,由于在航班指派與維修調(diào)度進(jìn)行了聯(lián)合優(yōu)化,MTDE模式相較定檢模式平均節(jié)省了11%總成本。綜上,面對(duì)MTDE模式下機(jī)隊(duì)維修調(diào)度優(yōu)化需求,COPTAMS能夠高效輸出航班指派與維修調(diào)度聯(lián)合優(yōu)化方案,幫助航司改善傳統(tǒng)定檢模式運(yùn)營(yíng)與維修計(jì)劃脫節(jié)、調(diào)度效率與靈活性差、飛機(jī)利用率低、停場(chǎng)時(shí)間長(zhǎng)等難題,顯著提升經(jīng)濟(jì)性指標(biāo)。

5 結(jié)束語(yǔ)

本研究面向MTDE模式下機(jī)隊(duì)維修調(diào)度經(jīng)濟(jì)性優(yōu)化需求,綜合考慮維修任務(wù)層面的飛機(jī)個(gè)體維修需要及機(jī)隊(duì)整體航班運(yùn)營(yíng)與維修資源分配,提出了機(jī)隊(duì)航班指派與維修調(diào)度聯(lián)合優(yōu)化方法。通過(guò)引入維修機(jī)會(huì)創(chuàng)新提出MCN框架以進(jìn)行統(tǒng)籌規(guī)劃,以聯(lián)合優(yōu)化方案經(jīng)濟(jì)性指標(biāo)為優(yōu)化目標(biāo),全面考慮航班覆蓋、執(zhí)飛連續(xù)性、飛機(jī)適航性、維修資源限制、網(wǎng)絡(luò)流平衡等約束,建立了問(wèn)題的整數(shù)規(guī)劃模型。首先通過(guò)維修機(jī)會(huì)導(dǎo)向的航班指派優(yōu)化,在保證飛機(jī)充足維修機(jī)會(huì)的前提下得到航班指派成本最優(yōu)的節(jié)點(diǎn)分配方案;隨后構(gòu)建維修任務(wù)分配啟發(fā)式算法,通過(guò)對(duì)任務(wù)剩余可用間隔的排序篩選進(jìn)行任務(wù)擇優(yōu)分配,在保證飛機(jī)適航性前提下有效降低長(zhǎng)期維修成本。

航司機(jī)隊(duì)實(shí)例分析結(jié)果驗(yàn)證了COPTAMS方法能夠高效得到總成本優(yōu)化的調(diào)度方案,幫助解決航司人工進(jìn)行定檢調(diào)度效率與經(jīng)濟(jì)性不足的難題。未來(lái)工作可將更復(fù)雜的機(jī)隊(duì)運(yùn)營(yíng)與維修場(chǎng)景納入優(yōu)化框架中,如跨日長(zhǎng)途航班指派、飛機(jī)長(zhǎng)期入庫(kù)拆解大修需求、維修基地人工時(shí)資源變動(dòng)等。