基于啟發(fā)式算法的飛機(jī)指派優(yōu)化模型及算法

劉　婧,　賈寶惠

(1.新疆大學(xué) 電氣工程學(xué)院,新疆 烏魯木齊　830047;2.中國民航大學(xué) 航空工程學(xué)院,天津　300300)

?

基于啟發(fā)式算法的飛機(jī)指派優(yōu)化模型及算法

劉婧1,賈寶惠2

(1.新疆大學(xué) 電氣工程學(xué)院,新疆 烏魯木齊830047;2.中國民航大學(xué) 航空工程學(xué)院,天津300300)

摘要：安全與經(jīng)濟(jì)是航空公司運(yùn)營中互相矛盾的兩個(gè)因素,安全性提高必然導(dǎo)致運(yùn)行成本的增加。首先,綜合考慮飛機(jī)航班任務(wù)與例行檢修任務(wù),建立了飛機(jī)指派優(yōu)化模型,使飛機(jī)的飛行時(shí)間盡可能接近飛機(jī)的期望飛行時(shí)間;其次,為了求解該模型,設(shè)計(jì)了基于專家規(guī)則的啟發(fā)式算法,快速實(shí)現(xiàn)了多任務(wù)分配的優(yōu)化飛機(jī)指派計(jì)劃;最后,采用某航空公司的實(shí)際航班數(shù)據(jù),進(jìn)行了算例分析,并與采用蟻群算法進(jìn)行優(yōu)化的結(jié)果進(jìn)行了比較,說明了該模型和算法的合理性。

關(guān)鍵詞：飛機(jī)排班; 優(yōu)化模型; 例行檢修; 啟發(fā)式算法

1引言

飛機(jī)排班是航班計(jì)劃中的一部分,它需要根據(jù)航班計(jì)劃要求、飛機(jī)機(jī)型特征與技術(shù)狀態(tài)等因素為每一架飛機(jī)分配每天的航班飛行任務(wù)和必要的檢修任務(wù),從而保證航班任務(wù)順利進(jìn)行。因此,如何高效并合理的制定飛行計(jì)劃,提高飛機(jī)利用率和利潤是航空公司在競(jìng)爭中取勝的重要因素。

國內(nèi)外很多學(xué)者在這方面做了大量的研究工作。Rexing[1]等提出了“時(shí)間窗”的概念,建立了機(jī)型指派和航班時(shí)刻的綜合模型;Rosenberger[2]與Sriram[3]等人分別研究了動(dòng)態(tài)的機(jī)型指派問題以及不正常航班下飛機(jī)計(jì)劃恢復(fù)中的機(jī)型調(diào)整問題等。Erling與Gronkvist[4]等建立飛機(jī)指派約束編程(Constraint Programming)模型,并提出了列生成等算法;朱星輝[5]等人對(duì)周機(jī)型指派問題的研究;孫宏、杜文[6]等學(xué)者將飛機(jī)指派問題劃分為三個(gè)方面,即基于飛機(jī)調(diào)度指令要求、基于最少需用飛機(jī)數(shù)、基于飛機(jī)使用均衡要求的飛機(jī)排班問題及求解算法;李耀華[7]等主要考慮航站銜接及過站時(shí)間銜接的約束條件,建立了航班串的優(yōu)化模型,并構(gòu)造了一種自適應(yīng)遺傳算法。

上述研究均未考慮飛機(jī)技術(shù)狀態(tài)因素,因此不能合理安排例行檢修任務(wù),導(dǎo)致檢修次數(shù)和航班運(yùn)營成本的增加。本文在例行檢修的約束下,以飛機(jī)使用均衡為目標(biāo),使飛機(jī)的飛行時(shí)間盡可能接近飛機(jī)的期望飛行時(shí)間,建立多任務(wù)分配的飛機(jī)排班優(yōu)化模型,采用基于專家規(guī)則的啟發(fā)式算法,完成航班任務(wù)和例行檢修任務(wù)的分配,使機(jī)隊(duì)中每架飛機(jī)的周飛行時(shí)間盡量接近期望的飛行時(shí)間。

2飛機(jī)排班問題分析

2.1飛機(jī)排班問題分析

飛機(jī)排班中需要考慮的基本約束有以下幾點(diǎn):(1)滿足航班計(jì)劃要求,即航班屬性與相應(yīng)執(zhí)飛飛機(jī)保持一致;飛機(jī)執(zhí)行航班節(jié)到站機(jī)場(chǎng)與出發(fā)機(jī)場(chǎng)一致;以及航班過站時(shí)間不得小于最小銜接時(shí)間。(2)滿足唯一性要求,即每個(gè)航班應(yīng)當(dāng)且僅能安排一架飛機(jī)執(zhí)行,每架飛機(jī)在同一時(shí)段最多只能執(zhí)行一個(gè)航班。(3)滿足相互匹配的要求,主要是指執(zhí)飛飛機(jī)應(yīng)滿足航班屬性要求,如高原航班所對(duì)應(yīng)的飛機(jī)必須能飛高原,以及不給臨近停場(chǎng)維修的飛機(jī)分配航班任務(wù)。

2.2例行檢修約束分析

例行檢修約束作為飛機(jī)排班的一個(gè)重要約束條件,對(duì)安全飛行起著關(guān)鍵作用。通常以飛行時(shí)間為檢修間隔的單位。根據(jù)適航條例,令M為檢修級(jí)別集合(檢修級(jí)別一般分為A檢,B檢,C檢),對(duì)任意m∈M,規(guī)定飛機(jī)在任意兩次檢修之間飛機(jī)的累計(jì)飛行時(shí)間不得大于檢修間隔時(shí)間。

3飛機(jī)排班優(yōu)化模型

為了清晰地描述模型,本文引入檢修節(jié)點(diǎn)、虛擬飛機(jī)節(jié)點(diǎn)、剩余飛行時(shí)間[8]來表示檢修任務(wù)的變量,建立多任務(wù)分配的飛機(jī)排班數(shù)學(xué)模型。

檢修節(jié)點(diǎn)Vm為指完成上次飛行任務(wù)后,飛機(jī)的停留機(jī)場(chǎng)可執(zhí)行檢修m或航班任務(wù)的最后到達(dá)機(jī)場(chǎng)可執(zhí)行檢修m的點(diǎn)的集合。

虛擬飛機(jī)節(jié)點(diǎn)vfc為表示飛機(jī)完成檢修后,可以繼續(xù)執(zhí)飛航班,即上一次檢修完成時(shí)刻與下一班航班起飛時(shí)間的間隔時(shí)間大于或等于最小過站時(shí)間。

根據(jù)上述定義[8]將飛機(jī)c執(zhí)飛航班至vi后,檢修m的累計(jì)飛行時(shí)間累計(jì)飛行時(shí)間定義為

(1)

飛機(jī)排班的優(yōu)化模型描述如下

(2)

s.t.

(3)

(4)

(5)

其中式(2)為目標(biāo)函數(shù),表示某架飛機(jī)實(shí)際飛行時(shí)間與期望飛行時(shí)間的差值最小;式(3)是流平衡約束,xij為決策變量,即飛機(jī)執(zhí)行完航班i后執(zhí)行航班j則xij=1;否則值為0;公式(4)是滿足例行檢修約束。

模型以滿足基本飛機(jī)指派約束為基礎(chǔ),以實(shí)現(xiàn)飛機(jī)的飛行時(shí)間最大程度的接近飛機(jī)計(jì)劃時(shí)間為目標(biāo)[6]。對(duì)于臨近停廠檢修的飛機(jī),對(duì)其實(shí)際飛行時(shí)間的限制比較嚴(yán)格,而對(duì)于其他飛機(jī),通常情況下采用均衡排班的原則,即每架飛機(jī)本周的實(shí)際飛行時(shí)間盡可能平均。為了簡化模型的陳述,考慮沒有飛機(jī)臨近檢修,此時(shí)所有飛機(jī)的期望飛行:

(6)

這里假設(shè)已得到航班計(jì)劃,即將一周的航班分成了與飛機(jī)數(shù)A相匹配的a組。即將飛機(jī)指派問題轉(zhuǎn)化為飛機(jī)對(duì)航班環(huán)的分配問題。即對(duì)于一個(gè)排班周期內(nèi)(一般為7天)每一天的a個(gè)航班組,分別指定給a架飛機(jī),使得在此排班周期內(nèi),每架飛機(jī)都盡可能的接近其計(jì)劃飛行時(shí)間。

4算法設(shè)計(jì)

4.1路徑搜索規(guī)則

假設(shè)模型中所有飛機(jī)均不考慮臨近停廠維修的特殊情況,設(shè)計(jì)搜索路徑為一個(gè)周一的航班連接一個(gè)周二的航班再連接一個(gè)周三的航班,依次到周日,再返回連接一個(gè)周一的航班,依次以7為周期循環(huán)。由此可滿足流平衡約束。

4.2對(duì)調(diào)優(yōu)化的決策規(guī)則

5仿真研究

為了驗(yàn)證飛機(jī)指派優(yōu)化模型及算法,這里采用某航空公司一個(gè)機(jī)隊(duì)10架飛機(jī)與70個(gè)航班環(huán)進(jìn)行仿真研究。假設(shè)每架飛機(jī)的日飛行時(shí)間為3到10個(gè)小時(shí)不等,我們對(duì)每個(gè)航班環(huán)隨機(jī)生成一個(gè) 210(min)到 600(min)之間的整數(shù),代表空中飛行時(shí)間(分鐘)。

初始數(shù)據(jù)如表1所示,其中第一列代表了飛機(jī)的機(jī)號(hào),第二列到第八列代表了隨機(jī)產(chǎn)生的航班環(huán)的空中飛行時(shí)間,第九列代表的是某一架飛機(jī)一周執(zhí)行的航班環(huán)的飛行時(shí)間,最后一列代表的是每架飛機(jī)的期望飛行時(shí)間。

表1　初始數(shù)據(jù)Tab.1　Intial data

經(jīng)過算法求解后,得到優(yōu)化后的排班結(jié)果如圖1所示。為了便于檢驗(yàn),這里將程序做成了可視文件,運(yùn)行結(jié)果截圖2所示。

圖1　啟發(fā)式算法運(yùn)行的飛機(jī)指派結(jié)果Fig.1　Aircrqft assignment reshlts bas on heuristic algonithm

本文以最小代價(jià)(每架飛機(jī)周飛行時(shí)間與期望飛行時(shí)間的均方根)來評(píng)價(jià)所得排班結(jié)果的優(yōu)化程度,引入最小代價(jià)的概念,即

根據(jù)上圖,計(jì)算其最小代價(jià)為:

由上圖可以看出,排序前機(jī)隊(duì)內(nèi)每架飛機(jī)的周飛行時(shí)間與期望飛行時(shí)間的差值差異較大,飛機(jī)B2的周飛行時(shí)間超過期望飛行時(shí)間較多,這有可能導(dǎo)致飛機(jī)提前進(jìn)入檢修時(shí)間,增加維修成本,而飛機(jī)B8的周飛行時(shí)間離期望飛行時(shí)間相差較遠(yuǎn),這就是說,該飛機(jī)資源沒有得到充分的利用,降低了航空公司的運(yùn)營利潤;經(jīng)過算法處理排序后,每架飛機(jī)的周飛行時(shí)間都以期望飛行時(shí)間為基準(zhǔn)波動(dòng),且波動(dòng)很小。達(dá)到了預(yù)期的目的,使得飛機(jī)的飛行時(shí)間盡可能的接近期望飛行時(shí)間。使每架飛機(jī)資源都得到充分的利用,提高了航空公司的經(jīng)濟(jì)利潤。

下面是其他學(xué)者用蟻群算法[8]求解該問題時(shí)得到的結(jié)果,如表2所示。

表2　基于蟻群算法運(yùn)行的飛機(jī)指派結(jié)果Tab.1　Aircraft assignment results borsed on ant colony algorithm

根據(jù)該表格中的數(shù)據(jù),計(jì)算其最小代價(jià)為

與本文中啟發(fā)式算法所得的最小代價(jià)為3.99相比,明顯地看出本文設(shè)計(jì)的啟發(fā)式算法的優(yōu)化效果

6結(jié)束語

本文在分析飛機(jī)排班的工作流程的基礎(chǔ)上,建立了飛機(jī)指派的優(yōu)化模型,在滿足飛行安全的前提下使飛機(jī)得使用飛行時(shí)間盡可能的接近飛機(jī)計(jì)劃飛行時(shí)間,充分利用飛機(jī)資源,實(shí)現(xiàn)航空公司經(jīng)濟(jì)效益最大化。采用基于專家規(guī)則的啟發(fā)式算法實(shí)現(xiàn)了快速求解,通過實(shí)際數(shù)據(jù)進(jìn)行仿

真研究,結(jié)果表明:本文建立的模型和算法切實(shí)可行,可動(dòng)態(tài)快速的進(jìn)行飛機(jī)指派,從而提高航空公司生產(chǎn)調(diào)度的自動(dòng)化水平。

參考文獻(xiàn):

[1]Rexing B,Barnhart C,Kniker T S.Airline fleet assignment with time windows,Transportation Science[J],2000,34(1):1-20.

[2]Sriram C,Haghani A.An optimization model for aircraft maintenance scheduling and reassignment Transportation Research Part A:Policy and Practice[J],2003;37(1):29-48.

[3]Erling G,Rosin D.Tail assignment with maintenance restrictions:a constraint programming approach[D],Chalmers University of Technology,Gothenburg,Sweden,2002.

[4]Gronkvist M.The tail assignment problem[D],Chalmers University of Technology,Gothenburg,Sweden,2005.

[5]朱星輝,朱金福,鞏在武.我國航空公司機(jī)型指派模型及算法研究,工業(yè)技術(shù)經(jīng)濟(jì)[J],2007,26(4):75-77.

ZHU Xinghui,ZHU Jinfu,GONG Zaiwu.Research on the model and algorithm of Chinese airline model assignment,Industrial technology economy[J],2007,26(4):75-77.

[6]高強(qiáng),朱星輝,李云,等.南京航空航天大學(xué)民航學(xué)院[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),2012,36(1):153-157.

GAO Qiang,ZHU Xinghui,LI Yun,et al.Civil aviation college of nanjing university[J].Journal of Wuhan University of Technology(Transportation Science & Engineering),2012,36(1):153-157.

[7]李耀華,秦如如.基于混合遺傳算法的航班串優(yōu)化模型研究.[J]中國民航大學(xué)學(xué)報(bào),2010,28(6):31-34

LI Yaohua,Qinruru.Research on the model of flight string optimization based on hybrid genetic algorithm[J].Journal of Civil Aviation University of China,2010,28(6):31-34.

[8]周琨,夏洪山.基于協(xié)同多任務(wù)分配的飛機(jī)排班模型與算法[J].航空學(xué)報(bào),2011,32(12):2293-2302.

ZHOU Kun,XIA Hongshan.Aircraft scheduling model and algorithm based on Cooperative multi task assignment[J].Aeronautical Journal,2011,32(12):2293-2302.

劉婧女(1987-),新疆哈密市人,碩士研究生,主要研究方向?yàn)楹娇站S修工程及生產(chǎn)計(jì)劃建模及智能算法。

賈寶惠女(1971-),山西省運(yùn)城人,副教授,碩士研究生導(dǎo)師,主要研究方向?yàn)楹娇站S修工程及生產(chǎn)計(jì)劃建模及智能算法、航空機(jī)電技術(shù)及維修工程。

中圖分類號(hào)：TP 319.9

文獻(xiàn)標(biāo)識(shí)碼：A

基金項(xiàng)目：國家科學(xué)基金資助項(xiàng)目(DMC)

Study on Optimization Model and Algorithm of flight Assignment based on Heuristic Algorithm

LIU Jing1,JIA Baohui2

(1.School of Electrical Engineering,XinJiang University,Urumqi 830047,China;2.Aeronautic Engineering College,Civil aviation university of China,Tianjin 300300,China)

Abstract：Safety and economic profit are two factors that contradict each other in the flight operation,Security improvement will inevitably lead to the increase of operating costs.First,considering the aircraft flight mission and routine maintenance tasks,established optimization model of aircraft assignment,the rate of using aircraft as a target,letting the aircraft fly time as close as possible to the expectations time;Secondly,in order to solve the model,designing an algorithm which named expert rule-based heuristic algorithm,which can quickly achieve optimized flight assigned.Finally,using actual data from an airline,completed calculation and analysis,at the same time compared with the ant colony algorithm.It has been proven that the rationality of the model and algorithm.

Key words：flight assignment; optimization model; routine maintenance; heuristic algorithm