遺傳與禁忌搜索算法組合的停機(jī)位優(yōu)化分配

孫淑光，張?zhí)s

（中國(guó)民航大學(xué)電子信息與自動(dòng)化學(xué)院，天津 300300）

機(jī)位分配是一個(gè)多約束、多目標(biāo)的組合優(yōu)化問題。目前機(jī)場(chǎng)以人工分配為主，依靠經(jīng)驗(yàn)對(duì)?？康娘w機(jī)進(jìn)行機(jī)位分配，導(dǎo)致效率低下、成本較高。當(dāng)飛機(jī)數(shù)量和機(jī)位數(shù)量達(dá)到一定程度時(shí)，較難得到一個(gè)高效合理的分配方案，而如果分配不合理，則會(huì)嚴(yán)重制約機(jī)場(chǎng)的運(yùn)行[1]。機(jī)位分配屬于NP-hard 問題，傳統(tǒng)方法難以解決。專家系統(tǒng)法[2]、分支定界算法[3]只能提出單個(gè)分配方案，并不實(shí)用，而啟發(fā)式算法[4]如遺傳算法（GA,genetic algorithm）、禁忌搜索算法（TS, tabu search）、蟻群算法（ACO,ant colony）、模擬退火算法（SA,simulated annealing algorithm）等均適用于解決該類問題。遺傳算法具有收斂性好、全局搜索能力強(qiáng)的優(yōu)點(diǎn)，但該算法容易陷入“早熟”，因此需要二次啟發(fā)。田晨等[5]以機(jī)位空閑時(shí)間方差最小化作為優(yōu)化目標(biāo)；戴順南[6]以航班等待延誤時(shí)間和機(jī)位使用空閑時(shí)間為優(yōu)化目標(biāo)建立模型；衛(wèi)東選[7]以最小化停機(jī)位各空閑時(shí)間段的離差為目標(biāo)函數(shù)建立數(shù)學(xué)模型；馮程等[8]建立了降低旅客進(jìn)出機(jī)場(chǎng)飛行區(qū)時(shí)間的停機(jī)位分配模型；徐浩[9]以總的延誤成本最小為目標(biāo)函數(shù)，采用改進(jìn)遺傳算法進(jìn)行求解。但上述研究?jī)?yōu)化目標(biāo)過少，很難符合實(shí)際情況，且在實(shí)際分配中航班存在不同優(yōu)先級(jí)的情況，而之前的研究更多是以先到先分配為原則進(jìn)行分配。

通過設(shè)計(jì)新的目標(biāo)函數(shù)并加入優(yōu)先級(jí)的概念，將遺傳算法與禁忌搜索算法組合，通過遺傳算法求出一組可行分配方案集合，然后通過禁忌搜索算法對(duì)該分配集進(jìn)行優(yōu)化。

1 模型建立

停機(jī)位分配涉及到的因素較多，包括機(jī)型大小、機(jī)位大小等。為方便研究，做出如下假設(shè)：

1）信息已知化 在預(yù)分配前，對(duì)當(dāng)天停靠飛機(jī)的所有信息如機(jī)型、降落時(shí)間、起飛時(shí)間、航班信息等均假設(shè)已知；

2）時(shí)間有限化 由于機(jī)位分配是一個(gè)動(dòng)態(tài)過程，如果不設(shè)定時(shí)間段很難求出最優(yōu)方案，因此，需要假設(shè)只分配一個(gè)時(shí)間段內(nèi)的飛機(jī)，方便求出最優(yōu)分配方案；

3）容量許可化 假設(shè)機(jī)場(chǎng)機(jī)位足夠所有飛機(jī)?？浚床粫?huì)出現(xiàn)機(jī)場(chǎng)超負(fù)荷的狀況。

由于在實(shí)際分配過程中會(huì)出現(xiàn)緊急情況，部分飛機(jī)擁有更高的優(yōu)先級(jí)，先到先分配原則的實(shí)用性受到影響，因此，將按照飛機(jī)優(yōu)先級(jí)進(jìn)行機(jī)位分配。要對(duì)機(jī)位分配進(jìn)行優(yōu)化，首先需要對(duì)其進(jìn)行數(shù)學(xué)建模，定義變量[10-11]如下：

飛機(jī)集合P={Pj|1≤j≤n}表示在一個(gè)時(shí)間段內(nèi)需要分配機(jī)位的飛機(jī)；

機(jī)位集合S={Si|1≤i≤m}表示在一個(gè)時(shí)間段內(nèi)機(jī)場(chǎng)可提供的機(jī)位；

Eij表示Pj進(jìn)入Si的時(shí)間；

Lij表示Pj離開Si的時(shí)間；

Td表示兩架飛機(jī)被安排?？吭谕粰C(jī)位之間相隔的安全時(shí)間，Td＞0；

Dj表示Pj可分配機(jī)位集合；

狀態(tài)變量Yij∈{0，1}，當(dāng)Si被分配給Pj時(shí)，Yij=1，反之為0；

Ti表示Si總空閑時(shí)間的平方和，即

其中：k 表示被分配到Si的飛機(jī)序號(hào)；Ni表示停到Si的飛機(jī)數(shù)，且Ei(k+1)-Lik≥Td；

T 表示所有機(jī)位總空閑時(shí)間的平方和，即

PZ 表示飛機(jī)機(jī)型的大小集合，PZ∈{3，2，1} 分別代表大、中、小型機(jī)型；

SZ 表示機(jī)位的大小集合，SZ∈{3，2，1} 分別代表大、中、小型機(jī)位；

PZj表示Pj的尺寸，PZj∈PZ；

SZi表示Si的尺寸，SZi∈SZ；

Fj表示Pj分配給Si的占用效率，F(xiàn)j=PZj/SZi；

F 表示分配方案中所有飛機(jī)的總占用效率，

在停機(jī)過程中，為防止某些機(jī)位使用過度，某些機(jī)位使用過少，造成機(jī)位使用的不均衡，應(yīng)將機(jī)位空閑時(shí)間平方和的最小化作為目標(biāo)函數(shù)之一。此外，如果機(jī)位大小與停放飛機(jī)的大小不匹配，也會(huì)造成資源的浪費(fèi)，使停機(jī)成本增加。因此，優(yōu)化目標(biāo)綜合考慮上述兩方面因素，目標(biāo)函數(shù)同時(shí)包含機(jī)位的占用效率最大化。

所以設(shè)立目標(biāo)函數(shù)為

f=-ω1T+ω2F

其中：ω1為機(jī)位空閑時(shí)間平方和的權(quán)重；ω2為占用效率的權(quán)重。由于空閑時(shí)間與占用效率不屬同一量綱，應(yīng)做歸一化處理，即

其中：Z1=ω1/Tmax；Z2=ω2/Fmax；Tmax為理論上所有機(jī)位最大空閑時(shí)間的平方和；Fmax為理論上最大占用效率。

因此，停機(jī)位分配優(yōu)化的目的是求f 的最大值，即

2 程序設(shè)計(jì)

2.1 基于優(yōu)先等級(jí)的基因編碼

機(jī)位分配優(yōu)先級(jí)具體為：國(guó)際航班優(yōu)于國(guó)內(nèi)航班，其優(yōu)先級(jí)別最高，不考慮其他因素；當(dāng)同為國(guó)內(nèi)或國(guó)際航班，大型飛機(jī)優(yōu)于小型飛機(jī)[6]；當(dāng)同為國(guó)際或國(guó)內(nèi)航班且機(jī)型機(jī)同，先到飛機(jī)優(yōu)于后到飛機(jī)。

采用實(shí)數(shù)進(jìn)行編碼，先將飛機(jī)以優(yōu)先級(jí)高低進(jìn)行排序，Pj優(yōu)先級(jí)計(jì)算如下

其中：nj表示Pj對(duì)應(yīng)的航班是否為國(guó)際航班；Emax表示在一個(gè)時(shí)間段內(nèi)理論上最晚降落的時(shí)間，Eij和Emax均進(jìn)行有理化轉(zhuǎn)換為整數(shù)值；K1、K2、K3為系數(shù)，根據(jù)優(yōu)先級(jí)的條件確定。

每條個(gè)體中序號(hào)代表飛機(jī)優(yōu)先級(jí)序號(hào)，對(duì)應(yīng)的賦值代表機(jī)位id，如圖1 所示，從0 位開始，第2 位表示將優(yōu)先級(jí)為2 的飛機(jī)分配到4 號(hào)機(jī)位（序號(hào)越小，優(yōu)先級(jí)越高）。

基于遺傳算法生成一組分配方案集的流程如圖2所示。

圖1 飛機(jī)機(jī)位基因編碼Fig.1 Gene coding of airport gate

圖2 基于遺傳算法的機(jī)位分配流程圖Fig.2 Flow chart of airport gate assignment based on GA

2.2 初始解生成

為提高初始解的生成效果，按如下步驟生成初始分配方案：

1）生成Pj的可分配機(jī)位集合Dj，可行性判別標(biāo)準(zhǔn)有PZj≤SZj，飛機(jī)使用機(jī)位的時(shí)間不與該機(jī)位分配給其他飛機(jī)的時(shí)間沖突；

2）隨機(jī)從可分配集合Dj中選一機(jī)位分配給Pj；

3）更新該分配機(jī)位的占用時(shí)間段；

4）重復(fù)此操作直至所有飛機(jī)分配完畢。

由于生成一架飛機(jī)的機(jī)位集合受之前分配影響，若某一飛機(jī)的可分配機(jī)位集合為空，則只能將該飛機(jī)分配到停機(jī)坪。

2.3 選擇

采用輪盤式選擇，每條個(gè)體所對(duì)應(yīng)的適應(yīng)度函數(shù)值越高，則被選中的可能性越大。第k 條個(gè)體被選中的概率POSk如下

其中：fk為第k 條個(gè)體對(duì)應(yīng)的適應(yīng)度值；N 為種群容量。

2.4 交叉

采用自適應(yīng)交叉率[12]，每條個(gè)體都以一定的交叉率進(jìn)行交叉運(yùn)算。第i 條個(gè)體交叉率Pci的計(jì)算如下

其中：C1、C2為小于1 的正數(shù)；favg為種群的平均適應(yīng)度值；fmax為種群中最大適應(yīng)度值；fi為第i 條個(gè)體的適應(yīng)度值。

交叉運(yùn)算采用兩點(diǎn)交叉[13]，通過選擇過程選出父代母代，隨機(jī)生成兩個(gè)交叉點(diǎn)a、b。ab 之間的部分就是需要交換的部分，如圖3 所示。

圖3 交叉運(yùn)算操作Fig.3 Crossover operation

為方便描述，設(shè)開始到a 點(diǎn)之前的基因稱為A段，b 點(diǎn)之后到結(jié)尾的基因稱為B 段，a、b 之間的基因稱為ab 段。先將A 段和B 段父代基因賦給子代相應(yīng)的位置。由于母帶ab 段的分配可能會(huì)與子代A、B 段分配在時(shí)間上產(chǎn)生沖突，產(chǎn)生無效解，所以應(yīng)做檢錯(cuò)處理，具體過程如下：

1）去除父代ab 段中對(duì)應(yīng)分配給飛機(jī)機(jī)位的占用時(shí)間段；

2）在母代中ab 段中每一位做如下操作：①判斷該位是否沖突，若不沖突，則將母代對(duì)應(yīng)位的分配賦給子代，更新子代該機(jī)位的占用時(shí)間段并判斷下一位；②若沖突，則清空該飛機(jī)的可分配機(jī)位集合，重新生成該機(jī)位的可分配機(jī)位集合，從該集合中選擇一個(gè)機(jī)位分配給該飛機(jī)。

3）將交叉后的子代個(gè)體替換父代個(gè)體。

2.5 變異

同交叉過程，采用自適應(yīng)變異率，每條個(gè)體都有一定概率進(jìn)行變異運(yùn)算，即

其中，C3、C4為小于1 的正數(shù)。

變異過程中，首先刪除一架飛機(jī)對(duì)應(yīng)分配給其機(jī)位的機(jī)位占用時(shí)間，清空該飛機(jī)對(duì)應(yīng)的可分配機(jī)位集合，并重新生成該集合。若該機(jī)位集合為1，則分配給其該機(jī)位，然后重新選擇基因，重復(fù)上述操作直至機(jī)位集合大于1，并重新進(jìn)行變異運(yùn)算；若不為1，則選擇一個(gè)與原先分配機(jī)位不同的機(jī)位分配給該飛機(jī)。

3 二次啟發(fā)

雖然遺傳算法具有很好的全局搜索能力，但局部搜索能力較差。由于遺傳算子中的交叉算子使得染色體之間具有很大的相似性，可能導(dǎo)致搜索停滯，種群多樣性得不到補(bǔ)充，從而出現(xiàn)“早熟”的特征。而禁忌搜索算法具有很好的局部搜索能力，將遺傳算法和禁忌搜索算法組合使用會(huì)起到很好的效果。具體方案為通過遺傳算法生成最終種群后，將該種群通過禁忌搜索算法對(duì)其進(jìn)行優(yōu)化，之后選擇種群中適應(yīng)度值最高的個(gè)體作為最終分配方案。這種混合策略有效地結(jié)合了遺傳算法極強(qiáng)的并行搜索能力和禁忌搜索算法出色的局部搜索能力。禁忌搜索算法的基本過程為：通過初始解產(chǎn)生一組鄰域解，然后在鄰域解中確定一定數(shù)量的候選解；若最佳候選解對(duì)應(yīng)的目標(biāo)函數(shù)值優(yōu)于當(dāng)前最優(yōu)解，則忽視其禁忌準(zhǔn)則，將該候選解替換為當(dāng)前解和當(dāng)前最優(yōu)解，并將相應(yīng)的對(duì)象加入禁忌表；若不存在上述候選解，則在候選解中選擇非禁忌的最優(yōu)解為新的當(dāng)前解，而無視它與當(dāng)前解的優(yōu)劣，同時(shí)將相應(yīng)的對(duì)象加入禁忌表；如此重復(fù)上述迭代搜索過程，直至滿足停止準(zhǔn)則。具體流程圖如圖4 所示。

圖4 禁忌搜索算法流程圖Fig.4 Flow chert of TS algorithm

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

采用首都國(guó)際機(jī)場(chǎng)的數(shù)據(jù)作為仿真實(shí)驗(yàn)數(shù)據(jù)。取時(shí)間段為0～24 點(diǎn)，需要分配的飛機(jī)架次為1 500 架，可用停機(jī)位數(shù)量為250 個(gè)。表1 為某日首都國(guó)際機(jī)場(chǎng)航班表（8：00～8：30），已將其按優(yōu)先級(jí)進(jìn)行排序。

表1 某日首都國(guó)際機(jī)場(chǎng)航班表Tab.1 Flight schedule of Capital International Airport on one day

利用遺傳算法進(jìn)行優(yōu)化分配時(shí)，取交叉率C1=C2=0.7，變異率C3=C4=0.05，最大迭代數(shù)為100，種群數(shù)量為50，適應(yīng)度函數(shù)中ω1=ω2=1。通過隨機(jī)數(shù)對(duì)初始種群進(jìn)行賦值，仿真結(jié)果如表2 所示。

表2 仿真結(jié)果Tab.2 Simulation result

最終分配方案即為通過二次啟發(fā)后最大適應(yīng)度值。其中，結(jié)合公式（1）～（4），可知其對(duì)應(yīng)的機(jī)位總空閑時(shí)間為113.73，實(shí)際有效分配機(jī)位的飛機(jī)架次為1 418，即每個(gè)航班與停機(jī)位類型的匹配程度為0.945 33（越接近1說明越匹配）。從表2 可看出，初始分配中最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值為1.718 71，通過遺傳算法優(yōu)化后達(dá)到了1.942 35，增幅為13%，而通過二次啟發(fā)后目標(biāo)函數(shù)值達(dá)到1.966 20，增幅為14.4%。遺傳算法取得較好的效果，禁忌搜索算法二次啟發(fā)后的分配效果比遺傳算法有進(jìn)一步提升，改進(jìn)的遺傳算法可給出更加優(yōu)化的機(jī)位分配方案，具有高效、實(shí)用的特點(diǎn)。

5 結(jié)語

在綜合考慮機(jī)型大小、機(jī)位大小、進(jìn)入機(jī)位時(shí)間與離開機(jī)位時(shí)間、飛機(jī)優(yōu)先級(jí)等因素的情況下，充分考慮實(shí)際情況，建立機(jī)場(chǎng)停機(jī)位分配模型，提出優(yōu)化目標(biāo)函數(shù)，采用禁忌搜索二次啟發(fā)后的遺傳算法，提高了目標(biāo)函數(shù)值，并通過實(shí)例對(duì)模型進(jìn)行了仿真測(cè)試。結(jié)果表明，相比隨機(jī)分配，遺傳算法優(yōu)化效果明顯，而結(jié)合禁忌搜索算法優(yōu)化后，優(yōu)化效果進(jìn)一步提高。