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

何靜　張玉潔

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

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

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

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

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

2 建立模型

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

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

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

2.2 遺傳算法

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

2.3 基因操作

2.3.1 基因選擇

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

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

2.3.2 交叉算子

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

2.3.3 變異算子

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

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

2.3.4 求解結(jié)果

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

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

3 結(jié)論

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

參考文獻(xiàn)

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

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