王 博, 王劍輝, 彭笑非, 蘇 剛

(1.中國民航飛行學(xué)院空中交通管理學(xué)院, 廣漢 618307； 2.中國民用航空總局第二研究所民航空管工程技術(shù)研究所, 成都 610041)

航空器推出作業(yè)是指牽引車將航空器由停機位牽引至滑行道的過程,是機坪保障的重要環(huán)節(jié)。但在實際保障過程中,航空器推出時刻不易預(yù)測、牽引車在機位間的行駛耗時和作業(yè)耗時存在波動,都會對牽引車的調(diào)度產(chǎn)生影響。隨著機場協(xié)同決策(airport collaborative decision making,A-CDM)在機場運行控制中心的實施,航空器推出時刻能夠被精準的預(yù)測,在此基礎(chǔ)上充分考慮車輛行駛耗時和航空器推出作業(yè)耗時的不確定性有利于機坪牽引車調(diào)度工作的展開。

機坪牽引車調(diào)度屬于某種車輛完成多架航空器某一類保障作業(yè)的調(diào)度問題[1],具有多目標、多約束等特性,作為一類非確定性多項式(non-deterministic polynomial hard)[2]問題,以往的研究多建立具有時間窗約束的車輛路徑規(guī)劃模型[3-5],多采用啟發(fā)式算法[6-7]、蟻群算法[8]和遺傳算法[9-10]等智能算法進行求解,但研究工作精細化程度不夠,保障作業(yè)耗時常取經(jīng)驗值或高斯分布隨機數(shù)值[11-12],車輛行駛速度多為固定值,尚未考慮航空器推出作業(yè)可能引發(fā)的運行沖突問題,得到的調(diào)度方案難以指導(dǎo)現(xiàn)場實地保障作業(yè)。

為此，在航空器推出時刻能夠被精準預(yù)測的前提下,建立以某一時段、單一保障區(qū)內(nèi)航空器推出作業(yè)產(chǎn)生的總費用最小、參與作業(yè)的牽引車數(shù)量最少、牽引車服務(wù)的航空器數(shù)量保持均衡的多目標優(yōu)化模型；通過分析歷史數(shù)據(jù),針對性地設(shè)計隨機數(shù)生成方式以確定航空器推出作業(yè)耗時和牽引車行駛耗時；基于停機位的分布情況設(shè)置約束條件,避免航空器發(fā)生推出沖突,然后設(shè)計多目標遺傳算法、結(jié)合實例進行驗證,最后采用MATLAB-GUI軟件設(shè)計可視化調(diào)度程序,以便應(yīng)用在現(xiàn)場實地保障作業(yè)中。

1 問題分析與建模

1.1 問題分析

牽引車服務(wù)過程是指牽引車由停放區(qū)開出,行駛到各指定機位為航空器提供牽引服務(wù)后回到停放區(qū),如圖1所示；航空器的推出耗時是指牽引車進入某機位開始作業(yè)直至結(jié)束該項作業(yè)離開機位所花費的時間；航空器的推出沖突是指在機坪某些區(qū)域必須將航空器錯時推出,如圖2所示。需要解決的問題是在避免航空器推出沖突的前提下合理調(diào)度牽引車,使得推出作業(yè)產(chǎn)生的總費用盡可能小、參與作業(yè)的牽引車盡可能少、牽引車服務(wù)的航班數(shù)量更加均衡。

A′、B′、C′為牽引車停放區(qū)；S1～Sn為牽引車調(diào)度過程圖1 牽引車服務(wù)過程Fig.1 The service procedure of towing tractors

圖2 航空器推出沖突Fig.2 The conflict of Push-Back between aircraft

為解決該多目標優(yōu)化問題,首先引入Pareto支配關(guān)系的概念[13],對于目標函數(shù)fi(x),i=1,2,…,n,任意給定兩個決策變量Xa、Xb,假定優(yōu)化方向為最小化,如果有以下兩個條件成立,則稱為Xa支配Xb:①?i∈1,2,…,n,都有fi(Xa)≤fi(Xb)成立；②?i∈1,2,…,n,使得fi(Xa)>fi(Xb)成立。

如果對于一個決策變量,不存在其他決策變量能夠支配他,即無法在改進任何目標函數(shù)的同時不削弱至少一個其他目標函數(shù),這種解稱作Pareto最優(yōu)解。

1.2 數(shù)學(xué)模型

航空器推出耗時、牽引車行駛耗時和推出作業(yè)產(chǎn)生的費用取值如下。

1.2.1 航空器推出作業(yè)耗時

航空器推出耗時ti,d在因素?1,?2,…,?N的影響下有不同的時間分布,可從該分布中取隨機值,記為

(1)

1.2.2 牽引車行駛耗時

1.2.3 推出作業(yè)費用

i,j=1,2,…,w；i≠j

(2)

假設(shè)牽引車Vh從停放區(qū)S0出發(fā),依次為航空器Fi,Fj,…,Fl提供牽引服務(wù),最后回到停放區(qū),在此期間,可以從停放區(qū)S0任意增派車輛為其他航空器服務(wù),直到完成該保障區(qū)所有航空器的推出作業(yè)。在航空器推出作業(yè)耗時、牽引車行駛耗時、推出作業(yè)費用取值的基礎(chǔ)上構(gòu)建機坪牽引車調(diào)度多目標優(yōu)化模型,具體可表示為

(3)

(4)

(5)

(6)

式中：式(3)和式(4)、式(5)分別求取所有航空器牽引作業(yè)產(chǎn)生的總費用最小、參與作業(yè)的車輛數(shù)目最小、不同車輛服務(wù)的航空器數(shù)量方差最??；M為一個極大的正數(shù)；λ為0～1變量,若車輛Vh為航空器Fi提供服務(wù)后直接駛往航空器Fj所停機位時,λ=1；否則λ=0,該式保證車輛在航空器之間的作業(yè)時序關(guān)系得到滿足；ti,e≥ti,sp+ti,d保證航空器Fi的推出耗時得到滿足；|tu,s-tv,s|≥td通過設(shè)置緩沖時間(td),保證航空器Fu、Fv不會產(chǎn)生推出沖突；xih為0～1變量,若航空器Fi由車輛Vh服務(wù),xih=1,否則,xih=0,該式保證同一個航空器只能被一輛牽引車服務(wù)；q為該保障區(qū)可提供牽引車的最大數(shù)量。

2 算法設(shè)計

機坪牽引車調(diào)度問題包含航空器推出作業(yè)總費用最小、參與作業(yè)的牽引車數(shù)量最少和牽引車服務(wù)的航班數(shù)量保持均衡3個目標函數(shù)的同時優(yōu)化,為了權(quán)衡不同目標之間的利益,需要得到一組 Pareto 解集。結(jié)合 NSGA-II 算法進行求解,所用函數(shù)如表1所示,算法流程如圖3所示,具體步驟如下。

步驟1染色體編碼與種群初始化。在多目標遺傳算法中,染色體作為實際的優(yōu)化對象,其編碼主要分為直接編碼和間接編碼[9]兩類。為提高效率,本算法直接對一段時間內(nèi)待保障航空器編號和牽引車編號進行編碼,每一條染色體pe由基因片段[x]、[y]、[f]組成。其中片段[x]={x1,x2,…,xw}={randperm(w)},即將w個航空器編號隨機排成一行；片段[y]={y1,y2,…,yq}={randi[q,1,w]},將指定對編號為xi(i=1,2,…，w)的航空器提供服務(wù)的牽引車編號yj(j=1,2,…,q)排列在基因片段[x]之后；片段[f]=[F1,F2,F3]為該套調(diào)度方案的目標函數(shù)值,并依次排在片段[y]后。按照編碼規(guī)則隨機生成種群規(guī)模為N的個體,將得到的所有個體記為初始種群P0。

步驟2適應(yīng)度設(shè)計。為避免航空器推出作業(yè)發(fā)生沖突,判斷編號為yj(j=1,2,…,q)的牽引車服務(wù)的航空器中是否存在Fu、Fv,若存在,則讓其作業(yè)實際開始時刻間隔td,并更新該個體的目標函數(shù)值。之后按照快速非支配排序和擁擠度算子進行適應(yīng)度設(shè)計,非支配排序[13]是基于個體的目標函數(shù)值,按個體非劣解水平對種群分層,向Pareto最優(yōu)解的方向進化；擁擠度算子是為優(yōu)先選擇擁擠距離較大的個體,保證種群多樣性。

步驟3非支配排序與擁擠度計算。基于NSGA-Ⅱ算法對初始種群P0進行快速非支配排序與擁擠度計算,并將層序irank值、擁擠度id一同寫入到染色體中。

步驟4選擇父代個體。

表1 函數(shù)釋義

圖3 算法流程圖Fig.3 The flow chart of algorithm

設(shè)配對池容量為N/2,選擇層序irank最小的個體加入配對池,如果有irank值相同的個體,則任選擁擠度id最大的個體加入配對池；反復(fù)進行該操作直到配對池容量已滿,得到父代種群P1。

步驟5去重交叉操作。從父代種群P1中成對選擇染色體pv、pv+1,若滿足交叉概率pc,則對其進行交叉操作。

針對片段[xv]、[xv+1]進行交叉操作:①令{v}=randi(w,1,2),設(shè)v1,v2∈v；r=v1≤v2；②將片段[xv]、[xv+1]上第r位基因進行互換,互換前的值分別記為rv、rv+1；③分別在片段[xv]、[xv+1]上找到與rv+1、rv相等的基因,將其變?yōu)閞v、rv+1;④判斷r與v2的大小關(guān)系,若r>v2,則結(jié)束交叉操作,否則,r=r+1,回到步驟②。

針對片段[yv]、[yv+1]進行交叉操作:令q=randi(w),將片段[yv]前q個基因與片段[yv+1]第q位以后的基因進行組合,得到染色體p′v,將[yv+1]前q個基因與片段[yv]第q位以后的基因組合,得到染色體p′v+1。

經(jīng)過交叉操作的個體組成子代種群P2,計算每一個體的目標函數(shù)值,更新片段[f]的基因,整個交叉過程如圖4所示。

圖4 染色體交叉示意圖Fig.4 The diagram of chromosomal chiasma

步驟6變異操作。針對種群P2的染色體pd(d=1,2,…,N),若滿足變異概率pm,則對其進行變異操作。令{s1,s2,…,sw}=randperm(w),將片段[xd]上第s1、s2個基因互換；令s=randi(w),將片段[yd]上第s個基因r′變?yōu)閝+1-r′。經(jīng)過變異操作的個體組成子代種群P3,計算每一個體的目標函數(shù)值,更新片段[f]的基因。

步驟7種群融合。將父代種群P1與子代種群P3進行融合,對融合種群P4進行非支配排序與擁擠度計算,得到非支配層級和對應(yīng)非支配層的擁擠度,寫入到染色體中。

步驟8精英保留。在一個的空種群中依次添加融合種群P4中irank={1,2,…,n}的個體,直到進一步添加層級i后種群規(guī)模將超過N,對層級i中個體按擁擠距離id由大到小逐個填充直到種群規(guī)模等于N,由此得到新的種群P5。

步驟9迭代。返回至步驟4,進行下一次迭代操作,直至達到最大迭代次數(shù)gen,最終得到的新種群Ppop即為優(yōu)化問題的帕累托最優(yōu)解集。

3 算法驗證

3.1 數(shù)據(jù)獲取與處理

以中國西南某一機場為例,基于該機場A-CDM系統(tǒng)得到某一保障責(zé)任區(qū)內(nèi)40架航空器的預(yù)計推出時刻和即將?？繖C位,部分示例如表2所示。

航空器推出作業(yè)耗時的影響因素?主要考慮時間段和機型,時間段具體分為Night(19：00—5：00)、Day(5：00—19：00),機型分為A(小型飛機)、B(中型飛機)、C(大型飛機),通過統(tǒng)計分析不同時段、不同機型共計1 200架航空器的推出作業(yè)所耗時長確定航空器推出作業(yè)時長的分布范圍,如圖5 所示。

基于機場基礎(chǔ)數(shù)據(jù)獲取牽引車停放區(qū)與各停機位以及各停機位間的距離dij。綜合考慮作業(yè)時間段和天氣因素對牽引車行駛速度的影響,結(jié)合機場方面的運行數(shù)據(jù)將因素設(shè)為0.8；針對可能產(chǎn)生推出沖突的航空器,將其作業(yè)實際開始時刻的間隔值td設(shè)為5 min；結(jié)合機場方面的相關(guān)經(jīng)驗,將牽引車行駛耗時轉(zhuǎn)化系數(shù)γ設(shè)為1,牽引車早到、遲到費用系數(shù)α、β分別設(shè)為5和10。

圖5 推出作業(yè)耗時統(tǒng)計圖Fig.5 The statistical chart of time-consuming of Push-Back

表2 部分航空器作業(yè)信息

3.2 計算結(jié)果

將種群規(guī)模N設(shè)為300,迭代次數(shù)(gen)設(shè)為 1 000,交叉概率(pc)設(shè)為0.75,變異概率(pm)設(shè)為0.3,利用MATLAB軟件求解,計算耗時為4.3 min,單條染色基因信息如圖6所示,Pareto解集如圖7所示,具體信息如表3所示；以解序4為例,繪制牽引車作業(yè)甘特圖,如圖8所示,在特殊機位可能產(chǎn)生運行沖突的航空器,其推出作業(yè)實際開始時刻均間隔在 5 min 以上。

3.3 方案對比與應(yīng)用擴展

采用相同的基礎(chǔ)數(shù)據(jù),將基于遺傳算法得出的調(diào)度方案中解序4的結(jié)果與傳統(tǒng)人工調(diào)度方案進行對比,前者可使總費用降低31.67%,服務(wù)航班數(shù)方差降至0,方案制定時間縮短71.15%,如表4所示。

圖6 單條染色體基因信息Fig.6 The gene information of single chromosome

圖7 Pareto解集圖Fig.7 The diagram of Pareto sets

表3 Pareto解集信息

圖8 牽引車作業(yè)甘特圖Fig.8 The gantte chart of towing tractors’service

表4 方案對比結(jié)果

利用MATLAB-Gui軟件制作可視化的調(diào)度程序,通過獲取A-CDM數(shù)據(jù)、導(dǎo)入基礎(chǔ)運行數(shù)據(jù),利用多目標遺傳算法輸出一組調(diào)度方案,為一線運營人員提供決策參考,如圖9所示。

圖9 牽引車調(diào)度程序Fig.9 The software of scheduling of towing tractors

4 結(jié)論

以某一時段、機坪單一保障區(qū)內(nèi)航空器推出作業(yè)產(chǎn)生的總費用最小、參與作業(yè)的牽引車數(shù)量最少、牽引車服務(wù)的航空器數(shù)量保持均衡為優(yōu)化目標,結(jié)合A-CDM系統(tǒng)和多目標遺傳算法設(shè)計出機坪牽引車調(diào)度方法,得到以下結(jié)論。

(1)與傳統(tǒng)的人工調(diào)度方法相比,該方法下的調(diào)度方案可使作業(yè)總費用降低31.67%、各牽引車服務(wù)的航空器數(shù)量更加均衡、方案制定時間縮短71.15%。

(2)通過該方法設(shè)計的可視化牽引車調(diào)度程序能指導(dǎo)實際保障作業(yè),為一線運營人員提供決策參考。

后續(xù)將針對多種車輛完成多類航班保障作業(yè)的調(diào)度問題展開研究。