劉　婧,　賈寶惠

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

?

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

劉婧1,賈寶惠2

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

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

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

1引言

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

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

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

2飛機排班問題分析

2.1飛機排班問題分析

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

2.2例行檢修約束分析

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

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

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

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

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

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

(1)

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

(2)

s.t.

(3)

(4)

(5)

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

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

(6)

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

4算法設(shè)計

4.1路徑搜索規(guī)則

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

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

5仿真研究

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

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

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

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

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

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

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

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

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

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

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

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

6結(jié)束語

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

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

參考文獻:

[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]朱星輝,朱金福,鞏在武.我國航空公司機型指派模型及算法研究,工業(yè)技術(shù)經(jīng)濟[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]高強,朱星輝,李云,等.南京航空航天大學(xué)民航學(xué)院[J].武漢理工大學(xué)學(xué)報(交通科學(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é)報,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].航空學(xué)報,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-),新疆哈密市人,碩士研究生,主要研究方向為航空維修工程及生產(chǎn)計劃建模及智能算法。

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

中圖分類號：TP 319.9

文獻標識碼：A

基金項目：國家科學(xué)基金資助項目(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