基于分層序列法的多目標停機位分配

沈笑云，于薈文

（中國民航大學天津市智能信號與圖像處理重點實驗室，天津 300300）

中國民航運輸業(yè)近年來發(fā)展迅速，機場數量、航班數量以及航空器規(guī)模等持續(xù)增加。如何在有限的資源條件下合理分配停機位，成為提高機場系統(tǒng)容量和服務效率的關鍵所在[1]。

停機位分配過程會受到諸多約束，分為硬約束和軟約束[2]。硬約束是指在任何情況下都需要滿足的約束條件，一旦違反可能會導致嚴重后果，包括時間約束、機型約束、唯一性約束。軟約束是指在某些情況下可以違反的約束條件，包括國際/國內約束、航空公司約束、任務約束。違反了軟約束則被視為軟沖突。軟沖突雖然不會造成嚴重后果，但會對機場正常運行造成負面影響。因此，為同時保證機場的正常運行和每架飛機都有機位可停，任何目標都應在軟沖突次數最少的前提下進行優(yōu)化。

國內外針對不同目標，運用多種方法對停機位分配問題進行了研究。尹嘉男等[3]以飛機滑行時間最短為目標進行了研究。楊越等[4]以近機位使用率最高和旅客步行距離最短為目標建立了分配優(yōu)化模型。上述研究中，軟約束被作為硬約束來進行建模。但在某些情況下，可能會出現(xiàn)飛機分配不到停機位的情況。Marinelli[5]以最小化旅客行走距離與遠機位使用率為目標，使用蜂群算法進行求解。Ghazouani等[6]以近機位使用率最高為目標，采用遺傳算法進行了求解。王永亮等[7]以旅客行走時間最短為優(yōu)化目標，設計了交叉熵算法進行了求解。上述研究在建模時只添加了硬約束而忽視了軟約束的存在，與機場實際運行狀況存在一定差異。

針對以上研究中存在的不足，將軟沖突次數作為較高優(yōu)先級的目標進行考慮，采用分層序列法構建多目標停機位分配優(yōu)化模型，同時設計針對性較強的混合遺傳算法進行求解。

1 數學模型

在機位分配時，軟沖突次數具有較高的優(yōu)先級。根據分層序列法的基本思想，按照目標優(yōu)先級的高低，將機位分配分為兩個階段，分別建立數學模型，分階段逐步求取最優(yōu)解。第一階段在只添加硬約束條件下，以軟沖突次數最少為目標構建優(yōu)化模型。第二階段利用第一階段得到的分配結果對軟約束條件進行松弛，在添加硬約束和經過松弛的軟約束條件下，采用線性加權法，以近機位使用率最高和停機位預分配方案魯棒性最好為目標進行建模。

為便于討論和處理，引入3個假設：

1）信息完備性假設 在進行機位分配時，可以得到關于待分配飛機和停機位的所有相關信息；

2）容量滿足假設 機場的實際容量可以滿足航班量的需求，即可以為所有飛機都分配一個停機位；

3）有限時間段假設 對停機位分配的研究僅限于某一時段內，將連續(xù)過程簡化為有限時間段進行處理。

1.1 參數定義

定義部分參數，如表1所示，其中M～MI為機位相關參數，N～NI為飛機相關參數。在表1基礎上，其他定義如下。

1）xi，j、yi，j為 0-1 決策變量，i∈N，j∈M。當飛機 i分配到機位j時其取值為1，否則為0。

2）V（i）={j|oj≤ai≤di≤cj，?j∈[1，2，…，m]}為開啟時間早于飛機i預計進港時間且關閉時間晚于飛機i預計離港時間的機位集合。

3）U（i）={k|ai≤ak≤di，?k∈[i+1，i+2，…，n]}為計劃進港時間晚于飛機i計劃進港時間且與飛機i有時間沖突的飛機集合。

1.2 第一階段

軟沖突次數為

表1 參數定義Tab.1 Parameter definition

航空公司沖突次數為

任務沖突次數為

以f1最小為目標，采用唯一性約束、時間約束、機型約束作為約束條件。因此，第一階段優(yōu)化模型為

其中：第1個約束條件為唯一性約束，即對于每架飛機，必須且僅能被分配到1個停機位，且占用時間在該停機位可用時間內；第2個約束條件為時間約束，即對于每個機位，同一時刻最多只能停放1架飛機；第3個約束條件為機型約束，即對于每個機位，只允許停放規(guī)定允許機型范圍內的飛機。

求解后得到第一階段分配方案，記為 yi，j，i∈N，j∈M，其滿足：①硬約束全部得到滿足，能夠保證機場的正常安全運行；②軟沖突次數最少，最大程度減少分配方案對機場運行的負面影響。

由于分配方案僅考慮軟沖突次數最少，沒有針對近機位使用率和停機位預分配方案魯棒性進行優(yōu)化，無法滿足實際運行需求，需進行第二階段優(yōu)化。

1.3 第二階段

以近機位使用率最高和停機位預分配方案魯棒性最好為目標，增加3種軟約束條件，并根據yi，j對軟約束進行松弛。由于同一時間段內，近機位使用率與遠機位使用率的和等于1，近機位使用率最高也就是遠機位使用率最低，即

取機位使用空閑時間平方和作為魯棒性代表，平方和越低表示飛機被更均勻地分配到各個機位上，則該分配方案吸收或抑制飛行計劃在執(zhí)行過程中進離港時刻波動的能力更強，即魯棒性越好。設飛機k為飛機i在機位j上緊鄰的前序飛機。則飛機i緊鄰的前序機位空閑時間為

機位j的最后一段空閑時間為

因此，分配方案的魯棒性最好對應

由于要同時考慮近機位使用率和分配方案的魯棒性，為了在同一目標函數中同時體現(xiàn)這兩個因素，設計權重參數 W∈[0，1]，選取歷史最大值 max（f5）和max（f6），對f5和f6進行歸一化后加權求和，構建多目標函數

則第二階段優(yōu)化模型為

其中：前3個約束條件與第一階段相同；第4個約束條件為國際/國內約束，yi，j=1時，飛機i可以分配到機位j上，否則飛機i只允許分配到國際/國內屬性集合MPj包含其國際/國內屬性Npi的機位j上；第5個約束條件為航空公司約束，yi，j=1時，飛機i可以分配到機位j上，否則飛機i只允許分配到可停航空公司集合MHj包含其所屬的航空公司Nhi的機位j上；第6個約束條件為任務約束，yi，j=1時，飛機i可以分配到機位j上，否則飛機i只允許分配到可停任務集合MRj包含其任務屬性Nri的機位j上。在該模型下求解得到的分配結果可在滿足機場安全運行、機場負面影響最小化條件下，實現(xiàn)對近機位使用率和預分配方案魯棒性的統(tǒng)籌優(yōu)化。

圖1 分配約束條件關系Fig.1 Relation between assignment constraints

兩階段的優(yōu)化過程和結果如圖1所示，其中包含10架飛機和6個機位。第一階段的優(yōu)化在圖1（a）空白區(qū)域內進行。經過第一階段優(yōu)化得到的分配方案被標記為“√”。由圖1（b）可知，第一階段得到的分配方案共產生了5次軟沖突。第二階段的優(yōu)化在空白及交叉區(qū)域內進行，保證優(yōu)化結果的軟沖突次數不高于5次。

2 算法設計

遺傳算法通過模擬自然界的物種進化過程，解決了許多傳統(tǒng)方法難以解決的非線性、多目標問題，擁有良好的全局搜索性能[8]。而貪婪算法具有簡單、有效、時間復雜度低的優(yōu)點，常應用于其他搜索算法初始解的生成[9]。將遺傳算法與貪婪算法結合，設計了混合遺傳算法，針對模型的兩個階段分別求解。算法流程如圖2所示。

圖2 算法流程圖Fig.2 Algorithm flowchart

2.1 第一階段算法

第一階段采用貪婪算法與遺傳算法結合的方式。

第1步染色體編碼 遺傳算法中，每個染色體都表示問題的一個解。首先對染色體進行編碼，設計染色體的排列組合形式，便于后續(xù)步驟的操作并獲得有效解。采用 1 個 n 維整數字符串（b1，b2，…，bn）表示對n架飛機的1個分配方案，稱為染色體編碼。其中每個編碼bi表示將第i架飛機分配到第bi個停機位。如圖3所示為一段時間內某10架飛機先后停在5個機位上的一組染色體編碼圖，b1=2表示將1號飛機分配到2號機位。

圖3 染色體編碼Fig.3 Chromosome coding

第2步種群初始化 按照飛機的計劃進港時間，順序初始化所有飛機。讀取飛機和機位的初始信息，根據相關約束（式（5））產生每架飛機對應的可分配機位集合。從第1架飛機開始，計算將其分配到每個可分配機位所產生的軟沖突次數，再根據貪婪準則從產生的軟沖突次數最少的幾個機位中隨機選擇1個作為該飛機的停機位。更新其他可分配機位集合。如果為空，則重新進行分配；如不為空，則依次分配得到1個初始可行解。循環(huán)執(zhí)行上述步驟a次，得到一組包含a個初始可行解的初始種群。

第3步計算目標函數值 根據第一階段目標函數（式（1））計算染色體的目標函數值。

第4步適應值映射 將目標函數值映射為適應值。目標函數值越小，其對應的適應值越高。

第5步選擇 按照染色體適應值高保留、低淘汰的原則選擇算子。采用聯(lián)賽選擇法作為此階段的選擇算子[10]，盡量保證適應值最高的染色體被選中。

第6步重組 重組算子采用單點交叉。設定重組次數r。隨機選擇兩個父代染色體p1和p2，產生小于染色體長度n的隨機整數k，將p1和p2第k位后的基因（bk+1，bk+2，…，bn）進行交換，產生出 2 個新的子代染色體p1′和p2′。新產生的子代染色體可能不滿足某約束條件，需要對其進行檢測和修復，直到滿足全部約束條件。重復進行r次即完成了r次重組。

第7步變異 變異算子采用多點變異。設定每代的變異次數v和每次的變異位數b。隨機選擇個體p，計算該分配方案下所有機位的空閑時間段。根據每個機位的空閑時間段和每架飛機的可分配機位集合，可得所有飛機的可變異機位集合。在集合中，隨機將飛機i分配到可變異機位j，即令bi=j。再將集合中包含飛機i或機位j的項全部刪除。重復進行b次，即完成了1次變異操作。重復本步驟v次，即完成了v次變異。

第8步精英保留 防止由于遺傳操作而導致父代較優(yōu)的染色體被破壞，在每代遺傳操作結束之后，對子代種群染色體進行評價，選擇種群中的最優(yōu)個體進行記錄。遺傳運算結束后，得到一組較優(yōu)的分配方案。選擇最優(yōu)分配方案作為最終方案。

第9步迭代 將每一代種群中較優(yōu)的染色體重新插入父代種群，替換父代種群中較差的染色體，重復進行選擇、重組、變異等操作，直至達到第一階段遺傳代數g的要求。

經過第一階段運算得到軟沖突次數最少的分配方案，記為yi，j。在保證機場安全運行的條件下，該分配方案最大程度減少了分配方案對機場的負面影響。

2.2 第二階段算法

第二階段仍采用遺傳算法，步驟與第一階段基本相似，第2步、第3步和第5步區(qū)別如下：

第2步種群初始化 根據第二階段約束條件（式（11）），產生每架飛機對應的可分配機位集合，并與第一階段分配結果yi，j中每架飛機所分配的機位取并集，作為第二階段的可分配機位集合。后續(xù)針對每架飛機的所有操作都在其各自的可分配機位集合中進行，從而保證在軟沖突次數不高于第一階段分配結果的同時，可對近機位使用率和預分配方案魯棒性進行優(yōu)化。初始種群隨機產生，以保證其多樣性，提高算法的全局搜索能力。從第1架飛機開始，隨機分配到其可分配機位集合中的某個機位。更新其他未分配飛機的可分配機位集合。如果為空，則重新進行分配；如不為空，則依次進行分配，得到1個初始可行解。

第3步計算目標函數值 根據第二階段目標函數（式（10）），計算染色體的目標函數值。

第5步選擇 采用比例選擇法作為該階段的選擇算子[11]。適應度越高的染色體被選中的概率越大。

第二階段運算實現(xiàn)了在滿足機場安全運行、機場負面影響最小化條件下，對近機位使用率和預分配方案魯棒性的統(tǒng)籌優(yōu)化。

3 實驗分析

針對國內某大型機場的3個指廊和3個停機坪共計49個機位進行模型仿真與算法實現(xiàn)。其中1～20號機位及27～36號機位為近機位，其余為遠機位。如該機位的開啟時間早于8：00，則以8：00為該機位的開啟時間。機位關閉時間統(tǒng)一選擇18：00。選取計劃進港時間在8：00后、計劃離港時間在18：00前的共計101架飛機的航班數據進行仿真驗證。

在進行實驗前，需要確定各項參數。首先確定種群規(guī)模，種群規(guī)模較小時，收斂速度快，但容易過早收斂；種群規(guī)模較大時，收斂到全局最優(yōu)解的概率更高，但收斂速度慢。綜合考慮，設定種群規(guī)模a=100。由于采用貪婪算法生成初始種群，第一階段可通過較少的遺傳代數得到優(yōu)化結果，因此設定第一階段遺傳代數g1=20，第二階段g2=150。重組次數與變異次數根據數據規(guī)模確定。設重組次數r=30，第一階段變異次數v1=5，變異位數b1=3。第二階段變異次數v2=20，變異位數b2=2。

利用Matlab求解該算例，以W=0.5為例，仿真分配結果甘特圖[12]如圖4所示。其中發(fā)生了1次軟沖突，多數飛機集中在近機位區(qū)域，且沒有出現(xiàn)機位空閑時間過短的情況。兩階段算法性能分別如圖5～圖6所示。算法分別在遺傳的第15代和第150代左右達到收斂。

圖4 停機位分配甘特圖（W=0.5）Fig.4 Gate assignment Gantt-chart（W=0.5）

圖5 第一階段算法性能圖（W=0.5）Fig.5 Algorithm performance of Stage Ⅰ（W=0.5）

圖6 第二階段算法性能圖（W=0.5）Fig.6 Algorithm performance of Stage Ⅱ（W=0.5）

CPLEX是國際上領先的優(yōu)化軟件包，也是目前公認最好的商業(yè)優(yōu)化軟件，在學術界和工業(yè)界中普遍認為可以將CPLEX中的算法作為新提出算法與之比較的標桿[13]。應用CPLEX在Matlab環(huán)境下建模并通過精確算法求解該算例，與通過兩階段混合遺傳算法求解的結果進行對比，計算結果各項評價指標如表2所示。

表2 計算結果比較Tab.2 Comparison of calculation results

通過觀察分析各項指標可以發(fā)現(xiàn)：

1）兩種方法都能在保證每架飛機都分配到機位的前提下，將軟沖突降低到1次，最大程度地減少了軟沖突對機場運行造成的影響。

2）W值不同，近機位使用率和魯棒性呈現(xiàn)出不同的升降趨勢，所建多目標優(yōu)化模型有效。在此優(yōu)化模型下，機場工作人員可通過設置權重因子W，滿足不同航班量及航班正常性下的分配需求：在航班量較少或預計次日航班正常的情況下，分配方案對魯棒性的需求有所降低，可設置較高的W值，使優(yōu)化更側重于提升近機位使用率；在航班量較多或預計次日航班正常性較差的情況下，分配方案對魯棒性的需求有所提升，可設置較低的W值使優(yōu)化更側重于預分配方案的魯棒性，保證次日分配方案的平穩(wěn)執(zhí)行。

3）在W值相同的情況下，雖然兩階段混合遺傳算法仿真結果的主要指標均略低于CPLEX，但前者僅需69 s即可得到優(yōu)化結果，后者則需要約1 300 s。證明所提算法具有良好的優(yōu)化性能和較高的運算效率。

4 結語

針對機場停機位預分配問題，提出了以軟沖突次數最少為前提，以近機位使用率和停機位預分配方案魯棒性為目標的多目標分配優(yōu)化模型，并設計了一種求解該模型的混合遺傳算法。算例應用表明，所建模型和所提算法能夠在較短的計算時間內得出更加符合機場實際運行的分配結果，具有良好的優(yōu)化性能和較高的運算效率，為解決機場停機位分配問題提供了理論參考。