基于航班延誤情況下的登機橋作業調度方法的研究

丁 芳 沙常濤

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

0 引 言

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

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

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

1 登機橋調度問題的問題描述

機場多數情況下不需要對登機橋預分配方案進行改動，通常在當航班延誤發生時，才需要對登機橋進行動態調度，登機橋調度包括對近機位廊橋和遠機位登機梯的調度。本文所提方法基于如下假設：

(1) 機場為單跑道；

(2) 登機橋數量一定，即機場根據當天監控系統，實時統計出可用登機橋，且登機橋數量滿足當天航班需求；

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

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

(5) 停靠在相鄰兩個登機橋的航班滿足安全的距離。

1.1 符號表

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

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

xik：第i個航班停靠在第k個登機橋上，則xik=1，否則xik=0；

Wik：航班i預調度在登機橋k的作業時間；

Lik：航班i預調度駛離登機橋k的時間；

Nik：登機橋k的無任務時間；

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

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

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

Rk：登機橋k的結束可用時間；

Jik：登機橋k服務航班i的時間；

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

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

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

Uik：航班i從著陸開始停靠到登機橋k所用的時間；

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

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

1.2 航班延誤的機場登機橋再調度模型

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

(2) 航班與登機橋原有對應關系改動數最小 航班與登機橋原有對應關系改動數應降到最小，可將其表示為：

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

參考模型的假設條件，約束條件如下：

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

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

(3) 根據民航局的規定，相同登機橋前序航班任務離開與后續航班任務的停靠之間必須要有一定的時間間隔，以防止航班發生碰撞等現象。

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

(7)

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

Lik-Wik≥Jik

(8)

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

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

(9)

(6) 由于受登機橋端口高度和航班機艙高度的約束，小型航班只能停靠小型登機橋，中型登機橋可以停靠中、小型航班，大型登機橋可以停靠大、中、小三種航班。即航班類型只能小于等于需停靠的登機橋的類型。

Ci≤xikBk

(10)

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

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

(11)

目標函數表示為調度員在已知延誤航班信息的基礎上，以調度到遠機位的航班數、航班登機橋原有對應關系的改動數及乘客進港所用時長加權之和最小。登機橋再調度模型的目標函數為：

minF=αF1+βF2+χF3

(12)

式中:α=0.3，β=0.3，χ=0.4，代表每個子任務的權重。不管是航空公司還是機場，最終目的都是服務乘客，所以權重應適當大一些。

2 改進的人工蜂群算法

算法與登機橋再調度模型的映射關系如表1所示。

2.1 構造食物源編碼

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

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

2.2 種群初始解

種群初始解的質量直接決定了最終解的質量高低，種群初始解分布越均勻，范圍越大，就會更容易產生最優解。

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

步驟1：讀取登機橋原調度方案，刪除延誤航班的登機橋預調度方案。

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

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

步驟4：判斷FN集合是否再無取值可能，如果無取值結果，則輸出相應的延誤航班的登機橋再調度方案，否則跳轉至步驟3繼續往下執行。

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

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

2.3 適應度評價函數

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

2.4 改進局部搜索機制

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

原始logistic混沌映射為：

xk+1=μxk(1-xk)

(14)

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

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

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

(15)

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

圖2 式(14)混沌系統

圖3 式(15)混沌系統

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

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

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

yk=xgbest+xk

(16)

產生新食物源的更新公式為Vik：

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

(17)

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

式中：iter是當前迭代次數，MCN為總迭代次數。

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

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

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

(19)

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

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

圖4 改進ABC算法的流程圖

3 仿真實驗及分析

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

表2 航班信息表

續表2

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

表3 登機橋類型及停靠用時 min

登機橋預調度方案如表4所示。

表4 登機橋預調度方案

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

表5 航班延誤信息表

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

圖5 目標函數收斂曲線

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

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

表6 登機橋再調度方案

分析實驗結果表明：

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

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

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

表7 預調度的遠機位登機梯安排方案

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

4 結 語

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