需求不確定狀態(tài)下的航班機(jī)型分配問題研究

張興香，朱星輝

（南京航空航天大學(xué)民航學(xué)院，江蘇 南京211106）

有關(guān)機(jī)型分配的研究方法經(jīng)歷了一個從簡單到復(fù)雜，從理想化模型到實用性研究的演變過程。最早的機(jī)型分配研究可以追溯到Abara［1］和Berge等［2］，其研究是建立在市場需求確定的假設(shè)基礎(chǔ)上，建立確定型機(jī)型分配模型進(jìn)行研究。然而在實際運營過程中，市場需求并不確定，這給航空公司制定航班計劃帶來了巨大挑戰(zhàn)。2009年，考慮到市場需求預(yù)測的準(zhǔn)確性隨著離港日期的迫近有所提高，Jiang和Barnhart［3］根據(jù)航班客票銷售情況動態(tài)預(yù)測市場需求，將重新調(diào)整航班時刻作為一種新的動態(tài)調(diào)整機(jī)制，建立了一個綜合航班時刻再調(diào)整和機(jī)型再分配的優(yōu)化模型。2010年，Sherali等［4］構(gòu)建了一個考慮航班計劃制定的機(jī)型分配模型，并對大規(guī)模規(guī)劃模型進(jìn)行了詳細(xì)的Polyhedral 分析和Benders 分解。由于燃油成本在航空公司整個運營成本中占據(jù)較大比重，2012年，Naumann［5］在燃油價格和市場需求均不確定的情況下，設(shè)計了一個兩階段隨機(jī)規(guī)劃的機(jī)型再分配模型。Pilla等［6］在Boeing公司提出的需求驅(qū)動分配理念的基礎(chǔ)上，將航班機(jī)型分配劃分為考慮機(jī)組——飛機(jī)分配兼容性的航班機(jī)型分配與提高旅客需求捕獲水平而進(jìn)行機(jī)型交換的兩個階段，并以此構(gòu)建航班機(jī)型分配的兩階段隨機(jī)規(guī)劃模型。針對兩階段隨機(jī)規(guī)劃問題，鑒于傳統(tǒng)的L-型算法收斂速度緩慢，Pilla提出應(yīng)用自適應(yīng)多切割聚合算法對模型進(jìn)行求解。2013年，Jiang等［7］在其2009年研究的基礎(chǔ)上作了進(jìn)一步研究，提出一個針對非航班波式運行的樞紐機(jī)場的魯棒性航班計劃模型。Cadarso［8］在Jiang［7］模型的基礎(chǔ)上，考慮旅客再捕獲效應(yīng)并作了進(jìn)一步研究。Sherali等［9］在機(jī)型分配問題中，考慮航班計劃中的其他環(huán)節(jié)，如柔性的航班時刻、需求再捕獲效應(yīng)、航節(jié)的選擇以及多種票價等問題，并采用分離技術(shù)對模型進(jìn)行預(yù)處理。此外，Sherali 等［10］人在航班計劃綜合模型中進(jìn)一步考慮飛機(jī)維修路徑問題和經(jīng)停航班問題，并利用有效不等式的引入提高了模型的可解性。

綜合分析上述研究成果，航空公司制定機(jī)型分配計劃是一項規(guī)模巨大且復(fù)雜的系統(tǒng)工程，是NP-Hard問題，針對制定機(jī)型分配計劃期間市場需求處于高度不確定的特性，構(gòu)造了一個兩階段隨機(jī)混合整數(shù)規(guī)劃模型，其中第一階段是機(jī)族分配階段（一種機(jī)族可能包括若干種飛行機(jī)組可以互換的機(jī)型），即確定每個航節(jié)所分配到的機(jī)族；第二階段是機(jī)型分配階段，主要考慮根據(jù)不同的需求情景在第一階段指定的機(jī)族內(nèi)選擇具體的機(jī)型分配給相應(yīng)航節(jié)。

1 模型建立

機(jī)型分配問題的建模基礎(chǔ)通常有連接網(wǎng)絡(luò)［1］和時空網(wǎng)絡(luò)［2］，選擇時空網(wǎng)絡(luò)為基礎(chǔ)對機(jī)型分配問題進(jìn)行研究，其節(jié)點表示航班到達(dá)或離崗，弧（邊）包括航班弧、地面弧和過夜弧。

1.1 模型符號說明

在構(gòu)建模型之前，首先對模型涉及的參數(shù)及變量予以說明：

集合。K：整個機(jī)隊中所有機(jī)族的集合，k∈K。T：整個機(jī)隊中所有機(jī)型的集合，t∈T。Tk：屬于機(jī)族k的機(jī)型集合，有Tk?T。Nt：機(jī)型t的航班網(wǎng)絡(luò)中節(jié)點的集合，n∈Nt。Gt：機(jī)型t的航班網(wǎng)絡(luò)中地面弧的集合，g∈Gt。L：所有航節(jié)的集合，l∈L。Lk：分配給機(jī)族k的航節(jié)集合，有Lk?L。∏：所有旅客行程的集合，i∈∏。∏(l)：所有包含航節(jié)l的旅客行程集合，有∏(l)?∏。Ot：表示機(jī)型t通過時間線的弧線集合，包括航班弧和地面弧，理論上時間線可以任意選擇，因為任何時刻都需要保持飛機(jī)流平衡，為方便計算，通常選擇空中飛機(jī)最少的時候作為時間線。S：市場需求情景集合，s∈S。

變量。z：第一階段決策變量向量。zlk：第一階段決策變量，當(dāng)航節(jié)l由機(jī)族k執(zhí)飛時，等于1，否則為0，有zlk?z。xs：表示在需求情景s下，第二階段決策變量向量。xslt：第二階段決策變量，在需求情景s下，當(dāng)航節(jié)l由機(jī)型t執(zhí)飛時，等于1，否則為0，有?xs。：表示在市場需求情景s下，機(jī)型t有地面弧g。：表示在市場需求情景s下，機(jī)型t的不可用性因子。qis：表示在市場需求情景s下，旅客行程i上可接受的需求變量。

參數(shù)及其它標(biāo)識。μs：表示在市場需求情景s下，所有旅客行程的需求向量。μsi：表示在市場需求情景s下，旅客行程i上的需求，有μis?μs。clt：表示用機(jī)型t執(zhí)飛航節(jié)l的成本。capt：表示機(jī)型t的座位數(shù)。fis：表示在市場需求情景s下，旅客行程i的平均票價。ps：表示市場需求情景s發(fā)生的概率值，有Bt：表示機(jī)型t中可用的飛機(jī)數(shù)量。ψt：表示機(jī)型t在不可用時的懲罰成本。v：第一階段的目標(biāo)函數(shù)值，即整個模型的目標(biāo)函數(shù)值。Hs(z,μs)：第二階段在需求情景s下的目標(biāo)函數(shù)值。bfln=±1，表示航節(jié)l開始或者結(jié)束于機(jī)型t的航班網(wǎng)絡(luò)節(jié)點n，l∈L，n∈Nt。bggn=±1，表示地面弧g開始或者結(jié)束于機(jī)型t的航班網(wǎng)絡(luò)節(jié)點n，g∈Gt，n∈Nt。

綜合應(yīng)用衛(wèi)星遙感等手段，準(zhǔn)確研判凌情變化，科學(xué)調(diào)度干流水庫，有效控制寧蒙河段及北干流河段凌情平穩(wěn)發(fā)展，實現(xiàn)了下游不封河，確保了黃河防凌安全。

1.2 建立模型

根據(jù)上述參數(shù)及變量，建立機(jī)型分配兩階段隨機(jī)混合整數(shù)規(guī)劃模型，簡稱“兩階段模型”，第一階段（P1）是機(jī)族分配問題，第二階段（P2）根據(jù)不同的需求情景，同一機(jī)族內(nèi)的機(jī)型分配問題。兩階段模型如下：

對于每個需求情景s∈S，有：

式（1）為期望總利潤最大化目標(biāo)函數(shù)；式（2）為第一階段覆蓋約束，要求每個航節(jié)分配1種且只有1種機(jī)族；式（3）為第一階段變量取值范圍約束；式（4）為第二階段目標(biāo)函數(shù)，要求在需求情景s下，期望利潤最大化；式（5）為第二階段覆蓋約束，要求每個航節(jié)從自身所分配到的機(jī)族里分配1種且只有1種機(jī)型；式（6）為航班網(wǎng)絡(luò)流守恒約束；式（7）為每種機(jī)型的飛機(jī)使用數(shù)量不能超過該機(jī)型的可用飛機(jī)總數(shù)；式（8）為座位數(shù)約束；式（9）為需求約束；式（10）為第二階段變量取值范圍約束。

如果將市場需求看成是確定性的，（P1）和（P2）可以合并成一個傳統(tǒng)的確定型模型。

2 算法分析

針對大規(guī)模的隨機(jī)規(guī)劃問題，多使用啟發(fā)式算法和智能算法求解。Benders提出求解混合線性和非線性整數(shù)規(guī)劃問題的分解算法。此算法的優(yōu)點在于不但可以求得最優(yōu)解或漸近最優(yōu)解，而且可以由計算的上界和估計的下界評價所求解的質(zhì)量。根據(jù)兩階段模型特點，采用Benders算法求解兩階段模型。Benders分解算法的基本思想是：將原問題剖分成相對簡單的主問題和容易求解的子問題，通過不斷迭代，用子問題的對偶信息構(gòu)造Benders切，作為新的約束條件加入到主問題中，繼續(xù)迭代，直到獲得原問題的最優(yōu)解或滿意解。

為了簡化計算，將上述模型中的二進(jìn)制變量xs松弛為連續(xù)變量（z變量保持不變）。設(shè)和分別表示模型（P2）中式（5）～（9）對應(yīng)的對偶變量，則由（P2）的對偶問題可以得到一個Benders切平面如下：

求解算法步驟：

步驟1初始化參數(shù)。設(shè)原問題的上、下限分別為：ub=0，lb=-∞；上、下限的相對誤差值為ε；迭代計數(shù)變量m=0，最大迭代次數(shù)為cut。

步驟2滿足下面條件之一終止迭代。(ub-lb )/ub≤ε，或者m=cut；否則，繼續(xù)下面的步驟。

步驟3解主問題（P3），將求出的目標(biāo)函數(shù)值作為新的下限，用解z更新子問題及其對偶問題中的相應(yīng)值；對于隨機(jī)需求的每一個情景，解子問題及其對偶問題。

步驟4由式（11），產(chǎn)生一個新的Benders切平面，并把它加入到主問題（P3）中。

步驟5如求出（P1）的現(xiàn)行目標(biāo)函數(shù)值νinc＜ub，按ub=νinc修正上限，然后重新執(zhí)行步驟2。

在利用Benders分解算法求解過程中，為了加快求解速度，針對式（7）可用性約束設(shè)計增加一個聚合可用性割，如式（16）所示。

式中，O′t表示機(jī)型t在一天中繁忙時刻（如15：00）的弧線集合，選擇繁忙時刻意味著航班弧遠(yuǎn)遠(yuǎn)多于地面弧，此時地面弧可忽略不計。聚合可用性割（16）的加入能夠在較短的時間內(nèi)獲得更高質(zhì)量的z解，減少求解過程的總耗時。

3 實例分析

設(shè)某航空公司的機(jī)隊分兩種機(jī)族k1、k2，其中機(jī)族k1包含機(jī)型t1、t2，機(jī)族k2包含機(jī)型t3、t4，而這四種機(jī)型的艙位容量分別為121 座，136 座，141 座和124 座，飛機(jī)架數(shù)均為4 架，且假設(shè)所有飛機(jī)都是可用的，因此ψt=∞，Pts=0。取Π=L={l1,l2,l3,l4}，即每條旅客行程只包括一個航節(jié)。S={s1,s2}，即包含兩種需求情景，且每種需求情景出現(xiàn)的概率分別為Ps1=0.6，Ps2=0.4，機(jī)型成本、票價和市場需求如表1所示。表1中最后兩列為兩種情景的平均票價和市場需求。

表1 模型中用到的參數(shù)值Tab.1 Parameters’values in the model

將以上數(shù)據(jù)代入兩階段模型，用平均值代入確定型模型，通過MATLAB 7.0編程求解，所得分配結(jié)果如表2所示。

表2 確定型需求和不確定型需求的分配結(jié)果Tab.2 Assignment results under certain and uncertain demands

由表2中的分配結(jié)果可以看出，兩階段模型用到了兩種機(jī)族k1和k2，且在兩種需求情景下的機(jī)型分配方案大有不同，而確定型模型中只用了一種機(jī)族k1，方案欠缺靈活性。此外，由兩階段模型和確定型模型計算得出的目標(biāo)函數(shù)值分別是-290 636和-274 160，通過比較可以得出兩階段模型比確定型模型的利潤多16476。從以上得出的機(jī)型分配方案和目標(biāo)函數(shù)值均可看出本文建立的兩階段模型比確定型模型較優(yōu)。

4 結(jié)論

針對機(jī)型分配模型研究，傳統(tǒng)的確定型模型并不符合市場需求高度不確定的實際情況，因此，它只能作為理論研究，缺乏實際可操作性。

1）建立了一個兩階段隨機(jī)混合整數(shù)規(guī)劃模型，不僅反映了機(jī)型分配階段需求不確定的實際情況，且第一階段的機(jī)族分配結(jié)果足以為機(jī)組排班提供決策支持，而第二階段不同需求情景下的機(jī)型分配結(jié)果也為后期的機(jī)型再分配階段提供參考。

2）由于兩階段模型的復(fù)雜性，本文中設(shè)計了收斂速度較快的Benders分解算法。

3）為了對兩種模型的優(yōu)劣有一個清晰而直觀的認(rèn)識，在最后設(shè)計了一個小規(guī)模算例，證明兩階段模型較確定型模型更具靈活性和有效性。在航空公司的實際運營中，由于機(jī)型種類和飛機(jī)數(shù)量繁多，制約機(jī)型分配方案的條件也非常多，因此，有關(guān)機(jī)型分配方面的研究還有待進(jìn)一步的深入和提高。

[1]ABARA J.Applying integer linear programming to the fleet assignment problem[J].Interfaces,1989,19(4)20-28.

[2]BERGE M E,HOPPERSTAD C A.Demand driven dispatch:A method for dynamic aircraft capacity assignment,models and algorithms[J].Opertional Research,1993,41(8):153-168.

[3]JIANG H,BARNHART C.Dynamic Airline Scheduling[J].Transportation Science,2009,43(3):336-354.

[4]SHERALI H D, KI-HWAN BAE, MOHAMED HAOUARI.Integrated airline schedule design and fleet assignment: polyhedral analysis and benders′decomposition aApproach[J].Informs Journal on Computing,2010,22(4):500-513.

[5]NAUMANN M, SUHL L, FRIEDEMANN M.A stochastic programming model for integrated planning of refleeting and financial hedging under fuel price and demand uncertainty[J].P rocedia Social and Behavioral Sciences,2012,54:47-55.

[6]PILLA V L,ROSENBERGER J M,VICTORIA CHEN,et al.A multivariate adaptive regression splines cutting plane approach for solving a two-stage stochastic programming fleet assignment model[J].European Journal of Operational Research, 2012,216:162-171.

[7]JIANG H, BARNHART C.Robust airline schedule design in a dynamic scheduling environment[J].Computers and Operations Research,2013,40(3):831-840.

[8]CADARSO L, MARíN A.Robust passenger oriented timetable and fleet assignment integration in airline planning[J].Journal of Air Transport Management,2013,26:44-49.

[9]SHERALI H D,KI-HWAN BAE,MOHAMED HAOUARI.A benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture[J].Annals of Operations Research,2013,210(1):213-244.

[10]SHERALI H D, KI-HWAN BAE, MOHAMED HAOUARI.An integrated approach for airline flight selection and timing, fleet assignment,and aircraft routing[J].Transportation Science,2013,47(4):455-476.