基于機(jī)場(chǎng)協(xié)同決策系統(tǒng)的機(jī)坪牽引車調(diào)度方法

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

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

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

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

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

1 問(wèn)題分析與建模

1.1 問(wèn)題分析

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

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

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

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

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

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

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

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

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

(1)

1.2.2 牽引車行駛耗時(shí)

1.2.3 推出作業(yè)費(fèi)用

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

(2)

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

(3)

(4)

(5)

(6)

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

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

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

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

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

步驟3非支配排序與擁擠度計(jì)算?；贜SGA-Ⅱ算法對(duì)初始種群P0進(jìn)行快速非支配排序與擁擠度計(jì)算,并將層序irank值、擁擠度id一同寫(xiě)入到染色體中。

步驟4選擇父代個(gè)體。

表1 函數(shù)釋義

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

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

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

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

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

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

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

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

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

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

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

3 算法驗(yàn)證

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

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

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

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

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

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

3.2 計(jì)算結(jié)果

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

3.3 方案對(duì)比與應(yīng)用擴(kuò)展

采用相同的基礎(chǔ)數(shù)據(jù),將基于遺傳算法得出的調(diào)度方案中解序4的結(jié)果與傳統(tǒng)人工調(diào)度方案進(jìn)行對(duì)比,前者可使總費(fèi)用降低31.67%,服務(wù)航班數(shù)方差降至0,方案制定時(shí)間縮短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 方案對(duì)比結(jié)果

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

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

4 結(jié)論

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

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

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

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