機(jī)場航空器地面滑行調(diào)度優(yōu)化研究

基于改進(jìn)遺傳算法的滑行道優(yōu)化研究摘要隨著我國民航運(yùn)輸業(yè)的快速發(fā)展，繁忙機(jī)場面臨著日漸增大的流量壓力。研究機(jī)場滑行調(diào)度優(yōu)化的目的，是在保證安全的前提下，充分利用機(jī)場滑行道系統(tǒng)的資源，提高運(yùn)行效率，增大機(jī)場容量。本文簡單地介紹了機(jī)場場面結(jié)構(gòu)及滑行優(yōu)化問題的建模思路。根據(jù)雙流機(jī)場得到的滑行路徑和序列數(shù)據(jù)，確定各個航班的滑行時間。在優(yōu)化算法的選擇環(huán)節(jié)，對比常見遺傳算法滑行道調(diào)度模型，提出一種基于標(biāo)準(zhǔn)遺傳算法與模擬退火算法思想相結(jié)合的改進(jìn)算法。展示了優(yōu)化結(jié)果與算法的收斂性，驗(yàn)證了該模型達(dá)到優(yōu)化的可行性。關(guān)鍵詞：機(jī)場；滑行調(diào)度；改進(jìn)遺傳算法；數(shù)學(xué)模型；模擬退火算法

ResearchonOptimizationoftaxiwaybasedonImprovedGeneticAlgorithmStudent:LiZiyuanInstructsteacher:JiangBoAbstractWiththerapiddevelopmentofChina'scivilaviationtransportindustry,busyairportsarefacingincreasingtrafficpressure.Thepurposeofstudyingairporttaxiwaydispatchingoptimizationistomakefulluseoftheresourcesofairporttaxiwaysystem,improveoperationefficiencyandincreaseairportcapacityonthepremiseofensuringsafety.Thispaperbrieflyintroducesthemodelingideaofairportscenestructureandtaxiingoptimizationproblem.AccordingtothetaxiingpathandsequencedataobtainedfromShuangliuAirport,thetaxiingtimeofeachflightisdetermined.Intheselectionofoptimizationalgorithm,animprovedalgorithmbasedonthecombinationofstandardgeneticalgorithmandsimulatedannealingalgorithmisproposedbycomparingthecommongeneticalgorithmtaxiwayschedulingmodel.Theconvergenceoftheoptimizationresultsandthealgorithmisshown,andthefeasibilityofthemodeltoachieveoptimizationisverified.Keywords:airport;taxiwayscheduling;improvedgeneticalgorithm;mathematicmodel;conflictresolution目錄摘要 頁引言1.1選題背景和意義我國民航事業(yè)近些年來發(fā)展迅速，作為一個民航大國正不斷向民航強(qiáng)國的目標(biāo)前進(jìn)。根據(jù)2018年民航業(yè)發(fā)展統(tǒng)計公報顯示[1]2018年我國機(jī)場主要生產(chǎn)指標(biāo)繼續(xù)保持平穩(wěn)較快增長，全年旅客吞吐量超過12億人次，完成126468.9萬人次，較上年增長10.2%。分航線看，國內(nèi)航線完成113842.7萬人次，較上年增長9.9%（其中內(nèi)地至香港、澳門和臺灣地區(qū)航線完成2872.7萬人次，較上年增長6.0%）；國際航線完成12626.1萬人次，較上年增長13.0%。據(jù)從民航資源網(wǎng)獲取的2018年中國民航機(jī)場吞吐量排名數(shù)據(jù)[2]顯示，2018年我國頒證運(yùn)輸機(jī)場數(shù)量達(dá)到235個，完成飛機(jī)起降1108.8萬架次，較上年同比增長8.2%。。詳細(xì)數(shù)據(jù)見下表（表1.12018年中國民航機(jī)場旅客吞吐量排名）。其中各機(jī)場起降架次更是呈現(xiàn)明顯增長趨勢，部分國內(nèi)機(jī)場2018年起降架次甚至比2017年同期增長超過百分之百，例如瓊海博鰲機(jī)場2018年起降架次比同期增長122.90%，廣元盤龍機(jī)場2018年起降架次比2017年同期增長100.30%，詳細(xì)數(shù)據(jù)見下表1.2（表1.22018年中國民航機(jī)場起降架次排名取前十）。表1-12018年中國民航機(jī)場旅客吞吐量排名機(jī)場旅客吞吐量（人次）名次本期完成上年同期同比增速%合計1,264,688,737114786.710.2北京/首都1100,983,29094,393,4545.4上海/浦東274,006,33166,002,4145.7廣州/白云369,720,40365,806,9775.9成都/雙流452,950,52949,801,6936.3深圳/寶安549,348,95045,610,6518.2昆明/長水647,088,14044,727,6915.3上海/虹橋743,628,00441,884,0594.2西安/咸陽844,653,31141,857,2296.7重慶/江北941,595,88738,715,2107.4杭州/蕭山1038,241,63035,570,4117.5表1-22018年中國民航機(jī)場起降架次排名機(jī)場起降架次（架次）名次起降架次本期完成同比增速%北京/首都1614022597,2592.80上海/浦東2504794496,7741.60廣州/白云3477364465,2952.60昆明/長水4360785350,2733.00深圳/寶安5355907340,3854.60成都/雙流6352124337,0554.50西安/咸陽7330477318,9593.60重慶/江北8300745288,5984.20杭州/蕭山9284893271,0665.10上海/虹橋10266790263,5861.20民航業(yè)務(wù)發(fā)展迅速，而各種原因造成的延誤也隨之增多，尤其是大型機(jī)場繁忙時段，機(jī)場場面的大面積延誤，不僅降低了機(jī)場場面資源的運(yùn)行效率，還增加了航空公司的成本，造成環(huán)境污染，而且使管制員的工作負(fù)荷加重，存在風(fēng)險，對空中交通和機(jī)場地面交通管理形成了極大的壓力。因此研究高效的機(jī)場場面調(diào)度的優(yōu)化手段成為當(dāng)務(wù)之急?；械镭?fù)責(zé)作為連接停機(jī)位和跑道的通道，機(jī)場活動區(qū)內(nèi)不僅存在航空器的運(yùn)行，還存在車輛、人員等諸多可能影響正常運(yùn)行的不定因素，交通狀況相當(dāng)復(fù)雜，管制員為進(jìn)離港航班分配滑行道需要同時考慮人員、車輛、航班等諸多因素，因此滑行道的利用率很難最大化，造成航班在滑行道以及跑道外等待的延誤。即使目前我國部分機(jī)場已發(fā)布對應(yīng)停機(jī)位的標(biāo)準(zhǔn)滑行路徑，但是管制現(xiàn)場大部分情況仍然是管制員人工決策，且機(jī)場場面活動具有動態(tài)性、復(fù)雜性的特點(diǎn)，大型機(jī)場航班量高度集中時標(biāo)準(zhǔn)滑行路徑難以滿足滑行安全與效率的需求。因此，在當(dāng)前中國民航大發(fā)展的背景下尋求可行的優(yōu)化算法對機(jī)場滑行道進(jìn)行研究具有現(xiàn)實(shí)意義。1.2國內(nèi)外研究概況針對機(jī)場滑行道調(diào)度問題，國內(nèi)外學(xué)者已經(jīng)做出了許多優(yōu)化研究。包括解決滑行沖突點(diǎn)避讓和動態(tài)優(yōu)先級滑行調(diào)度的優(yōu)化等。HenryYKLan等團(tuán)隊[3]提出一種帶有邊界約束的路徑集合劃分的方法調(diào)度進(jìn)離場航空器；GillianLClare團(tuán)隊成員[4]采用了混合整數(shù)線性規(guī)劃模型（mixedintegerlinearprogramming，MILP）和滾動時域相結(jié)合的方法解決此問題，提高了MILP算法的可操作性。國內(nèi)的研究方面，汪千川[5]在2001年研究記憶遺傳算法和模擬退火算法的改進(jìn)和應(yīng)用，潘全科在解決車間調(diào)度問題上，提出了遺傳算法和模擬退火算法的不足，結(jié)合采用了遺傳退火，并與遺傳算法作比較取得了進(jìn)展。劉兆明[6]研究了基于計算智能的航空調(diào)度優(yōu)化方法研究，通過自適應(yīng)函數(shù)代入遺傳算法進(jìn)行航空路徑的優(yōu)化。在中國研究航空器滑行調(diào)度方面，仍然不夠成熟，沒有講方法進(jìn)行規(guī)模和系統(tǒng)化，只能根據(jù)以往的歷史數(shù)據(jù)進(jìn)行統(tǒng)計分析，但依賴統(tǒng)計數(shù)據(jù)缺乏實(shí)際操作和系統(tǒng)性理論的支撐。國外學(xué)者對機(jī)場機(jī)動區(qū)域內(nèi)的關(guān)鍵沖突點(diǎn)以及安全風(fēng)險識別和評估等相關(guān)問題進(jìn)行了較全面深入的研究。2010年NASA[7]由提出了一種“機(jī)場地面交通沖突避免”的概念，用以實(shí)現(xiàn)機(jī)場滑行道等的潛在沖突。S.G.PonnambalamandM.MohanReddy于2003年提出了遺傳退火算法多目標(biāo)混合搜索算法用于排序。在上述文獻(xiàn)中，大量地闡述了場面沖突的監(jiān)視或者規(guī)避，對于靜態(tài)路徑規(guī)劃具有較大的意義；但對隨機(jī)突發(fā)事件引起的時間狀態(tài)和路徑改變，原有方法將不再適用，在科技急速發(fā)展的當(dāng)下，需要對原有算法進(jìn)行大膽創(chuàng)新與驗(yàn)證。1.3課題主要研究工作機(jī)場調(diào)度問題覆蓋許多子問題，而地面滑行調(diào)度是連接多個問題的樞紐，將進(jìn)離港航空器與停機(jī)等問題連接起來。本文在國內(nèi)外學(xué)者相關(guān)研究的基礎(chǔ)上，提出一種基于標(biāo)準(zhǔn)遺傳算法動態(tài)變化交叉遺傳的概率，以及與退火算法相結(jié)合。利用改進(jìn)的遺傳算法，調(diào)整航班優(yōu)先級序列，達(dá)到既能解決標(biāo)準(zhǔn)遺傳算法的缺陷也能取得模擬退火算法的有點(diǎn)；根據(jù)法律以及相關(guān)明文規(guī)定的滑行調(diào)度約束條件，為滑行道各節(jié)點(diǎn)確定各個航班經(jīng)過的滑行路徑。在解決航空器滑行沖突的情況后，將沖突等待時間分散在停機(jī)位和滑行道上，更加符合實(shí)際運(yùn)行的情況。

第二章機(jī)場場面介紹由于我國航空業(yè)的發(fā)展速度較快，空中交通流量的增長也隨之加快，我國民航機(jī)場的數(shù)量與規(guī)模也隨之壯大，機(jī)場地面運(yùn)行結(jié)構(gòu)也變得更加復(fù)雜多樣。本章簡單介紹機(jī)場場面各單元的基本概念，對機(jī)場場面滑行網(wǎng)絡(luò)進(jìn)行抽象成有向網(wǎng)絡(luò)結(jié)構(gòu)模型，對航空器的滑行過程，存在的沖突以及沖突解決策略進(jìn)行簡單描述，簡述了多跑道（尤其是平行跑道）運(yùn)行的相關(guān)規(guī)定，明確本文問題研究目標(biāo)。2.1機(jī)場場面結(jié)構(gòu)機(jī)場場面功能區(qū)主要包括飛行區(qū)、航站樓、貨運(yùn)站、飛機(jī)維修區(qū)等區(qū)域，本文研究機(jī)場場面優(yōu)化的對象主要是針對機(jī)場飛行區(qū)內(nèi)供航空器起降與滑行的跑滑系統(tǒng)，包括航空器的滑行過程，主要涉及包括跑道、滑行道系統(tǒng)。2.1.1跑道跑道是機(jī)場上為航空器起飛和落地而劃定修建的場地，主要用于航空器的起降、滑跑活動。若有進(jìn)離場航空器正使用跑道，禁止其他航空器進(jìn)入同一條跑道。跑道屬性有：方向、數(shù)量、長度、寬度、運(yùn)行模式等。跑道設(shè)計的方向主要考慮機(jī)場的主要風(fēng)向及風(fēng)速。跑道長度受諸多因素影響，其中典型影響因素包括機(jī)場所處海拔高度、平均溫度、跑道道面強(qiáng)度、坡度及設(shè)計供起降的最大機(jī)型的起降滑跑距離。2.1.2滑行道滑行道主要作用是作為進(jìn)離場航空器在跑道與其他機(jī)場區(qū)域之間活動的通道，滑行道將機(jī)場各單元連接為一個整體，使機(jī)場場面連貫運(yùn)行，是避免航空器在地面運(yùn)行產(chǎn)生沖突的重要系統(tǒng)。根據(jù)滑行道不同的功能以及分布，滑行道一般可分為主滑行道（也稱作平行滑行道）、快速脫離道、繞行滑行道等。主滑行道是指在跑道與停機(jī)位之間，航空器主要使用的滑行道，通常也稱作平形滑行道?？焖倜撾x道是起連接跑道和主滑行道的功能，沿著跑道分布的通道，主要用以加快跑道使用效率，供落地航空器盡快脫離跑道。2.2機(jī)場場面滑行過程滑行道連接跑道和停機(jī)位，是機(jī)場場面運(yùn)行的重要元素。機(jī)場場面滑行過程主要是進(jìn)港過程以及離港過程。航空器進(jìn)港滑行過程。對于進(jìn)港的航空器而言，獲取落地許可后，航空器落地并經(jīng)由適當(dāng)?shù)拿撾x道脫離跑道，脫離跑道后航空器沿管制員指定的滑行路徑滑行進(jìn)位分配的停機(jī)位，進(jìn)港滑行過程結(jié)束。航空器離港滑行過程。對于離港的航空器而言，當(dāng)其在停機(jī)位上所有的保障工作完成后，根據(jù)管制員的指令進(jìn)行推出開車或原地開車。當(dāng)完成開車的準(zhǔn)備工作后，飛行員向管制員發(fā)出請求滑出的請求，地面管制員經(jīng)綜合分析該航空器所使用跑道以及當(dāng)時機(jī)場場面交通狀況，向該航空器發(fā)出滑行指令，指令中包含為該航空器指定的滑行路徑。航空器沿管制員指定的滑行路徑滑行至正確的跑道，并在跑道等待點(diǎn)等待管制員的進(jìn)一步指令，離港滑行過程結(jié)束。在航空器滑行過程中飛行員與駕駛員必須遵守相應(yīng)的滑行規(guī)則，包括：（1）飛行員必須嚴(yán)格按照管制員指定的滑行路徑滑行；（2）航空器滑行速度應(yīng)根據(jù)飛行手冊或機(jī)場相關(guān)駕駛規(guī)定調(diào)整，場面滑行速度一般不允許大于50；（3）航空器滑行時應(yīng)注意保持安全間隔，實(shí)際運(yùn)行之中，由飛行員負(fù)責(zé)把握與其他航空器之間的間隔；（4）管制員指定滑行路徑時應(yīng)考慮提前規(guī)避對頭沖突。對航空器的地面滑行過程進(jìn)行分析，可將滑行路徑上存在的潛在沖突歸為交叉沖突、追尾沖突以及對頭沖突三大類：（1）交叉沖突：兩架或多架航空器滑行過程中存在同時經(jīng)過同一個滑行道道口的情況。在大型繁忙機(jī)場，主滑行道一般連接多條快速脫離道，而實(shí)際管制工作中，管制員一般會盡可能指揮航空器在平行滑行道上滑行，這種情況下，在平行滑行道上的航空器容易與從快速脫離道脫離跑道的航空器產(chǎn)生交叉沖突。交叉沖突的沖突解除策略一般采用先到先服務(wù)原則，即允許先到達(dá)滑行道道口的航空器通過節(jié)點(diǎn)，另一架后到達(dá)的航空器等待一段時間直至滿足最小安全間隔。（2）追尾沖突：兩架滑行方向相同的航空器同時使用同一段滑行道，而在滑行過程中，存在后機(jī)追趕前機(jī)發(fā)生碰撞的可能。但實(shí)際運(yùn)行中，后機(jī)駕駛員會依據(jù)情況調(diào)整航空器速度自行把握與前機(jī)的安全間隔。在構(gòu)建數(shù)學(xué)模型時，為規(guī)避這類沖突，可以規(guī)定鏈路中的所有航空器滑行速度相同。（3）對頭沖突：兩架滑行方向相對的航空器同時使用同一段滑行道。實(shí)際管制工作過程中，機(jī)場場面布局復(fù)雜，無法完全理想化分配滑行路徑，而滑行路徑由管制員臨場指定，管制員易遺忘已發(fā)布的滑行路徑，這就會導(dǎo)致對頭沖突的發(fā)生。在數(shù)學(xué)模型中，假定兩節(jié)點(diǎn)分別為與，為規(guī)避對頭沖突，若已經(jīng)將的鏈路分配給一架航空器，則將的鏈路視作0，該鏈路不可用，并且每架航空器經(jīng)過某節(jié)點(diǎn)后不可重復(fù)經(jīng)過。2.3機(jī)場場面滑行優(yōu)化問題針對進(jìn)場航空器是指給進(jìn)場航空器分配適當(dāng)?shù)呐艿莱隹诿撾x跑道，進(jìn)入滑行道并指定適當(dāng)?shù)幕新肪€使其順利進(jìn)入指定的停機(jī)位。針對離場航空器是指給離場航空器指定適當(dāng)?shù)幕新肪€使其由停機(jī)位出發(fā)滑行到所使用跑道的跑道等待點(diǎn)。機(jī)場場面滑行路徑優(yōu)化主要研究工作是為進(jìn)離場航空器分配最優(yōu)的滑行路徑，達(dá)到進(jìn)離場航空器總滑行時間最短的目標(biāo)。跑道的運(yùn)行調(diào)度也是影響機(jī)場場面運(yùn)行調(diào)度的一個重要環(huán)節(jié)。進(jìn)場航空器落地后，何時以及從哪個脫離道口脫離跑道，決定了其滑行過程的開始滑行時間、滑行路徑的起點(diǎn)。離場航空器滑行至跑道等待點(diǎn)等待的時間決定其使用跑道的最早時間，進(jìn)入跑道的時間也受前行使用跑道的航空器運(yùn)行情況影響，因此跑道運(yùn)行也是離場滑行過程的影響因子。本文將跑道的運(yùn)行調(diào)度考慮進(jìn)了滑行優(yōu)化模型，主要針對離場航空器，將連續(xù)放行多架航空器以及著陸與起飛航空器之間的安全間隔考慮進(jìn)模型中，構(gòu)建滑行道與跑道的聯(lián)合優(yōu)化模型。2.4建立機(jī)場場面網(wǎng)絡(luò)結(jié)構(gòu)模型機(jī)場場面系統(tǒng)整體而言是一個相對復(fù)雜的結(jié)構(gòu)。本文擬使用網(wǎng)絡(luò)模型來簡化描述機(jī)場場面系統(tǒng)的各組成部分，網(wǎng)絡(luò)由節(jié)點(diǎn)、還有節(jié)點(diǎn)之間的連線組成，機(jī)場場面系統(tǒng)可以抽象理解成機(jī)場場面網(wǎng)絡(luò)圖，其中，表示節(jié)點(diǎn)集合，主要包括滑行道之間的交叉點(diǎn)、跑道等待點(diǎn)以及脫離道口。表示鏈路邊，即各段滑行道，鏈路邊的屬性包括長度屬性、航空器機(jī)型限制、滑行速度限制、滑行方向限制等。機(jī)場場面結(jié)構(gòu)圖簡單示例見圖2.1。圖2-1雙流機(jī)場場面結(jié)構(gòu)局部示例2.5多跑道運(yùn)行相關(guān)規(guī)定根據(jù)跑道的數(shù)量，可以將機(jī)場分為單跑道和多跑道機(jī)場。多跑道機(jī)場中，比較普遍的是平行跑道布局，而我國目前所有多跑道機(jī)場均采用平行跑道布局模式。根據(jù)我國民航局于2004年6月26日開始實(shí)施中國民用航空總局第123號令《平行跑道同時儀表運(yùn)行管理規(guī)定》，平行跑道同時儀表運(yùn)行分為獨(dú)立平行儀表進(jìn)近、相關(guān)平行儀表進(jìn)近、獨(dú)立平行離場、隔離平行運(yùn)行等四種模式。本文模型考慮的是雙流機(jī)場隔離平行運(yùn)行模式，即其中一條跑道只用于離場，另一條跑道只用于進(jìn)近。根據(jù)跑道間距的條件不同，規(guī)定了該平行跑道能夠使用的運(yùn)行模式，總結(jié)見下表2.1。表2.1平行跑道同時儀表運(yùn)行規(guī)定平行跑道中心線最小間距/m運(yùn)行模式按一條跑道起降間隔執(zhí)行允許隔離運(yùn)行、獨(dú)立平行離場允許相關(guān)平行儀表進(jìn)近允許獨(dú)立平行儀表進(jìn)近先后連續(xù)起降的航空器之間必須配備一定的縱向間隔，以保證航空器使用跑道的過程中不存在沖突。起降航班之間的安全間隔通常為根據(jù)航空器的機(jī)型分類而規(guī)定的尾流間隔最低標(biāo)準(zhǔn)，根據(jù)航空器最大起飛權(quán)重劃分為重、中、輕三類，見下表2.2。表2.2航空器分類航空器最大準(zhǔn)許起飛全重/噸航空器機(jī)型輕型機(jī)中型機(jī)重型機(jī)（備注：B757尾流歸為重型機(jī)尾流）若前機(jī)為離場航空器，后機(jī)為進(jìn)場航空器，在前機(jī)起飛并離開跑道后，后機(jī)可以落地；若前，后機(jī)均為離場航空器，則需根據(jù)機(jī)型滿足相關(guān)的尾流間隔。若前機(jī)為進(jìn)場航空器，后機(jī)為離場航空器，只有前機(jī)報告其脫離跑道后，后機(jī)方可開始進(jìn)入跑道（實(shí)際在流量大的情況下前機(jī)落地后，可指揮后機(jī)進(jìn)入跑道等待）；若后機(jī)為進(jìn)場航空器，則需根據(jù)機(jī)型滿足相關(guān)的尾流間隔。本文計劃采用雙流國際機(jī)場作為實(shí)際案例進(jìn)行分析，雙流國際機(jī)場平行跑道02L/20R與跑道02R/20L的跑道中心線間距1525米，根據(jù)我國《民用航空空中交通管理規(guī)則》對安全尾流間隔進(jìn)行規(guī)定。前后起飛離場或前后進(jìn)近的航空器，其雷達(dá)間隔的尾流標(biāo)準(zhǔn)見下表2.3：表2.3雷達(dá)間隔的尾流標(biāo)準(zhǔn)單位：千米后機(jī)重型機(jī)中型機(jī)輕型機(jī)前機(jī)A380-80011.113.014.8重型機(jī)7.49.311.1中型機(jī)669.3輕型機(jī)6662.6本章小結(jié)本章對機(jī)場場面結(jié)構(gòu)進(jìn)行了一個簡單的分析討論，尤其是針對飛行區(qū)的滑行系統(tǒng)以及跑道系統(tǒng)進(jìn)行了簡單的探討。關(guān)于本文研究的滑行路徑優(yōu)化問題，本章針對滑行過程中航空器應(yīng)注意的幾個規(guī)則以及滑行過程中可能出現(xiàn)的三種沖突與如何在算法中解決此類沖突進(jìn)行了簡單闡述，探討了規(guī)避各類沖突的解決方案，提出了構(gòu)建機(jī)場場面網(wǎng)絡(luò)機(jī)構(gòu)模型，介紹了平行跑道同時儀表運(yùn)行的運(yùn)行模式以及運(yùn)行間隔標(biāo)準(zhǔn)，為構(gòu)建機(jī)場場面滑行優(yōu)化模型建立理論基礎(chǔ)。

第三章遺傳算法介紹3.1遺傳算法的生物學(xué)基礎(chǔ)[22]自然界生物在繁衍生息過程中，遵循著對于自然環(huán)境的“適者生存”法則和一定的遺傳規(guī)律。現(xiàn)代生物進(jìn)化理論以自然選擇學(xué)說為核心，其基本觀點(diǎn)為：生物的進(jìn)化是以種群為單位，而不是以個體為單位。生物的進(jìn)化主要依賴于基因的變異，所以生物進(jìn)化的實(shí)質(zhì)就是種群基因的變化。通常，自然界中新物種的形成需要以下幾個步驟：第一步是基因突變和基因重組，這個過程會形成多種基因組合形式，進(jìn)而以表現(xiàn)型出現(xiàn)在自然界中，經(jīng)歷第二步的自然選擇；第二步就是自然界的“物競天擇，優(yōu)勝劣汰”過程，能夠適應(yīng)環(huán)境的基因得以留存，反之則被淘汰消失；第三步為種群隔離，新生的種群開始與其它種群形成生殖隔離，這起到保護(hù)新種群的作用。生物新物種的形成有兩種方式：漸變式和爆發(fā)式。漸變式是指物種隨著時間的推移，通過多代的突變積累，最終形成新的物種，這個過程當(dāng)中還會有亞種的出現(xiàn)；爆發(fā)式與漸變式最大的不同在于沒有中間亞種的階段，一次完成新物種的產(chǎn)生。這種新物種的產(chǎn)生方式一般有三種類型：雜交、染色體結(jié)構(gòu)變化、多倍體化。遺傳是漸變式和爆發(fā)式兩種方式的融合。人類基于遺傳這一自然界現(xiàn)象開發(fā)出的遺傳算法，在解決各種復(fù)雜優(yōu)化問題的過程中，能展現(xiàn)出其獨(dú)特的優(yōu)勢。3.2遺傳算法的原理概述遺傳算法是一種借鑒現(xiàn)代生物進(jìn)化理論。以生物遺傳的規(guī)律為框架，屬于啟發(fā)式算法的一種，目前得到的廣泛的應(yīng)用。遺傳算法通過模擬優(yōu)勝劣汰的過程來進(jìn)行種群的優(yōu)化，首先利用特定的編碼技術(shù)，將染色體用字符串的形式表示，之后將這些字符串類比于生物群體然后進(jìn)行計算。算法過程使用有組織的、隨機(jī)的字符交換來重新組合一些適應(yīng)性好的字符串，產(chǎn)生新的、由適應(yīng)性好的字符串組成的群體。經(jīng)過這樣多次的迭代，最終尋找到一個最優(yōu)解或者相對最優(yōu)解。3.3遺傳算法應(yīng)用于繁忙機(jī)場路徑優(yōu)化的優(yōu)劣勢分析遺傳算法相比一般的路徑規(guī)劃算法存在優(yōu)勢，是因?yàn)檫z傳算法在尋找最優(yōu)解時，不僅僅是對狀態(tài)空間中的節(jié)點(diǎn)進(jìn)行一個個地排除，而且在不同結(jié)果組成的集合中尋找最優(yōu)解。在對所有飛機(jī)的路徑形成的集合進(jìn)行尋優(yōu)時，可以充分考慮效率要求和沖突約束條件，在全局層面上找到最優(yōu)解，使得單位時間所有航班的總滑行路程（時間）最小，并可以最大程度避免沖突。遺傳算法屬于啟發(fā)式算法，但其在全局規(guī)劃方面的優(yōu)勢，是諸如貪婪算法，模擬退火算法算法所無法比擬的。遺傳算法在應(yīng)對繁忙機(jī)場的路徑優(yōu)化時，也存在不足。遺傳算法的搜索空間較大、算法較為復(fù)雜，所以效率不高。特別是，隨著環(huán)境中節(jié)點(diǎn)的增加或障礙物數(shù)目的增加，算法的復(fù)雜度和尋優(yōu)難度會迅速增加。另外，由于繁忙機(jī)場場面情況時刻在變化，因此需要進(jìn)行較高頻率的重規(guī)劃，也會使得系統(tǒng)負(fù)擔(dān)過重，造成效率下降。解決這樣的問題，一是在滿足安全條件的情況下，要不斷嘗試簡化設(shè)計遺傳算法，使得算法的體量減小；二是路徑規(guī)劃系統(tǒng)的硬件計算能力要足夠強(qiáng)大，才能在較短時間內(nèi)完成尋優(yōu)和保證穩(wěn)定性。3.4遺傳算法的實(shí)現(xiàn)步驟3.4.1流程框架使用遺傳算法求解目標(biāo)函數(shù)的最優(yōu)解，通常需要圍繞所建立的數(shù)學(xué)模型，進(jìn)行遺傳算法的操作，簡單遺傳算法的流程框圖如圖3.1所示。圖3-1簡單遺傳算法的流程框圖3.4.2染色體編碼編碼是將遺傳算法應(yīng)用到實(shí)際優(yōu)化問題的第一步，根據(jù)所研究問題的性質(zhì)和要求，可選擇不同的編碼方式。編碼方式的選擇，直接影響到之后的選擇、交叉、變異等操作，進(jìn)而影響整個算法的性能。從所求解問題的可行解空間，轉(zhuǎn)化為能夠被遺傳算法處理的搜索空間這一過程，叫做編碼。路徑優(yōu)化類問題常見的編碼方式有二進(jìn)制編碼和實(shí)數(shù)編碼。（1）二進(jìn)制編碼二進(jìn)制編碼方法是遺傳算法中最常見的編碼方式，它使用由二進(jìn)制符號0、1組成的二進(jìn)制字符串表示種群中個體的基因，每個字符串對應(yīng)一個基因型。例如：1≤x≤100，精度為1。m表示二進(jìn)制編碼長度，m的值取決于式：2m-1≤100（精度為1）≤2m-1，所以此例中取m=7。則字符串0100100表示一個基因，其對應(yīng)的解空間中的x=36。二進(jìn)制編碼具有如下特點(diǎn)：編碼與解碼簡單易行，容易實(shí)現(xiàn)交叉與變異操作，但當(dāng)字符串的長度較大時，會使遺傳算法的搜索空間急劇增大。另外，它不能像實(shí)數(shù)編碼那樣直觀地反映出所求問題本身的特征和性質(zhì)。（2）實(shí)數(shù)編碼對于一些擁有較大搜索空間、較多變量約束條件并且精度要求較高的優(yōu)化問題，使用二進(jìn)制編碼表示基因時將會有上述的不利之處。這種情況下實(shí)數(shù)編碼更為適用。實(shí)數(shù)編碼使用一定范圍內(nèi)的實(shí)數(shù)來表示種群中個體的基因型，其個體的編碼長度只取決于數(shù)學(xué)模型中變量的位數(shù)。3.4.3適應(yīng)度函數(shù)的選擇

遺傳算法中以個體適應(yīng)度的大小來評定各個個體的優(yōu)劣程度，從而決定其遺傳機(jī)會的大小。如果說利用自然選擇從一群普通羊中篩選出能夠適應(yīng)高原氣候的羊便是遺傳算法優(yōu)勝劣汰的原理，那么每只羊?qū)τ诟咴h(huán)境的適應(yīng)能力就用適應(yīng)度來表示，在本文用適應(yīng)度函數(shù)表示。直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解或者近似最優(yōu)解，主要取決于適應(yīng)度函數(shù)（fitnessfunction）的選取，因?yàn)檫z傳算法在進(jìn)化搜索中僅考慮種群內(nèi)部的各種約束，外界因素影不納入到實(shí)際計算中，所以適應(yīng)度函數(shù)就成為了影響整個算法的主要依據(jù)，利用種群每個個體的適應(yīng)度來進(jìn)行搜索。因?yàn)檫m應(yīng)度函數(shù)的復(fù)雜度是遺傳算法復(fù)雜度的主要組成部分,所以適應(yīng)度函數(shù)的設(shè)計應(yīng)盡可能簡單,使計算的時間復(fù)雜度最小。為了描述在遺傳算法中各個體的主要指標(biāo)，就會引入適應(yīng)度函數(shù)。根據(jù)對環(huán)境適應(yīng)度的大小，對種群中個體進(jìn)行優(yōu)勝劣汰。從生物學(xué)角度講,適應(yīng)度相當(dāng)于達(dá)爾文進(jìn)化論提出的“生存競爭、適者生存”的生物生存能力。將優(yōu)化問題的目標(biāo)函數(shù)與個體的適應(yīng)度建立映射關(guān)系,即可在群體進(jìn)化過程中實(shí)現(xiàn)對優(yōu)化問題目標(biāo)函數(shù)的尋優(yōu)。適應(yīng)度函數(shù)也稱評價函數(shù)，是用于區(qū)分群體中個體優(yōu)劣的標(biāo)準(zhǔn)，總是非負(fù)的，到最后函數(shù)會進(jìn)行收斂，取決于適應(yīng)度函數(shù)以及迭代次數(shù)的選擇，結(jié)果越收斂越合理。最后，算法應(yīng)構(gòu)建合理的適應(yīng)度函數(shù)來評估個體的解決方案的利弊，適應(yīng)度函數(shù)針對不同的問題有不同的定義。有必要根據(jù)特定問題來構(gòu)造合適的適應(yīng)度函數(shù)。3.4.5遺傳操作（一）選擇選擇操作的目的是從種群中挑選出優(yōu)秀的個體，使它們保留下來，將優(yōu)秀的基因遺傳下去。選擇操作的方法是基于上述構(gòu)造的適應(yīng)度函數(shù)，得出個體的適應(yīng)度值，依據(jù)適應(yīng)度值對種群中的個體給予評價，挑選出優(yōu)秀的個體保留并遺傳到下一代。適應(yīng)性強(qiáng)的個體將有更大的概率將基因遺傳給后代，這是符合達(dá)爾文的適者生存原則的。本文中使用輪賭盤選擇法實(shí)現(xiàn)選擇操作。每一個個體進(jìn)入下一代的概率與其適應(yīng)度呈正相關(guān)，適應(yīng)度值越高的個體，被選擇保留并進(jìn)入下一代的概率就越大，從而做到每一代新個體相比于上一代有了優(yōu)化，反之重新加入循環(huán)，優(yōu)化后在輸出。（二）交叉標(biāo)準(zhǔn)遺傳算法中起決定性作用的遺傳操作就是交叉操作。新的個體的獲取可以由種群之中個體的交叉操作得到，并使之組成新的種群。隨機(jī)配對的個體在群體的基礎(chǔ)上，配以一定概率（通常交叉概率），一旦出現(xiàn)在趕驢區(qū)間范圍，則在它們之間交換的染色體，成為新個體的染色體。因此，新個體組合了上一代個體的基因。但決定交叉率時應(yīng)當(dāng)注意其大小，交叉率過大，計算過程就成為了純粹的隨機(jī)操作。本文采用雙切點(diǎn)交叉法，實(shí)現(xiàn)此操作的步驟為：（1）在種群內(nèi)隨機(jī)挑選兩個個體進(jìn)行配對；（2）基于交叉概率Pc，決定是否進(jìn)行交叉操作，如果是，執(zhí)行第三步；（3）在相互配對的兩個個體的染色體（編碼串）中，各隨機(jī)設(shè)置兩個交叉點(diǎn)；（4）在兩個人設(shè)定的交點(diǎn)之間的部分染色體交換。假設(shè)Ⅰ、Ⅱ?yàn)閮蓷l染色體，對其交叉操作可以得到Ⅲ、Ⅳ兩條新染色體，具體示意如下：Ⅰ：125789Ⅲ：124569Ⅱ：234568Ⅳ：235789（三）變異在自然界的生物變化是由于該基因片段的變化。在遺傳算法中，相應(yīng)的變化是在串結(jié)構(gòu)數(shù)據(jù)特定值的變化。變異操作群體中的一個隨機(jī)選擇的個體，并且是以一定的概率（突變的通常的概率）來改變某一基因或幾個基因與其它等位基因。不同于交叉概率，變異的概率一般很低，因?yàn)樵诒举|(zhì)上是一種生物變異的可能性。變化提供了新的個人發(fā)展機(jī)會。同交叉流程，變異率應(yīng)該更小，否則算法會成為單一的隨機(jī)選擇操作。本文依據(jù)一定的變異概率Pm來決定上一步產(chǎn)生的新染色體是否發(fā)生變異。如果染色體被選中進(jìn)行變異，則隨機(jī)產(chǎn)生兩個指定的染色體交換位置，互換基因（單個實(shí)數(shù)），例如有一條染色體為123456，隨機(jī)產(chǎn)生兩個交換位置1和4，則變異后的染色體為423156。3.4.6終止條件運(yùn)行遺傳算法解決優(yōu)化類問題時，算法不會自動停止，需要設(shè)置一個用來終止算法無休止進(jìn)行搜索的條件。這個終止條件可以是以下幾種。（一）一個設(shè)定好的個體適應(yīng)度值，當(dāng)種群中個體的適應(yīng)度值與給定值相同時，算法停止搜索；（二）當(dāng)遺傳算法中同時存在種群適應(yīng)度和個體適應(yīng)度時，當(dāng)兩者都穩(wěn)定在一個值附近時，算法即停止；（三）遺傳算法的尋優(yōu)搜索是一個不斷迭代的過程，為使得算法求解在某個時刻終止，可以設(shè)定迭代的次數(shù)。一般設(shè)置為100-150代，這種方法是在遺傳算法尋優(yōu)問題中常用的。3.5遺傳算法的運(yùn)行參數(shù)在基本的遺傳算法，以下四種工作參數(shù)需要被預(yù)先設(shè)定，即M，T，PC，PM。M為群體大小，這個值代表群體中擁有個體的數(shù)量，常用取值為20-100；T為遺傳算法的迭代終止代數(shù)，當(dāng)算法迭代代數(shù)達(dá)到這個值時，算法自動終止，常用取值為100-150；Pc為交叉概率，常用取值為0.4-0.99，本文采用概率區(qū)間（0.55,0.75）；Pm為變異概率，常用取值為0.0001-0.1，由于概率過小，如要達(dá)到預(yù)期效果計算量會過大，所以本文根據(jù)實(shí)際計算量適當(dāng)增加了變異率，采用區(qū)間（0.1,0.3）。

第四章基于改進(jìn)遺傳算法的滑行路徑優(yōu)化調(diào)度4.1模型建立4.1.1滑行道調(diào)度模型航班滑行調(diào)度是在保證滑行安全前提下為每架航班制定滑行路徑及到達(dá)其路徑上交叉點(diǎn)的時間，使得總滑行時間最短或總經(jīng)濟(jì)損失最小。本文根據(jù)機(jī)場場景的布局和飛行的滑行特性，我們可以抽象機(jī)場滑行道布局到由點(diǎn)和圓弧的網(wǎng)絡(luò)結(jié)構(gòu)圖中，由G=(V，E)表示。124563789A1A2A3G1G2G312131516181910111417圖4-1某機(jī)場滑行道簡化模型將飛機(jī)分為進(jìn)場和離場兩類，如果有一架進(jìn)場飛機(jī)，則終點(diǎn)為點(diǎn)A1，A2，A3，起點(diǎn)為脫離道口點(diǎn)1；若有一架離場飛機(jī)，則終點(diǎn)為跑道入口點(diǎn)10，起點(diǎn)為點(diǎn)G1，G2，G3。其中各路段距離表示為進(jìn)場路段：（1,2）=100，（2,3）=200，（2,4）=300，（4,5）=500，（5,6）=200，（4,7）=200，（5.8）=200，（6,9）=150，（3,7）=300，（7,8）=500，（8,9）=300，（7，A1）=300,（8，A2）=500，（9，A3）=400，離場階段：（10,11）=100，（11,12）=100，（11,14）=200，（14,17）=400，（12,13）=200，（13,15）=200，（13,14）=100，（15,16）=200，（16,18）=300,（16,17）=100，（18,19）=500，（15，G1）=300，（18，G2）=200，（19，G3）=400，約束條件為：Eti,u≤ti,u≤Lti,u，?u∈Ri，i=1,2…，n(4-2)Eti,v=Eti,u+du,v/Vimax?(u，v)∈Ri，i=1,2…，n(4-3)Ltiv=Ltiu+duv/Vimin?(u，v)∈Ri，i=1,2…，n(4-4)Sij,u=(tiv一tiu)／du,v*dsep（u,v）∈Ri∩Rj,ij∈F，i≠J(4-5)yij,utj,u≥yij,u(tiu+Sij,u)?i,j∈F,i≠j?,u∈Ri∩Rj(4-6)yij,u-yij,v=0?i,j∈F,?(u，v)∈Ri∩Rj(4-7)yij,u-yij,v=0?i,j∈F,?(u,v)∈Ri,(v,u)∈Rj(4-8)yij,u=0或1?ij∈F，?u∈（Ri∩Rj）（4-9）F={1,2…n)為飛機(jī)的集合，F(xiàn)arr∈F(進(jìn)場降落飛機(jī)集合)，F(xiàn)dep∈F(離場飛機(jī)集合)；R=｛R1，R2。。。Rn｝，Ri表示飛機(jī)i的滑行路線；Ri是由一系列點(diǎn)組成(v0i，v1i...vkii)，vij∈V(j=1,2…，ki)，并且(vij，vij+1)∈E（j=1,2...，ki-1)；（u，v）∈Ri表示弧(u，v）是飛機(jī)i的滑行線路之一；u∈Ri:點(diǎn)u在飛機(jī)i的滑行線路上；Du,v:點(diǎn)u和v之間的距離；Vimin（i=1,2...n）:飛機(jī)i的最小速度；Vimax（i=1,2...n）:飛機(jī)i的最大速度；Ti,u∈R+(i∈F，u∈Ri):飛機(jī)i到達(dá)點(diǎn)u的實(shí)際時間；Eti,u∈R+(i∈F，u∈Ri):預(yù)計飛機(jī)i到達(dá)點(diǎn)u的最早時間；Lti,u∈R+(i∈F，u∈Ri):預(yù)計飛機(jī)i到達(dá)點(diǎn)u的最晚時間；二元變量yij,u=1表示飛機(jī)i在j之前到達(dá)點(diǎn)U，否則=0；Sij,u(ij∈F，u∈(Ri∩Rj))表示飛機(jī)i和j到達(dá)點(diǎn)u的最小時間間隔；目標(biāo)函數(shù)（4-10）ti,uk表示飛機(jī)i到滑行終點(diǎn)k的時間，ti,u1表示飛機(jī)i第一個點(diǎn)開始滑行的時間。目標(biāo)函數(shù)求所有航空器滑行時間總和，描述所有個體飛機(jī)總的滑行時間最短；（4-2）式表示，這架飛機(jī)的實(shí)際到達(dá)時間必須是最早到達(dá)時間和最遲到達(dá)時間之間;公式（4-3）和（4-4）分別確定飛機(jī)到達(dá)的最早和最晚時間。兩架飛機(jī)ij的飛機(jī)之前和之后的到達(dá)之間的最小時間間隔由（4-5）表示。當(dāng)兩個飛行器滑行前進(jìn)，后退，有一定的安全距離，必須按照有關(guān)規(guī)定出租車保證。否則，會發(fā)生危險，而不同類型的飛機(jī)之前和之后的安全距離不相同，一般安全距離為d=50米;；式(4-6)確保兩架飛機(jī)滑行在同一條線路上時保持一個安全的距離；式(4-7)確保任意兩架飛機(jī)不會相互超過；式(4-8)確保飛機(jī)之間不會相遇；式(4-9)表示變量y只能在0和1中取值。4.1.2標(biāo)準(zhǔn)遺傳算法過早收斂及改進(jìn)猜想早熟收斂是標(biāo)準(zhǔn)遺傳算法的一種現(xiàn)象。由于本文采用賭輪盤的方式篩選個體，當(dāng)算法前期出現(xiàn)超級個體時，即該個體對于環(huán)境的適應(yīng)度大大超過了當(dāng)前種群的平均適應(yīng)度，從而導(dǎo)致在賭輪盤計算時，該類個體被篩選的概率大大增加，進(jìn)而種群多樣性提早且迅速降低，種群進(jìn)化能力急劇喪失。以上現(xiàn)象發(fā)生，就會導(dǎo)致算法提前收斂于局部最優(yōu)解。為避免或者減少此類現(xiàn)象發(fā)生，本文在一定程度上引入模擬退火算法（SA）的思想。標(biāo)準(zhǔn)遺傳算法在對種群全局優(yōu)化的選擇能力較強(qiáng)，但存在“早熟收斂”問題使得種群優(yōu)化容易偏向于取得相對最優(yōu)解，模擬退火算法正好可以彌補(bǔ)標(biāo)準(zhǔn)遺傳算法“爬坡難”的問題，本文嘗試將兩種算法結(jié)合以解決滑行道調(diào)度優(yōu)化問題。根據(jù)模擬退火算法實(shí)際使用情況，本文對SA算法原理僅做簡單介紹。SA靈感源于將固體加熱至足夠高的溫度，然后對加熱固體進(jìn)行自然冷卻，然后記錄其內(nèi)部變化的原理。加熱時，固體內(nèi)部受熱導(dǎo)致粒子逐漸無序，溫度升高，固體內(nèi)能增加，而當(dāng)緩慢冷卻，內(nèi)部顆粒逐漸變得有序，每個溫度達(dá)到平衡，最后在常溫下達(dá)到基態(tài)，內(nèi)能降低到最小。隨著溫度T的不斷下降，在算法取得最優(yōu)解或者相對最優(yōu)解時，SA算法會想右跳躍部分取得新解，并且以一定概率接收這個新解，即局部最優(yōu)解以概率方式跳躍并最終變?yōu)槿肿罴鸦蛳鄬ψ罴选＃?.11）圖4-2標(biāo)準(zhǔn)遺傳算法早熟收斂示意圖4.1.5模型改進(jìn)采用模擬退火算法指數(shù)型函數(shù)的思想，即本文實(shí)際沒有使用到模擬退火算法關(guān)于溫度自然降低導(dǎo)致結(jié)構(gòu)突變的計算方法，而是借鑒了SA算法使用的指數(shù)型約束函數(shù)。由于指數(shù)比例既可以讓非常好的串保持多的復(fù)制機(jī)會。同時，它限制復(fù)制的機(jī)會，以免迅速控制整個群體，能夠有效地抑制算法的早熟收斂，同時也提高了類似的字符串之間的競爭。所以適應(yīng)度函數(shù)取指數(shù)形式表示為：（4.13）針對標(biāo)準(zhǔn)遺傳算法“爬坡難”的問題，該算法雖不能直接彌補(bǔ)早熟收斂的現(xiàn)象，但指數(shù)比例既可以讓非常好的串保持多的復(fù)制機(jī)會．同時又限制了其復(fù)制數(shù)目以免很快控制整個群體。在“算法后期，適應(yīng)度趨于一致”的時候，該方法可以拉伸適應(yīng)度，標(biāo)準(zhǔn)遺傳算法采用的賭輪盤方式選擇目標(biāo)個體，諸如“早熟收斂”中出現(xiàn)的“超級個體”被選取的概率遠(yuǎn)遠(yuǎn)高于其他個體，而拉伸適應(yīng)度可以做到將“超級個體”的選取概率減小，從而使遺傳算法中的選擇更有擇優(yōu)的效果，有效地抑制算法的過早收斂，同時也提高了相近串間的競爭性。Tchrome為種群時間，即航空器總滑行時間，β為常數(shù)，取值越小函數(shù)值越收斂，本文根據(jù)實(shí)際情況，取值β=1。4.1.6初始群體的生成隨機(jī)產(chǎn)生初始滑行數(shù)據(jù)，每條路徑所滑行時間稱為一個個體，所有滑行時間組合起來成為一個種群。在滿足約束條件（4,2）到（4,9）的基礎(chǔ)上，將飛機(jī)分為進(jìn)離港兩類。采用圖4.1簡化機(jī)場模型，每個點(diǎn)只能走一次不能重復(fù)。再利用賭輪盤算法，適應(yīng)度高的個體選中幾率大，即滑行時間越短的個體，相較于其他方案有更大概率被選擇，如果發(fā)生沖突則重新選擇，這樣確保了初始種群安全安全的同時也保證了種群之間的競爭。4.2優(yōu)化策略在基于標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上，對變異率進(jìn)行動態(tài)變化，交叉率設(shè)置值為0.55，變異率適當(dāng)增大為（0.1,0.3）當(dāng)沒有發(fā)生變異時，將種群回退到第一步，并將變異率增加0.01，輸出之后，將種群代入預(yù)先設(shè)置的指數(shù)型約束函數(shù)，針對遺傳算法“爬山難”的問題，指數(shù)型約束函數(shù)可以將“坡道”變緩，提高種群競爭性，減輕標(biāo)準(zhǔn)遺傳算法早熟收斂問題所帶來的影響。具體流程圖如下：圖4-3滑行道分配算法流程圖4.3算法的實(shí)現(xiàn)模擬實(shí)驗(yàn)采用雙流機(jī)場五月十四日上午四點(diǎn)到五點(diǎn)連續(xù)三架離港飛機(jī)和三架進(jìn)港飛機(jī)，模擬機(jī)場如圖4.1所示，共有6個停機(jī)坪，隔離跑道，2個跑道入口，編號1,10；交叉點(diǎn)16個，給定交叉點(diǎn)之間路徑的取值，取交叉率（0.35,0.55）每次增量0.01，變異率（0.1,0.3）每次增量0.01。本文采用宏碁筆記本i5處理器，4GB內(nèi)存GTX850顯卡，MATLAB軟件進(jìn)行程序模擬，迭代200次，操作50次，總時間264,611秒，結(jié)果如下：圖4-4MATLAB模擬數(shù)據(jù)航班序號分配滑行路線new_chrome11237A100000000000212378A200000000003124789A30000000004G1151617111000000000005G218161513141110000000006G319181615131211100000000表4-1實(shí)驗(yàn)結(jié)果例如第四架飛機(jī)為離場飛機(jī)，經(jīng)過點(diǎn)位15,13,12,11到達(dá)終點(diǎn)10進(jìn)入跑道，0為填充字符，無實(shí)際意義。本文在計算時間時未考慮停機(jī)位推出開車以及地面引導(dǎo)時間，所以時間結(jié)算到飛機(jī)滑行至停機(jī)位前一點(diǎn)。根據(jù)指數(shù)型適應(yīng)度函數(shù)的收斂情況可以推斷出種群時間越短，函數(shù)值越大；即方案越趨于優(yōu)化，適應(yīng)度函數(shù)值越趨于收斂。最后收斂會向fitness=1靠攏。本文取第40至最后第50次操作的函數(shù)取值繪制成曲線圖，如下圖4.4?？梢灾庇^看出前期函數(shù)值波動大，后期趨近于平緩fitness=0.8024，從而可以進(jìn)一步得出利用退火算法思想的指數(shù)型函數(shù)作為適應(yīng)度函數(shù)，可以一定程度上減少標(biāo)準(zhǔn)遺傳算法早熟收斂的現(xiàn)象，并且在迭代200次基礎(chǔ)上做到函數(shù)值收斂。圖4-5最后十次操作函數(shù)收斂情況初始數(shù)據(jù)優(yōu)化后數(shù)據(jù)飛機(jī)編號停機(jī)位滑行時間起始節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)路徑滑行距離滑行時間1A1201A11-2-3-760013.82A2351A21-2-3-7-8110023.43A3451A31-2-4-7-8-9160035.04G130G11015-16-17-14-11-10100023.75G240G21018-16-15-13-14-11-10110027.26G350G31019-18-16-15-13-12-11-10160038.6總滑行時間220總滑行時間161.7表4-2仿真優(yōu)化結(jié)果優(yōu)化后發(fā)現(xiàn)，優(yōu)化滑行時間相比于初始滑行時間縮短了58.3個單位時間，與實(shí)際管制員提供的滑行指令思路相似但仍有偏差。能取得這樣的效果主要是機(jī)場模型的建立基于實(shí)際機(jī)場圖，以及遺傳算法優(yōu)秀的全局搜索能力，但模型簡化，無法體現(xiàn)出復(fù)雜機(jī)場實(shí)際沖突的復(fù)雜性。4.4本章總結(jié)本章針對機(jī)場航空器調(diào)度問題，根據(jù)進(jìn)離場航空器提供滑行道分配的優(yōu)化方案，利用基本的遺傳算法模型，理論與流程圖相結(jié)合，直觀了解遺傳算法的流程。適當(dāng)引用了模擬退火算法的思想對適應(yīng)度函數(shù)進(jìn)行改進(jìn)，將滑行調(diào)度問題轉(zhuǎn)化為模型與圖表的形式。從結(jié)果來看，本章節(jié)提出了一種基于遺傳算法和模擬退火算法思想的優(yōu)化算法，其系統(tǒng)地優(yōu)化整個滑行調(diào)度，提高調(diào)度的效率和準(zhǔn)確性，并在一定程度上減輕標(biāo)準(zhǔn)遺傳算法過早收斂的問題。

第五章研究展望和總結(jié)5.1總結(jié)設(shè)計工作提出不足本次研究對于滑行道調(diào)度問題做了一下研究：（1）參考國內(nèi)外文獻(xiàn)，學(xué)習(xí)了解基本遺傳算法算法的機(jī)制與算法流程；（2）對機(jī)場場面運(yùn)行模式進(jìn)行總結(jié)，將復(fù)雜機(jī)場場面區(qū)抽象化成節(jié)點(diǎn)網(wǎng)絡(luò)圖；（3）對航班滑行過程進(jìn)行分析，總結(jié)滑行過程中存在的潛在三大沖突；（4）將成都雙流國際機(jī)場的跑滑系統(tǒng)與停機(jī)位進(jìn)行簡化，得出研究所需的模型，根據(jù)算法需要，編寫了滑行道距離矩陣，利用遺傳算法嘗試對成都雙流國際機(jī)場某一時段的6架航班滑行路徑進(jìn)行優(yōu)化，并在優(yōu)化過程中考慮沖突避讓，得出各停機(jī)區(qū)最優(yōu)滑行路徑。（5）本研究最終所得結(jié)果更偏向于靜態(tài)的航班滑行最優(yōu)路徑，因此遺傳算法可供機(jī)場管制單位未來設(shè)計標(biāo)準(zhǔn)滑行路徑時作為一項(xiàng)參考，可以此作為預(yù)指定的滑行路徑選擇方案的工具。由于機(jī)場滑行道優(yōu)化問題是一個比較復(fù)雜的問題，因此研究仍然存在一定的不足，分別為：（1）簡化模型中的成都雙流國際機(jī)場的跑道脫離道單一，而實(shí)際工作中進(jìn)場航空器脫離跑道的方式更加復(fù)雜多樣，后續(xù)研究應(yīng)將與實(shí)際運(yùn)行更加貼近；（2）本文通過遺傳算法算法得出的解中存在劣質(zhì)解以及考慮不夠全面的問題，這是由于算法設(shè)計時僅考慮了航空器避讓節(jié)點(diǎn)附近某一范圍內(nèi)的其他航空器，沖突避讓機(jī)制不夠完善造成的，研究動態(tài)的航空器滑行路徑優(yōu)化應(yīng)當(dāng)設(shè)計更合適的沖突規(guī)避約束，基于動態(tài)沖突避讓考慮在動態(tài)尋優(yōu)問題中，諸如遺傳算法這一類的啟發(fā)式算法存在短板，后續(xù)研究應(yīng)加以改進(jìn)或?qū)で笃渌惴ㄟM(jìn)行求解；（3）本研究最終所得結(jié)果更偏向于靜態(tài)的航班滑行最優(yōu)路徑，因此本文優(yōu)化的遺傳算法可供機(jī)場管制單位未來設(shè)計標(biāo)準(zhǔn)滑行路徑時作為一種借鑒，但不適用于實(shí)際管制工作中的滑行路徑分配。5.2研究展望由于能力有限，最終完成的結(jié)果未能實(shí)現(xiàn)多航班同時在復(fù)雜機(jī)場協(xié)同優(yōu)化，尚不能滿足大型繁忙機(jī)場的場面滑行調(diào)度優(yōu)化。針對本文的滑行道調(diào)度優(yōu)化問題仍有以下可加以改進(jìn)的空間：（1）本文考慮的雙跑道同時儀表運(yùn)行模式是隔離運(yùn)行模式，進(jìn)離場航空器在場面的交通流較為規(guī)律，模型不能較好地體現(xiàn)實(shí)際運(yùn)行中的復(fù)雜情況；（2）本文考慮場面運(yùn)行時將停機(jī)位模糊化成若干塊停機(jī)區(qū)，與實(shí)際情況復(fù)雜且數(shù)量較大的停機(jī)位相比，本文模型相對簡單，在未來的研究中可以將停機(jī)位、跑滑系統(tǒng)充分結(jié)合考慮，以滿足實(shí)際運(yùn)行需求；（3）本文采用遺傳算法和模擬退火思想，路徑尋優(yōu)趨于靜態(tài)路徑規(guī)劃，航空器的實(shí)際場面滑行具有復(fù)雜性、動態(tài)性特點(diǎn)，因此未來可進(jìn)一步針對兩種算法的優(yōu)劣性，做到對實(shí)際滑行調(diào)度具有優(yōu)化作用的取長補(bǔ)短或者使用其他智能算法進(jìn)行尋優(yōu)。對于機(jī)場場面滑行道調(diào)度優(yōu)化這個問題，未來滑行道的分配將更加智能化，針對場面的情況實(shí)現(xiàn)協(xié)同優(yōu)化是必然的趨勢。未來滑行道的分配應(yīng)該趨于自動分配最優(yōu)路徑，而實(shí)現(xiàn)這個目標(biāo)需要有效且可行可靠的智能算法提供支持。尤其機(jī)場場面結(jié)構(gòu)復(fù)雜的大型繁忙機(jī)場，靠管制員人為決策滑行道分配的情況將越來越少，智能算法與人工智能的發(fā)展，將為管制員對機(jī)場地面管制提供更迅速、更安全、更高效的滑行道調(diào)度策略。

致謝在《機(jī)場航空器地面滑行優(yōu)化調(diào)度》課題撰寫過程中，我的指導(dǎo)老師江波給了我莫大的幫助，包括算法和寫作框架的思路上。史曉紅老師在為我提供了大量文獻(xiàn)，在她的幫助下我找到了適合自己的算法模型，并且得到了進(jìn)一步的修改和指正。周云帆老師在程序編寫方面提供個講解與指導(dǎo)，讓我得以在有限的計算機(jī)能力基礎(chǔ)上將算法實(shí)現(xiàn)。最終在三位老師的耐心指導(dǎo)下，我的論文得以完成。感謝中國民用航空飛行學(xué)院對我的培養(yǎng)，讓我在四年的學(xué)習(xí)生活中積累到了足夠的明航相關(guān)知識。感謝家人在論文期間給我的鼓勵和關(guān)懷。感謝大學(xué)生活中的朋友一起互相勉勵和共同進(jìn)步，陪伴著我走過大學(xué)四年歲月。

參考文獻(xiàn)中國民用航空局.2018年民航行業(yè)發(fā)展統(tǒng)計公報[Z].2018民航資源網(wǎng).2018年民航機(jī)場吞吐量排名[Z].2018,03.B.Pesic,N.Durand,andJ.M.Alliot.Aircraftgroundop