楊思浩，羅鳳娥

（中國民用航空飛行學(xué)院空中交通管理學(xué)院，廣漢 618300）

0 引言

隨著民航業(yè)的不斷發(fā)展，航空器數(shù)量增加，但可用空域卻無法進(jìn)一步開拓，于是在數(shù)年前就提出了“自由飛”這個概念。但是為了保證安全運(yùn)行，所有上天的航空器都必須接受管制員的“管制”。目前為止，為了實(shí)現(xiàn)這個目標(biāo)，可以從優(yōu)化航線網(wǎng)絡(luò)、加強(qiáng)導(dǎo)航技術(shù)與導(dǎo)航系統(tǒng)和數(shù)據(jù)傳輸系統(tǒng)等方式入手，下面就航線優(yōu)化方面進(jìn)行敘述，主要對基于GA 尋優(yōu)算法和航線調(diào)度優(yōu)化管理進(jìn)行研究。

首先從一條航線的誕生開始分析，因為航空歷史悠久，發(fā)展過程較長，所以目前為止已經(jīng)產(chǎn)生的航線大都是數(shù)年前的老舊航線，而當(dāng)時的設(shè)計師并沒有足夠的前瞻性來預(yù)見現(xiàn)在的情況。而受到多種因素的局限，無法對這些已經(jīng)誕生的航線網(wǎng)絡(luò)進(jìn)行大規(guī)模的改進(jìn)，所以現(xiàn)代設(shè)計師即使是從這個基礎(chǔ)上進(jìn)行不斷地改進(jìn)，依舊是難堪大用。在我國現(xiàn)在的航空使用權(quán)絕大部分還是歸屬于空軍的背景下，民航業(yè)所能使用的只是極其有限的一部分，除此之外還存在諸多的危險區(qū)、禁區(qū)和限制區(qū)，所以如何利用好這些資源顯得更加重要。綜合以上內(nèi)容，可以總結(jié)出一條航線的誕生需要考慮的因素：

空域。所規(guī)劃設(shè)計的空域首先必須是允許飛行的航段，因為一條航路還需要考慮到數(shù)公里的寬度。

確定保護(hù)區(qū)評估障礙物高度，以保證航空器的安全。

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

主要飛行器機(jī)載設(shè)備要求。因為航線規(guī)劃在不同的地方對于航空器的性能要求也不一樣，比如以高原機(jī)場為起降場的航線，就會對于機(jī)載導(dǎo)航設(shè)備有更高的要求，同時由于環(huán)境的特殊情況，會對數(shù)據(jù)通信也有更高的要求以保證航空器的安全運(yùn)行。

還需要考慮給當(dāng)?shù)毓苤苹蛄髁啃略龆啻髩毫Γ欠裥枰至?。如上文所言，在航空業(yè)高速發(fā)展的今天，部分機(jī)場已經(jīng)是高負(fù)荷工作了，所以在設(shè)立一條新航線時，還需要考慮管制人員的工作量與機(jī)場的服務(wù)能力。

1 航線優(yōu)化的評價內(nèi)容和指標(biāo)

油耗指標(biāo)。油耗是航班在執(zhí)行日常飛行計劃中與航空公司運(yùn)營成本直接相關(guān)的內(nèi)容，若在航線優(yōu)化后可以獲得明顯的油耗量減少效果，從經(jīng)濟(jì)方面而言減少了航空公司大量的運(yùn)營成本，從綠色運(yùn)行而言減少了碳排放量，則符合可持續(xù)發(fā)展的觀念。

時間指標(biāo)。這一項指標(biāo)主要是為了體現(xiàn)動態(tài)管理的優(yōu)勢，在遇到突發(fā)事件時可以靈活變通。比如航班在運(yùn)行過程中突然得知著陸機(jī)場有惡劣天氣，那么就可以在條件允許的情況下，安排合適的航班提前降落以躲避惡劣天氣。

準(zhǔn)時到達(dá)。該指標(biāo)主要是指在機(jī)場當(dāng)局考慮到經(jīng)濟(jì)、安全和效率等方面的情況下，給予飛機(jī)進(jìn)場和離場的時間有一個嚴(yán)格的規(guī)定，并依據(jù)制定的計劃來完成飛機(jī)進(jìn)場和離場的時間安排，除此之外，在航空公司日常的運(yùn)行中，準(zhǔn)時到達(dá)率也是一項重要的評價標(biāo)準(zhǔn)。

當(dāng)前已有學(xué)者對航線的動態(tài)優(yōu)化［1］進(jìn)行了研究，在研究的過程中發(fā)現(xiàn)，在航線動態(tài)優(yōu)化的過程中，飛機(jī)系統(tǒng)和ATC 系統(tǒng)是最重要的兩個部分。首先是飛機(jī)系統(tǒng)通過接受地面ATC 系統(tǒng)發(fā)布的不同種類的信息，將其匯總，并根據(jù)指標(biāo)評估該條航線是否需要重新規(guī)劃［2］。若是需要重新規(guī)劃線路，則需要在新的航線規(guī)劃數(shù)據(jù)生成后對其進(jìn)行模擬仿真來檢測其合理性，合格之后將信息發(fā)送給地面相關(guān)部門。地面ATC 系統(tǒng)在接收到信息之后首先是對信息進(jìn)行處理，將信息中包含的飛行環(huán)境、交通情況和不可用空域等情況發(fā)布出去。整個過程用如圖1所示。

圖1 仿真系統(tǒng)的結(jié)構(gòu)框圖

2 基于GA尋優(yōu)算法的簡介

對于航線實(shí)時優(yōu)化來說，一旦作用的對象（航路網(wǎng)絡(luò)）規(guī)模超過一定界限，一般的尋優(yōu)算法所消耗的時間是令人難以接受的［3］，而GA 尋優(yōu)算法在眾多的算法中具有面對大規(guī)模航線進(jìn)行尋優(yōu)計算的能力，而且還具有快速得出結(jié)果的功能，這就使它成為目前為止效果最好的算法。然而隨著實(shí)時優(yōu)化的任務(wù)量不斷的增大，即使是GA 算法也需要進(jìn)一步的改進(jìn)，才能用于解決相關(guān)的航線實(shí)時優(yōu)化任務(wù)。

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

基于GA 尋優(yōu)算法的優(yōu)點(diǎn)是可以比較準(zhǔn)確地解決飛行中航線的動態(tài)實(shí)時優(yōu)化的問題，但缺點(diǎn)是整體過程較為復(fù)雜，需要付出大量的人力物力進(jìn)行計算過程的數(shù)據(jù)處理。創(chuàng)新點(diǎn)在于實(shí)時進(jìn)行優(yōu)化，可以極大地增加航線網(wǎng)絡(luò)優(yōu)化的準(zhǔn)確率和效率。

3 航線調(diào)度優(yōu)化方法的簡介

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

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

3.1 生成調(diào)配方案時需要注意的規(guī)則

在整個航線的調(diào)配過程中需滿足所述幾條要求。

（1）符合航班計劃。在航線調(diào)配方案生成時不能與之前已有的飛行計劃產(chǎn)生沖突，比如不改變原計劃中的機(jī)型、航班起飛到達(dá)機(jī)場、航班起飛到達(dá)時間等。

（2）航班覆蓋。在一般情況下只有一架航空器可執(zhí)行單次飛行任務(wù)。

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

3.2 航線調(diào)配等圖建模

航線優(yōu)化調(diào)配模型的建立需要先表述一下參數(shù)。

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

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

（2）維護(hù)過夜集合。用來表示在某一機(jī)場過夜維修的航班。

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

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

（5）運(yùn)營天數(shù)。在航空器出發(fā)時距離上次檢查維修的過夜時間的天數(shù)。

考慮到線路規(guī)劃的特殊性，就在以上的基礎(chǔ)上將整個建模問題帶入到一張圖中，從圖中更加清晰的展現(xiàn)出優(yōu)化結(jié)果和思路。

圖的定義：

一個圖（G）定義為一個偶對（V,E），記為G=（V,E）。其中：V是頂點(diǎn)（vertex）的非空有限集合，記為V（G）；E是無序集V&V的一個子集，記為E（G），其元素是圖的?。╝rc）。將頂點(diǎn)集合為空的圖稱為空圖。

其形式化定義為：

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

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

P（v,w）：表示從頂點(diǎn)v到頂點(diǎn)w有一條直接通路。

?。╝rc）：表示兩個頂點(diǎn)v和w之間存在一個關(guān)系，用頂點(diǎn)偶對表示。通常根據(jù)圖的頂點(diǎn)偶對將圖分為有向圖和無向圖。

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

無向圖（undigraph）：若圖G的關(guān)系集合E（G）中，頂點(diǎn)偶對的v和w之間是無序的，稱圖G是無向圖。在無向圖中，若?E（G），有?E（G），即E（G）是對稱，則用無序?qū)Γ╲,w）表示v和w之間的一條邊（edge），因此（v,w）和（w,v）代表的是同一條邊。

在了解了圖的基本定義之后，可以進(jìn)一步介紹本方法中的航線調(diào)配等圖建模。

可以將飛機(jī)航線調(diào)配有向圖進(jìn)行以下定義，任何一個機(jī)場在任何時間，如果有大于等于一個航班在離開時刻，機(jī)場都會相應(yīng)地形成一個點(diǎn)，稱之為內(nèi)部點(diǎn)，而相對應(yīng)地將每一個源節(jié)點(diǎn)賦予該機(jī)場，并將一架飛機(jī)的起降點(diǎn)在圖中表現(xiàn)為其航班弧。將航班離開飛機(jī)的連續(xù)的時間點(diǎn)作為一個地面弧，那么就會有N條地面弧生成。再將所有滿足初始條件和限制條件的節(jié)點(diǎn)命名為中間點(diǎn)。我們可以根據(jù)之前的研究得出其實(shí)可以將航班的航線調(diào)配問題看成是在一張等圖上對其進(jìn)行一個路徑劃分問題的研究［7］，所以就可以進(jìn)一步轉(zhuǎn)化為研究在解決一個狀態(tài)圖中的路徑劃分問題，在此基礎(chǔ)之上可以加入航線調(diào)配過程的一些限制條件以及初始狀態(tài)，可以更加準(zhǔn)確地描述這個問題。所以就可以將網(wǎng)絡(luò)路徑劃分問題的可行解作為航線優(yōu)化調(diào)配問題的可行解。依賴以上所建立的模型，依據(jù)狀態(tài)圖整體的構(gòu)造流程和數(shù)學(xué)方程構(gòu)建的約束，可以得出可行解。

使用軟件（java）完成狀態(tài)圖的構(gòu)建，并利用（lingo）對得出的狀態(tài)圖進(jìn)行處理和計算，可以得出相應(yīng)的可行解。如表1所示。

表1 實(shí)驗得出的結(jié)果

3.3 航線調(diào)度優(yōu)化管理方法

航線調(diào)度優(yōu)化管理方法的優(yōu)點(diǎn)就在于將復(fù)雜的航線優(yōu)化問題轉(zhuǎn)化為一個相對簡單明了的圖形來解決，并且在其中將限制條件和初始狀態(tài)以數(shù)學(xué)模型和圖相結(jié)合的形式來呈現(xiàn)，極大地簡化了問題。缺點(diǎn)是只單獨(dú)地提出了航線優(yōu)化這一問題，并沒有將其他（例如機(jī)型分配、機(jī)組調(diào)配等）問題結(jié)合在一起。創(chuàng)新點(diǎn)是別出心裁地用圖表示了航線優(yōu)化這一復(fù)雜問題并將其劃為路徑分配問題來解決。

4 結(jié)語

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