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

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

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

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

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

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

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

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