基于遺傳模擬退火算法的航班著陸調度問題.pdf

1、隨著國民經濟的持續(xù)發(fā)展和中國在世界上受歡迎程度持續(xù)增加，我國民航飛行量快速增長，導致空中交通擁擠現(xiàn)象越來越嚴重。尤其在一些較繁忙的大型機場，航班延誤現(xiàn)象時有發(fā)生。這不僅給航空公司帶來了巨大的經濟損失和信譽損失，也給旅客的出行安全帶來了隱患。為了解決日益嚴重的空中交通擁擠現(xiàn)象，加大乘坐航班的安全系數(shù)，減少航空公司的延誤損失，本文對航班調度問題進行了數(shù)學建模，建立了基于遺傳模擬退火算法的數(shù)學模型，對單跑道的航班調度問題進行了充分的研究分析。

2、
　　本文在參照國內外相關研究的基礎上，主要對單跑道的航班調度問題進行分析研究。本文首先介紹了空中交通流量管理的相關內容，著重介紹了終端區(qū)流量管理的相關知識，包括終端區(qū)基本概念，航班飛行過程，航班排序等基礎知識。其次，在考慮航班延誤損失最小的基礎上，建立了航班調度的數(shù)學規(guī)劃模型，并利用先到先服務算法進行仿真分析，并對其進行了模型上的評價。最后，建立了基于遺傳模擬退火算法的航班調度模型。主要設計思路有以下幾個方面:
　　(1)

3、遺傳算法中采用整數(shù)序號的編碼方式，以航班的實際降落順序作為染色體的基因值，然后對染色體進行解碼，生成航班的實際到達時間。其中解碼操作的主要思想是:對于任意的染色體chrom=(x1，x2,…，xN)，為了保證總損失最小，首先考慮第一個降落的航班x1，令其實際到達時間即為其目標到達時間;然后對于第二個降落的航班x2，從最早到達和最晚到達的時間集合中，刪去與航班x1不滿足時間間隔的時間，從剩下的時間集合中選擇距離x2的目標到達時間最小的時間

4、作為航班的實際到達時間;其次，對于航班x3，同樣從其最早達到和最晚達到的時間集合中，刪去與航班x1和航班x2都不滿足時間間隔的時間，從剩下的時間集合中選擇距離x3的目標到達時間最小的時間作為航班的實際到達時間;以此類推可以得到各個航班的實際到達時間，進而完成染色體chrom的解碼工作。對解碼后的個體reach求解目標函數(shù)值objv。
　　(2)對初始種群中染色體進行選擇，交叉，變異等操作。其中選擇操作采用隨機遍歷抽樣算法SUS。設

5、子代的染色體的個數(shù)為Nsel，SUS具體方法為:隨機排列種群適應度，在[0,SUM/Nsel]范圍內隨機產生一隨機數(shù)作為指針，然后生成相隔SUM/Nsel的Nsel個指針，選擇適應度范圍在指針上的個體。相對于輪盤賭選擇操作來說，SUS算法不僅具有更低的時間復雜度，而且具有最優(yōu)零偏差、最小個體擴展。
　　(3)交叉操作采用兩點交叉的方法。首先利用兩兩配對的原則對子代中的染色體進行兩兩配對，然后判斷它們是否進行交叉操作。對通過交叉概率

6、Pc的染色體進行交叉，首先產生兩個隨機整數(shù)作為交叉位置，交換兩個染色體在交叉位置間的基因;然后利用部分映射的方法，消除染色體中的重復基因，最終得到可行的染色體。
　　(4)變異操作采用單點變異的方法。對通過變異概率Pm的染色體進行變異，對個體的某兩個位置的基因值進行交換。
　　(5)對經過選擇、交叉、變異得到的新個體Selch進行解碼，對解碼后的個體newreach求解目標函數(shù)值newobjv，然后調整解碼后的個體并計算新的

7、目標函數(shù)值。
　　(6)通過采用以上的遺傳操作，再將模擬退火算法加入其中，對產生的新解進行Metropolis準則的判斷:設reachi為問題的當前解，newreachi為新解，T為當前溫度。objv, newobjv分別為解的目標函數(shù)值，增量df=newobjvi-objvi。則Metropolis準則為P={1, df＞0exp(-df/T)， df≤0如果df＞0,則以概率1接受新解;否則，以概率exp（-df/T）接受新解