基于最大貢獻的航班計劃優化模型

馮輝宇，武丁杰，羅 超

(中國民用航空飛行學院 空中交通管理學院，四川 廣漢 618307)

為了提升航空公司的市場競爭力，其生產運營效率是至關重要的。生產運營效率可以在很多方面得到體現，例如完善的機隊維修計劃、機組的配備以及航班計劃等。航班計劃是一切生產運營活動的基礎，也是后續服務的保障。本文將從航班計劃優化的角度探討如何提高航空公司的收益及生產運營效率。

1 航班計劃優化模型

1.1 問題分析

一般來說，航班計劃的優化是以利潤最大化為基礎的。本文從航班貢獻的角度去研究航班計劃的優化問題。航班貢獻的多少可以反映出一個航空公司整體的盈利情況[1]。航班貢獻小于0，則飛行越多，虧損越多。航班貢獻大于0，即使利潤為負，由于航班收入可以覆蓋變動成本及附加稅，航班飛行之后，可以分攤一些固定成本。為了開辟市場，這樣的航班仍可繼續運行[2]。

1.2 模型假設及符號說明

1.2.1 模型假設

(1)航班的飛行頻率即每天飛行的航班架次已經確定；

(2)航空公司的機隊規模已經確定，短時間內不會有很大的變化；

(3)不考慮機型，這里我們定義最小過站時間為45 min；

(4)航線網絡已經確定，航班會按既定的航線飛行；

(5)客運和貨運流量根據歷史數據已經預測。

1.2.2 常用符號說明

1.2.3 模型的建立

本文主要從航班收入、航班成本、航班貢獻這三方面考慮來建立模型。航班的收入主要以座公里收入及客座率來體現，座公里收入是民航領域的最終評估指標，既可以用來對比單個航班的經營品質優劣，也可以用來對比整條航線的優劣。航班的成本主要由2部分組成，即固定運輸成本和變動運輸成本。固定運輸成本在上述中講過，在一定時期內是不變的。變動運輸成本與航班的運行情況有關，一般與航班的客運和貨運量相關，客運、貨運量的提升都會使航班的變動運輸成本增加。

建立一個以航班總貢獻最大的航班計劃模型：

(1)

上式中，用W表示航班的總貢獻，它由收入、成本、附加稅計算所得，其中的kij·dik·sij·yij表示單個航班的收入，k表示該航班的座公里收入，它是衡量航班運營情況的一個重要指標。d表示航班飛行的航線距離，該值主要以民航局公布的航段距離為主，不考慮實際航班飛了多長。s表示執飛該航班飛機的座位數，以官網公布的數據為準，由于存在改裝，各個航空公司同一種機型的座位數略微存在差異。y表示客座率，它可以很好的反應航班的銷售情況。變動運輸成本主要體現在客運和貨運兩方面，它們是影響變動運輸成本最主要的兩個因素，這里我們用一個線性函數βij+Lijbij+Kijeij表示變動運輸成本。其中βij表示機型j在航線i上的空載情況下的變動運輸成本，bij和eij分別表示機型j在航班i上的客運和貨運的空載和滿載情況下所需變動運輸成本的差值，Lij和Kij分別是與之對應的一個系數。λij表示的是一個0-1變量：

此外，根據研究，民建基金為運輸收入的5%，營業稅金及附加為運輸收入的3.75%[3]。

建立的模型滿足以下約束條件：

(2)

(3)

(4)

(5)

(6)

(7)

2 模型求解算法

由于上述模型屬于NP問題，現代優化方法中精確算法是解決小規模問題的求解方法，針對這種大規模問題的求解，常采用啟發式算法或者說近似算法。由于傳統的遺傳算法收斂過快，禁忌搜索算法只能求得局部最優，為了克服這一缺點，本文采用引入禁忌搜索的遺傳算法，將禁忌算法的“禁忌”和“特赦”準則引入到遺傳算法中，克服遺傳算法早熟的現象，求得全局最優解[6]。這種思想主要表現在遺傳算法的交叉算子上，通過改進后的交叉算子我們將其稱為TSR算子。

2.1 遺傳-禁忌混合算法

(1)編碼。一般遺傳算法在處理問題空間的參數時有一定難度，需要用一定的方式將其翻譯成遺傳算法可識別的參數，這里我們采用有序串編碼的方式來實現這一過程。對于上述n個航班的優化問題，我們將染色體分為n段，這樣，每一段就對應著航班的編號。例如待優化的航班有6個，那么|5|6|1|3|2|4就可以表示是一個可行的染色體。

(2)種群初始化。編碼之后就是種群的初始化，在此之前，需要確定初始化種群的數量，初始化種群的數量一般根據經驗得到，本文中種群的數量可以根據航班規模的大小確定。確定初始種群數量之后，選擇其中一個作為初始解。

(3)適應度評價。適應度是用來區分群體中個體優劣的標準，是對種群染色體篩選的一個依據。適應度值需要根據實際情況選取，優化的目標就是盡可能尋找適應度值大的染色體，選取的染色體適應度值越大，優化的結果就越好。

(4)選擇。選擇操作就是以一定的概率將舊群體中的個體選擇到一個新的群體中，適應度值的大小影響個體被選取的幾率，適應度值越大的個體往往被選取的幾率就越大。本文中，選擇算子我們選擇子輪盤賭法的方式，個體i被選中的概率為

(8)

其中，Ki為個體i的適應度值。

(5)TSR算子。將禁忌搜索算法的禁忌和特赦準則運用到遺傳算法中的交叉操作上，它是基于一種優勝劣汰的方法，將較好的染色體直接保留到下一代中，減少了個體被替換的次數，優化了算法的速度。在交叉操作產生的子代中，如果子代足夠優秀，已經達到渴望水平，那么無論其是否被禁忌，它都可以直接進入到下一代。如果產生的子代不是很優秀，未達到所需的渴望水平，那么需要考慮其是否被禁忌了。如果沒有被禁忌，就可以保留到下一代；如果被禁忌的話，我們選擇保留父代中優秀的染色體進入到下一代中，子代被淘汰。

(6)變異。為了使物種呈現多樣化的特征，需要進行變異操作，隨機選擇種群中的個體進行變異操作，以產生更加優異的個體。第i個個體的第j個基因gij進行變異的操作方法為

(9)

其中，gmax表示基因gij的上限，gmin表示基因gij的下限；f(g)=r2(1-g/Gmax)2,其中的r2是一個隨機數，g是當前迭代次數，Gmax是最大進化次數，r表示[0,1]區間的隨機數。

2.2 算法步驟

主要步驟如下：

步驟1 編碼，初始化群體，給出算法的初始參數，主要包括群體規模、最大迭代次數、交換概率等信息；

步驟2 計算各個個體的適應度值；

步驟3 利用選擇算子進行選擇；

步驟4 利用TSR算子進行交叉操作，具體操作方法如下：

(1)對于每一個染色體，隨機生成一個數，如果這個數大于交叉概率，那么這個染色體被選中，否則沒有被選中；

(2)被選中的染色體為父代染色體，對父代染色體進行交叉操作，以產生兩個后代染色體；

(3)渴望水平由父代適應度的均值確定，禁忌對象為群體中染色體的適應度值；

(4)若子代染色體的適應度值大于預先設定的渴望水平，則不考慮其是否被禁忌的情況，直接將子代染色體保留到下一代中；若沒達到渴望水平，則進行下一步操作；

(5)對于沒有達到渴望水平的子代染色體，如果其沒有被禁忌，也可以將其保留到下一代中，并更新禁忌表，如果未達到渴望水平同時也被禁忌的話，則將其全部淘汰，選擇父代染色體中優秀的部分保留到下一代中；

步驟5 進行變異操作；

步驟6 判斷篩選結果是否滿足終止條件，如果滿足，直接輸出結果，如果它不符合，返回到步驟(2)。

3 案例分析

以某航空公司南京祿口機場為樞紐的航班為例，2016年11月份部分航班銷售情況如表1所示。

表1 部分航班銷售情況

注：T1為航班的起飛時間；T2為航班的到達時間；T為航班的飛行時間，單位為h(小時)。

航班的變動運輸成本主要有飛行小時費、航空油耗消耗、航材消耗件消耗、起降服務費、航食及供應品費、代理業務手續費、基建和稅金等。確定了機型、航段，飛行小時、單位小時油耗、航材消耗件消耗單位值、起降費用及航路費都可以確定。航食及供應品隨旅客的變化而變化，該航空公司的飛機大多是客貨混裝的，由于貨郵需求不是很大，為了簡化模型，在模型中就不考慮貨郵的變動運輸成本。

通過Matlab軟件仿真，設定種群規模為30,最大遺傳代數為300,變異概率為0.2,對比尋優分析模擬結果如圖1所示。

圖1 對比尋優分析模擬結果

從圖中我們可以看出，相比傳統的遺傳算法，遺傳禁忌混合算法求得的結果更優，且進化代數也較小。由于選取部分航班數據，兩種算法之間的差距不是很明顯。但隨著數據的增多，數據復雜程度增加，遺傳混合算法的優越性會更加明顯。

4 結語

本文通過對航空公司經營效率和航班計劃的分析，以航班貢獻為切入點，研究航空公司整體的盈利情況。從航班收入、航班成本以及航班貢獻三者之間的關系出發，建立了以航班貢獻為目標的優化模型，該模型可以很好的反映出航班運營情況對航班貢獻的影響。采用遺傳和禁忌的混合算法對模型求解，把禁忌算法的禁忌和特赦準則引入到遺傳算法中，緩和遺傳算法收斂過快的現象，從而提高最終的優化結果。

[1] 程望斌，馮彩英，曾毅，等.航班計劃的優化設計研究[J].湖南理工學院學報(自然科學版)，2016，29(2):38-42，88.

[2] 上官雪民. 航班計劃的模擬與優化研究[D].上海：復旦大學，2008.

[3] 張伯生，劉飛.實現航班計劃優化的動態規劃模型[J].上海工程技術大學學報，2004，18(2):135-140.

[4] 黃小榮. 航班收益分析與最佳航班安排[J].中國民航學院學報(綜合版),2001，19(6):19-22，26.

[5] 楊新湦，齊莉，翟文鵬.航班時刻資源優化配置與延誤水平評估[J].河南科技大學學報(自然科學版)，2016，37(3):19-23，5.

[6] 李大衛，王莉，王夢光.遺傳算法與禁忌搜索算法的混合策略[J].系統工程學報，1998，13(3):28-34.