不確定需求下的兩階段機型指派模型

張春曉，石曉磊，臧其銀

（1.中國民航大學a.天津市民用航空器適航與維修重點實驗室；b.理學院，天津 300300；2.山東航空股份有限公司太原營業(yè)部，太原 030001）

不確定需求下的兩階段機型指派模型

張春曉1a，石曉磊1b，臧其銀2

（1.中國民航大學a.天津市民用航空器適航與維修重點實驗室；b.理學院，天津 300300；2.山東航空股份有限公司太原營業(yè)部，太原 030001）

針對航空公司新開辟航線的機型指派問題，由于缺乏歷史運營數(shù)據(jù)，無法得到乘客需求的概率分布，因此將需求描述為不確定變量。建立帶有機會約束的兩階段機型指派0-1整數(shù)規(guī)劃模型，第1階段為機族指派，第2階段對指定機族所屬機型進行指派。給定新航線需求的不確定分布，將不確定整數(shù)規(guī)劃模型轉換成確定性模型，通過一個改進的分枝定界算法進行求解。算例采用某航空公司樞紐機場6條新航線共20個航班的數(shù)據(jù)進行分析，結果驗證了模型的可行性和算法的有效性。

機型指派；新航線需求；不確定理論；兩階段；0-1整數(shù)規(guī)劃；分枝定界算法

機型指派問題是指航空公司對于已確定的航線和相應的航班時刻表，考慮不同機型飛機艙位數(shù)、運營成本及潛在收益等因素，在滿足各種運營約束條件的情況下，為每一個航班指派合適的飛機機型，最終達到收益最大化或成本最小化的過程[1]。機型指派作為航空公司航班生產(chǎn)運作過程中的核心環(huán)節(jié)，是航空公司有效控制運營成本、進行精益管理的關鍵。針對航空公司新開辟航線旅客需求的不確定性，考慮不同機族、機型飛機的技術特點，新航線機型指派問題對提升航空公司經(jīng)濟效益具有重要的現(xiàn)實意義。

關于機型指派的研究，較早的可回溯到Abara等人的研究成果。Abara[2]在1989年建立了基于航班弧網(wǎng)絡結構的確定性機型指派模型。朱星輝等[3]基于航線需求研究了中國航空公司機型指派的模型及算法。劉昕等[4]以航空公司成本最小化為目標，兼顧顧客滿意度和飛機使用數(shù)目，建立了帶有時間窗的多目標規(guī)劃飛機排班確定性模型。事實上，在樞紐航線網(wǎng)絡結構中，乘客會在樞紐機場進行轉機，需求有較高的不確定性。故Listes等[5]建立了一個兩階段SP模型，將實際背景與動態(tài)規(guī)劃相結合，詳細描述了基于隨機需求的機型指派問題。

由于不同機族通常有著不同的機組需求，且機組成員通常也只能勝任執(zhí)飛同一類機族的航班，因此產(chǎn)生了兩階段機型指派問題；即航空公司在指派某航班的飛機機型時，考慮不同機族、機型的運營成本，機組人員的配對以及不同航線需求量的差異等因素，將機型指派決策分為兩個階段，第1階段進行機族層次的指派，第2階段基于第1階段選擇的機族進行機型指派。Sherali等[6]在2008年基于隨機需求提出了兩階段機型指派模型，數(shù)值試驗結果表明基于隨機需求預測的兩階段機型指派模型比傳統(tǒng)的確定性模型更加有效。

然而，對于航空公司新開辟航線的機型指派問題，由于沒有歷史運營數(shù)據(jù)，新航線需求的概率分布函數(shù)無法確定，使得Sherali等的隨機模型和算法不再適用。在此情況下，只能依據(jù)業(yè)內專家憑經(jīng)驗和知識提供的新航線需求信度來估計經(jīng)驗分布函數(shù)。由于人們經(jīng)常高估不太可能發(fā)生的事件，使得專家的主觀信度通常比真實頻率有更大的方差[7]。此時，如果把主觀信度看成概率，則推導出的結果與預期大相徑庭。為解決這一問題，Liu[8]在2007年建立了不確定理論。2010年，Liu[9]修訂了不確定理論，使其成為一個基于規(guī)范性公理、對偶性公理、次可加公理和乘積公理的數(shù)學系統(tǒng)。如今，不確定理論已成為研究主觀信度的數(shù)學分支，被廣泛應用到數(shù)學規(guī)劃等領域[9]。因此，本文將新航線需求描述為不確定變量，基于不確定規(guī)劃方法來研究新開辟航線的兩階段機型指派問題。

1 預備知識

本節(jié)介紹文中將用到的不確定理論知識[7]。

令Γ是一個非空集合，Γ的一個子集族L被稱為σ-代數(shù)。如果：①?！蔐；②若Λ∈L，則Λc∈L；③若Λ1，Λ2，…∈L，則Λ1∪Λ2∪…∈L。σ-代數(shù)L中每個元素Λ稱為事件。不確定測度是從L到[0，1]的函數(shù)。為了給出不確定測度的公理化定義，有必要給每個事件Λ確定一個測度Μ{Λ}，這個測度Μ{Λ}表明事件Λ可能發(fā)生的信度。為了確保測度Μ{Λ}有某些數(shù)學性質，Liu[7]提出如下3條公理：

公理1（正則性）對于全集Γ，有Μ{Γ}=1

公理2（對偶性）對于任何事件Λ，都有Μ{Λ}+ Μ{Λc}=1

公理3（次可加性）對于任意可數(shù)事件序列Λ1，Λ2，…，Λn，有

定義1 如果函數(shù)集Μ滿足正則性、對偶性及次可加性，則稱函數(shù)集Μ為不確定測度。

定義2 對于任意實數(shù)x，不確定變量ξ的不確定分布定義為

定義3 一個不確定變量ξ被稱為是線性的，如果它有一個線性不確定分布

記為L（a，b），a、b為實數(shù)，且a＜b。

定義4 不確定分布Φ被稱為是正則的，如果對每一個α∈（0，1），其逆函數(shù)Φ-1（α）存在且唯一。

定義5 令ξ是一個不確定變量且具有正則不確定分布。則逆函數(shù)Φ-1稱為ξ的不確定逆分布。

例：線性不確定分布L（a，b）的逆分布為

不確定規(guī)劃是涉及不確定變量的一種數(shù)學規(guī)劃。假設x是決策變量，ξ是不確定變量，f（x，ξ）為不確定目標函數(shù)。假設有p個約束，記為

給定置信水平α1，α2，…αp，則有機會約束集

2 假設和符號

2.1 假設

1）新開辟航線航班為直達航班；

2）航班運營以一天24 h為一個周期；

3）航空公司機隊含有多種機族，每種機族含有多個不同艙位數(shù)的機型；

4）只考慮航班運營成本，包括飛機燃料成本、維護成本和管理成本。將航班運營成本分攤折算成座公里運營成本（CASK）[10]；

5）新開辟航線需求為不確定變量，服從不確定分布Φ；

6）對于航班串，兩個時間上相鄰的銜接航班使用的是同一種機型；

7）有效的航班串必須滿足到達時間與地面最低過站時間之和不得超過相鄰航班的出發(fā)時間；

8）基于時空網(wǎng)絡[11]，考慮新開辟航線的機型指派問題，如圖1所示。

圖1 時空網(wǎng)絡示意圖Fig.1 Two-station time-space flight network

時空網(wǎng)絡圖由一系列節(jié)點和弧線組成。對于多種機型的時空網(wǎng)絡，由于不同機型有不同屬性，故每種機型對應1個子網(wǎng)絡層。時空網(wǎng)絡圖就是一系列子網(wǎng)絡層的疊加。以圖1兩種機型、兩個航站的時空網(wǎng)絡示意圖加以說明，節(jié)點是由航站軸和時間軸所確定的二維時空點，表示航班的到港、離港事件；如圖1中黑點?；“ǎ孩俸桨嗷。瑘D1中以傾斜箭頭線表示，如A1表示機型1在10：00AM到達航站A，E2表示機型2在10：00AM離開航站B；②地面弧，圖1中以豎直箭頭線表示飛機在該時間段內停留在該航站；③環(huán)繞弧，圖1中以曲線箭頭連接的、一個航班周期內一個航站的最后一個航班起飛或到達事件節(jié)點至該航站的最早事件節(jié)點。

A1和A2指向的節(jié)點是同一航班不同機型的到達節(jié)點，由于不同機型過站時間不同，所以這兩個節(jié)點的到達時間坐標也稍有不同。如果航班弧C1和B1形成連接，則表示由機型1執(zhí)行航班C1，到達航站A后，停留了一段時間（必須滿足最小過站時間要求），再執(zhí)行航班B1。

2.2 符號

K：機族k的集合，即k∈K；

Tk：機族k的機型tk集合，即tk∈Tk；

Lk：指派了機族k的航班l(xiāng)k的集合，即lk∈Lk；

L：所有航班l(xiāng)的集合，即l∈L；包含航班出發(fā)時間Td（l）、到達時間Ta（l）、出發(fā)站點Sd（l）、到達站點Sa（l）；

Q（·）：選取某執(zhí)飛方案所產(chǎn)生的總運營成本；

cltk：機族k的機型t執(zhí)飛航班l(xiāng)的成本；

CASKtk：機族k的機型t的座公里成本；

hl：航班l(xiāng)的飛行距離；

Captk：機族k的機型t擁有的座位數(shù)；

GT：完成一次地面過站作業(yè)所需最低時間標準；

S：時空網(wǎng)絡中航站s的集合，即s∈S；

n：時空網(wǎng)絡節(jié)點；

N（s）：航站s的時空節(jié)點集合N（s）={1，2，…，ns}，其中ns為航站s的最后一個節(jié)點，如果兩個節(jié)點時刻相同，則到港節(jié)點優(yōu)先排列在離港節(jié)點之前。

Atk：機族k的機型t能夠使用的飛機數(shù)量；

dl：表示航班l(xiāng)的旅客需求量，為不確定變量；

α：表示新航線需求小于指派機型飛機座位數(shù)的不確定測度的控制水平。

3 模型

本文同時考慮機族與執(zhí)飛機組、機型艙位和不確定需求的匹配性，因此將新航線機型指派問題分為兩階段。第1階段為機族指派，目的是尋求航空公司運營成本最小的機族決策方案。第2階段在第1階段機族指派之上，以航線運營成本最小為目標進行機型層次的指派。

設第1階段決策變量為

則機族指派模型為

其中，式（6）表示每一航班l(xiāng)都必須由某個機族k執(zhí)飛。

設第2階段決策變量為

則機型指派模型為

其中：式（7）表示選擇機族k的機型執(zhí)飛所有航班產(chǎn)生的最小總成本；式（8）表示機型覆蓋約束，即確保每個航班都必須被一個第1階段確定的機族里的機型覆蓋；式（9）表示飛機平衡流約束，即保證在任一航站的任何節(jié)點上事件發(fā)生后，機族k的機型t的地面飛機數(shù)量等于前一節(jié)點該機型的飛機數(shù)量加上到港飛機數(shù)量減去離港飛機數(shù)量，假定第1個節(jié)點的前一節(jié)點是ns；式（10）表示一個周期中第1個節(jié)點事件發(fā)生后，機族k的機型t的地面飛機數(shù)量等于上一周期最后一個節(jié)點該機型的飛機數(shù)量，加上到港飛機數(shù)量減去離港飛機數(shù)量；式（11）表示任一航站的任何節(jié)點上事件發(fā)生后機族k的機型t的地面飛機數(shù)量是非負的；式（12）表示機隊規(guī)模約束，即以各航站最后一個節(jié)點為基準，保證各航站機族k的機型t過夜飛機的總數(shù)量不得超過該機型的可用數(shù)量；式（13）為新航線需求的機會約束，表示新航線需求小于指派機型容量的不確定測度通過一個設定的置信度α來控制。

第2階段的機型指派模型帶有新航線不確定需求的機會約束，為便于求解，需將機會約束式（13）等價轉化為確定性約束。假定新航線需求服從正則的不確定分布Φ，利用不確定逆分布的定義（見定義5）可將式（13）改寫為

至此，新開辟航線的兩階段機型指派模型成為確定的純0-1整數(shù)規(guī)劃模型。

4 算法

分支定界法是用于求解純整數(shù)或混合整數(shù)規(guī)劃問題的重要方法[12-15]。本文將時間窗理念融入傳統(tǒng)的分支定界法，設計了適合于新航線兩階段機型指派模型求解的算法。算法的主要改進是基于時空網(wǎng)絡進行航班編碼，以航班串的形式進行不同機族的機型指派。算法考慮了實際的航班計劃在時間窗上的排序，并實現(xiàn)了航班平衡流約束，從而保證了指派方案的合理性。具體算法描述如下：

Step 0 首先將需要機型指派的航班按出發(fā)時間順序編號為L={l|1，2，…，m}，其中m為總航班數(shù)；第k個機族的機型按照自然順序編號為Tk={tk|1，2，…，jk}，其中k=1，2，…，K，K為機族數(shù)，j為第k個機族的可指派機型種類；則決策方案表示為x={xltk|l=1，2，…，m，tk=1，2，…，jk}。

將機型指派問題定義為P（N0，N1），其中N0={xltk｜

Step 1 采集實際航班數(shù)據(jù)，對指派模型中的參數(shù)賦值，令k=0，l=0；初始化最小成本為+∞，即Qk*=+∞；

Step 2 若k=K，轉Step 7，否則k=k+1；

Step 3 若l=m，轉Step 6，否則l=l+1；將決策變量xltk作為節(jié)點進行分支，且每個節(jié)點分為兩支，即0兩支。依序將xltk分支直到tk取遍所有機型，即tk=jk；

Step 4 檢驗Q（k，l，tk）≤Qk*是否成立。若不成立轉Step 3；若成立，令Qk*=Q（k，l，tk），則轉Step 5；

Step 5 將對應于Qk*的決策方案xk逐一驗證是否滿足時間、流量及需求約束（分別見式（9）～式（10）、式（12）～式（14）），若有約束條件不滿足，則停止驗證后面的約束條件，并轉Step 3；若所有約束條件均滿足，則轉Step 6；

Step 6 目標函數(shù)最優(yōu)值為Qk*，最優(yōu)解為xk*（Qk*），即為第k個機族的機型最優(yōu)執(zhí)飛方案；

Step 7 將所有機族的最優(yōu)值Qk*（k=1，2，…，K）進行比較，取最小值作為整個兩階段機型指派的最優(yōu)值Q*，即：Q*=min{Qk*|k=1，2，…，K}。

5 算例

假設某航空公司樞紐機場新開辟航線6條，共20個航班，航班信息如表1所示。世界上最大的兩家民用飛機制造商是波音與空客，選取這兩大機族各3個機型作為新航線的指派機型，各機型的座公里成本（CASK）、可用飛機數(shù)及座位數(shù)如表2所示。

假定6條新航線的需求皆服從不確定線性分布，其分布函數(shù)形式見定義3，逆分布函數(shù)形式見式（2），則式（14）可表示為

表1 部分航班信息統(tǒng)計表Tab.1 Partial statistics of flight information

表2 機型信息表Tab.2 Information of aircraft types

若給出新航線需求的上界a和下界b，等價的確定性約束式（15）在給定的置信度α下就可以實現(xiàn)。a、b值可通過定性或定量預測方法估計，如比德爾菲法、專家打分法和最小二乘法等。

基于改進的分枝定界算法編寫Matlab程序，求解不確定需求的兩階段機型指派模型（見式（7）～式（13）），輸出結果如表3所示。

表3表明了該航空公司6條新航線20個航班兩個機族的最優(yōu)機型指派方案。如將波音機族的B737機型或空客機族的A320機型指派給101航班。假定GT=40 min，基于表3所示的最優(yōu)機型指派方案，得到兩機族有效航班串如下：

1）波音機族

B737型飛機執(zhí)行8個航班，有效航班串分別為119-120-101-102，103-104-111-112；

B747型飛機執(zhí)行4個航班，有效航班串為117-118-107-108；

B767型飛機執(zhí)行8個航班，有效航班串分別為105-106-113-114，109-110-115-116。

波音機族的航班串結果表明，只需調用5架波音機族飛機執(zhí)飛。其中2架B737，1架B747，2架B767，最終的運營成本為2 662 616元。

表3 各航班機型指派結果Tab.3 Type-assignment decisions of various flights

2）空客機族

A300型飛機執(zhí)行6個航班，有效航班串分別為109-110，105-106-113-114；

A320型飛機執(zhí)行8個航班，有效航班串分別為103-104-111-112，119-120-101-102；

A340機飛機執(zhí)行6個航班，有效航班串分別為117-118-107-108，115-116。

空客機族的航班串結果表明，只需調用6架空客機族飛機執(zhí)飛。其中2架A300，2架A320，2架A340，最終運營成本為2 719 756元。

因此，第1階段機族指派的結果是波音機族。第2階段波音機族指派的機型和架次為：B737飛機2架，B767飛機2架，B747飛機1架，最終運營成本為2 662 616元，比空客機族少57 140元。進一步說明對于該公司的新航線，選擇波音機族執(zhí)飛要比選擇空客機族執(zhí)飛更經(jīng)濟。

6 結語

本文在新航線需求不確定的情形下，對兩階段機型指派問題進行了研究。主要工作如下：

1）對于新開辟航線的機型指派問題，由于缺乏歷史運營數(shù)據(jù)，本文將新航線需求設為不確定變量，建立了一個帶有機會約束的兩階段機型指派0-1整數(shù)規(guī)劃模型；

2）為便于求解，使用不確定理論將不確定需求約束轉換成確定性約束，并將不確定規(guī)劃問題轉換為等價的確定性問題；

3）針對模型中復雜的時間窗約束，改進傳統(tǒng)分支定界法，給出了求解兩階段機型指派模型的進化算法；

4）算例驗證了模型的可行性和算法的有效性，結果可為航空公司的機型指派決策提供參考。

本文還存在不足之處，如模型未考慮航空市場中存在的隨機性對運營成本的影響，在后續(xù)研究中將考慮隨機因素，建立不確定隨機機型指派模型。

[1]馬蘇德·巴扎爾甘.航空公司運營與規(guī)劃管理[M].邵 龍，王美佳，譯.北京：中國民航出版社，2006.

[2]ABARA J.Applying integer linear programming to the fleet assignment problem[J].Interfaces，1989，19（4）：20-28.

[3]朱星輝，朱金福，鞏在武.我國航空公司機型指派模型及算法研究[J].工業(yè)技術經(jīng)濟，2007，26（4）：75-77.

[4]劉 昕，白存儒，劉慧穎.帶時間窗的飛機排班問題優(yōu)化[J].航空工程進展，2012，3（4）：517-521.

[5]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.

[6]SHERALI H D，ZHU X.Two-stage fleet assignment model considering stochastic passenger demands[J].Operations Research，2008，56（2）：383-399.

[7]LIU B.Why is there a need for uncertainty theory[J].Journal of Uncertain Systems，2011，5（1）：3-20.

[8]LIUB.UncertaintyTheory[M].2nded.Berlin：Springer-Verlag，2007.

[9]LIU B.Uncertainty Theory[M].3rded.Berlin：Springer Link，2010.

[10]耿淑香.航空公司運營與管理方略[M].北京：中國民航出版社，2000.

[11]BERGE M E，HOPPERSTAD C A.Demand driven dispatch：A method for dynamic aircraft capacity assignment，models and algorithms[J]. Operational Research，1993，41（8）：153-168.

[12]SHERALI H D，BISH E K，ZHU X M.Airline fleet assignment concepts，models，and algorithms[J].European Journal of Operational Research，2006，172（1）：1-30.

[13]JACOBS T L，SMITH B C，JOHNSON E L.Incorporating network flow effects into the airline fleet assignment process[J].Transportation Science，2008，42（4）：514-529.

[14]BARNHART C，F(xiàn)ARAHAT A，LOHATEPANONTM.Airline fleet assignment with enhanced revenue modeling[J].Operations Reserch，2009，57（1）：231-244.

[15]YEN C L，KUEI T F，BERTRAND L.A branch-and-bound algorithm for makespan minimization in differentiation flow shops[J].Engineering Optimization，2013，45（12）：1397-1408.

（責任編輯：黨亞茹）

Two-stage fleet assignment model with uncertain demand

ZHANG Chun-xiao1a，SHI Xiao-lei1b，ZANG Qi-yin2
（1a.Civil Aircraft Airworthiness and Maintenance Key Lab of Tianjin；1b.College of Science，CAUC，Tianjin 300300，China；2.Sales Department in Taiyuan，Shandong Airlines Co.Ltd.，Taiyuan 030001，China）

For the fleet assignment problem of a new opening airline，the probability distribution of its demand cannot be obtained due to the absence of previous data.Therefore，the demands of new flights are assumed as uncertain variables.A binary integer programming model of two-stage fleet assignment with chance constrains is proposed，where the first stage makes family-assignment decision，and the second stage solves type-assignment problem for a certain aircraft family.Given the uncertain distribution form of new flight demand，the proposed model is converted into a deterministic programming model.An improved branch and bound algorithm is designed to solve this model.Finally，a numerical example considers the fleet assignment problem of twenty flights of six new opening routes in a hub airport，results indicate the proposed model and algorithm are effective in practice.

fleet assignment；new airline demand；uncertainty theory；two-stage；binary integer programming；branch and bound algorithm

V355；TP319；O22

：A

：1674-5590（2015）04-0010-06

2014-05-07；

：2014-06-12

：中央高?；究蒲袠I(yè)務費專項（3122014D034）

張春曉（1971—），女，青海西寧人，副教授，碩士，研究方向為民航統(tǒng)計與優(yōu)化.