基于機場協同決策系統的機坪牽引車調度方法

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

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

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

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

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

1 問題分析與建模

1.1 問題分析

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

A′、B′、C′為牽引車停放區；S1～Sn為牽引車調度過程圖1 牽引車服務過程Fig.1 The service procedure of towing tractors

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

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

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

1.2 數學模型

航空器推出耗時、牽引車行駛耗時和推出作業產生的費用取值如下。

1.2.1 航空器推出作業耗時

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

(1)

1.2.2 牽引車行駛耗時

1.2.3 推出作業費用

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

(2)

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

(3)

(4)

(5)

(6)

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

2 算法設計

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

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

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

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

步驟4選擇父代個體。

表1 函數釋義

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

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

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

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

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

經過交叉操作的個體組成子代種群P2,計算每一個體的目標函數值,更新片段[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′變為q+1-r′。經過變異操作的個體組成子代種群P3,計算每一個體的目標函數值,更新片段[f]的基因。

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

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

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

3 算法驗證

3.1 數據獲取與處理

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

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

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

圖5 推出作業耗時統計圖Fig.5 The statistical chart of time-consuming of Push-Back

表2 部分航空器作業信息

3.2 計算結果

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

3.3 方案對比與應用擴展

采用相同的基礎數據,將基于遺傳算法得出的調度方案中解序4的結果與傳統人工調度方案進行對比,前者可使總費用降低31.67%,服務航班數方差降至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 牽引車作業甘特圖Fig.8 The gantte chart of towing tractors’service

表4 方案對比結果

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

圖9 牽引車調度程序Fig.9 The software of scheduling of towing tractors

4 結論

以某一時段、機坪單一保障區內航空器推出作業產生的總費用最小、參與作業的牽引車數量最少、牽引車服務的航空器數量保持均衡為優化目標,結合A-CDM系統和多目標遺傳算法設計出機坪牽引車調度方法,得到以下結論。

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

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

后續將針對多種車輛完成多類航班保障作業的調度問題展開研究。