基于遺傳算法尋優(yōu)的登機0分配策略

何靜　張玉潔

摘要：本文考慮旅客流程時間和換乘緊張度并優(yōu)化分配登機口，將20日內(nèi)規(guī)定出發(fā)、到達時間的303次國內(nèi)、國際航班分配給69個符合航班屬性的登機口，提出符合各問題要求的登機口優(yōu)化方案。

[關(guān)鍵詞]遺傳算法 匹配策略 登機口

1 數(shù)據(jù)收集

航站樓T和衛(wèi)星廳S的布局設(shè)計如圖1所示。航站樓T有28個登機口，衛(wèi)星廳S有41個登機口。航站樓T和衛(wèi)星廳S之間需要捷運時間，S廳沒有辦理出入境手續(xù)功能。

20日起降航班量為303次，機場總登機口數(shù)為69，如果直接進行整數(shù)規(guī)劃方案，69303的解空間將會大大增加問題的復(fù)雜度和運算時間，降低運行效率，計算結(jié)果也會難以接受。因此，我們將遺傳算法種群根據(jù)登機口的功能屬性劃分為（NII，NDI，NDD，NID，WII，WID，WDI，WDD）8個種群（其中N代表窄機型，W代表寬機型，I表示國際，D表示國內(nèi)。

2 建立模型

2.1 目標函數(shù)構(gòu)建

考慮航班——登機口分配，因此只需要盡可能最小化登機口的數(shù)量。因此可以將目標函數(shù)構(gòu)建如下：

其中|M|為集合的大小。

2.2 遺傳算法

這里采用自然數(shù)編碼，使用自然數(shù)對每個登機口進行編碼，以登機口作為基因，按航班到達的先后次序組成染色體。登機口按照T1，T2，..T28，S1，S2，..S41的順序排序，然.后使用非零自然數(shù)編碼，其中T1為1號，S1為29號，S41為69號。整數(shù)字符串呈現(xiàn)的染色體是表達航班到具體登機口的情況。字符串的長度為航班的班次，共303次航班，每一個數(shù)位對應(yīng)一個航班，基因序列中的具體數(shù)字是指該航班所分配的登機口編號。例如，字符串“23565...521”中連續(xù)的兩個“5”表示第五個登機口依次被分配給第三個和第五個航班。

2.3 基因操作

2.3.1 基因選擇

選擇擇算子增大父代適應(yīng)度值大的個體遺傳至下一代的概率，以保證種群的基因優(yōu)良，使種群個體能夠不斷接近最優(yōu)解。

本次采用輪盤賭選擇方式選擇操作，將個體適應(yīng)度值與整體適應(yīng)度值比例作為被選擇的概率。采用輪盤賭方法作為選擇算子，使得具有更好適應(yīng)度（目標函數(shù)）的染色體具有更多的選擇機會，能夠保證優(yōu)良基因的存續(xù)能力，保證了程序的魯棒性，增加了尋找到最優(yōu)解的概率，但是也容易使種群在前期失去多樣性。

2.3.2 交叉算子

交叉算子可以用來模擬生物進化過程中生物的基因重組，因此交叉算子也被叫做基因重組。每一次交叉操作在兩條染色體上進行操作，并通過結(jié)合兩種染色體的特征產(chǎn)生后代。在遺傳算法中，人們希望通過交叉操作能夠生成比父代更為優(yōu)良的個體，因而有利于更快更好地進化出人們想要得到的最優(yōu)解。

2.3.3 變異算子

本文采用隨機生成方法實現(xiàn)運變異操作。由于本題約束條件較多，因此我們選中的變異位點將在其對應(yīng)的解空間內(nèi)隨機生成于當前點不同的登機口。

我們對原始數(shù)據(jù)進行了描述統(tǒng)計和分析，我們觀察原數(shù)據(jù)發(fā)現(xiàn)換乘旅客中有三位乘客情況不正確，分別為T2891、T2892、T2893，這三位乘客所買降落航班時間均晚于換乘航班的起飛時間。

2.3.4 求解結(jié)果

首先，我們對原始數(shù)據(jù)進行了描述統(tǒng)計和分析，我們觀察原數(shù)據(jù)發(fā)現(xiàn)換乘旅客中有三位乘客情況不正確，分別為T2891、T2892、T2893，這三位乘客所買降落航班時間均晚于換乘航班的起飛時間，為了使后面的仿真結(jié)果更準確，我們對錯誤數(shù)據(jù)進行了分離。

然后，在我們的求解結(jié)果中，登機口按照T1，T2，.T28，S1，S2，..S41的順序排序，然后使用非零自然數(shù)編碼，其中T1為1號，S1為29號，S41為69號，在圖表中取序號表示。

3 結(jié)論

在只考慮航班一登機口分配。盡可能多地分配航班到合適的登機口，最小化被使用登機口的數(shù)量的情況下，最小損失函數(shù)值為0.5142，最小化登機口數(shù)量為36，T登機口數(shù)為19，S登機口數(shù)為17，中轉(zhuǎn)乘客的登機口平均時間占用率為81.25%，時間占用率最小的為編號為4和18的登機口，他們的時間占用率分別為25.57%和21.69%。

參考文獻

[1]程林輝，王江晴.求解車輛路徑問題的改進遺傳算法[J].計算機工程與應(yīng)用，2010，46（36）：219-221.

[2]田巧玉，龍建忠，遺傳算法的編碼理論研究[J].自動化與儀器儀表，2013，10（04）：4-7.