基于航班延誤情況下的登機橋作業(yè)調(diào)度方法的研究

丁 芳 沙常濤

(中國民航大學(xué)電子信息與自動化學(xué)院 天津 300300)

0 引 言

登機橋調(diào)度包含航班進港和離港使用登機橋的時間段。航班延誤原因一般有以下幾個因素：天氣、空中交通管制、航空公司自身失誤、機場作業(yè)不當(dāng)、以及軍事活動[1]。航班大面積延誤多由天氣造成的，延誤發(fā)生后，旅客就會給航空公司很低的評分反饋[2]，也會降低該機場在航空公司的好感度。航班延誤就必然影響到機場登機橋的預(yù)調(diào)度方案，依靠人工進行登機橋調(diào)度效率低且難度大。因此，在延誤情況下，建立登機橋動態(tài)調(diào)度模型對機場運行至關(guān)重要。航班延誤后需根據(jù)延誤航班的實時進離港時間及機型對登機橋進行再調(diào)度，確保延誤航班的地面服務(wù)和服務(wù)旅客的需求。

針對登機橋多目標(biāo)調(diào)度優(yōu)化問題，國內(nèi)外眾多學(xué)者將多個目標(biāo)融合進行更全面的研究。2006年，王力、劉長友使用禁忌搜索策略對模型進行調(diào)度求解[3]。2013年，文獻[4]考慮到旅客滿意度及舒適度提出旅客進港用時最短為目標(biāo)來求解。2015年，陳驍睿提出了改進粒子群算法的調(diào)度方法，以各個停機位負(fù)載達到均衡和旅客移動距離為最短目標(biāo)[5]。2016年，李亞玲等[6]提出了一種基于禁忌搜索方法的動態(tài)調(diào)度方案，此方案以利用率最大化及旅客移動距離最小為目標(biāo)。同年，薛清文等[7]考慮到航空公司的利益，以航空公司成本最小化及均衡成本為目標(biāo)，建立了動態(tài)分配模型。

在分析某大型機場登機橋配置信息及當(dāng)天固定時間段航班信息的基礎(chǔ)上，本文提出了一種在航班延誤情況下的登機橋調(diào)度的改進ABC算法。以停靠在遠機位航班數(shù)、航班與登機橋原有對應(yīng)關(guān)系的改動數(shù)及旅客進港用時最短加權(quán)之和最小為優(yōu)化目標(biāo)的整數(shù)規(guī)劃模型。

1 登機橋調(diào)度問題的問題描述

機場多數(shù)情況下不需要對登機橋預(yù)分配方案進行改動，通常在當(dāng)航班延誤發(fā)生時，才需要對登機橋進行動態(tài)調(diào)度，登機橋調(diào)度包括對近機位廊橋和遠機位登機梯的調(diào)度。本文所提方法基于如下假設(shè)：

(1) 機場為單跑道；

(2) 登機橋數(shù)量一定，即機場根據(jù)當(dāng)天監(jiān)控系統(tǒng)，實時統(tǒng)計出可用登機橋，且登機橋數(shù)量滿足當(dāng)天航班需求；

(3) 默認(rèn)機場與航空公司沒有簽訂登機橋強制性使用哪種廊橋；

(4) 所有進港航班均采用先到先服務(wù)原則；

(5) ?？吭谙噜弮蓚€登機橋的航班滿足安全的距離。

1.1 符號表

i：航班序列號，表示第i個航班(0≤i≤M)；

k：登機橋序列號，表示第k個登機橋(0≤k≤N)；

xik：第i個航班?？吭诘趉個登機橋上，則xik=1，否則xik=0；

Wik：航班i預(yù)調(diào)度在登機橋k的作業(yè)時間；

Lik：航班i預(yù)調(diào)度駛離登機橋k的時間；

Nik：登機橋k的無任務(wù)時間；

Ci：航班i的機型，1、2、3分別代表小、中、大型航班；

Bk：登機橋k的類型，1、2、3分別代表小、中、大型登機橋；

Dk：登機橋k的開始可用時間；

Rk：登機橋k的結(jié)束可用時間；

Jik：登機橋k服務(wù)航班i的時間；

δ：登機橋安全時間間隔；

di：若航班i再分配的登機橋與預(yù)分配的登機橋不同，則di=1，否則di=0；

Yi：航班i被分配至遠機位，則Yi=1，否則Yi=0；

Uik：航班i從著陸開始?？康降菣C橋k所用的時間；

Hik：航班i在登機橋k上的地面保障時間；

zijk：若航班i和航班j停靠在相同登機橋上，且航班j在航班i之后到達，則zijk=1，否則zijk=0。

1.2 航班延誤的機場登機橋再調(diào)度模型

(1) 停靠在遠機位航班數(shù)最少 當(dāng)航班數(shù)量過多，近機位廊橋個數(shù)無法滿足需求時，需要將航班分配至遠機位使用登機梯對旅客進行服務(wù)。而多數(shù)情況下旅客是不希望在遠機位登機的，所以要把調(diào)度到遠機位航班數(shù)降到最小，表示為：

(2) 航班與登機橋原有對應(yīng)關(guān)系改動數(shù)最小 航班與登機橋原有對應(yīng)關(guān)系改動數(shù)應(yīng)降到最小，可將其表示為：

(3) 旅客進港用時最小 旅客進港用時包括從航班降落至跑道滑行到登機橋及航班在登機橋上所需的地面保障時間的和，旅客進港用時最小公式為：

參考模型的假設(shè)條件，約束條件如下：

(1) 每個等待起降的航班必須被調(diào)度且只能被調(diào)度到一個登機橋。

(2) 登機橋在被調(diào)度給某航班的該時間段內(nèi)，不能將該登機橋再調(diào)度給其他航班。即在相同登機橋上，每個航班只能有一個前序航班和一個后續(xù)航班。

(3) 根據(jù)民航局的規(guī)定，相同登機橋前序航班任務(wù)離開與后續(xù)航班任務(wù)的?？恐g必須要有一定的時間間隔，以防止航班發(fā)生碰撞等現(xiàn)象。

Wjk≥Lik+δi,j∈N,k∈M,Wjk≥Wik

(7)

(4) 由于航班靠橋后地服人員還需對航班進行安全檢查及航餐、加油的服務(wù)，因此同一航班任務(wù)駛離登機橋時刻與靠橋時刻的差應(yīng)大于登機橋?qū)嶋H服務(wù)航班的時長。

Lik-Wik≥Jik

(8)

(5) 使用同一登機橋的相鄰兩個航班任務(wù)之間的空余時間，等于后面航班的預(yù)進港時間減去前面航班的預(yù)離港時間。

Nik=Wjk-Liki,j∈N,k∈M,Wjk≥Wik

(9)

(6) 由于受登機橋端口高度和航班機艙高度的約束，小型航班只能停靠小型登機橋，中型登機橋可以?？恐?、小型航班，大型登機橋可以?？看蟆⒅?、小三種航班。即航班類型只能小于等于需?？康牡菣C橋的類型。

Ci≤xikBk

(10)

(7) 小、中、大型航班類型Ci及小、中、大型登機橋類型Bk從小到大都分別用1、2、3表示。

Ci={1,2,3}Bk={1,2,3}

(11)

目標(biāo)函數(shù)表示為調(diào)度員在已知延誤航班信息的基礎(chǔ)上，以調(diào)度到遠機位的航班數(shù)、航班登機橋原有對應(yīng)關(guān)系的改動數(shù)及乘客進港所用時長加權(quán)之和最小。登機橋再調(diào)度模型的目標(biāo)函數(shù)為：

minF=αF1+βF2+χF3

(12)

式中:α=0.3，β=0.3，χ=0.4，代表每個子任務(wù)的權(quán)重。不管是航空公司還是機場，最終目的都是服務(wù)乘客，所以權(quán)重應(yīng)適當(dāng)大一些。

2 改進的人工蜂群算法

算法與登機橋再調(diào)度模型的映射關(guān)系如表1所示。

2.1 構(gòu)造食物源編碼

采用二進制編碼方式進行食物源編碼，設(shè)現(xiàn)有N個航班要分配給M個登機橋，x為N行M列的矩陣。每個航班都在M個登機橋中取值，每個種群初始解都有N×M個基因，每個基因取值只有0或1。

其中xik=1表示將第i個航班分配給第k個登機橋，否則xik=0。

2.2 種群初始解

種群初始解的質(zhì)量直接決定了最終解的質(zhì)量高低，種群初始解分布越均勻，范圍越大，就會更容易產(chǎn)生最優(yōu)解。

進行登機橋再調(diào)度問題時，應(yīng)考慮登機橋調(diào)度的各種約束條件和降低登機橋再調(diào)度對原預(yù)調(diào)度方案的改動性，因此，采用貪婪算法產(chǎn)生初始可行解。由如下搜索步驟產(chǎn)生：

步驟1：讀取登機橋原調(diào)度方案，刪除延誤航班的登機橋預(yù)調(diào)度方案。

步驟2：讀取延誤航班信息，將n個延誤航班按進港時間Wik升序排列，得到延誤航班排序隊列FN=fi(i=1，2，…n)。

步驟3：從Fn中選出一個延誤航班fi，根據(jù)約束條件，計算其目標(biāo)函數(shù)值，在可選登機橋集合中選取目標(biāo)函數(shù)值最小的登機橋分配給該延誤航班，更新該登機橋的開始可用時間Dk和結(jié)束可用時間Rk，從FN中刪除fi。

步驟4：判斷FN集合是否再無取值可能，如果無取值結(jié)果，則輸出相應(yīng)的延誤航班的登機橋再調(diào)度方案，否則跳轉(zhuǎn)至步驟3繼續(xù)往下執(zhí)行。

初始可行解的搜索流程如圖1所示。

圖1 初始可行解搜索流程圖

2.3 適應(yīng)度評價函數(shù)

本文中，采用文獻[8]的對數(shù)適應(yīng)度評估方式，將各種群間的差異區(qū)分開來，改進后的適應(yīng)度評價方式為[8]：

2.4 改進局部搜索機制

原始ABC算法中，全局搜索較好，但后期局部搜索的隨機性太強，易陷入局部最優(yōu)，導(dǎo)致對種群初始解沒有充分地搜索。對于文獻[12]中只是將每一代中的最優(yōu)解提取出來加入到跟隨蜂及偵察蜂的搜索策略當(dāng)中，容易導(dǎo)致更優(yōu)解的丟失。所以本文提出一種基于Logistic混沌搜索的更優(yōu)解改進策略，在每一代中最優(yōu)解的基礎(chǔ)上，再進行k次的混沌迭代搜索，并且將更優(yōu)解策略加入到跟隨蜂及偵察蜂的搜索策略當(dāng)中，這樣更容易找出更優(yōu)解。

原始logistic混沌映射為：

xk+1=μxk(1-xk)

(14)

式中：k為迭代次數(shù)，k=(1,2，…，K)，K為最大迭代次數(shù)。當(dāng)μ=4時，y1∈(0,1)，且y1≠(0.25,0.5,0.75)，此時，式(14)是一個混沌系統(tǒng)。

本文采用文獻[9]的映射模型：

xk÷1=ωxk-2tanh(ξxk)exp(-3xk2)

(15)

當(dāng)μ=4，y1=0.65，ω=0.5，ξ=2.7時，式(14)及式(15)對應(yīng)的混沌系統(tǒng)如圖2和圖3所示。由圖可知，式(14)混沌系統(tǒng)產(chǎn)生的解分布在(0,1)之間，式(15)混沌系統(tǒng)產(chǎn)生的解分布在(-1,1)之間。在產(chǎn)生最優(yōu)解的過程中，由于引進了當(dāng)前代最優(yōu)解的概念，所以選擇式(15)產(chǎn)生的隨機序列有更大的范圍及更好的遍歷性，能產(chǎn)生較高質(zhì)量的個體。

圖2 式(14)混沌系統(tǒng)

圖3 式(15)混沌系統(tǒng)

2.5 改進跟隨蜂局部搜索策略

跟隨蜂在雇傭蜂搜索完成產(chǎn)生的最好個體xgbest基礎(chǔ)上再次搜索更好個體[10-11]，然后在xgbest附近根據(jù)式(16)再進行k次混沌搜索，得到k個個體，比較k個個體中質(zhì)量最高的個體作為xkbest，比較xgbest與xkbest的適應(yīng)度值，選擇大的成為最優(yōu)個體xbest。本文中觀察蜂搜索就是將某個航班在其可?？康牡菣C橋集合里重新選擇一個登機橋進行替換。

在xgbest附近進行混沌搜索的公式為：

yk=xgbest+xk

(16)

產(chǎn)生新食物源的更新公式為Vik：

Vik=xbest+τ(xik-xbest)+φ(xr1,k-xr2,k)

(17)

式中:i=1,2,…,SN；k=1,2,…,D；gbest表示當(dāng)前代最優(yōu)個體，r1、r2表示鄰域內(nèi)隨機解，D表示解的維數(shù),SN表示種群數(shù)量，φ在[-1,1]隨機取值。τ為比例系數(shù)，大小為[12]：

式中：iter是當(dāng)前迭代次數(shù)，MCN為總迭代次數(shù)。

2.6 改進的偵查蜂局部偵查策略

在進行局部搜索時，原始ABC算法偵查峰沒有很好地找出更優(yōu)食物源的能力，易陷于局部最優(yōu)。在本文中，偵察蜂搜索即航班隨機的變換登機橋，形成新的候選解，每次搜索產(chǎn)生的候選解數(shù)量與種群規(guī)模保持一致。搜索時，在依靠跟隨蜂最優(yōu)解基礎(chǔ)上加入比例系數(shù)策略，如下式所示：

Vik=xbest+rand(0,1)×τ×xbest

(19)

2.7 改進后的人工蜂群算法的流程

改進后ABC算法工作流程圖如圖4所示。

圖4 改進ABC算法的流程圖

3 仿真實驗及分析

基于國內(nèi)某大型機場某時間段的航班信息進行仿真實驗，航班信息如表2所示。

表2 航班信息表

續(xù)表2

根據(jù)機場實際距離及民航運輸標(biāo)準(zhǔn)[13]計算出的各個階段的用時如表3所示。數(shù)字序號1-8代表遠機位登機梯，航班到達時所需的靠橋用時為3.5 min，101-108代表近機位廊橋，所需的靠橋用時為5 min。只有遠機位需用擺渡車。

表3 登機橋類型及?？坑脮r min

登機橋預(yù)調(diào)度方案如表4所示。

表4 登機橋預(yù)調(diào)度方案

在進行模擬登機橋再調(diào)度時，在這32個航班中選擇任意8個航班作為延誤航班，航班延誤信息如表5所示。

表5 航班延誤信息表

通過上文提出的改進人工蜂群算法與所建立的航班延誤的登機橋再調(diào)度模型進行求解，需對參數(shù)初始化，SN=32，D=16，MCN=3 000，Limit=50，K=200。登機橋使用最小時間間隔δ=5 min。實驗采用MATLAB R2014a進行仿真，選擇第100,200,…,3 000代的目標(biāo)函數(shù)值仿真出的收斂曲線對比圖如圖5所示。

圖5 目標(biāo)函數(shù)收斂曲線

由圖5可知，文獻[12]提出的MMABC在1 000代前算法的收斂速度快，但是之后的收斂速度接近于0，且沒有達到收斂的條件，也沒有產(chǎn)生可行的解。未加混沌特性且改進了適應(yīng)度評價方式后的ABC算法在1 000代前期收斂速度較快，且1 000代以后的收斂相較于MMABC效果更好，只能產(chǎn)生可行解，目標(biāo)函數(shù)值為148.3 min。加入混沌搜索后的改進ABC算法的圖像收斂速度更快，產(chǎn)生更優(yōu)解的時間明顯縮短，這不僅與所需要的進化次數(shù)和群體規(guī)模有關(guān)，而且還與當(dāng)前迭代的初代個體有關(guān)，初代個體的質(zhì)量越高，就更容易達到更優(yōu)解，目標(biāo)函數(shù)值為142.6 min。

登機橋再分配方案如表6所示。

表6 登機橋再調(diào)度方案

分析實驗結(jié)果表明：

(1) 航班登機橋原有對應(yīng)關(guān)系的改動數(shù)變小 在選擇的8個延誤航班中，有4個航班被指派到與預(yù)調(diào)度方案相同的登機橋，4個航班被分配到別的登機橋。對登機橋再調(diào)度后，有6架航班登機橋進行了調(diào)整，分別為第3、15、19、21、24、29。

(2) 航班可能?？吭诮鼨C位廊橋的概率增大 在延誤航班中，第6、11、21、24號航班進行了靠橋，當(dāng)將延誤航班全部安排到遠機位登機梯時，靠橋率為0%，根據(jù)以上方法靠橋率達到了50%。

(3) 減少了旅客進港用時總和 若將延誤航班全部安排到遠機位，則按照預(yù)調(diào)度的遠機位登機梯安排方案如表7所示。

表7 預(yù)調(diào)度的遠機位登機梯安排方案

按照此方案，延誤航班進港用時總和為123.9 min，按照本文的優(yōu)化方案，延誤航班的進港用時總和為104.55 min，減少了旅客的進港用時。

4 結(jié) 語

本文研究了在航班發(fā)生大面積性延誤時，機場對登機橋的再調(diào)度問題?？紤]了顧客滿意度、登機橋類型、航班類型及航班的進離港時間等因素，以減少使用遠機位登機梯的航班數(shù)、減少對原調(diào)度方案的改動性及減少旅客進港用時為目標(biāo)。根據(jù)機場實際標(biāo)準(zhǔn)建立約束條件，建立了航班延誤時登機橋再調(diào)度的多目標(biāo)模型，以國內(nèi)某機場航班延誤情況為實驗樣本，驗證了所提方法的可行性。本文所研究的登機橋再調(diào)度問題屬于再調(diào)度的NP-hard問題，目前還沒有找到可以高效解決該問題的方法，本文根據(jù)改進的ABC算法仿真結(jié)果來看算法的收斂性較好。結(jié)合模型、算法和實驗數(shù)據(jù)進行仿真研究，證明了實驗得出的登機橋再調(diào)度方案在三個目標(biāo)上都得到較優(yōu)的效果。后續(xù)工作還要去深入分析機場登機橋在多跑道條件下的多目標(biāo)綜合調(diào)度問題，并設(shè)計出更合理有效的調(diào)度求解方法，以此來獲得更優(yōu)的調(diào)度方案是未來工作的關(guān)鍵和難點。