基于遺傳算法的動(dòng)態(tài)飛機(jī)停機(jī)位分配模型研究

曾 琛，王潤(rùn)東

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

0 引言

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

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

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

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

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

1 停機(jī)位分配建模

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

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

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

1.1 約束條件

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

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

(1)

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

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

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

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

1.2 模型建立

首先對(duì)模型之中涉及到的各項(xiàng)數(shù)據(jù)進(jìn)行說(shuō)明：

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

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

(2)Aij表示配對(duì)航班i計(jì)劃進(jìn)入停機(jī)位j的時(shí)間；

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

(4)CXi表示第i個(gè)配對(duì)航班所使用的飛機(jī)型號(hào)；

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

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

(1)設(shè)某機(jī)場(chǎng)共有M個(gè)停機(jī)位，其中M

(2)JKj表示第j個(gè)機(jī)位允許?？康娘w機(jī)型號(hào)集合；

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

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

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

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

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

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

(2)

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

(3)

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

(4)

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

(5)

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

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 停機(jī)位空閑時(shí)間方差模型

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

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

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

模型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 停機(jī)位空閑時(shí)間范圍模型

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

綜上，最小化空閑時(shí)間范圍的優(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是一個(gè)用于避免不影響最大空閑時(shí)間的虛擬空閑時(shí)間。其值代表某個(gè)機(jī)位的最大可用時(shí)間，即：

(23)

1.5 停機(jī)位空閑時(shí)間方差二元線性模型

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

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

(24)

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

I0，j=Ajj=1，…，N

(25)

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

(26)

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

模型P3：

(27)

(28)

(29)

(30)

(31)

(32)

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

(33)

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

另一方面，式(31)和(32)表明，只有一架飛機(jī)可以分別分配在航班j之前和航班i之后。最后，使用目標(biāo)函數(shù)(17)選擇N+M個(gè)空閑時(shí)間最小化空閑時(shí)間的方差。模型P3具有(N+1)(N+2)/2個(gè)二元變量和2N+3個(gè)約束條件，由于模型P3具有線性目標(biāo)函數(shù)，因此可以通過(guò)LPR進(jìn)行優(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)化模型針對(duì)相同保障水平的停機(jī)位，某些停機(jī)位可能不適用于某些航班，或者可能無(wú)法提供所需的保障服務(wù)。在任何情況下，當(dāng)停機(jī)位不相同時(shí)，還應(yīng)確定航班分配到的停機(jī)位的特征。

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

(38)

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

(39)

(40)

為了便于提高計(jì)算效率，純二進(jìn)制線性規(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)的簡(jiǎn)單擴(kuò)展?，F(xiàn)在必須單獨(dú)考慮每個(gè)停機(jī)位，以確定第一次分配的飛機(jī)，即約束(43)。等式(44)和(45)是等式(31)和(32)的擴(kuò)展，它們分別保證在一架航班之前和之后只能分配一架航班。

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

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

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

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

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

根據(jù)Ii，j，k構(gòu)建有效的適應(yīng)度函數(shù)如下，該函數(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ù)分配到同一停機(jī)位的兩個(gè)航班(jP和j)。邊界條件δ0，k=δN+1，k=1，使適應(yīng)度函數(shù)能夠評(píng)估某段時(shí)間范圍內(nèi)開始和結(jié)束時(shí)的機(jī)位空閑時(shí)間。即適應(yīng)度越低，機(jī)位分配方案優(yōu)化效果越好。

2.2 父本選擇、交叉和變異過(guò)程

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

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

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

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

3.1 模型性能測(cè)試

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

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

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

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

3.2 仿真結(jié)果

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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