汪 瑜，朱金福，葛 偉

(1.中國民航飛行學(xué)院航空運輸管理學(xué)院，四川 廣漢 618307;2.南京航空航天大學(xué)民航學(xué)院，江蘇 南京 210016)

明確航空公司擬運營區(qū)域未來一段時期內(nèi)機隊的規(guī)模與結(jié)構(gòu)，是確保航空運輸企業(yè)在需求旺季時實現(xiàn)運營利潤最大化的前提，也是航空公司在需求淡季時降低運營過剩運力的保證.魯棒的機隊構(gòu)成可以提高民航企業(yè)優(yōu)化稀缺資源配置的能力，因此，合理有效的機隊魯棒優(yōu)化方法關(guān)系到民航運輸企業(yè)的運營成本和風(fēng)險可控性，是獲取最大收益的關(guān)鍵性戰(zhàn)略決策.

文獻［1］在分析機隊規(guī)劃基本方程的基礎(chǔ)上，給出了宏觀規(guī)劃的經(jīng)驗分析方法.文獻［2］在航空公司未來擬運營網(wǎng)絡(luò)環(huán)境的層面上建立了機隊宏觀規(guī)劃的數(shù)學(xué)模型.文獻［3-7］從航班/航線機型分配的角度構(gòu)建了微觀機隊規(guī)劃數(shù)學(xué)模型，并探討了機隊的魯棒性規(guī)劃方法.文獻［8］利用數(shù)學(xué)模型分析了機隊構(gòu)成與航線特征的關(guān)系，指出了航空管制因素對航空公司機隊構(gòu)成的影響.文獻［9］利用成本分析法分析了歐盟碳排放規(guī)則對于機隊構(gòu)成的影響.文獻［10-11］在考慮了需求限制、機場交通流限制等因素的基礎(chǔ)上，構(gòu)建了微觀機隊規(guī)劃數(shù)學(xué)模型.

通過上述分析可以發(fā)現(xiàn)，基于航線網(wǎng)絡(luò)層面的宏觀機隊規(guī)劃法［1］雖然簡單易操作，但卻很難反映出旅客需求溢出對于擬運營機隊構(gòu)成的影響，也無法準(zhǔn)確反映機型航線的適應(yīng)性問題.而從航線/航班層面的微觀機隊規(guī)劃法［3］又很難準(zhǔn)確反映出未來機隊擬運營環(huán)境的特點，例如旅客需求的不確定性、生產(chǎn)運營組織模式特征等.加之國內(nèi)各大航空公司生產(chǎn)運營模式向樞紐輪輻式航線網(wǎng)絡(luò)結(jié)構(gòu)的轉(zhuǎn)型，大量的中轉(zhuǎn)銜接旅客在增加航段旅客流量的同時，又使得流經(jīng)航段的旅客組合更為復(fù)雜，這些現(xiàn)象導(dǎo)致傳統(tǒng)微觀機隊規(guī)劃法已經(jīng)無法準(zhǔn)確評估航段旅客組合［12-13］對于機隊構(gòu)成的影響.因此，從旅客組合優(yōu)化角度研究機隊的魯棒優(yōu)化方法，對于航空公司準(zhǔn)確把握未來擬運營環(huán)境中所需機隊的規(guī)模與結(jié)構(gòu)有重大的現(xiàn)實意義.

本文首先通過比較全連通航線網(wǎng)絡(luò)與樞紐輪輻式航線網(wǎng)絡(luò)兩種不同航班運營組織模式對于機隊構(gòu)成的影響，指出在具有旅客中轉(zhuǎn)銜接的航班組織模式(例如樞紐輪輻式航線網(wǎng)絡(luò)運營模式)下旅客需求溢出的網(wǎng)絡(luò)效應(yīng)問題，同時又進一步說明從航線網(wǎng)絡(luò)環(huán)境運力優(yōu)化配置角度構(gòu)建機隊規(guī)劃方法的必要性;其次，以機隊規(guī)劃成本最小化為目標(biāo)函數(shù)，綜合考慮未來擬運營區(qū)域內(nèi)航班頻次限制、旅客需求限制、飛行時間限制等資源約束，構(gòu)建航空公司機隊的魯棒優(yōu)化模型;然后，通過構(gòu)造旅客需求的離散情景集，利用情景匯聚(scenario aggregation)算法求解機隊規(guī)劃問題;最后，通過算例驗證了機隊規(guī)劃方法的有效性.

1 問題提出

從微觀層面構(gòu)建機隊規(guī)劃方法必須準(zhǔn)確模擬企業(yè)在未來一段時期內(nèi)的運營環(huán)境，然而在樞紐航線網(wǎng)絡(luò)運營模式下，某一航段旅客的溢出很有可能會造成整個航線網(wǎng)絡(luò)環(huán)境內(nèi)旅客流量的下降，進而導(dǎo)致傳統(tǒng)基于航段的微觀機隊規(guī)劃法無法準(zhǔn)確評估旅客溢出成本對于機隊規(guī)劃結(jié)果的影響.圖1(圈內(nèi)字母表示機場，線上數(shù)字表示座級)給出了全連通航線網(wǎng)絡(luò)結(jié)構(gòu)與樞紐輪輻式航線網(wǎng)絡(luò)結(jié)構(gòu)下，不同航班運營模式對機隊構(gòu)成的影響.全連通航線網(wǎng)絡(luò)是指任意兩個城市之間都有直達(dá)航班的航線網(wǎng)絡(luò);樞紐輪輻式航線網(wǎng)絡(luò)是指航線的安排以某個城市為樞紐，其它城市之間沒有直達(dá)航線，而是都與樞紐相連，通過樞紐進行中轉(zhuǎn)銜接［14］.

假設(shè)在充分考慮航班機型運營成本的前提下，圖1(a)的全連通航線網(wǎng)絡(luò)結(jié)構(gòu)中可以采用110座級的飛機運輸8次，而在圖1(b)的樞紐輪輻式航線網(wǎng)絡(luò)結(jié)構(gòu)中，H點成為樞紐且為其它節(jié)點旅客需進行轉(zhuǎn)運，此時需要采用260座級的飛機運輸4次，但同時會導(dǎo)致10位旅客需求溢出，若溢出的是中轉(zhuǎn)銜接旅客，就會造成其它銜接航段上旅客同時溢出的現(xiàn)象(即航線網(wǎng)絡(luò)效應(yīng))，因此，在機隊規(guī)劃時準(zhǔn)確反映該效應(yīng)是提高機隊規(guī)劃準(zhǔn)確性的關(guān)鍵.

與全連通航線網(wǎng)絡(luò)結(jié)構(gòu)不同的是，由于樞紐航線網(wǎng)絡(luò)結(jié)構(gòu)采用航班中轉(zhuǎn)銜接模式運輸旅客，這使得流經(jīng)任一航段的旅客會產(chǎn)生疊加現(xiàn)象.疊加現(xiàn)象可以保證航空公司采用更大座級飛機執(zhí)飛而形成一定的網(wǎng)絡(luò)經(jīng)濟性，因此，準(zhǔn)確反映航線網(wǎng)絡(luò)構(gòu)型對于需求的影響同樣也是保證機隊規(guī)劃結(jié)果準(zhǔn)確性的關(guān)鍵.

圖1 不同航線網(wǎng)絡(luò)運營模式對機隊構(gòu)成的影響Fig.1 Impact of different route network operation modes on fleet composition

2 模型建立

考慮旅客需求溢出的網(wǎng)絡(luò)效應(yīng)，機隊規(guī)劃過程必須考慮旅客的組合優(yōu)化問題.航段上旅客需求的疊加現(xiàn)象，又使得機隊規(guī)劃過程必須考慮航線網(wǎng)絡(luò)運力的優(yōu)化分配問題.鑒于此，本文在充分考慮旅客組合優(yōu)化問題的基礎(chǔ)上，利用需求運力優(yōu)化配置技術(shù)構(gòu)建航空公司的機隊規(guī)劃數(shù)學(xué)模型.

2.1 符號說明

基于航線網(wǎng)絡(luò)效應(yīng)下的運力優(yōu)化配置的機隊規(guī)劃模型決策變量與參數(shù)說明如下:

zk為決策變量，表示在機隊規(guī)劃期內(nèi)所需機型k(k∈K)飛機的架數(shù)，單位:架;

xik為決策變量，表示機型k飛機執(zhí)飛航段i(i∈I)的頻次，單位:次;

ypr為決策變量，表示同一市場上行程路線p(p∈P)溢出至行程路線r(r∈P)上的旅客數(shù)，單位:人次;

ak為在機隊規(guī)劃期內(nèi)機型k(k∈K)飛機的平均單位采購成本，單位:萬元;

bpr為行程路線p(p∈P)上的旅客溢出至行程路線r(r∈P)上的再捕獲率;

δpi為 0-1 變量，

cik為機型k飛機執(zhí)飛航段i發(fā)生的變動成本，單位:萬元/次;

fp為行程路線p上旅客的平均票價，單位:萬元;

Fi為航段i上航班的最大飛行次數(shù)，單位:次;

Ccapik為機型k飛機執(zhí)飛航段i的實際可用座位數(shù)，單位:個;lik為機型k飛機執(zhí)飛航段i的期望客座率;dp為行程路線p上的旅客數(shù)，為需求隨機變量，單位:人次;

tik為機型k飛機執(zhí)飛航段i的輪擋飛行時間，單位:h;

mk為機型k飛機的日期望利用率，單位:h.

2.2 數(shù)學(xué)模型

航空運輸市場的季節(jié)性特征使得旅客需求具有不確定性，該現(xiàn)象使得傳統(tǒng)確定性機隊規(guī)劃法所得出的機隊構(gòu)成無法很好地適應(yīng)市場需求的波動.例如，在需求旺季時，會由于公司運力不足而導(dǎo)致收益的大量流失;而在需求淡季時，又往往會由于運力過剩而導(dǎo)致不必要的成本支出.因此，本文將旅客行程路線上的旅客需求視為隨機變量，并構(gòu)建機隊的魯棒優(yōu)化模型.判斷機隊構(gòu)成優(yōu)劣需要一個統(tǒng)一的評估指標(biāo)，本文構(gòu)建的機隊規(guī)劃成本包括:

(1)機隊采購成本;

(2)機型航段運行變動成本;

(3)旅客需求溢出成本.

構(gòu)建的機隊魯棒優(yōu)化模型可以描述為

式(1)表示機隊規(guī)劃成本最小化目標(biāo)函數(shù);式(2)表示任一航段i上執(zhí)飛的航班頻次不能超過其所允許的最大航班數(shù)量;式(3)和(4)是旅客組合優(yōu)化模型約束，式(3)表示任一航段i上承載的旅客人數(shù)不小于實際經(jīng)過該航段的旅客人數(shù)，式(4)表示任一旅客行程路線p上的溢出人數(shù)不能超過該行程路線的需求量;式(5)表示第k種機型機隊的實際輪擋飛行小時數(shù)不超過機隊所能提供的最大輪擋飛行小時數(shù);式(6)為決策變量的類型與取值范圍.

需要說明的是，在行程路線p與r相同時，旅客溢出的再捕獲率是相同的，即 bpp=1，此時，式(1)中第3項的系數(shù)(fp－bppfp)為0.

由于式(1)以機隊規(guī)劃成本最小化為目標(biāo)函數(shù)，因此，決策變量ypp反映了實際承載行程路線p上的旅客數(shù)量.另外，針對旅客實際溢出問題，本文設(shè)計了虛擬旅客行程路線，用yp表示從行程路線p溢出后轉(zhuǎn)至虛擬旅客行程路線的旅客數(shù).

3 算法設(shè)計

旅客需求的不確定性使得魯棒優(yōu)化模型中旅客需求的轉(zhuǎn)移和再捕獲過程變得復(fù)雜化，因此，本文采用情景匯聚算法［7，15-17］進行求解.情景匯聚算法的基本思想可以描述為:首先，假設(shè)旅客需求服從正態(tài)分布，按照等間距劃分需求累積概率值的原則，將每個行程路線上的旅客需求概率分布范圍進行劃分并產(chǎn)生需求情景(scenario)集S;然后，構(gòu)造機隊規(guī)劃目標(biāo)函數(shù)的增廣拉格朗日函數(shù)，且對第s(s∈S)種情景求解其增廣拉格朗日函數(shù)值，并將機隊構(gòu)成決策變量值進行匯聚;最后得出期望機隊規(guī)劃成本最小的魯棒機隊構(gòu)成.算法步驟如下:

(1)產(chǎn)生需求情景集.根據(jù)行程路線p上的旅客需求分布函數(shù)，按照等間距劃分需求累積概率值的原則，利用式(7)進行等分并產(chǎn)生個需求，對這些需求進行隨機排列后形成行程路線層面上的需求情景集

式中:N為行程路線數(shù)目.

式中:F為需求累積分布函數(shù).

(2)構(gòu)造增廣拉格朗日函數(shù).設(shè)ˉzk表示待求解魯棒機隊構(gòu)成決策變量，為了保證機隊構(gòu)成在任意情景下的一致性，在機隊規(guī)劃模型(式(1)～(6))的基礎(chǔ)上，還必須滿足約束條件式(8).因此，構(gòu)造第s種情景下的增廣拉格朗日函數(shù)如式(9)所示.

式中:f(xik(s)，ypr(s)，zk(s))為情景s下機隊規(guī)劃成本的目標(biāo)函數(shù);

wk為拉格朗日乘子.

(3)計算需求再捕獲率.利用工業(yè)指標(biāo)量化市場份額指數(shù)(quantitative share index)［12］，計算情景s下旅客從行程路線p轉(zhuǎn)移至r(r∈P)的需求再捕獲率，如式(10)所示.

式中:qr(s)為情景s下行程路線r對旅客的吸引力.

(5)迭代求解情景匯聚模型.對于每一情景，求解以式(9)為目標(biāo)函數(shù)、式(1)～(6)和(8)為約束條件的數(shù)學(xué)規(guī)劃模型.判斷規(guī)劃結(jié)果是否滿足式(11)的終止條件，若是則停止，并按式(12)計算隨機情景下期望的機隊規(guī)劃成本G，并將其作為情景匯聚算法求解的目標(biāo)函數(shù)值;否則，按式(13)和(14)分別更新拉格朗日乘子w(t)k和變量 ˉz(t)k的值，重復(fù)步驟(5)，直至滿足式(11)為止.

式中:ε為預(yù)先設(shè)定的一個充分小的非負(fù)實數(shù).

考慮到旅客需求為符合正態(tài)分布的連續(xù)型隨機變量，因此，在求解步驟(5)中的數(shù)學(xué)規(guī)劃模型時，可以將變量ypr松弛為非負(fù)實數(shù).

4 算例

為了說明本文設(shè)計方法的有效性，采集圖2所示航線網(wǎng)絡(luò)結(jié)構(gòu)運營模式的某航空公司運營數(shù)據(jù)(見表1和表2)，利用ILOG/CPLEX軟件對6種候選機型、12個航段、57條旅客行程路線進行分析.根據(jù)算法的收斂性以及決策變量的類型，本文給定情景匯聚算法的收斂條件為ε=10－6.

圖2 非嚴(yán)格樞紐輪輻式航線網(wǎng)絡(luò)結(jié)構(gòu)運營模式Fig.2 Operation mode of nonstrict hub-and-spoke airline network structure

表1 航線網(wǎng)絡(luò)環(huán)境下機型運營信息Tab.1 Operation information of fleet types under airline network environment

表2 航線網(wǎng)絡(luò)環(huán)境下航段運營數(shù)據(jù)Tab.2 Leg-based operation data under airline network environment

圖2中所有輪輻機場的旅客只能通過樞紐機場H1和H2進行中轉(zhuǎn)，且輪輻機場之間沒有旅客中轉(zhuǎn)銜接功能.

從表3可見，與不考慮旅客網(wǎng)絡(luò)效應(yīng)問題的基于航段的機隊規(guī)劃方法(傳統(tǒng)機隊規(guī)劃模型)相比較，本文所設(shè)計的機隊規(guī)劃模型的機隊構(gòu)成為:機型2/1架，機型 3/76架;機型 4/1架，機型 6/12架.機隊規(guī)劃成本相應(yīng)減少了167.07萬元，而溢出人數(shù)、溢出率(指溢出人數(shù)與旅客需求總數(shù)的比值)以及溢出成本(指溢出人數(shù)與平均票價的乘積)卻分別增加了 1606.66人次、8.27% 和222.46 萬元.

另外，兩種方法所得出的飛機數(shù)目相差7架，這意味著傳統(tǒng)機隊規(guī)劃法中旅客溢出成本的減少是以增加飛機運行頻次(飛機數(shù))為代價的，而飛機數(shù)的增加意味著更多采購成本的支出，因此，合理的旅客需求溢出對于航空公司機隊規(guī)劃決策在一定程度上是有利的.該現(xiàn)象也充分說明了樞紐航線網(wǎng)絡(luò)運作模式下本文所設(shè)計機隊規(guī)劃方法的優(yōu)勢.

為了說明情景匯聚算法的有效性，將本文設(shè)計算法求解得出的期望解與確定解的隨機期望值進行比較.通過表4可以發(fā)現(xiàn)，在情景數(shù)目為20、40和60個時，隨機規(guī)劃期望解的各項指標(biāo)(機隊構(gòu)成、機隊規(guī)劃成本、旅客溢出數(shù)、旅客溢出率和旅客溢出成本)的偏差保持了一定的穩(wěn)定性，這說明情景數(shù)目的取值對于情景匯聚算法求解結(jié)果穩(wěn)定性的影響較小.另外，對比隨機規(guī)劃的期望解與確定解的隨機期望值，可以發(fā)現(xiàn)在情景數(shù)目為20、40和60個時，利用情景匯聚算法所得出的機隊規(guī)劃成本分別減少了19.88、21.02 與 17.55 萬元，這表明了在需求不確定性前提下，本文所設(shè)計算法的有效性.3種情景下的旅客溢出數(shù)、溢出率以及溢出成本的變化也充分說明了機隊在需求不確定性前提下，雖然提供更多運力會引起額外的固定成本支出，但可以有效的避免旅客溢出所帶來的成本損失，而當(dāng)這種旅客溢出損失大于機隊固定成本增加時，那么就應(yīng)該選擇更多運力的機隊決策方案.

綜上所述，本文在考慮需求不確定性前提下所設(shè)計的算法能夠有效地降低機隊規(guī)劃成本，因此，所得出的機隊構(gòu)成能夠更好的適應(yīng)市場需求的波動，具有更好的魯棒特點.

需要說明的是，隨機規(guī)劃模型的期望解是指相應(yīng)決策變量與目標(biāo)函數(shù)的解，以及在此基礎(chǔ)上所形成的相關(guān)指標(biāo)的解;確定解的隨機期望值是指以旅客需求均值為基礎(chǔ)求解得出的機隊規(guī)劃的確定解，并以此為基礎(chǔ)進一步求解得出的各種情景下最小機隊規(guī)劃成本的相關(guān)解的期望值.

表3 與傳統(tǒng)機隊規(guī)劃模型計算結(jié)果的相關(guān)指標(biāo)比較Tab.3 Comparison to the results from traditional fleet planning model on related indices

表4 隨機規(guī)劃的期望解與確定解的隨機期望值的比較Tab.4 Comparison between the expected solution to stochastic planning and the deterministic solution to stochastic expectation

5 結(jié)束語

本文利用需求運力優(yōu)化配置技術(shù)，結(jié)合各航段機型最大飛行頻次限制、最大旅客需求限制以及機隊最大飛行時間限制等因素，將旅客組合優(yōu)化方法應(yīng)用到機隊規(guī)劃問題之中，在考慮旅客溢出再捕獲情況的基礎(chǔ)上，構(gòu)建了基于航線網(wǎng)絡(luò)效應(yīng)下運力優(yōu)化配置的機隊魯棒優(yōu)化模型，并在旅客需求不確定性的基礎(chǔ)上，利用情景匯聚算法求解機隊的魯棒性優(yōu)化數(shù)學(xué)模型.案例分析表明，基于航線網(wǎng)絡(luò)效應(yīng)的機隊規(guī)劃方法能夠有效降低機隊規(guī)劃成本;利用情景匯聚算法求解得出的機隊隨機規(guī)劃期望成本值比確定解下的機隊規(guī)劃成本最小期望值更低.因此，本文設(shè)計的機隊規(guī)劃方法所得出的機隊構(gòu)成能夠更好的適應(yīng)市場需求的波動，且是有效可行的.考慮航空公司備份運力以及因維修計劃所需周轉(zhuǎn)運力的需要，公司實際運營所需的飛機數(shù)應(yīng)多于本文計算結(jié)果.

［1］彭語冰，張永莉，張曉全.機隊規(guī)劃模型的建立及其應(yīng)用［J］.系統(tǒng)工程:理論與實踐，2001，21(6):100-103.PENG Yubing，ZHANG Yongli，ZHANG Xiaoquan.Fleetplanning modeling and its applications［J］.Systems Engineering:Theoryand Practice， 2001，21(6):100-103.

［2］朱金福.航空運輸規(guī)劃［M］.西安:西北工業(yè)大學(xué)出版社，2008:238-240.

［3］汪瑜，孫宏.基于航班機型分配技術(shù)的機隊規(guī)劃啟發(fā)式算法［J］.系統(tǒng)工程:理論與實踐，2011，31(2):371-378.WANG Yu，SUN Hong.Heurist algorithm of fleet planning based on airline fleet assignment［J］.Systems Engineering:Theory and Practice，2011，31(2):371-378.

［4］汪瑜，孫宏.航空公司機隊的魯棒性規(guī)劃啟發(fā)式算法［J］.系統(tǒng)工程:理論與實踐，2013，33(4):963-970.WANG Yu， SUN Hong. Heuristic algorithm to incorporating robustness into airline fleet planning［J］.Systems Engineering:Theory and Practice， 2013，33(4):963-970.

［5］孫宏，張培文，汪瑜.基于航線網(wǎng)絡(luò)運力優(yōu)化分配的機隊規(guī)劃方法［J］.西南交通大學(xué)學(xué)報，2010，45(1):111-115.SUNHong， ZHANG Peiwen， WANG Yu. Fleet planning approach based on route fleet assignment optimizing［J］. Journal of Southwest Jiaotong University，2010，45(1):111-115.

［6］段曉江，馮允成.啟發(fā)式民用飛機機隊規(guī)劃［J］.北京航空航天大學(xué)學(xué)報，1996，22(4):504-508.DUAN Xiaojiang，F(xiàn)ENG Yuncheng.Efficient heuristic algorithm to airline fleet planning［J］. Beijing University of Aeronautics and Astronautics， 1996，22(4):504-508.

［7］LISTES O，DEKKER R.A scenario aggregation-based approach for determining a robust airline fleet composition for dynamic capacity allocation［J］.Transportation Science，2005，39(3):367-382.

［8］BROWN J H. Airline fleet composition and deregulation［J］. Review of Industrial Organization，1992，8(4):435-449.

［9］TSAI W H，LEE K C，LIU J Y，et al.A mixed activity-based costing decision model for green airline fleet planning under the constraints of the European Union Emissions Trading Scheme［J］.Energy，2012，39(1):218-226.

［10］ZHURBENKO N G，PINAEY E G，SHOR N Z，et al.Choice of fleet composition and allocation of aircraft to civilairline routes［J］. Cybernetics and Systems Analysis，1976，12(4):636-640.

［11］都業(yè)富.機隊規(guī)劃的優(yōu)化［J］.系統(tǒng)工程:理論與實踐，1997，23(7):136-138.DU Yefu.Optimization of fleet planning［J］.Systems Engineering:Theory and Practice，1997，23(7):136-138.

［12］BARNHART C，KNIKER T S，MANOJ L.Itinerary-based airline fleet assignment［J］. Transportation Science，2002，36(2):199-217.

［13］JACOBS TL， SMITH BC， JOHNSON EL.Incorporating network flow effects into the airline fleet assignment process［J］.Transportation Science，2008，42(4):514-529.

［14］柏明國，朱金福.全連通航線網(wǎng)絡(luò)和樞紐航線網(wǎng)絡(luò)的比較研究［J］.系統(tǒng)工程:理論與實踐，2006，26(9):113-117.BAI Mingguo，ZHU Jinfu.Comparative study on fully-connected and hub-and-spoke airline networks［J］.Systems Engineering:Theory and Practice，2006，26(9):113-117.

［15］ROCKAFELLAR R T，WETS R J B.Scenarios and policy aggregation in optimization under uncertainty［J］. Mathematics Operation Research，1991，16(1):119-147.

［16］CAROE C C，SCHULTZ R.Dual decomposition in stochastic integer programming［J］. Operation Research Letters，1999，24(2):37-45.

［17］WATSON J P，WOODRUFF D L.Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems［J］. Computer Management Science，2011，8:355-370.