航線網絡優化方法研究

楊思浩 羅鳳娥

摘要：航線網絡優化對民航業有著舉足輕重的作用。以現如今的航線網絡分布而言還有很多不合理的地方，由于歷史和經濟原因，我國現如今的航空資源分布不合理，航線規劃過時，缺少及時的更新，以及資源利用率低，造成了大面積的空域不能合理運用，而部分空域航線規劃又過于緊密。在這種情況下就會造成資源浪費，且效率低下的問題。所以航線優化這一題目就具有極高的研究價值和現實意義，可以直接作用于提升民航業的運行效率，優化整體結構。

關鍵詞：民航網絡，調配，尋優，狀態圖

1.引言

隨著民航業的不斷發展，航空器數量增加但可用空域卻無法進一步開拓，于是在數年前就提出了“自由飛”這個概念。但是為了保證安全運行，所有上天的航空器都必須接受管制員的“管制”。目前為止為了實現這個目標，可以從優化航線網絡、加強導航技術與導航系統和數據傳輸系統等方式，下面就航線優化方面進行敘述，主要對基于GA尋優算法和航線調度優化管理進行研究。

首先從一條航線的誕生開始分析，因為航空歷史悠久，發展過程較長，所以目前為止已經產生的航線大都是數年前的老舊航線，而當時的設計師并沒有足夠的前瞻性來預見現在的情況。而局限于多種因素無法對這些已經誕生的航線網絡進行大規模的改進，所以現代設計師即使是從這個基礎上進行不斷的改進，依舊是杯水車薪難堪大用。基于我國現在的航空使用權絕大部分還是歸屬于空軍的背景下，民航業所能使用的只是極其有限的一部分，從上圖上來顯示就是諸多的危險區、禁區和限制區，所以如何利用好這些資源顯得更加重要。綜合以上內容，可以總結出一條航線的誕生需要考慮的因素：

（1）空域。所規劃設計的空域首先必須是允許飛行的航段，因為一條航路還需要考慮到數公里的寬度。

（2）確定保護區評估障礙物高度.以保證航空器的安全。

（3）與現有的航路有多少交匯點。若是與已有航路出現了過多交匯點，勢必會影響這一條航路上航空器飛行計劃的制定，會憑空增加許多難度，同時也增加了突發事件發生的概率。

（4）主要飛行器機載設備要求。因為航線規劃在不同的地方對于航空器的性能要求也是不一樣的，比如以高高原機場為起降場的航線，就會對于機載導航設備有更高的要求，同時由于環境的特殊情況，會對數據通信也有更高的要求以保證航空器的安全運行。

（5）還需要考慮給當地管制或流量新增多大壓力是否需要分流。就如上文所言，在航空業高速發展的今天，有部分機場已經是高負荷工作了，所以在設立一條新航線時，還需要考慮管制人員的工作量與機場的服務能力。

2.航線優化的評價內容和指標

（1）油耗指標。油耗是航班在執行日常飛行計劃中與航空公司運營成本直接相關的內容，若在航線優化后可以獲得明顯的油耗量減少效果，從經濟方面而言減少了航空公司大量的運營成本，從綠色運行而言減少了碳排放量，符合可持續發現的觀念。

（2）.時間指標。這一項指標主要是為了體現動態管理的優勢，在遇到突發事件時可以靈活變通。比如航班在運行過程中突然得知著陸機場有惡劣天氣，那么就可以在條件允許的情況下，安排合適的航班提前降落以躲避惡劣天氣。

（3）準時到達。該指標主要是指在機場當局考慮到經濟、安全和效率等方面的情況下，給予飛機進場和離場的時間有一個嚴格的規定，并依據制定的計劃來完成飛機進場和離場的時間安排，除此之外，在航空公司日常的運行中，準時到達率也是一項重要的評價標準。

當前以有學者對航線的動態優化進行了研究，在研究的過程中發現，在航線動態優化的過程中，飛機系統和ATC系統是最重要的兩個部分。首先是飛機系統通過接受地面ATC系統發布的不同種類的信息，將其匯總，并根據指標評估該條航線是否需要重新規劃。若是需要重新規劃線路，則需要在新的航線規劃數據生成后對其進行模擬仿真來檢測其合理性，合格之后將信息發送給地面相關部門。地面ATC系統在接受到信息之后首先是對信息進行處理，將信息中包含的飛行環境、交通情況和不可用空域等情況發布出去。整個過程用圖來表示結果見圖1。

3.基于GA尋優算法的簡介

對于航線實時優化優化來說，一旦當作用的對象（航路網絡）規模超過一定界限時，一般的尋優算法所消耗的時間是令人難以接受的，而GA尋優算法在眾多的算法中具有面對大規模航線進行尋優計算的能力，而且還具有高速得出結果的功能，這就使得它是目前為止效果最好的算法，然而隨著實時優化的任務量在不斷的增大，即使是GA算法也需要進一步的改進，才能用于解決相關的航線實時優化任務。

由于在實現航路的實時優化過程中發現因為大多數情況地形比較復雜，所以求解的質量并不能令人滿意，于是在研究過程中，專家引入了“成長”和“幼代”這兩個概念來完善GA算法。在GA算法未進行改進之前，其實也是一種“幼代”，只不過在產生下一代的過程中，所有的種類都被保存下來，致使所得到后代的質量無法得到保證，而優化后的GA算法則是在產生下一代的過程中，加入了競爭階段，然后令優秀的后代得以保存下來。在這一過程中，需要保證的是初代種群數目足夠大，這樣在不斷地淘汰過程中才能保持整個種群的多樣性，也就是GA算法中的隨機搜索能力。在這整個過程中采用了自適應交叉的延續方式，并在后續指導染色體的產生，可以達到將沒有優勢的染色體得到完善的目的，然后加強該算法的尋優能力，使所得結果的質量得到提高。

3.1總結基于GA尋優算法

基于GA尋優算法的優點是可以比較準確的解決在飛行中航線的動態實時優化的問題，但是缺點是整體過程較為復雜，需要付出大量的人力物力進行計算過程的數據處理。創新點在于實時進行優化，可以極大地增加航線網絡優化的準確率和效率。

4.航線調度優化方法的簡介

除了對整個航線網絡進行優化，還有一種思路是進行航線優化調度。航空公司在日常的計劃制定后需要根據已有的航路來分配特定的機型，然后合理的分配航班，需要滿足過程中的安全問題以及飛行器在運行任務后的定期維修檢查，所以在構建模型時，需要考慮多個因素。為了滿足這一要求，研究出了將各個因素作為約束條件所構成的方程中。由于現實情況的特殊性，方程在構建完成時往往是非線性的，然后根據運籌學中的解非線性方程組的方法得出一個最優解，這是最初代解決航線調度優化方法的基本思路。

在解決航線調度優化的時，首先需要考慮的就是其需要滿足航空公司所指定的航班飛行計劃得以正常運行，然后在保證航行安全的情況下，生成新的調度方案。除此之外，航線調度還需要將各類規則考慮其中，滿足上述幾點條件后，可以令該問題模型轉變另一種思路，即逆向思維將航線匹配至適合的機型，如此便將整體建模的難度降低了。

4.1生成調配方案時需要注意的規則

在整個航線的調配過程中需滿足所述幾條要求：

（1）符合航班計劃：在航線調配方案生成時不能之前已有的飛行計劃產生沖突，比如不改變原計劃中的機型、航班起飛到達機場、航班起飛到達時間等。

（2）航班覆蓋，在一般情況下只有一架航空器可執行單次飛行任務。

（3）維護要求：在正常情況下，為了方便和經濟效益，維護檢修工作都是在航空公司所屬的機場進行的，維護檢修的目的是為了使航空器在執行任務時能在需要的時間在正確的機場獲得檢修。

4.2航線調配等圖建模

航線優化調配模型的建立需要先表述一下參數：

用兩個三元的方程組來表示一個航班，第一個方程組來描述該航班的起始狀態，相應的第二個方程組來描述該航班的降落狀態。該方程還需要包括以下重要參數。

過夜集合：用來表示該航班屬于某一過夜集合。

維護過夜集合：用來表示在某一機場過夜維修的航班。

過站時間：來表示相連的兩架航班的時間間隔和過站所需要時間的比較。

航班串：如果相鄰的兩架航空器的維護周期時長滿足一個維護過夜集，說明該兩架航空器為可行航班串。

運營天數：在航空器出發時距離上次檢查維修的過夜時間的天數。

考慮到線路規劃的特殊性，就在以上的基礎上將整個建模問題帶入到一張圖中，從圖中更加清晰的展現出優化結果和思路。

圖的定義：

一個圖（G）定義為一個偶對（V，E） ，記為G=（V，E） 。其中： V是頂點（Vertex）的非空有限集合，記為V（G）;E是無序集V&V的一個子集，記為E（G） ，其元素是圖的弧（Arc）。將頂點集合為空的圖稱為空圖。

其形式化定義為：

G=（V ，E），V={v|v?data object}，

E={<v，w>| v，w?V∧p（v，w）}，

P（v，w）表示從頂點v到頂點w有一條直接通路。

弧（Arc） ：表示兩個頂點v和w之間存在一個關系，用頂點偶對<v，w>表示。通常根據圖的頂點偶對將圖分為有向圖和無向圖。

有向圖（Digraph）： 若圖G的關系集合E（G）中，頂點偶對<v，w>的v和w之間是有序的，稱圖G是有向圖。在有向圖中，若 <v，w>?E（G） ，表示從頂點v到頂點w有一條弧。 其中：v稱為弧尾（tail）或始點（initial node），w稱為弧頭（head）或終點（terminal node） 。

無向圖（Undigraph）： 若圖G的關系集合E（G）中，頂點偶對<v，w>的v和w之間是無序的，稱圖G是無向圖。 在無向圖中，若"<v，w>?E（G） ，有<w，v>?E（G） ，即E（G）是對稱，則用無序對（v，w） 表示v和w之間的一條邊（Edge），因此（v，w） 和（w，v）代表的是同一條邊。

在了解了圖的基本定義之后，可以進一步介紹本方法中的航線調配等圖建模。

可以將飛機航線調配有向圖進行以下定義，任何一個機場在任何時間，如果有大于等于一個航班在離開時刻，機場都會相應的形成一個點，稱之為內部點，而相對應的將每一個源節點賦予該機場，并將一架飛機的起降點在圖中表現為其的航班弧。將航班離開飛機的連續的時間點作為一個地面弧，那么就會有N條地面弧生成。再將所有滿足初始條件和限制條件的節點命名為中間點。

我們可以根據之前的研究得出其實可以將航班的航線調配問題看成是在一張等圖上對其進行一個路徑劃分問題的研究，所以就可以進一步轉化為研究在解決一個狀態圖中的路徑劃分問題解決方法的研究，在此基礎之上可以加入航線調配過程的一些限制條件以及初始狀態，可以更加準確的描述這個問題。所以就可以將網絡路徑劃分問題的可行解作為航線優化調配問題的可行解。依賴以上所建立的模型，依據狀態圖整體的構造流程和數學方程構建的約束，可以得出可行解。

使用軟件（java）完成狀態圖的構建，并利用（lingo）對得出的狀態圖進行處理和計算，可以得出相應的可行解。

4.3總結航線調度優化管理方法

航線調度優化管理方法的優點就在于將復雜的航線優化問題轉化為一個相對簡單明了的圖形來解決，并且在其中將限制條件和初始狀態以數學模型和圖相結合的形式來呈現，極大地簡化了問題。缺點是只單獨的提出了航線優化這一問題，并沒有將其他（例如機型分配，機組調配等）問題結合在一起。創新點是別出心裁的用圖表示了航線優化這一復雜問題并將其劃為路徑分配問題來解決。

5.結語

為了解決航班網絡優化這一難題，國內外專家學者都進行了大量的研究與實驗，但是囿于已建成老航線的干擾以及可飛空域的限制，總會伴隨有諸多問題的出現。而經過不斷的努力現在已經有類似于基于GA尋優算法和航線調度優化管理等優秀方法的出現，逐漸是航線優化的可行性和準確性得到不斷提高，在接下來的時間還需要進一步的修正與改善，并通過將多種因素考慮其中而研究出更加完善的航線網絡優化方法。

參考文獻

【1】樂美龍，黃文秀，基于時空網絡的航班機型分配問題研究【J】交通運輸系統工程與信息，2014.14（1）：81-87.

【2】孫宏，杜文，航空公司飛機排班問題的排序模型及算法【J】系統工程理論方法應用，2002，11（3）：244-247

【3】R Gopalan，K T Talluri. The aircraft maintance routing problem【J】Operations Research，1998，32（1）：43-53

【4】于詳，樊瑋 ?，機場航班航線調度優化管理仿真研究【J】計算機仿真，2018.7（7）：54-58

【5】胡小兵，吳樹范，江 駒，民航飛機飛行航線動態實時優化仿真研究【J】計算機仿真，2001.5（3）：80-83

【6】朱星輝 ，朱金福 ，髙強，基于約束編程的飛機排班問題研究【J】交通運輸系統工程與信息，2011.（6）

【7】朱星輝，朱金福，髙強， 基于動態列生成算法的飛機排班問題 研究【J】數學的實線與認識 ，2014，（19） .

作者簡介：楊思浩，男，1997.6- ?籍貫：寧夏省惠農縣;研究方向：交通運輸規劃與管理。

通訊作者：羅鳳娥，女，1972.11- ，職稱：教授，學歷：碩士，研究方向：航空運行和飛行簽派。