沈笑云，于薈文

（中國(guó)民航大學(xué)天津市智能信號(hào)與圖像處理重點(diǎn)實(shí)驗(yàn)室，天津 300300）

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

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

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

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

1 數(shù)學(xué)模型

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

為便于討論和處理，引入3個(gè)假設(shè)：

1）信息完備性假設(shè) 在進(jìn)行機(jī)位分配時(shí)，可以得到關(guān)于待分配飛機(jī)和停機(jī)位的所有相關(guān)信息；

2）容量滿足假設(shè) 機(jī)場(chǎng)的實(shí)際容量可以滿足航班量的需求，即可以為所有飛機(jī)都分配一個(gè)停機(jī)位；

3）有限時(shí)間段假設(shè) 對(duì)停機(jī)位分配的研究?jī)H限于某一時(shí)段內(nèi)，將連續(xù)過(guò)程簡(jiǎn)化為有限時(shí)間段進(jìn)行處理。

1.1 參數(shù)定義

定義部分參數(shù)，如表1所示，其中M～MI為機(jī)位相關(guān)參數(shù)，N～NI為飛機(jī)相關(guān)參數(shù)。在表1基礎(chǔ)上，其他定義如下。

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

2）V（i）={j|oj≤ai≤di≤cj，?j∈[1，2，…，m]}為開(kāi)啟時(shí)間早于飛機(jī)i預(yù)計(jì)進(jìn)港時(shí)間且關(guān)閉時(shí)間晚于飛機(jī)i預(yù)計(jì)離港時(shí)間的機(jī)位集合。

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

1.2 第一階段

軟沖突次數(shù)為

表1 參數(shù)定義Tab.1 Parameter definition

航空公司沖突次數(shù)為

任務(wù)沖突次數(shù)為

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

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

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

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

1.3 第二階段

以近機(jī)位使用率最高和停機(jī)位預(yù)分配方案魯棒性最好為目標(biāo)，增加3種軟約束條件，并根據(jù)yi，j對(duì)軟約束進(jìn)行松弛。由于同一時(shí)間段內(nèi)，近機(jī)位使用率與遠(yuǎn)機(jī)位使用率的和等于1，近機(jī)位使用率最高也就是遠(yuǎn)機(jī)位使用率最低，即

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

機(jī)位j的最后一段空閑時(shí)間為

因此，分配方案的魯棒性最好對(duì)應(yīng)

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

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

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

圖1 分配約束條件關(guān)系Fig.1 Relation between assignment constraints

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

2 算法設(shè)計(jì)

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

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

2.1 第一階段算法

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

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

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

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

第3步計(jì)算目標(biāo)函數(shù)值 根據(jù)第一階段目標(biāo)函數(shù)（式（1））計(jì)算染色體的目標(biāo)函數(shù)值。

第4步適應(yīng)值映射 將目標(biāo)函數(shù)值映射為適應(yīng)值。目標(biāo)函數(shù)值越小，其對(duì)應(yīng)的適應(yīng)值越高。

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

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

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

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

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

經(jīng)過(guò)第一階段運(yùn)算得到軟沖突次數(shù)最少的分配方案，記為yi，j。在保證機(jī)場(chǎng)安全運(yùn)行的條件下，該分配方案最大程度減少了分配方案對(duì)機(jī)場(chǎng)的負(fù)面影響。

2.2 第二階段算法

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

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

第3步計(jì)算目標(biāo)函數(shù)值 根據(jù)第二階段目標(biāo)函數(shù)（式（10）），計(jì)算染色體的目標(biāo)函數(shù)值。

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

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

3 實(shí)驗(yàn)分析

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

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

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

圖4 停機(jī)位分配甘特圖（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是國(guó)際上領(lǐng)先的優(yōu)化軟件包，也是目前公認(rèn)最好的商業(yè)優(yōu)化軟件，在學(xué)術(shù)界和工業(yè)界中普遍認(rèn)為可以將CPLEX中的算法作為新提出算法與之比較的標(biāo)桿[13]。應(yīng)用CPLEX在Matlab環(huán)境下建模并通過(guò)精確算法求解該算例，與通過(guò)兩階段混合遺傳算法求解的結(jié)果進(jìn)行對(duì)比，計(jì)算結(jié)果各項(xiàng)評(píng)價(jià)指標(biāo)如表2所示。

表2 計(jì)算結(jié)果比較Tab.2 Comparison of calculation results

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

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

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

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

4 結(jié)語(yǔ)

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