曾 琛，王潤東

(1.中國民用航空飛行學(xué)院 新津分院，四川 新津 611431；2.中國民用航空飛行學(xué)院，四川 廣漢 618307)

0 引言

民航機場是航空運輸鏈的起點、中轉(zhuǎn)點及終點，而機場停機位又作為其中生產(chǎn)工作的重要設(shè)施之一，是飛機在地面活動的中心[1]。因此，機場停機位分配問題是機場地面工作的核心任務(wù)，是現(xiàn)階段提高航空運輸效率與運輸質(zhì)量的一個關(guān)注熱點。停機位分配問題是一個多目標(biāo)、多約束條件的優(yōu)化問題，復(fù)雜且多變，沒有唯一的分配方案，只有在具體限定條件下的最優(yōu)解?，F(xiàn)階段我國大多數(shù)機場主要依靠人工經(jīng)驗來進行機位分配，分配效率較低[2]。機場運營者為了有效地管理和利用機位等關(guān)鍵資源，需要采納更加科學(xué)系統(tǒng)的理論可行性方案，跟上現(xiàn)代化民航運輸業(yè)不斷發(fā)展的腳步[3]。

目前利用遺傳算法研究的眾多問題中，主要出現(xiàn)了兩個問題，第一個是傳統(tǒng)的遺傳算法在計算過程中，計算的執(zhí)行效率十分低下，針對此問題現(xiàn)在主要的解決辦法是通過優(yōu)化計算機硬件的方法對遺傳算法的計算效率進行優(yōu)化，主要將算法移植到大型的服務(wù)器上計算運行；另一個問題就是遺傳算法的收斂速過慢或者結(jié)果中無法找到最優(yōu)解，針對此問題不少專家及研究者通常對遺傳算法的因子和整體計算結(jié)構(gòu)進行相應(yīng)的改進。以上措施在遺傳算法的實施過程中取得了顯著的成效，而且改進的遺傳因子和計算結(jié)構(gòu)框架也慢慢的被廣大學(xué)者認(rèn)可，也代表著未來遺傳算法的發(fā)展方向。

現(xiàn)階段，國內(nèi)外學(xué)者普遍認(rèn)為解決機場機位資源緊缺的方法可以歸納為兩種：第一種方法是通過結(jié)合自動化設(shè)備使用，制定、采納一系列科學(xué)合理的優(yōu)化措施來解決現(xiàn)有機位資源的分配；第二種方法從根本出發(fā)，直接新建或擴建機場來緩解現(xiàn)有壓力，但該措施需要投入大量資源與時間成本[4]。

Abdullah Aktel(2017年)使用概率方法作為期望準(zhǔn)則，并比較了禁忌搜索算法與模擬退火算法性能，對其他學(xué)者的研究有借鑒作用[1]。2020年，Ramazan兼顧旅客和航空公司的利益，采用模擬退火算法對模型求解，以此減少管制員進行機位分配的時間[5-6]。

2018年，馬思思，唐小衛(wèi)等人基于Flexsim仿真軟件建立飛行區(qū)仿真模型，提升了航班運行效率，縮短了平均延誤時間[7]。2020年袁媛等人綜合考慮信息可視化與文獻計量方法，用可視化的方式分析機位分配的進程與基礎(chǔ)，一定程度上明確機位分配研究問題的發(fā)展趨勢[8]。

1 停機位分配建模

航站樓為飛機和乘客提供服務(wù)的能力主要取決于停機位的分配是否合理，停機位分配問題考慮主要基于停機位的可用性和兼容性、其大小和容量、操作規(guī)則等[9]。在實時執(zhí)行過程中，當(dāng)航班時刻表的意外變化擾亂機位分配時，機位分配問題變得更加復(fù)雜。因此，機位靜態(tài)分配模型應(yīng)能夠應(yīng)對航班動態(tài)變化，并及時提供解決方案，以滿足實時動態(tài)調(diào)整的需求[10]。

在第一個航班到達之前、兩個后續(xù)航班起飛和到達之間以及最后一個航班起飛之后，停機位處于空閑狀態(tài)。當(dāng)空閑時間均勻分布在各停機位時，為實現(xiàn)停機位空閑時間均勻分布而引入的優(yōu)化目標(biāo)是按照進程時間順序最小化空閑時間的范圍和方差。

本文首先假設(shè)停機位類型相同，并且為所有航班提供相同的保障服務(wù)。對最小化停機位空閑時間范圍和方差問題進行建模，使其可以通過整數(shù)松弛線性規(guī)劃(LPR)方法求解。多項式算法可以將LPR解轉(zhuǎn)換為停機位之間的可行分配問題解[11]。針對不同保障服務(wù)水平的停機位分配問題，本文提出了一種利用分配問題特定搜索的遺傳算法，該算法與以往的單通道啟發(fā)式算法相比，遺傳算法在適應(yīng)實時分配方面表現(xiàn)良好，計算出的停機位分配方案接近最優(yōu)并且為機位動態(tài)變化提供了優(yōu)化方案[12]。

1.1 約束條件

停機位分配問題在實際運行過程中受諸多外界客觀因素的影響，存在有很強的不確定性和不穩(wěn)定性，并不受預(yù)先計劃分配方案的絕對控制，而是一個實時的結(jié)果，受到多方因素制約。其主要約束條件如下所示：

1)唯一性約束：一個停機位只能為一個航班提供服務(wù)。對于航班i，yik來表示航班i與停機位k之間的配置關(guān)系，yik=1當(dāng)且僅當(dāng)分配航班i到停機位k中，否則yik=0。該約束條件如式(1)所示：

(1)

2)獨占性約束：機位被使用期間不能同時為其他航班提供服務(wù)。

3)航班優(yōu)先級約束：專機優(yōu)先于其他航班等約束。

4)機位安全間隔與緩沖時間約束：使用同一機位的前后兩架航班之間必須產(chǎn)生一定安全間隔時間以此來避免潛在飛行沖突，此外相鄰機位之間也需要保持一定間隔來實現(xiàn)航班進出的流暢性，避免飛行意外，保證飛行安全。

5)機型與機位匹配約束：機場停機位有大、中、小等級之分，匹配性發(fā)生偏差便會影響后繼的飛機地面工作，降低機場運行效率。一般應(yīng)盡量減少小型航班停放大型機位。

1.2 模型建立

首先對模型之中涉及到的各項數(shù)據(jù)進行說明：

1)航班數(shù)據(jù)：

(1)設(shè)當(dāng)天停放該機場的配對航班共有N對，HB為配對航班的集合，表示HB={hi|0

(2)Aij表示配對航班i計劃進入停機位j的時間；

(3)Bij表示配對航班i計劃離開停機位j的時間；

(4)CXi表示第i個配對航班所使用的飛機型號；

(5)Wi表示第i個配對航班的旅客數(shù)量。

2)停機位數(shù)據(jù)：

(1)設(shè)某機場共有M個停機位，其中M

(2)JKj表示第j個機位允許?？康娘w機型號集合；

(3)Dj表示第j個停機位距離航站樓的距離。

3)其他數(shù)據(jù)：

(1)yij表示航班分配結(jié)果，如果第i次航班分配到第j個機位則其值為1，否則為0；

(2)FT表示兩次航班使用同一個機位的安全時間間隔；

(3)Fij表示同一個停機位上兩個相鄰航班之間的空閑時間。

Dj表示第j個停機位距離航站樓距離，Wi表示第i個配對航班的旅客數(shù)量，yij表示航班分配結(jié)果，那么在停機位j停放的航班人數(shù)為：

(2)

n表示機位j上分配的航班配對數(shù)量，則所有旅客登機距離表示為：

(3)

綜上設(shè)旅客總登機距離最少化目標(biāo)函數(shù)為f1，則：

(4)

Aij表示配對航班i計劃進入停機位j的時間，Bij表示配對航班i計劃離開停機位j的時間；Fij表示同一個停機位上兩個相鄰航班之間的空閑時間，即Fij=Aij-Bij表示時間差。設(shè)停機位空閑時間均勻目標(biāo)函數(shù)為f2，則：

(5)

基于上述分析的假設(shè)條件、定義以及單個目標(biāo)函數(shù)，獲得機場應(yīng)進行的機位分配模型：

1)模型目標(biāo)函數(shù)：

(6)

2)模型約束條件：

yij∈{0，1}，?i∈HB，?m∈TJW

(7)

(8)

CXi∈JKj，?(i，j)∈{(i，j)|yij=1}

(9)

Aij-Bij≥FT，?i∈HB，?m∈TJW，且Aij，Bij≥0

(10)

1.3 停機位空閑時間方差模型

假設(shè)N架飛機計劃在某一時間段內(nèi)到達機場，并且其預(yù)期落地時間Aj和地面保障時間Gj是事先已知的。航班j的起飛時間則為Dj=Aj+Gj。在一般的情況下，假設(shè)航班按照其到達時間的升序排序，則i>j，并且Ai>Aj，M個停機位中，停機位k在Bk和Fk時間節(jié)點內(nèi)被占用[13]。

在靜態(tài)分配階段，盡可能均勻地利用空閑時間分配停機位，為了便于說明，規(guī)定：

Xj，k：如果航班j分配給停機位k，則等于1，否則為0；Ej，k：航班j進入停機位k的時間；Lj，k：航班j離開停機位k的時間；Sj，k：停機位k在航班j到達前的空閑時間；SN+1，k：最后一架飛機推出后停機位k的空閑時間；最后，Pj，k用于表示停機位的不同狀態(tài)：如果在滿足所有限制條件下，將航班j分配給停機位k，則Pj，k=1。使用模型P1優(yōu)化停機位空閑時間的方差。

模型P1：

(11)

(12)

E1，k=max{A1X1，k，Bk}k=1，…，M

Ej，k=max{AjXj，k，Lj-1，k}j=2，…，N，k=1，…，M

(13)

Lj，k=Ej，k+GjXj，kj=1，…，N，k=1，…，M

(14)

S1，k=E1，k-Bkk=1，…，M

Sj，k=Ej，k-Lj-1，kj=2，…，N，k=1，…，M

(15)

SN+1，k=Fk-LN，kk=1，…，M

(16)

Xj，k=0或1j=1，…，N，k=1，…，M

(17)

Ej，k，Lj，k，Sj，k，SN+1，k≥0

j=1，…，N，k=1，…，M

(18)

1.4 停機位空閑時間范圍模型

由于停機位的總可用時間和飛機的地面保障時間是恒定的，因此機位的總空閑時間恒定且與飛機的分配位置無關(guān)。因此，機位空閑時間的方差優(yōu)化可用式(1)表示[14]。當(dāng)Xj，k=0時，Sj，k=0稱為虛擬空閑時間，此時間不會影響式(1)的大小。實際分配次數(shù)為N，非虛擬空閑時間為N+M。如果航班j剛好在航班i離開機位k后到達，即Xi，k=Xj，k=1，Li，k=Lj-1，k=Di，Ej，k=Aj，此時會出現(xiàn)零但非虛擬空閑時間Sj，k=Aj-Di=0。可以用合適的線性約束代替用于監(jiān)控目前分配航班j之前的最后實際分配的非線性遞歸函數(shù)(13)。

綜上，最小化空閑時間范圍的優(yōu)化模型P2如下：

模型P2：

minSmax-Smin

(19)

s.t.Smax≥Sj，kj=1，…，N，k=1，…，M

(20)

Smin≤Sj，k+(1-Xj，k)Zj=1，…，N，k=1，…，M

(21)

Smax，Smin≥0

(22)

Z是一個用于避免不影響最大空閑時間的虛擬空閑時間。其值代表某個機位的最大可用時間，即：

(23)

1.5 停機位空閑時間方差二元線性模型

如果航班i和j連續(xù)分配給同一個停機位，則Yi，j=1，其中i=1，…，N-1，j=i+1，…，N。由于停機位是相同的，因此上一架航班i所分配的機位對于確定是否在航班i之后立即分配航班j不再重要。對于某段時間內(nèi)的首末班航班，則規(guī)定如果航班j是分配給某停機位的第一個航班，則Y0，j=1，其中j=1，…，N；如果航班i是分配給的某停機位的最后一個航班，則Yi，N+1=1其中i=1，…，N[15]。

由于停機位的服務(wù)水平是相同的，因此所有停機位在0和H時間單位之間可用，即Bk=0?k，F(xiàn)k=H?k。如果某一飛機被連續(xù)分配到同一個停機位，假設(shè)Ii，j是航班i和j之間的空閑時間，則：

(24)

這里，Z用于表示將連續(xù)的航班i和j分配給同一個停機位是不可行的。因此，為第一次和最后一次分配的空閑時間定義I0，j和Ii，N+1：

I0，j=Ajj=1，…，N

(25)

Ii，N+1=H-Dii=1，…，N

(26)

綜上，最優(yōu)化空閑時間方差的純二元線性模型P3如下：

模型P3：

(27)

(28)

(29)

(30)

(31)

(32)

Yi，j=0或1i=0，1，…，N，j=i+1，…，N+1

(33)

式(28)表明，如果所有航班都可以有可用的停機位服務(wù)，則將有N+M個空閑時間?？紤]到最多有M個停機位可供使用，約束條件(29)和(30)分別保證每個停機位最多有一個航班可以是第一個到達的航班，最多一個可以是最后一個離開的航班[16]。

另一方面，式(31)和(32)表明，只有一架飛機可以分別分配在航班j之前和航班i之后。最后，使用目標(biāo)函數(shù)(17)選擇N+M個空閑時間最小化空閑時間的方差。模型P3具有(N+1)(N+2)/2個二元變量和2N+3個約束條件，由于模型P3具有線性目標(biāo)函數(shù)，因此可以通過LPR進行優(yōu)化求解，即：

模型P4：

minSmax-Smin

(34)

s.t.Smax≥Ii，jYi，ji=0，…，N，j=i+1，…，N+1

(35)

Smin≤Ii，jYi，ji=0，…，N，j=i+1，…，N+1

(36)

Smax，Smin≥0

(37)

以上討論的優(yōu)化模型針對相同保障水平的停機位，某些停機位可能不適用于某些航班，或者可能無法提供所需的保障服務(wù)。在任何情況下，當(dāng)停機位不相同時，還應(yīng)確定航班分配到的停機位的特征。

假設(shè)航班i和航班j被連續(xù)分配到停機位k，則Yi，j，k=1，其中i=1，…，N-1；j=i+1，…，N；k=1，…，M，因此，Y0，j，k和Yi，N+1，k為第一架和最后一架分配給停機位k的航班，則空閑時間段為II，j，k為被分給停機位k的航班i和航班j的空閑時間，因此：

(38)

同樣，第一次和最后一次分配給停機位k的航班的空閑時間定義如下：

(39)

(40)

為了便于提高計算效率，純二進制線性規(guī)劃如模型P5所示。

模型P5：

(41)

(42)

(43)

(44)

(45)

i=0，…，N-1；j=i+1，…，N；k=1，…，M

(46)

Yi，j，k=0或1

i=0，…，N；j=i+1，…，N+1；k=1，…，M

(47)

目標(biāo)函數(shù)(41)和(42)是P3的目標(biāo)函數(shù)(27)和公式(28)的簡單擴展。現(xiàn)在必須單獨考慮每個停機位，以確定第一次分配的飛機，即約束(43)。等式(44)和(45)是等式(31)和(32)的擴展，它們分別保證在一架航班之前和之后只能分配一架航班。

2 基于遺傳算法的純二進制線性規(guī)劃模型

無論飛機何時起飛或降落，停機位的狀態(tài)都將發(fā)生變化，如果更新后的飛行計劃未對當(dāng)前機位分配產(chǎn)生影響，則目前的機位分配方案仍然有效。盡管模型P5的目標(biāo)函數(shù)傾向于最小化中斷目前機位分配方案的可能性，但產(chǎn)生重大飛行計劃改變時，則需要重新對機位分配進行計算[17]。因此，我們需要考慮使用遺傳算法(GA)對動態(tài)的機位分配進行實時計算。

我們使用N位整數(shù)字符串，其中第j位的值表示為為航班j分配的停機位的編號。

染色體如圖1所示，其中3號停機位分配給航班1，6號停機位指定給航班2，M號登機門指定給航班3等等；π∈{1，2，…，M}N中可能出現(xiàn)一個不可行的解，對于機位分配的解，至少有一個航班違反了停機位限制條件或被分配給當(dāng)已前占用的停機位[18]。即，如果存在j，對于任意i，使得Pj，π(j)=0，或者Ai≤Aj≤Di，π(i)=π(j)，在處理不可行解時，我們調(diào)整了只產(chǎn)生和保留可行父本和子代的措施。

2.1 適應(yīng)度函數(shù)構(gòu)建

根據(jù)Ii，j，k構(gòu)建有效的適應(yīng)度函數(shù)如下，該函數(shù)與最小化空閑時間的方差函數(shù)的目標(biāo)兼容：

δo，k=δN+1，k=1 ?k

jP=max{i：0≤i

(48)

上述函數(shù)中δjP，kδj，k用于監(jiān)控連續(xù)分配到同一停機位的兩個航班(jP和j)。邊界條件δ0，k=δN+1，k=1，使適應(yīng)度函數(shù)能夠評估某段時間范圍內(nèi)開始和結(jié)束時的機位空閑時間。即適應(yīng)度越低，機位分配方案優(yōu)化效果越好。

2.2 父本選擇、交叉和變異過程

選擇標(biāo)準(zhǔn)的二進制聯(lián)賽選擇算法進行父本選擇。首先將整體形成兩個父本群體，每個群體由兩個以相同概率隨機抽取的個體組成。為了防止高度獨立的個體主導(dǎo)選擇的過程，通過允許多樣性并控制收斂速度的方式減小選擇壓力。從兩個群體池里分別選擇兩個最適合的個體作為父本。不僅每個群體池中的個體數(shù)量增多會增加選擇更多合適個體的機會，而且二進制的選擇方法效率更高[19]。

以下交叉方法適用于從雙親中產(chǎn)生一個子代。在1和N-1之間選擇一個隨機長度L。然后從第一個父代復(fù)制第一個L染色體，從第二個父代復(fù)制最后一個N-L染色體，生成一個子代。交叉后，如果新生成的解不可行，則對其執(zhí)行變異過程[20]。在遺傳算法的原始規(guī)則中，變異算子用于引入多樣性，但在這里它用于修復(fù)染色體。導(dǎo)致不可行性的第一條染色體從其當(dāng)前值突變[21]。在1和M之間均勻生成的隨機數(shù)確定所選染色體的新值。初步實驗表明，較高的突變率不會增加修改不可行方案的概率。因此，選擇較小的變異率(每串最大進行M次試驗)，以減小此運算過程對總運行時間的影響。

初始種群是隨機生成的，其大小由分配問題的參數(shù)確定，即S=NM。對于所考慮字符串的第j位數(shù)字，隨機分配一個可行的解。當(dāng)目前部分解不能形成可行的完整解時，就會丟棄該部分解并啟動新字符串重新計算。如果初始種群由可行解和不同的父本構(gòu)建，遺傳過程(交叉和突變)將繼續(xù)進行，直到生成250NM的非重復(fù)子代。穩(wěn)態(tài)替換方法用于消除適應(yīng)度值最高的個體，并保持種群的大小不變[22]。

3 基于遺傳算法的機位分配模擬仿真

3.1 模型性能測試

假設(shè)在時間單位為5分鐘，飛機進入停機位的時間均勻地在15到36個時間單位之間變化。設(shè)有小型停機位5個；中型停機位10個；大型停機位20個。每個停機位的平均服務(wù)的航班數(shù)為5.15架次。小型、中型和大型機位的平均飛機?？看螖?shù)分別為26.125次、52.25次和105.417次。3種類型的機位總體平均利用率分別為45.725%、66.548%和88.871%。

首先，我們假設(shè)所有停機位類型相同，并且可以應(yīng)用模型P3分配計劃航班。根據(jù)設(shè)定給出了機位分配問題的變量和約束條件的數(shù)量、迭代次數(shù)和總計算時間以及優(yōu)化方案的目標(biāo)值(平方和、方差和空閑時間范圍)。從結(jié)構(gòu)上看，變量和約束條件的數(shù)量主要取決于航班和停機位的數(shù)量。

表1顯示，單純形迭代的次數(shù)隨著停機位利用率的增加而減少。在所有問題中，ANOVA的F檢驗表明具有5%顯著性水平的利用率水平具有顯著影響，即F0.05，2，21=3.47。對于具有較小P值的中型停機位和大型停機位分配問題，其影響變得更加顯著，即利用率水平顯著，顯著性水平為1%，F(xiàn)0.01，2，21=5.78。

表1 不同服務(wù)水平停機位的機位分配模型性測試性能結(jié)果

3.2 仿真結(jié)果

最后，使用真實數(shù)據(jù)評估該基于遺傳算法的機位分配方案，對應(yīng)于四川綿陽南郊機場2020年8月國內(nèi)航班機位的一周運行數(shù)據(jù)。日常維護工作表和停機位停機位時刻表用于提取飛行時刻表、地面指揮員的初始分配和實時運行期間的最終機位分配。管制員在初始階段主要考慮飛機尺寸、維修要求和飛機推出滑行等因素，例如，在航站樓的8個停機位中，停機位1和2不能用于寬體飛機(A330、B747和B777等)。每架飛機也有不同的地面保障要求。例如，B747飛機起飛前至少需要75分鐘，抵達后至少需要60分鐘，而B737飛機分別需要45分鐘和30分鐘。與此同時，一架飛機可能從前天起一直停留，地面停留時間超過三小時。指揮員則須考慮將這種類型的飛機安排到一個偏遠機位。根據(jù)實際實現(xiàn)的飛機到達和起飛時間，管制員可以通過評估滑行道擁堵和遠程停機位的使用來修改初始分配。

在7天的運行期間，四川綿陽南郊機場每天的航班數(shù)分別為72、77、82、72、83、64和79班。在靜態(tài)階段，第一到第七天必須分別將6架、8架、11架、5架、6架、3架和7架飛機分配到偏遠機位，并在實時操作期間將6架，5架、六架、3、3架、2架和3架飛機從近機位推出到遠機位。

我們使用相同的飛行計劃來準(zhǔn)備初始分配，然后結(jié)合實際(實現(xiàn)的)飛行計劃來評估解決方案的魯棒性。如果任務(wù)的空閑時間不足以吸收飛行計劃中的變化，則假設(shè)相應(yīng)的飛機按照目前的做法被拖到偏遠機位。首先，遺傳算法執(zhí)行較高的運算效率，平均需要96秒(范圍為57～143秒)的CPU運算來生成平均大小為594個不同解的總體。如表2所示。在最壞的情況下，計算出來的分配解離最優(yōu)性只有0.2%。

表2 基于遺傳算法的機位分配在仿真模擬情況下的性能表現(xiàn)

與目前七天實際的機位分配做法相比，在實際實施期間，共有四架飛機最初被分配到遠機位，共有五架飛機被拖曳。相應(yīng)地，使用最佳遺傳算法給出的機位分配解決方案，靜態(tài)階段的平均改善率為92.15%，動態(tài)階段的改善率為78.57%。

4 結(jié)束語

民航業(yè)的不斷發(fā)展進步，有關(guān)機位分配問題的研究不斷受到重視。一個機場若不重視機位資源的有效合理安排，那么其發(fā)展會從根本上受到制約，更不必談到實現(xiàn)“四型”機場的目標(biāo)。本文主要針對民航運輸機場中的停機位資源分配問題進行研究，在對國內(nèi)外相關(guān)機位分配研究的分析基礎(chǔ)之上確立本文的模型，并且采用遺傳算法來實現(xiàn)該模型的求解。提出了非線性數(shù)學(xué)模型以提供魯棒性更高的飛機停機位分配模型，使停機位的空閑時間分布最小。本文提出了一個具有決策變量的框架將非線性二元模型轉(zhuǎn)換為具有最小空閑時間范圍或方差的等價線性二元模型。與四川綿陽南郊機場實際的機位分配方案相比，靜態(tài)和動態(tài)階段的平均改善率分別為92.15%和78.57%。

首先，具有相同服務(wù)水平的停機位分配模型可以直接用于實踐。一些機場的停機位可以分組在一起，這樣一個大的分配問題就可以分解成具有“相同屬性停機位”的小分配問題。其次，遺傳算法可以非常高效地為停機位分配問題提供實時響應(yīng)計算。當(dāng)航班時刻表的重大變化打亂了初始分配方案時，遺傳算法可快速的計算出接近最優(yōu)的替代分配方案。最后，遺傳算法可以與機位分配專家系統(tǒng)集成，以滿足人與人之間的系統(tǒng)交互，跨航空公司相關(guān)功能的標(biāo)準(zhǔn)化數(shù)據(jù)庫以及用于優(yōu)化的模型和程序。規(guī)劃和運行環(huán)境之間的聯(lián)系將為維護停機位分配和航班時刻表提供一個高效的系統(tǒng)。