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

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

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

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

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

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

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

7、目標(biāo)函數(shù)值。
　　(6)通過(guò)采用以上的遺傳操作，再將模擬退火算法加入其中，對(duì)產(chǎn)生的新解進(jìn)行Metropolis準(zhǔn)則的判斷:設(shè)reachi為問(wèn)題的當(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）接受新解