飛機(jī)路線多目標(biāo)決策研究

樂美龍，黃翠萍

(1.上海海事大學(xué) 科學(xué)研究院，上海201306;2.上海海事大學(xué) 物流研究中心，上海201306)

飛機(jī)路線就是將一組飛機(jī)分配給一個(gè)航班集以產(chǎn)生能滿足市場需求的日常航班調(diào)度［1］。在全球范圍內(nèi)，關(guān)于飛機(jī)路線方面的研究早已形成一套完整體系。在文獻(xiàn)［2］中，CLARKE 等將飛機(jī)路線問題看成是帶有側(cè)約束的歐拉回路問題，實(shí)質(zhì)就是旅行商問題，順帶研究了兩者之間的相似之處，并利用拉格朗日松弛使計(jì)算變得簡單。在文獻(xiàn)［3］中，GOPALAN 等也將飛機(jī)路線問題看成是歐拉回路問題。而在文獻(xiàn)［4］中，CORDEAU等認(rèn)為，飛機(jī)路線是一個(gè)航空資源分配的問題，是一個(gè)非線性的資源約束的多商品流網(wǎng)絡(luò)設(shè)計(jì)問題，由于約束之間相互關(guān)聯(lián)，其采用了Benders 分解。在文獻(xiàn)［5］中，MERCIER 等也將飛機(jī)路線問題看成是多商品流網(wǎng)絡(luò)設(shè)計(jì)問題，在改進(jìn)模型的基礎(chǔ)上增強(qiáng)了調(diào)配方案的魯棒性，與CORDEAU不同的是，MERCIER 根據(jù)問題的主次采用了兩種Benders 分解方法，具有較強(qiáng)的對比性。

1 航班環(huán)的生成方法

飛機(jī)路線問題的關(guān)鍵就是航班環(huán)的生成，人工完成這項(xiàng)工作非常耗時(shí)和疲憊，但是利用計(jì)算機(jī)來完成卻非常省時(shí)快捷。具體的計(jì)算機(jī)運(yùn)行步驟如下：

(1)輸入所有航班的航班號(hào)、離港和進(jìn)港城市及時(shí)間。

(2)生成所有可能周期為一日的有效飛機(jī)路線調(diào)配方案(航班串)，并設(shè)定地面過站時(shí)間最小為1 h，一天之內(nèi)一航班串的總的時(shí)間不得超過12 h，將結(jié)果存入一個(gè)文件夾。

(3)把這個(gè)文件中的每一個(gè)航班串與其文件中的所有航班串按照過夜機(jī)場與下一天的起飛機(jī)場相同的原則連接起來。該步驟重復(fù)兩次即可得到周期為三日的航班環(huán)，需要注意的是，所有航班環(huán)的起始機(jī)場和終止機(jī)場相同，并且至少在中心機(jī)場過夜一次。

2 飛機(jī)路線調(diào)配模型

設(shè)置飛機(jī)路線調(diào)配模型的參數(shù)：Tsk為第sk個(gè)航班的總的飛行時(shí)間;Msk為第sk個(gè)航班環(huán)在中心城市過夜的次數(shù);Csk為第sk個(gè)航班環(huán)的飛行成本;Fc為被覆蓋的航班數(shù);F為總的航班數(shù)。

決策變量：

目標(biāo)函數(shù)：

飛機(jī)利用率最大化，即maxxsTsk

維修機(jī)會(huì)最大化，即maxxsMsk

飛機(jī)數(shù)量最小化，即minxs

飛行總成本最小化，即minxsCsk

航班覆蓋率最大化，即maxFc/F

3 模型的求解

3.1 染色體設(shè)置

染色體的設(shè)置方法很多，為了簡化運(yùn)算，采用二進(jìn)制編碼［6］。

一共有S個(gè)航班環(huán)可供選擇，則可以把S個(gè)航班環(huán)看成是S個(gè)遺傳因子，構(gòu)成一個(gè)染色體，編碼為1 表示選擇了該航班環(huán)，代表顯性基因，編碼為0 表示未選擇該航班環(huán)，代表隱性基因。

初始化設(shè)置：進(jìn)化代數(shù)進(jìn)化器t=0，最大進(jìn)化代數(shù)T，隨機(jī)生成M個(gè)個(gè)體作為初始種群P(0)。

3.2 適應(yīng)性函數(shù)設(shè)置

根據(jù)模型特點(diǎn)，主要有5 個(gè)目標(biāo)函數(shù)，因此是一個(gè)多目標(biāo)規(guī)劃問題。單純使用權(quán)重的方法不是很合適［7］，在這里采用ELECTRE -IV 來評價(jià)個(gè)體的適應(yīng)度。ELECTRE -IV 相對于ELECTRE -I、ELECTRE -II 和ELECTRE -III 而言，最大的特點(diǎn)就是不設(shè)定表示屬性相對重要性的權(quán)［8］。

首先，確定各個(gè)目標(biāo)j下的無差別閾值qj，嚴(yán)格優(yōu)于閾值pj，否決閾值vj，一般滿足qj＜pj＜vj。閾值的確定原則可參考文獻(xiàn)［9］，如表1 所示。

表1 各目標(biāo)屬性值下的閾值

其次，根據(jù)式(1)和式(2)計(jì)算目標(biāo)屬性的集合。其中，J+(ai，ak)為個(gè)體ai優(yōu)于ak的目標(biāo)屬性的集合，J-(ai，ak)為個(gè)體ai劣于ak的目標(biāo)屬性的集合，cij為目標(biāo)屬性j下的個(gè)體i的屬性值。然后，根據(jù)式(3)和式(4)確定個(gè)體之間強(qiáng)級別高于關(guān)系Os和弱級別高于關(guān)系Ow。

表2 所示為M個(gè)個(gè)體之間的優(yōu)劣比較結(jié)果的直觀表示。a1行和a2列對應(yīng)的是Ow，則說明a1劣于a2，是a1Owa2的直觀表示。那么反過來，a2就應(yīng)該優(yōu)于a1，即為a2Osa1的直觀表示。

表2 個(gè)體之間的級別高于關(guān)系

最后，根據(jù)表2 的級別高于關(guān)系，得出排序結(jié)果，如表3 所示。

表3 排序結(jié)果

根據(jù)整個(gè)種群在考慮5 個(gè)目標(biāo)屬性上的總排序，確定適應(yīng)性函數(shù)。

3.3 選擇

將經(jīng)過適應(yīng)度評價(jià)的個(gè)體按照一定的概率篩選。將種群中M個(gè)個(gè)體按照適應(yīng)度從大到小排列，由于筆者在選擇過程中采用的是精英策略［10］，因此前10%的個(gè)體按P=1 的概率直接復(fù)制到下一代，將下一代的后10%替換掉，以保持種群數(shù)量不變。

3.4 交叉配對

隨機(jī)將兩個(gè)父代個(gè)體進(jìn)行交叉運(yùn)算生成新的個(gè)體。交叉運(yùn)算原則可用以下矩陣運(yùn)算規(guī)則表示：

若新的個(gè)體的顯性因子較多，那么，不可避免地會(huì)出現(xiàn)不可行解(有航班同一天內(nèi)被覆蓋兩次及兩次以上)，這就需要將同一天內(nèi)覆蓋同一航班的眾多航班環(huán)按照隨機(jī)抽取的原則，隨機(jī)選擇一個(gè)航班環(huán)，去掉其他的航班環(huán)，將其修正為可行解。

3.5 變異運(yùn)算

若個(gè)體中兩個(gè)父代配對以后不按上述矩陣運(yùn)算規(guī)則產(chǎn)生子代，則為變異。

3.6 終止原則

按照適應(yīng)性函數(shù)的設(shè)置，選擇、交叉配對，如此循環(huán)，直到進(jìn)化代數(shù)進(jìn)化器t=T，最后一個(gè)種群為P(t)。在所有臨時(shí)最優(yōu)解中尋找最優(yōu)作為該模型的近似最優(yōu)解。

4 算例

以東方航空的波音737 機(jī)型的北京、上海、南京、廣州、成都、昆明的航班時(shí)刻表(表4)為例，一共是22 個(gè)航班。

(1)對表4 航班時(shí)刻進(jìn)行規(guī)范處理，利用Matlab 編程，按照上述的要求，生成周期為一天的航班串，最多為4 個(gè)航班，共有85 個(gè)航班串。

(2)利用Matlab 生成周期為3 日的航班環(huán)。但是，考慮到現(xiàn)實(shí)中3 天飛兩個(gè)航班以及覆蓋率問題，可考慮在航班串中加入這22 個(gè)航班以及符合3 天飛兩個(gè)航班的航班環(huán)，為696 個(gè)。

(3)按照改進(jìn)遺傳算法的步驟，設(shè)定種群M=100，遺傳因子S=696，交叉配對的概率0.6，變異的概率0.1，部分結(jié)果如下：

表4 航班時(shí)刻表

在這個(gè)算例中，經(jīng)過500 次迭代，最終選出了9 個(gè)航班環(huán)，即只需要9 架飛機(jī)來執(zhí)行所有的航班，但是對S444，S452，S458和S468這4 個(gè)航班環(huán)的航班可作適當(dāng)?shù)恼{(diào)整?？傦w行成本如圖1 所示。

由圖1 可知，總的飛行成本由大變小，最后趨于穩(wěn)定。經(jīng)過近300 代以后，收斂于一固定成本，主要是各個(gè)目標(biāo)互相牽制作用的結(jié)果，雖然過程此起彼伏，但是最終結(jié)果趨向于能兼顧各目標(biāo)的一個(gè)成本，即成本的增加已不能使其他目標(biāo)更加優(yōu)化。

圖1 總飛行成本

5 結(jié)論

筆者結(jié)合ELECTRE-IV 和改進(jìn)遺傳算法來研究飛機(jī)路線規(guī)劃，具有計(jì)算速度快、時(shí)間短的優(yōu)勢，但也有不足之處，例如航班環(huán)的數(shù)量過大，以及如何快速收斂到近似最優(yōu)解等，只有解決了這些問題，才能使飛機(jī)路線規(guī)劃在實(shí)際使用的效率和速率上得到令人滿意的結(jié)果。

［1］CHOU T Y，LIU T K，LEE C N，et al.Method of inequality-based multiobjective genetic algorithm for domestic daily aircraft routing［J］.IEEE Transactions on Systems，Man，and Cybernetics(Part A：Systems and Humans)，2008，38(2)：299 -308.

［2］CLARKE L，JOHNSON E，NEMHAUSER G，et al.The aircraft rotation problem［J］. Annals of OR：Mathematics of Industrial Systems II，1997，69(1)：33-46.

［3］GOPALAN R，TALLURI K. The aircraft maintenance routing problem［J］. Operations Research，1998(46)：260 -271.

［4］CORDEAU J，STOJKOVIC G，SOUMIS F，et al.Benders decomposition for simultaneous aircraft routing and crew scheduling［J］. Transportation Science，2001(35)：375-388.

［5］MERCIER A，CORDEAU J，SOUMIS F.A computational study of benders decomposition for the integrated aircraft routing and crew scheduling problem［J］. Computers ＆Operations Research，2005，32(6)：1451-1476.

［6］沈中林，李廷朵. 遺傳算法在航班覆蓋問題中的應(yīng)用研究［J］.中國民航大學(xué)學(xué)報(bào)，2008，26(6)：5 -9.

［7］游進(jìn)軍，紀(jì)昌明. 基于遺傳算法的多目標(biāo)問題求解方法［J］.水利學(xué)報(bào)，2003(7)：64 -69.

［8］孫世巖，邱志明. 級別不低于方法及其發(fā)展評述［J］.管理工程學(xué)報(bào)，2008，22(3)：41 -45.

［9］LIU P D，ZHANG X.Research on the supplier selection of a supply chain based on entropy weight and improved ELECTRE-III method［J］.International Journal of Production Research，2011，49(3)：637 -646.

［10］李耀華，秦如如.基于混合遺傳算法的航班串優(yōu)化模型研究［J］.中國民航大學(xué)學(xué)報(bào)，2010，28(6)：31-34.