張春曉，石曉磊，臧其銀

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

不確定需求下的兩階段機(jī)型指派模型

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

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

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

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

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

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

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

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

1 預(yù)備知識

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 假設(shè)和符號

2.1 假設(shè)

1）新開辟航線航班為直達(dá)航班；

2）航班運(yùn)營以一天24 h為一個周期；

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

4）只考慮航班運(yùn)營成本，包括飛機(jī)燃料成本、維護(hù)成本和管理成本。將航班運(yùn)營成本分?jǐn)傉鬯愠勺镞\(yùn)營成本（CASK）[10]；

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

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

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

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

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

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

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

2.2 符號

K：機(jī)族k的集合，即k∈K；

Tk：機(jī)族k的機(jī)型tk集合，即tk∈Tk；

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

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

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

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

CASKtk：機(jī)族k的機(jī)型t的座公里成本；

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

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

GT：完成一次地面過站作業(yè)所需最低時(shí)間標(biāo)準(zhǔn)；

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

n：時(shí)空網(wǎng)絡(luò)節(jié)點(diǎn)；

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

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

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

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

3 模型

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

設(shè)第1階段決策變量為

則機(jī)族指派模型為

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

設(shè)第2階段決策變量為

則機(jī)型指派模型為

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

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

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

4 算法

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

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

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

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

Step 2 若k=K，轉(zhuǎn)Step 7，否則k=k+1；

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

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

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

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

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

5 算例

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

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

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

表2 機(jī)型信息表Tab.2 Information of aircraft types

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

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

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

1）波音機(jī)族

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

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

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

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

表3 各航班機(jī)型指派結(jié)果Tab.3 Type-assignment decisions of various flights

2）空客機(jī)族

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

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

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

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

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

6 結(jié)語

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

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

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

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

4）算例驗(yàn)證了模型的可行性和算法的有效性，結(jié)果可為航空公司的機(jī)型指派決策提供參考。

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

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

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

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

[4]劉 昕，白存儒，劉慧穎.帶時(shí)間窗的飛機(jī)排班問題優(yōu)化[J].航空工程進(jìn)展，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]耿淑香.航空公司運(yùn)營與管理方略[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.

（責(zé)任編輯：黨亞茹）

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è)務(wù)費(fèi)專項(xiàng)（3122014D034）

張春曉（1971—），女，青海西寧人，副教授，碩士，研究方向?yàn)槊窈浇y(tǒng)計(jì)與優(yōu)化.