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

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

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

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

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

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

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

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

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

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