混合遺傳算法求解航班延誤恢復調(diào)度

摘 要：綜合考慮航班延誤各類損失，建立了合理的大規(guī)模航班延誤恢復調(diào)度模型。以此模型的目標函數(shù)為適應度函數(shù)，設計了基于遺傳算法和模擬退火算法的混合遺傳算法來快速有效的尋找優(yōu)化恢復調(diào)度方案。仿真結果表明，該算法與先到先服務的現(xiàn)行調(diào)度方法相比，可以有效的減少各種延誤損失。

關鍵詞：航班延誤；調(diào)度模型；混合遺傳算法

引言

航班延誤恢復調(diào)度（Recovery Scheduling of Flight Delays， RSFD）是指由于某些原因造成了大面積的航班延誤，當恢復起飛時，需要重新調(diào)度延誤航班。航班恢復調(diào)度問題是一個多目標的優(yōu)化問題，目前國際、國內(nèi)在理論與實際應用上都沒有很好的解決方法。國內(nèi)機場的普遍做法是靠航空管制員自身的經(jīng)驗和判斷進行的，基于先到先服務原則（First Come First Serve，F(xiàn)CFS），調(diào)度效率較低。因此本文考慮引入遺傳算法，遺傳算法（Genetic Algorithm，GA）在解決最優(yōu)化問題上有較好的效果，但“早熟”（Prematurely）現(xiàn)象是目前遺傳算法研究中的關鍵問題。所以在這種情況下考慮引入模擬退火算法對遺傳算法進行改進，利用該算法在搜索時可以以一定概率接受劣質(zhì)解的策略避免遺傳迭代過程提前陷入局部最優(yōu)，從而提高算法的魯棒性，將兩者結合，有利于豐富優(yōu)化過程中的搜索行為，增強全局和局部搜索能力和搜索效率。

1 航班延誤經(jīng)濟損失

航班延誤經(jīng)濟損失通常包括顯性損失和隱性損失兩部分[1][2]，如圖1：

延誤航班的運營成本

2 混合遺傳算法求解航班延誤回復調(diào)度問題

本文采用遺傳算法與模擬退火算法相結合，設計混合遺傳算法[3][4][5][6][7]如下：

（1）選擇編碼，生成初始群體

本文對于研究的航班延誤恢復調(diào)度問題采用實數(shù)編碼，如：12345678代表發(fā)生延誤的航班序列，在經(jīng)過優(yōu)化后得到新的染色體18524376，這條新的染色體代表延誤發(fā)生后給出的最新調(diào)度方案。通常取值在10到80之間的群體規(guī)模比較合理。因此先按照實數(shù)編碼形成n個航班的一個全排列，然后重復生成需要的種群數(shù)目。

（2）設計適應度函數(shù)

（4）設計交叉算子

本文采用改進的部分匹配交叉（PMX）方法。隨機選取兩個父輩染色體，任意選擇兩個交叉點，將一個染色體的交叉段移到對方染色體的前部，然后將對方染色體的相同基因刪掉得到新的子個體。

（5）設計變異算子

本文采用倒位變異法設計變異算子。隨機選擇一個染色體的任意兩個點，顛倒此個體編碼中這兩個點的基因排列順序，從而形成一個新的子代染色體。

（6）自適應參數(shù)調(diào)整策略

本文采用自適應參數(shù)調(diào)整策略調(diào)整交叉率pc和變異率pm，達到有效防止早熟收斂，具體為：

其中，fmax是某一代群體中適應度函數(shù)最大的個體的適應度；f表示此代染色體的平均適應度；f'為隨機選取的兩個交叉?zhèn)€體中適應度較大的一個，f\"為變異個體的適應度。

（7）最優(yōu)個體保留策略

為了避免“早熟”，在遺傳算法中采用了保留最優(yōu)個體的策略，用它直接替換掉本代種群中經(jīng)過所有遺傳操作后所新生成的適應度值為最低的個體，避免一些好的基因個體被提前淘汰。

（8）模擬退火操作

模擬退火算法[8]模擬固體退火的過程，采用Metropolis接受準則，該算法可以有效緩解遺傳算法的早熟壓力，避免一些劣質(zhì)解里的有用基因在迭代過程選擇中被淘汰。

3 仿真結果分析

仿真案例

假設北京首都機場上午8：00開始出現(xiàn)了霧霾天氣，造成大量滯留，大面積延誤，直到10：00天氣情況好轉(zhuǎn)，可以恢復調(diào)度。延誤數(shù)據(jù)如下表所示（假設每2分鐘起飛一架次航班）：

結果分析

本例中種群數(shù)目取為30，初始溫度為8000，終止溫度取為320，最大遺傳次數(shù)取為300，衰減系數(shù)？姿取為0.999，算法采用MATLAB編程；圖3分別給出第20代種群和第300代種群的染色體適應度分布圖，迭代過程中總延誤費用變化圖。

從圖3可以很明顯看出，隨著遺傳操作的深入，染色體分布由最初的混亂無序漸漸步入穩(wěn)定，延誤費用的變化曲線逐漸趨于平緩，延誤費用最后收斂為一個較小的數(shù)值，說明搜索到的解是滿意解。得到新的調(diào)度方案如表5：

從得到的調(diào)度方案看到，采用混合遺傳算法得到的總延誤費用比先到先得的傳統(tǒng)調(diào)度算法得到的總延誤費用減少了7.05%，由此可見，本文選取的調(diào)度模型和設計算法比較有效。

4 結束語

本文在延誤模型的建立中，綜合考慮了航班延誤所造成的航空公司經(jīng)濟損失和旅客經(jīng)濟損失以及各個航線的影響系數(shù)，構建了新的恢復調(diào)度模型。在算法設計中，采用了自適應參數(shù)調(diào)整策略來控制交叉和變異操作，有效的避免優(yōu)秀個體被破壞，改善了遺傳算法的性能，同時考慮到遺傳算法雖然有很好的全局尋優(yōu)能力，但有陷入“早熟”問題的風險，將模擬退火算法引入到算法中，利用其在一定概率下接受劣質(zhì)解的特性改善遺傳算法的不足，提高算法的魯棒性，從而生成新的混合遺傳算法來求解此問題。并針對首都機場的某時段離港航班數(shù)據(jù)進行了仿真試驗，計算結果表明了此模型的實用性及算法的有效性。

參考文獻

[1]丁健立，王新如，徐濤.航班延誤恢復調(diào)度的混合粒子群算法[J].交通運輸工程學報，2008，8（2）.

[2]丁建立，李華峰.一種新型航班延誤組合預測模型[J].中國民航大學學報，2011（3）.

[3]王小平，曹立明.遺傳算法-理論、應用與軟件實現(xiàn)[M].西安：西安交通大學出版社，2002.

[4]趙慧娟，孫文輝.基于退火遺傳算法的單元測試方法[J].計算機工程，2013（1）.

[5]王秋芬，梁雷道.一種求解0-1背包問題的啟發(fā)式遺傳算法[J].計算機應用與軟件，2013（2）.

[6]李書全，孫雪.遺傳算法中的交叉算子的述評[J].計算機工程與應用，2012（1）.

[7]孔德劍.基于改進的遺傳算法的多目標優(yōu)化問題研究[J].計算機仿真，2012（2）.

[8]彭勇剛，羅小平，韋巍.一種新的模糊自適應模擬退火遺傳算法[J].控制與決策，2009（6）.

作者簡介：曲倩倩，畢業(yè)于西北工業(yè)大學自動化學院交通運輸規(guī)劃與管理專業(yè)，現(xiàn)就職于上海民航職業(yè)技術學院經(jīng)管系運輸組，助講，主要研究方向為民航運輸。