張文成, 熊 靜, 張 虹, 嚴(yán) 宇

(上海工程技術(shù)大學(xué) 航空運輸學(xué)院, 上海 201620)

隨著民航運輸業(yè)的發(fā)展,航空公司機組排班問題復(fù)雜性和規(guī)模性顯著增加.機組排班研究被眾多學(xué)者認(rèn)為是一個十分困難的組合優(yōu)化問題(NP-hard)[1],而機組配對(Crew pairing)是其中一個子問題.

機組配對問題是指在滿足中國民航局規(guī)定以及航空公司特殊要求下,生成一個覆蓋所有航班并達到目標(biāo)最優(yōu)的配對(Pairing)集合.機組配對優(yōu)化目標(biāo)可以定義為機組成本最小[2]、飛行員工作量均衡[3]、配對數(shù)量最少、機組資源利用率最大等.

國內(nèi)外機組配對優(yōu)化研究成果很豐富,大部分研究思路是先生成配對再尋優(yōu).學(xué)者們常用遺傳算法來解決機組配對尋優(yōu)問題,并提出改進方案以獲得高質(zhì)量解:以Yen等[4]提出的模型為基礎(chǔ),李建[5]對機組配對問題進行描述,使用改進遺傳算法對其進行算法設(shè)計;石麗娜等[6]將遺傳算法同時應(yīng)用在機組任務(wù)選擇和配對階段;Demirel等[7]開發(fā)基于改進動態(tài)遺傳算法的啟發(fā)式算法和代價較低的替代配對搜索方法;Deveci等[8]基于遺傳算法優(yōu)化過程,選擇成本最低的最佳配對.

遺傳算法實現(xiàn)復(fù)雜,部分學(xué)者將目光投向其他優(yōu)化算法:Agustin等[9]提出可變鄰域搜索方法;Tsubasa等[10]提出一種在特殊增強條件下應(yīng)用部分優(yōu)化兩級分解算法(POPMUSIC);于海波等[11]提出使用離散型粒子群算法來解決飛機排班問題,該算法涉及參數(shù)少,全局搜索能力強,常被作為尋優(yōu)研究的重點.為提高該算法尋優(yōu)效率,各種改進策略被提出,如引入經(jīng)驗因子[12]等.

本文在實現(xiàn)機組配對時,將機組資源利用率最大作為優(yōu)化目標(biāo).先采用深度優(yōu)先搜索(DFS)算法產(chǎn)生所有滿足約束的配對結(jié)果,再使用二進制粒子群優(yōu)化(BPSO)算法選擇產(chǎn)生配對集合一個子集,選擇過程中為避免陷入局部最優(yōu),設(shè)計改進二進制粒子群優(yōu)化(IBPSO)算法參與尋優(yōu).

1 機組配對數(shù)學(xué)模型

在航空公司總營運成本組成中,機組人員成本僅次于航油成本.我國航空公司機組成本主要由基本工資、飛行小時津貼、外站過夜補貼費用和機組成本等組成,基本工資通常固定不變.在機組配對時應(yīng)該提高機組資源利用率,著力降低人員成本,從而達到總成本最優(yōu)的目的.機組配對原則如下:

1) 同一配對中機型必須統(tǒng)一;

2) 配對中前序航班到達站和后序航班出發(fā)站必須相互銜接,相鄰航段經(jīng)停時間或航班交接時間一般至少40 min;

3) 配對飛行路徑應(yīng)盡可能為封閉回路,避免機組在外待過長時間,減少不必要的機組成本;

4) 為保證飛行安全,機組飛行任務(wù)時間不能違反民航當(dāng)局相關(guān)規(guī)定.具體要求為:每日歷周飛行時間要少于40 h;每日歷月飛行時間要少于100 h;每日歷年飛行時間要少于1 000 h;增加一名正駕駛的單套機組最多飛行時間不得超過10 h,值勤時間不得超過16 h.

以上述配對原則及成本最優(yōu)目標(biāo)為出發(fā)點,在僅考慮單套機組(可增加一名正駕駛)情況下,擬構(gòu)建以機組資源利用率最大為基本優(yōu)化目標(biāo)的數(shù)學(xué)模型.機組資源利用率定義為總飛行時間與總值勤時間之比.對于給定航班計劃,每個航班飛行時間是定值,因此將求解機組資源利用率最大轉(zhuǎn)化為求解總值勤時間最短,構(gòu)建數(shù)學(xué)模型的目標(biāo)函數(shù)為

(1)

式中:目標(biāo)函數(shù)(1)為最短總值勤時間;目標(biāo)函數(shù)(2)為最少機組配對數(shù);i為第i個航班;j為第j個配對;tj為第j個配對值勤時間;F為所有航班集合;D為所有配對集合;xj為機組配對0-1決策變量,如果機組配對j被選擇,xj=1,其他則為0;[aij]為0-1矩陣,aij=1表示配對j中包含航班i,aij=0則表示航班i不在配對j中.

2 機組配對生成

2.1 構(gòu)建航班連接網(wǎng)絡(luò)

機組配對生成分兩步:第一步是構(gòu)建航班連接網(wǎng)絡(luò)圖;第二步是根據(jù)相關(guān)法規(guī)限制條件從網(wǎng)絡(luò)圖中搜索可行機組配對.

構(gòu)建航班連接網(wǎng)絡(luò)圖時,首先在航班計劃表中依次將每個離港機場作為根節(jié)點,得到所有以該機場為出發(fā)機場的航班集合;然后用銜接邊將其航班節(jié)點與根節(jié)點連接起來,用航班邊將其與航班連接起來,構(gòu)建單層航班樹;在基地機場航班樹基礎(chǔ)上遍歷葉節(jié)點,將各到達機場出發(fā)航班樹連接到該節(jié)點,逐級連接,直到?jīng)]有滿足規(guī)定的后續(xù)航班為止,完成航班連接樹構(gòu)建;在航班樹基礎(chǔ)上,增加基地機場(或過夜機場)終節(jié)點,用銜接邊將各葉節(jié)點與終節(jié)點連接起來,構(gòu)造成航班連接網(wǎng)絡(luò).

2.2 機組配對搜索

機組配對搜索采用圖論中DFS算法[13],它是用于遍歷搜索樹或圖的數(shù)據(jù)結(jié)構(gòu)算法.DFS算法過程描述如下:

1) 將基地機場作為起始點放入棧中,并標(biāo)記為已訪問;

2) 當(dāng)棧不為空時,若當(dāng)前棧中第1個航班節(jié)點后序所有航班存在未被訪問的,任意選擇其一作為下一個訪問航班,并將該航班節(jié)點入棧并標(biāo)記為已訪問,重復(fù)此過程至棧為空,轉(zhuǎn)過程4);

3) 若當(dāng)前訪問節(jié)點為終節(jié)點,則將其出棧,并重復(fù)過程2);

4) 若棧為空,則算法結(jié)束.

第1次DFS得到的配對值勤時間較短,即機組資源利用率不高,需要將第1次配對編號,再構(gòu)造航班樹進行第2次DFS.在兩次搜索過程中,航班之間銜接時間必須滿足要求,記錄路徑上的飛行時間和值勤時間,保證得到的初始可行配對符合配對原則.DFS結(jié)束后,對孤立航班進行手工編排.

3 機組配對尋優(yōu)

3.1 粒子群優(yōu)化算法

1995年,Eberhart和Kennedy從鳥群覓食行為中得到靈感,提出粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法.PSO算法是通過設(shè)計一種無質(zhì)量粒子來模擬鳥群中的鳥,該粒子僅具有速度和位置兩個屬性,分別代表移動的快慢和方向.算法具體流程如圖1所示.

3.2 改進二進制粒子群優(yōu)化(IBPSO)算法的實現(xiàn)

機組配對尋優(yōu)是一個約束離散優(yōu)化問題,在使用PSO算法時需要對算法解的編碼方式、粒子位置和速度更新做出相應(yīng)改進.Kennedy和Eberhart在1997年最先設(shè)計出針對離散空間約束優(yōu)化問題的離散二進制粒子群優(yōu)化算法(BPSO)[14],BPSO容易陷入局部最優(yōu),本文對其進行改進.

在設(shè)計適應(yīng)度值時,主要考慮模型中目標(biāo)函數(shù)值.針對違反約束條件的粒子,設(shè)計指數(shù)型增長懲罰因子p,違反程度越大,懲罰力度也越大,公式為

圖1 PSO流程圖Fig.1 Flow chart of PSO

(2)

p=round(elength(C(aij·xj～=1)))

(3)

其中:fitness為適應(yīng)度值;C為航班覆蓋向量,其元素個數(shù)反映不滿足約束條件的程度;length函數(shù)為返回C向量中元素個數(shù);round為四舍五入函數(shù).

為更加接近算法尋優(yōu)實際進化狀態(tài),本文提出基于余弦自適應(yīng)慣性權(quán)重w,計算公式為

(4)

式中:wmin、wmax分別為慣性權(quán)重最小值、最大值;t為迭代次數(shù);tmax為最大迭代次數(shù).改進后算法在尋優(yōu)早期w較大,具有較強全局探索能力;在尋優(yōu)后期w較小,局部開發(fā)能力更強.

原始BPSO算法中S形映射函數(shù)基本公式為

(5)

(6)

式中:rand()為分布在[0,1]的隨機數(shù);S(vj)為xj取1的概率,S(vj)為Sigmoid函數(shù).為使函數(shù)S(vj)不靠近端點值,粒子速度限定在[-vmax,vmax].映射函數(shù)曲線如圖2所示.

由圖2及強制性位置更新程序可知,正方向速度不斷增大,位置向量取值為1的概率也不斷增大;反之,負(fù)方向速度不斷增大,位置向量取值為0的概率不斷增大.

圖2 映射函數(shù)曲線Fig.2 Curves of mapping function

原始BPSO算法在迭代后期容易局部收斂,為使算法更符合粒子運動規(guī)律,本文將種群進化過程等分成收斂和跳出局部最優(yōu)兩個階段.迭代前期采用無速度限制S形映射函數(shù),以促進算法穩(wěn)定收斂;后期采用正弦映射函數(shù)以加速收斂,并且粒子位置更新采用非強制性更新程序,即當(dāng)概率值大于隨機數(shù)時,位置取其原位置向量的補集,否則粒子位置向量保持不變.

正弦映射函數(shù)圖像如圖2中虛線所示,公式為

(7)

本文改進IBPSO算法步驟如下:

1) 粒子種群隨機初始化操作;

2) 設(shè)置種群參數(shù);

3) 慣性權(quán)重自適應(yīng)調(diào)整;

4) 粒子速度更新,公式為

(8)

5) 粒子位置更新,前期采用無速度限制S形映射函數(shù)與強制性位置更新程序,后期采用正弦映射函數(shù)與非強制性位置更新程序;

6) 重復(fù)步驟3)～步驟5),直至滿足終止條件;

7) 滿足終止條件,輸出最優(yōu)解及相應(yīng)適應(yīng)度值,算法結(jié)束.

4 航班算例實證

本文選取某航空公司波音737機型,以某天虹橋機場基地運營航班數(shù)據(jù)進行機組配對優(yōu)化實例研究,部分航班信息見表1.

表1 某航空公司波音737航班信息表Table 1 Boeing 737 flight information sheet for an airline

4.1 算例配對生成

假設(shè)配對第一個航班起飛之前和最后一個航班落地之后花費時間為1 h,根據(jù)限制條件,本文算例中所得單一配對最多飛行時間不得超過10 h,每個配對中第一個航班起飛到最后一個航班落地時間(即本文所指值勤時間)不超過15 h.

為測試算法實際優(yōu)化效果,從表1中選取航班規(guī)模為24(算例1)和50(算例2)的兩組數(shù)據(jù)進行機組任務(wù)配對,兩組算例第1次DFS分別生成14、37個配對,第2次DFS分別生成31、126個配對.

4.2 算例配對尋優(yōu)

1) 算法參數(shù)設(shè)置

配對尋優(yōu)時,為對比分析本文設(shè)計的IBPSO算法性能,選取原始BPSO和另外3種改進BPSO算法參與優(yōu)化.原始BPSO粒子最大速度為0.2;NEWBPSO1在原始BPSO基礎(chǔ)上設(shè)置粒子最大速度為0.6,慣性權(quán)重基于余弦自適應(yīng)變化;NEWBPSO2在NEWBPSO1基礎(chǔ)上放開粒子速度限制;NEWBPSO3在NEWBPSO2基礎(chǔ)上采用正弦映射與非強制性位置更新程序.

根據(jù)文獻[15],算法迭代次數(shù)固定為1 000,學(xué)習(xí)因子c1、c2均設(shè)置為2,慣性權(quán)重最大值為0.9,最小值為0.4.考慮到粒子種群規(guī)模會影響算法性能,選擇100和200兩種種群規(guī)模做對比試驗.

本文算例仿真環(huán)境為Win10系統(tǒng),使用Matlab 2016編程.硬件環(huán)境為INTEL酷睿處理器I5-6200U,主頻為2.30 GHz,內(nèi)存為8 GB.

2) 配對尋優(yōu)結(jié)果分析

兩組算例采用5種算法在種群規(guī)模為100和200情況下分別獨立運行30次,獲得適應(yīng)度值的均值和方差,見表2,最優(yōu)值加粗表示.觀察表2,配對尋優(yōu)中4種測試條件下IBPSO算法都具有最好的均值和方差,其求解穩(wěn)定性更好,具有更好的收斂能力,原因在于:慣性權(quán)重基于余弦自適應(yīng)變化,根據(jù)粒子種群進化時期特點,采取兩種不同映射方式更符合粒子運動規(guī)律,從而提高尋優(yōu)能力和解的質(zhì)量.

表2 5種算法配對尋優(yōu)仿真結(jié)果Table 2 Simulation results of five algorithms for pairing optimization

同一算例中,初始種群規(guī)模的增加雖然會使收斂時間增大,但能增強全局搜索能力,有效提高解的質(zhì)量,使算法尋優(yōu)更穩(wěn)定.對比兩組算例,航班規(guī)模增加使得問題求解維度明顯增大,適應(yīng)度值方差明顯擴大,算法求解穩(wěn)定性和質(zhì)量有所下降.

4種測試條件下5種算法總體收斂曲線圖如圖3所示.由圖可以發(fā)現(xiàn),所有算法都會出現(xiàn)收斂曲線呈直線的情況,即陷入局部最優(yōu).NEWBPSO1由于提高了粒子最大速度和慣性權(quán)重自適應(yīng)變化,其收斂速度會快于BPSO,表2中數(shù)據(jù)可看出其得到的解也優(yōu)于BPSO;NEWBPSO2對粒子速度無限制,提升算法全局搜索能力,其收斂速度快于NEWBPSO1,容易獲得較穩(wěn)定的解;NEWBPSO3采取正弦映射和非強制性位置更新程序,收斂速度加快,算例1中得到的解會差于NEWBPSO2,但增加算例航班規(guī)模后其解明顯優(yōu)于NEWBPSO2;IBPSO結(jié)合NEWBPSO2和NEWBPSO3優(yōu)點,算例1中其收斂速度不遜色于NEWBPSO3,并獲得更優(yōu)秀和穩(wěn)定的解,算例2中迭代前期其收斂速度介于NEWBPSO2和NEWBPSO3之間,后期明顯比NEWBPSO3收斂更快,且更容易跳出局部最優(yōu),得到更好的解.

算例1采用IBPSO得到的最優(yōu)配對見表3.

表3 算例1機組配對結(jié)果Table 3 Crew pairing results of example 1

算例2由于增加航班規(guī)模,使得優(yōu)化問題維度明顯提高,表現(xiàn)出啟發(fā)式算法局限性,即算法尋優(yōu)解會靠近最優(yōu)解.算例2采用IBPSO得到的最優(yōu)配對見表4.

圖3 5種算法總體收斂曲線圖Fig.3 Overall convergence curves of five algorithms

表4 算例2機組配對結(jié)果Table 4 Crew pairing results of example 2

5 結(jié) 語

針對BPSO算法易陷入局部最優(yōu)等問題,本文采用IBPSO算法尋優(yōu)實現(xiàn)機組配對優(yōu)化.兩組不同規(guī)模航班算例表明,IBPSO從整體上提高算法收斂速度,求解穩(wěn)定性好,并得到很好的機組配對結(jié)果,為優(yōu)化機組排班提供理論基礎(chǔ).后續(xù)研究應(yīng)考慮更復(fù)雜的實際航班配對約束,關(guān)注航班規(guī)模擴大使求解不穩(wěn)定的問題,以提升算法應(yīng)用能力.