孫淑光，張?zhí)s

（中國民航大學電子信息與自動化學院，天津 300300）

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

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

1 模型建立

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

1）信息已知化 在預分配前，對當天?？匡w機的所有信息如機型、降落時間、起飛時間、航班信息等均假設(shè)已知；

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

3）容量許可化 假設(shè)機場機位足夠所有飛機停靠，即不會出現(xiàn)機場超負荷的狀況。

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

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

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

Eij表示Pj進入Si的時間；

Lij表示Pj離開Si的時間；

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

Dj表示Pj可分配機位集合；

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

Ti表示Si總空閑時間的平方和，即

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

T 表示所有機位總空閑時間的平方和，即

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

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

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

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

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

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

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

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

f=-ω1T+ω2F

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

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

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

2 程序設(shè)計

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

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

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

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

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

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

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

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

2.2 初始解生成

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

1）生成Pj的可分配機位集合Dj，可行性判別標準有PZj≤SZj，飛機使用機位的時間不與該機位分配給其他飛機的時間沖突；

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

3）更新該分配機位的占用時間段；

4）重復此操作直至所有飛機分配完畢。

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

2.3 選擇

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

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

2.4 交叉

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

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

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

圖3 交叉運算操作Fig.3 Crossover operation

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

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

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

3）將交叉后的子代個體替換父代個體。

2.5 變異

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

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

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

3 二次啟發(fā)

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

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

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

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

表1 某日首都國際機場航班表Tab.1 Flight schedule of Capital International Airport on one day

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

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

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

5 結(jié)語

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