基于免疫遺傳算法的停機位動態再分配優化

閆 萍，劉夢詩

(沈陽航空航天大學經濟與管理學院，遼寧 沈陽 110136)

1 引言

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

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

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

2 停機位再分配數學模型

停機位分配問題需要綜合考慮航班機型、停機位類型和航班進、離港時刻等因素，在給定的作業時間窗內，為執行每個航班的飛機分配適當的停機位，以保證機場客貨的有效銜接。停機位再分配模型是在停機位靜態預分配優化方案的基礎上進行實時動態調度。

2.1 模型參數的定義

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

N—航班集合；

M—停機位集合；

dkl—停機位k到停機位l的距離；

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

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

T′—停機位的可用運行時間；

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

vk—停機位k允許停放的最大機型；

H—一個大正常數；

此問題的決策變量為：

2.2 目標函數

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

(1)

(2)

(3)

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

(4)

2.3 約束條件

停機位動態再分配問題需要考慮的約束條件與靜態預分配時相同，主要包括下面幾個方面

(5)

(6)

(7)

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

(8)

(9)

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

(10)

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

3 免疫遺傳算法設計

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

3.1 個體編碼

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

例如，對于有5個航班的停機位分配問題，其個體編碼為長度是5的行向量(5，2，1，3，4)，代表5個航班的停機位分配順序。首先，為航班5分配停機位；然后，對航班2進行停機位指派；以此類推，按照航班序列5→2→1→3→4的順序，完成所有5個航班的停機位分配過程。基于航班序列的自然數編碼方案，在后續遺傳操作中可以始終保持個體產生可行解，進而提高了算法的執行效率。

3.2 初始種群的產生

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

3.3 計算個體密度

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

3.3.1 個體之間的相似度

(11)

其中，

3.3.2 個體的密度

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

(12)

3.4 計算適應度

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

(13)

3.5 遺傳操作

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

3.5.1 交叉操作

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

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

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

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

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

圖1 順序交叉操作

3.5.2 變異操作

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

圖2 插入變異操作

3.6 算法流程

改進免疫遺傳算法求解停機位分配優化問題的具體執行步驟如下。

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

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

3)判斷算法的迭代次數是否大于G：如果大于G，轉向步驟10；否則執行下面的步驟；

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

5)個體適應度評價。按照式(13)計算每個個體的適應度值：對于停機位預分配問題，目標函數為式(1)；對于停機位動態再分配問題，目標函數為式(4)；

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

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

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

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

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

4 仿真結果與分析

4.1 實驗設置

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

表1 進離港航班信息

表2 航班機型與停機位的匹配關系

4.2 實驗結果分析

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

圖3 航班停機位預分配方案

圖4 航班停機位再分配方案

5 結論

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

1)構建停機位靜態預分配模型和考慮航班延誤情況下的動態再分配模型，并設計改進免疫遺傳算法對模型進行求解。

2)針對20個航班的停機位分配過程進行優化仿真分析，結果表明：當4個航班發生延誤時，動態調整后的停機位分配方案中，僅有3個航班改變了停機位預分配計劃。所提出的免疫遺傳算法達到了較好的優化效果。

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