基于最大貢獻(xiàn)的航班計(jì)劃優(yōu)化模型

馮輝宇，武丁杰，羅 超

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

為了提升航空公司的市場(chǎng)競(jìng)爭(zhēng)力，其生產(chǎn)運(yùn)營(yíng)效率是至關(guān)重要的。生產(chǎn)運(yùn)營(yíng)效率可以在很多方面得到體現(xiàn)，例如完善的機(jī)隊(duì)維修計(jì)劃、機(jī)組的配備以及航班計(jì)劃等。航班計(jì)劃是一切生產(chǎn)運(yùn)營(yíng)活動(dòng)的基礎(chǔ)，也是后續(xù)服務(wù)的保障。本文將從航班計(jì)劃優(yōu)化的角度探討如何提高航空公司的收益及生產(chǎn)運(yùn)營(yíng)效率。

1 航班計(jì)劃優(yōu)化模型

1.1 問(wèn)題分析

一般來(lái)說(shuō)，航班計(jì)劃的優(yōu)化是以利潤(rùn)最大化為基礎(chǔ)的。本文從航班貢獻(xiàn)的角度去研究航班計(jì)劃的優(yōu)化問(wèn)題。航班貢獻(xiàn)的多少可以反映出一個(gè)航空公司整體的盈利情況[1]。航班貢獻(xiàn)小于0，則飛行越多，虧損越多。航班貢獻(xiàn)大于0，即使利潤(rùn)為負(fù)，由于航班收入可以覆蓋變動(dòng)成本及附加稅，航班飛行之后，可以分?jǐn)傄恍┕潭ǔ杀尽榱碎_(kāi)辟市場(chǎng)，這樣的航班仍可繼續(xù)運(yùn)行[2]。

1.2 模型假設(shè)及符號(hào)說(shuō)明

1.2.1 模型假設(shè)

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

(2)航空公司的機(jī)隊(duì)規(guī)模已經(jīng)確定，短時(shí)間內(nèi)不會(huì)有很大的變化；

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

(4)航線網(wǎng)絡(luò)已經(jīng)確定，航班會(huì)按既定的航線飛行；

(5)客運(yùn)和貨運(yùn)流量根據(jù)歷史數(shù)據(jù)已經(jīng)預(yù)測(cè)。

1.2.2 常用符號(hào)說(shuō)明

1.2.3 模型的建立

本文主要從航班收入、航班成本、航班貢獻(xiàn)這三方面考慮來(lái)建立模型。航班的收入主要以座公里收入及客座率來(lái)體現(xiàn)，座公里收入是民航領(lǐng)域的最終評(píng)估指標(biāo)，既可以用來(lái)對(duì)比單個(gè)航班的經(jīng)營(yíng)品質(zhì)優(yōu)劣，也可以用來(lái)對(duì)比整條航線的優(yōu)劣。航班的成本主要由2部分組成，即固定運(yùn)輸成本和變動(dòng)運(yùn)輸成本。固定運(yùn)輸成本在上述中講過(guò)，在一定時(shí)期內(nèi)是不變的。變動(dòng)運(yùn)輸成本與航班的運(yùn)行情況有關(guān)，一般與航班的客運(yùn)和貨運(yùn)量相關(guān)，客運(yùn)、貨運(yùn)量的提升都會(huì)使航班的變動(dòng)運(yùn)輸成本增加。

建立一個(gè)以航班總貢獻(xiàn)最大的航班計(jì)劃模型：

(1)

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

此外，根據(jù)研究，民建基金為運(yùn)輸收入的5%，營(yíng)業(yè)稅金及附加為運(yùn)輸收入的3.75%[3]。

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

(2)

(3)

(4)

(5)

(6)

(7)

2 模型求解算法

由于上述模型屬于NP問(wèn)題，現(xiàn)代優(yōu)化方法中精確算法是解決小規(guī)模問(wèn)題的求解方法，針對(duì)這種大規(guī)模問(wèn)題的求解，常采用啟發(fā)式算法或者說(shuō)近似算法。由于傳統(tǒng)的遺傳算法收斂過(guò)快，禁忌搜索算法只能求得局部最優(yōu)，為了克服這一缺點(diǎn)，本文采用引入禁忌搜索的遺傳算法，將禁忌算法的“禁忌”和“特赦”準(zhǔn)則引入到遺傳算法中，克服遺傳算法早熟的現(xiàn)象，求得全局最優(yōu)解[6]。這種思想主要表現(xiàn)在遺傳算法的交叉算子上，通過(guò)改進(jìn)后的交叉算子我們將其稱為T(mén)SR算子。

2.1 遺傳-禁忌混合算法

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

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

(3)適應(yīng)度評(píng)價(jià)。適應(yīng)度是用來(lái)區(qū)分群體中個(gè)體優(yōu)劣的標(biāo)準(zhǔn)，是對(duì)種群染色體篩選的一個(gè)依據(jù)。適應(yīng)度值需要根據(jù)實(shí)際情況選取，優(yōu)化的目標(biāo)就是盡可能尋找適應(yīng)度值大的染色體，選取的染色體適應(yīng)度值越大，優(yōu)化的結(jié)果就越好。

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

(8)

其中，Ki為個(gè)體i的適應(yīng)度值。

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

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

(9)

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

2.2 算法步驟

主要步驟如下：

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

步驟2 計(jì)算各個(gè)個(gè)體的適應(yīng)度值；

步驟3 利用選擇算子進(jìn)行選擇；

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

(1)對(duì)于每一個(gè)染色體，隨機(jī)生成一個(gè)數(shù)，如果這個(gè)數(shù)大于交叉概率，那么這個(gè)染色體被選中，否則沒(méi)有被選中；

(2)被選中的染色體為父代染色體，對(duì)父代染色體進(jìn)行交叉操作，以產(chǎn)生兩個(gè)后代染色體；

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

(4)若子代染色體的適應(yīng)度值大于預(yù)先設(shè)定的渴望水平，則不考慮其是否被禁忌的情況，直接將子代染色體保留到下一代中；若沒(méi)達(dá)到渴望水平，則進(jìn)行下一步操作；

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

步驟5 進(jìn)行變異操作；

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

3 案例分析

以某航空公司南京祿口機(jī)場(chǎng)為樞紐的航班為例，2016年11月份部分航班銷(xiāo)售情況如表1所示。

表1 部分航班銷(xiāo)售情況

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

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

通過(guò)Matlab軟件仿真，設(shè)定種群規(guī)模為30,最大遺傳代數(shù)為300,變異概率為0.2,對(duì)比尋優(yōu)分析模擬結(jié)果如圖1所示。

圖1 對(duì)比尋優(yōu)分析模擬結(jié)果

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

4 結(jié)語(yǔ)

本文通過(guò)對(duì)航空公司經(jīng)營(yíng)效率和航班計(jì)劃的分析，以航班貢獻(xiàn)為切入點(diǎn)，研究航空公司整體的盈利情況。從航班收入、航班成本以及航班貢獻(xiàn)三者之間的關(guān)系出發(fā)，建立了以航班貢獻(xiàn)為目標(biāo)的優(yōu)化模型，該模型可以很好的反映出航班運(yùn)營(yíng)情況對(duì)航班貢獻(xiàn)的影響。采用遺傳和禁忌的混合算法對(duì)模型求解，把禁忌算法的禁忌和特赦準(zhǔn)則引入到遺傳算法中，緩和遺傳算法收斂過(guò)快的現(xiàn)象，從而提高最終的優(yōu)化結(jié)果。

[1] 程望斌，馮彩英，曾毅，等.航班計(jì)劃的優(yōu)化設(shè)計(jì)研究[J].湖南理工學(xué)院學(xué)報(bào)(自然科學(xué)版)，2016，29(2):38-42，88.

[2] 上官雪民. 航班計(jì)劃的模擬與優(yōu)化研究[D].上海：復(fù)旦大學(xué)，2008.

[3] 張伯生，劉飛.實(shí)現(xiàn)航班計(jì)劃優(yōu)化的動(dòng)態(tài)規(guī)劃模型[J].上海工程技術(shù)大學(xué)學(xué)報(bào)，2004，18(2):135-140.

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

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

[6] 李大衛(wèi)，王莉，王夢(mèng)光.遺傳算法與禁忌搜索算法的混合策略[J].系統(tǒng)工程學(xué)報(bào)，1998，13(3):28-34.