閆 萍，劉夢詩

(沈陽航空航天大學(xué)經(jīng)濟(jì)與管理學(xué)院，遼寧 沈陽 110136)

1 引言

近年來，我國民航運輸業(yè)發(fā)展迅速，機(jī)場急劇增長的航班量增加了場面資源的運行負(fù)荷，導(dǎo)致場面交通擁堵現(xiàn)象日益凸顯，不僅降低了旅客服務(wù)水平，而且增加了航空器的運行成本。停機(jī)位是機(jī)場地面作業(yè)的重要資源，是進(jìn)港航班的運行終點和離港航班的運行起點。機(jī)場停機(jī)位分配問題(airport gate assignment problem，簡稱AGAP)是實現(xiàn)航班快速安全地?？?，保證航班之間的有效銜接，提高整個機(jī)場系統(tǒng)容量和服務(wù)效率的關(guān)鍵環(huán)節(jié)。因此，對停機(jī)位優(yōu)化分配的研究具有重要理論意義和實用價值[1-3]。

停機(jī)位分配問題的優(yōu)化目標(biāo)主要是旅客步行距離最小、停機(jī)位的空閑時間最小、停機(jī)位利用率最大等。由于停機(jī)位分配問題具有NP-hard特性，因此很難在有限的時間內(nèi)獲得大規(guī)模問題的最優(yōu)解。目前，國內(nèi)外學(xué)者對停機(jī)位分配問題的研究主要包括數(shù)學(xué)規(guī)劃和智能優(yōu)化兩類方法。數(shù)學(xué)規(guī)劃方法首先構(gòu)建停機(jī)位分配問題的數(shù)學(xué)規(guī)劃模型，再通過精確算法[4]或者借助數(shù)學(xué)優(yōu)化軟件[5-7]求解模型，進(jìn)而得到問題的優(yōu)化解。應(yīng)用于解決機(jī)場停機(jī)位分配問題的智能優(yōu)化方法主要包括：遺傳算法[8-10]、禁忌搜索算法[11-12]、蟻群算法[13]、粒子群算法[14]、領(lǐng)域搜索啟發(fā)式算法[15-16]等。

綜上，目前的研究主要以停機(jī)位靜態(tài)預(yù)分配計劃為研究對象，通過優(yōu)化模型與算法，得到較為完整的停機(jī)位分配方案。較少的文獻(xiàn)考慮到航班延誤情況下的停機(jī)位動態(tài)再分配問題[2]，并且在實際的停機(jī)位分配過程中，需要平衡航空公司、機(jī)場和旅客等多方利益，探尋綜合考慮多目標(biāo)優(yōu)化的求解方法有待研究。因此，本文首先給出停機(jī)位實時再分配的多目標(biāo)優(yōu)化數(shù)學(xué)模型。其次，提出一種改進(jìn)的免疫遺傳求解算法，將免疫系統(tǒng)中抗體多樣性的保持機(jī)制引入遺傳算法中，有效提升算法的全局搜索能力。仿真結(jié)果驗證了所提出的模型和算法能夠得到合理有效的停機(jī)位再分配方案。

2 停機(jī)位再分配數(shù)學(xué)模型

停機(jī)位分配問題需要綜合考慮航班機(jī)型、停機(jī)位類型和航班進(jìn)、離港時刻等因素，在給定的作業(yè)時間窗內(nèi)，為執(zhí)行每個航班的飛機(jī)分配適當(dāng)?shù)耐C(jī)位，以保證機(jī)場客貨的有效銜接。停機(jī)位再分配模型是在停機(jī)位靜態(tài)預(yù)分配優(yōu)化方案的基礎(chǔ)上進(jìn)行實時動態(tài)調(diào)度。

2.1 模型參數(shù)的定義

為了便于模型的描述，首先給出構(gòu)造模型所需的符號、參數(shù)和變量的含義。

N—航班集合；

M—停機(jī)位集合；

dkl—停機(jī)位k到停機(jī)位l的距離；

hk—分配到停機(jī)位k的航班進(jìn)離港場面滑行距離，即航班進(jìn)港時從降落跑道到停機(jī)位k的滑行距離與航班離港時從停機(jī)位k到起飛跑道的滑行距離之和；

T—相繼分配給同一停機(jī)位的連續(xù)兩個航班之間的最小安全時間間隔；

T′—停機(jī)位的可用運行時間；

ui—航班i的航空器類型；

vk—停機(jī)位k允許停放的最大機(jī)型；

H—一個大正常數(shù)；

此問題的決策變量為：

2.2 目標(biāo)函數(shù)

以旅客的角度優(yōu)化停機(jī)位配置，指標(biāo)為旅客轉(zhuǎn)機(jī)所需要移動的距離最小。從航空公司和機(jī)場的角度優(yōu)化停機(jī)位分配，一方面，航班在機(jī)場場面的滑行距離盡量短，才能節(jié)省燃料的消耗，同時增大機(jī)場場面的容量；另一方面，提高停機(jī)位的使用效率，加快機(jī)場機(jī)位的周轉(zhuǎn)速度，以優(yōu)化停機(jī)位資源的利用率。因此，停機(jī)位靜態(tài)預(yù)分配模型的目標(biāo)函數(shù)為

(1)

(2)

(3)

停機(jī)位再分配模型的優(yōu)化目標(biāo)為多目標(biāo)函數(shù)(4)，即在停機(jī)位預(yù)分配目標(biāo)函數(shù)f1的基礎(chǔ)上，增加了航班停機(jī)位再分配的魯棒性目標(biāo)。當(dāng)發(fā)生航班延誤或取消時，會造成對原有航班停機(jī)位分配方案的擾動，因此應(yīng)盡量減少受干擾的航班數(shù)目。w1和w2分別是目標(biāo)函數(shù)兩部分的權(quán)重系數(shù)。

(4)

2.3 約束條件

停機(jī)位動態(tài)再分配問題需要考慮的約束條件與靜態(tài)預(yù)分配時相同，主要包括下面幾個方面

(5)

(6)

(7)

yijk+yjik≤1， ?i，j∈N，?k∈M

(8)

(9)

ui-vk≤+H(1-xik)，?i∈N，?k∈M

(10)

式(5)表示每個航班只能分配一個停機(jī)位。式(6)表示每個航班在同一個停機(jī)位上，最多只有一個直接相鄰的后繼航班。式(7)表示每個航班在同一個停機(jī)位上，最多只有一個直接前驅(qū)航班。式(8)和式(9)表示聯(lián)合確定yijk的值，當(dāng)兩個航班連續(xù)使用同一停機(jī)位時，相鄰航班必須要滿足一定的安全時間間隔T，以保證場面作業(yè)的安全性。式(10)表示航班機(jī)型與停機(jī)位類型的匹配約束，停機(jī)位只能停放允許的航班機(jī)型。

3 免疫遺傳算法設(shè)計

遺傳算法通過自然選擇、遺傳和變異等作用機(jī)制，實現(xiàn)各個個體適應(yīng)性的提高，是一種高效的自適應(yīng)進(jìn)化搜索算法。但大量的實踐和研究表明，標(biāo)準(zhǔn)遺傳算法存在局部搜索能力差和“早熟”的缺陷。免疫算法是受生物免疫系統(tǒng)的啟示而設(shè)計出來的一種新型的智能搜索算法，具有較強(qiáng)的魯棒性。因此，本文將免疫系統(tǒng)中抗體多樣性的保持機(jī)制引入遺傳算法中，避免遺傳算法的過早收斂，綜合遺傳算法和免疫算法的優(yōu)點，以提升混合算法的搜索性能。

3.1 個體編碼

求解停機(jī)位分配優(yōu)化問題的免疫遺傳算法采用一種基于自然數(shù)編碼的策略。算法個體表示航班序列，個體編碼的總長度等于所有航班的數(shù)目總和。個體中的每一個基因位代表一個航班，表示航班的停機(jī)位指派優(yōu)先級順序。在為各航班指派停機(jī)位時，按照航班序列的順序，優(yōu)先為排在前面的航班分配停機(jī)位。對于每一個航班，如果存在多個候選停機(jī)位，則優(yōu)先選擇使得航班的到達(dá)時間與停機(jī)位的最早可使用時間之差最小的停機(jī)位，以提高停機(jī)位的占用效率。

例如，對于有5個航班的停機(jī)位分配問題，其個體編碼為長度是5的行向量(5，2，1，3，4)，代表5個航班的停機(jī)位分配順序。首先，為航班5分配停機(jī)位；然后，對航班2進(jìn)行停機(jī)位指派；以此類推，按照航班序列5→2→1→3→4的順序，完成所有5個航班的停機(jī)位分配過程?；诤桨嘈蛄械淖匀粩?shù)編碼方案，在后續(xù)遺傳操作中可以始終保持個體產(chǎn)生可行解，進(jìn)而提高了算法的執(zhí)行效率。

3.2 初始種群的產(chǎn)生

免疫遺傳算法的初始種群由兩部分組成：首先，由啟發(fā)式規(guī)則產(chǎn)生一些解質(zhì)量比較好的個體加入到初始種群中，用于改進(jìn)初始種群的解質(zhì)量；然后，通過隨機(jī)生成個體的方法產(chǎn)生初始種群中的其它個體，以改善算法初始種群中個體的多樣性。啟發(fā)式規(guī)則產(chǎn)生的初始種群包括：按照航班離港時間升序排列的航班序列、按照航班進(jìn)港時間升序排列的航班序列，以及這兩類個體的鄰域個體。鄰域個體通過交換個體的航班序列中任意兩個基因位置的航班得到。例如，對于包含5個航班的航班序列(5，2，1，3，4)，將第1個和第3個基因位上的航班交換后，得到新的航班序列(1，2，5，3，4)即為原航班序列的一個鄰域個體。

3.3 計算個體密度

在免疫遺傳算法中引入個體密度的概念，將個體密度的計算結(jié)果作為評價個體優(yōu)劣的一個重要標(biāo)準(zhǔn)。個體密度的計算過程用信息熵來描述個體之間的相似度，表示群體中相似可行解的多少。

3.3.1 個體之間的相似度

(11)

其中，

3.3.2 個體的密度

根據(jù)種群中個體之間的相似度，設(shè)計每個個體a的密度值Ca通過式(12)計算

(12)

3.4 計算適應(yīng)度

為了保持群體的多樣性，將個體密度Ca引入適應(yīng)度值的計算過程，以抑制群體中密度高的個體，使目標(biāo)函數(shù)值優(yōu)良且密度較小的個體適應(yīng)度值也越大。對于種群中每個個體a，定義個體的適應(yīng)函數(shù)f′a如式(13)。其中，fa為個體a的目標(biāo)函數(shù)值，參數(shù)k為取值-0.5的常數(shù)。

(13)

3.5 遺傳操作

免疫遺傳算法的選擇和交叉操作采用“君主方案”，即在對群體根據(jù)適應(yīng)度值高低進(jìn)行排序的基礎(chǔ)上，用最優(yōu)個體與其它偶數(shù)位置的所有個體以交叉概率pc進(jìn)行交叉操作，每次交叉產(chǎn)生兩個新的子代個體。在交叉操作后，對新產(chǎn)生的群體以變異概率pm進(jìn)行變異操作，并計算其適應(yīng)度值。

3.5.1 交叉操作

為了較好地保留父代航班序列中的航班相鄰關(guān)系和先后關(guān)系，采用順序交叉操作，具體方法如下：

1)從兩個父代個體P1、P2的編碼中隨機(jī)選擇兩個切點位置X和Y；

2)交換父代個體P1、P2的位置X和Y之間的編碼部分，并分別復(fù)制到子代個體C1、C2的相應(yīng)位置中；

3)按照父代個體的原航班排序，將未排入的航班依次填入子代個體的空基因位中。

圖1描述了父代個體P1=(3，1，6，4，2，5，7)和P2=(6，2，1，5，3，4，7)進(jìn)行順序交叉操作后產(chǎn)生子代個體C1=(6，4，1，5，3，2，7)和C2=(1，5，6，4，2，3，7)的過程。

圖1 順序交叉操作

3.5.2 變異操作

通過隨機(jī)改變個體編碼的某些基因?qū)€體進(jìn)行較小擾動來生成新的個體，以增加種群的多樣性，改善算法的局部搜索能力。變異操作采用插入變異：首先，在變異個體中隨機(jī)選擇兩個基因位置X和Y；然后，將基因位置Y的航班信息插入到基因位置X之后，其它的航班先后順序保存不變。圖2描述了對個體P=(3，1，6，4，2，5，7)進(jìn)行插入變異操作后產(chǎn)生變異個體P′=(3，1，5，6，4，2，7)的過程。

圖2 插入變異操作

3.6 算法流程

改進(jìn)免疫遺傳算法求解停機(jī)位分配優(yōu)化問題的具體執(zhí)行步驟如下。

1)參數(shù)設(shè)置。包括種群規(guī)模NP、迭代次數(shù)G、個體密度的閾值λ、交叉概率pc、變異概率pm等；

2)種群的初始化。利用提出的初始種群的產(chǎn)生方法對種群個體初始化，使初始種群既包含質(zhì)量較好的個體，又包括隨機(jī)生成的個體。子代個體種群初始化為Φ；

3)判斷算法的迭代次數(shù)是否大于G：如果大于G，轉(zhuǎn)向步驟10；否則執(zhí)行下面的步驟；

4)遍歷父代與子代種群中每個個體，依據(jù)式(12)計算每個個體a的密度值Ca；

5)個體適應(yīng)度評價。按照式(13)計算每個個體的適應(yīng)度值：對于停機(jī)位預(yù)分配問題，目標(biāo)函數(shù)為式(1)；對于停機(jī)位動態(tài)再分配問題，目標(biāo)函數(shù)為式(4)；

6)子代個體種群與父代個體種群合并，并且根據(jù)適應(yīng)度值進(jìn)行排序，取前NP個個體作為新群體，進(jìn)行下一次遺傳操作；

7)以交叉概率pc對新種群進(jìn)行交叉操作。兩個父代個體交叉產(chǎn)生兩個新的子代個體；

8)對交叉得到的種群中滿足變異概率的個體按照變異策略進(jìn)行變異，得到新一代子代種群；

9)算法的迭代次數(shù)增加一次，返回步驟3；

10)輸出全局最好解信息，算法運行結(jié)束。

4 仿真結(jié)果與分析

4.1 實驗設(shè)置

將上述模型應(yīng)用于具有8個停機(jī)位的某小型機(jī)場停機(jī)位分配過程。對機(jī)場在9:00-13:00時間內(nèi)的20個航班進(jìn)行仿真，分別模擬停機(jī)位靜態(tài)預(yù)分配和航班延誤情況下的再分配方案。航班進(jìn)離港時間以及航班的機(jī)型信息見表1，航班機(jī)型與停機(jī)位的匹配關(guān)系見表2。分配到停機(jī)位k的航班進(jìn)離港場面滑行距離hk以千米為單位，取值為區(qū)間[1，5]內(nèi)的隨機(jī)整數(shù)。停機(jī)位的最小安全時間間隔T為5分鐘。對于免疫遺傳算法，算法種群規(guī)模NP=50，最大迭代次數(shù)G=1000，交叉概率pc=0.9，變異概率pm=0.01，個體密度的閾值λ=0.5。

表1 進(jìn)離港航班信息

表2 航班機(jī)型與停機(jī)位的匹配關(guān)系

4.2 實驗結(jié)果分析

免疫遺傳算法得到停機(jī)位靜態(tài)預(yù)分配方案如圖3所示。在20個航班中隨機(jī)產(chǎn)生20%的延誤航班。設(shè)航班F03、F07、F10、F15先后延誤25min、20min、15min、10min，通過停機(jī)位再分配優(yōu)化模型，采用免疫遺傳算法得到停機(jī)位再分配方案。圖4給出航班的動態(tài)調(diào)整結(jié)果。延誤航班導(dǎo)致對3個航班的停機(jī)位預(yù)分配方案進(jìn)行了動態(tài)調(diào)整，具體調(diào)整方案為：航班F10由原來的停機(jī)位G3調(diào)整到G6，航班F13由原來的停機(jī)位G8調(diào)整到G7，航班F20由原來的停機(jī)位G3調(diào)整到G5。從實驗結(jié)果可以看出，停機(jī)位再分配方案兼顧了旅客、航空公司和機(jī)場的利益，在減少旅客轉(zhuǎn)機(jī)步行距離和航班場面滑行距離，提高停機(jī)位利用率的同時，最小化由延誤航班帶來的停機(jī)位預(yù)分配計劃擾動。

圖3 航班停機(jī)位預(yù)分配方案

圖4 航班停機(jī)位再分配方案

5 結(jié)論

本文從平衡航空公司、機(jī)場和旅客等多方利益的角度，研究機(jī)場航班停機(jī)位的分配問題。

1)構(gòu)建停機(jī)位靜態(tài)預(yù)分配模型和考慮航班延誤情況下的動態(tài)再分配模型，并設(shè)計改進(jìn)免疫遺傳算法對模型進(jìn)行求解。

2)針對20個航班的停機(jī)位分配過程進(jìn)行優(yōu)化仿真分析，結(jié)果表明：當(dāng)4個航班發(fā)生延誤時，動態(tài)調(diào)整后的停機(jī)位分配方案中，僅有3個航班改變了停機(jī)位預(yù)分配計劃。所提出的免疫遺傳算法達(dá)到了較好的優(yōu)化效果。

3)由于天氣條件、機(jī)場、機(jī)組、航空公司等諸多方面因素都會對停機(jī)位分配過程造成影響，因此，考慮更多綜合因素的停機(jī)位實時動態(tài)分配方法還有待做更進(jìn)一步的研究。