基于免疫遺傳算法的停機(jī)位動(dòng)態(tài)再分配優(yōu)化

閆 萍，劉夢詩

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

1 引言

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

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

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

停機(jī)位分配問題需要綜合考慮航班機(jī)型、停機(jī)位類型和航班進(jìn)、離港時(shí)刻等因素，在給定的作業(yè)時(shí)間窗內(nèi)，為執(zhí)行每個(gè)航班的飛機(jī)分配適當(dāng)?shù)耐C(jī)位，以保證機(jī)場客貨的有效銜接。停機(jī)位再分配模型是在停機(jī)位靜態(tài)預(yù)分配優(yōu)化方案的基礎(chǔ)上進(jìn)行實(shí)時(shí)動(dòng)態(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)港時(shí)從降落跑道到停機(jī)位k的滑行距離與航班離港時(shí)從停機(jī)位k到起飛跑道的滑行距離之和；

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

T′—停機(jī)位的可用運(yùn)行時(shí)間；

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

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

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

此問題的決策變量為：

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

以旅客的角度優(yōu)化停機(jī)位配置，指標(biāo)為旅客轉(zhuǎn)機(jī)所需要移動(dòng)的距離最小。從航空公司和機(jī)場的角度優(yōu)化停機(jī)位分配，一方面，航班在機(jī)場場面的滑行距離盡量短，才能節(jié)省燃料的消耗，同時(shí)增大機(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ā)生航班延誤或取消時(shí)，會(huì)造成對原有航班停機(jī)位分配方案的擾動(dòng)，因此應(yīng)盡量減少受干擾的航班數(shù)目。w1和w2分別是目標(biāo)函數(shù)兩部分的權(quán)重系數(shù)。

(4)

2.3 約束條件

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

(5)

(6)

(7)

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

(8)

(9)

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

(10)

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

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

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

3.1 個(gè)體編碼

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

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

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

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

3.3 計(jì)算個(gè)體密度

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

3.3.1 個(gè)體之間的相似度

(11)

其中，

3.3.2 個(gè)體的密度

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

(12)

3.4 計(jì)算適應(yīng)度

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

(13)

3.5 遺傳操作

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

3.5.1 交叉操作

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

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

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

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

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

圖1 順序交叉操作

3.5.2 變異操作

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

圖2 插入變異操作

3.6 算法流程

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

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

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

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

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

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

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

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

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

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

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

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

4.1 實(shí)驗(yàn)設(shè)置

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

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

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

4.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

5 結(jié)論

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

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

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

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