樂(lè)美龍， 鄒凱中

(上海海事大學(xué) 物流研究中心， 上海 201306)

?

基于魯棒性的外加航班機(jī)組配對(duì)研究

樂(lè)美龍， 鄒凱中*

(上海海事大學(xué) 物流研究中心， 上海 201306)

為了提高中小型航空公司的服務(wù)水平，增強(qiáng)其應(yīng)對(duì)外加航班的靈活性，文章針對(duì)外加航班機(jī)組配對(duì)問(wèn)題設(shè)計(jì)了新型的機(jī)組配對(duì)方案.在基于傳統(tǒng)的機(jī)組配對(duì)模型上，滿(mǎn)足外加航班機(jī)組配對(duì)的要求下，提出具有魯棒性的機(jī)組配對(duì)模型.之后通過(guò)算例分析，用CPLEX軟件對(duì)所建立的模型進(jìn)行求解，得出了模型下目標(biāo)函數(shù)的最優(yōu)解.最后通過(guò)不同結(jié)果的對(duì)比，顯示了魯棒性建模方法的好處并表明魯棒性模型在以相對(duì)較小的成本增加而不干擾已有航班的情況下可以為恢復(fù)提供自然的選擇，為中小型航空公司在處理外加航班問(wèn)題上提供有意義的參考.

中小型航空公司； 外加航班； 機(jī)組配對(duì)； 魯棒性

在航空公司運(yùn)營(yíng)中，機(jī)組成本是繼燃油成本之后的第二大成本項(xiàng)目.然而，與燃油成本不同，機(jī)組費(fèi)用的大部分是可以控制的，對(duì)此很多學(xué)者進(jìn)行了研究.Marsten和Shepardson[1]建立了機(jī)組排班問(wèn)題的集劃分模型，并采用隱枚舉和拉格朗日松弛算法對(duì)模型進(jìn)行了求解.Lavoie等[2]在早期采用列生成算法對(duì)機(jī)組排班問(wèn)題進(jìn)行了有效求解.Beasley和Chu[3]為非單一費(fèi)用的集合覆蓋問(wèn)題設(shè)計(jì)了基于啟發(fā)式的遺傳算法.李耀華和譚娜[4]在求解機(jī)組指派模型時(shí)采用自然數(shù)編碼的改進(jìn)遺傳算法，通過(guò)仿真驗(yàn)證了模型和算法的可行性.肖真真[5]建立了任務(wù)均衡的機(jī)組人員指派問(wèn)題模型，并采用改進(jìn)的自適應(yīng)遺傳算法進(jìn)行求解.魯紅珍[6]提出了多目標(biāo)的機(jī)組配對(duì)模型，最后對(duì)機(jī)組資源利用率最大的模型求解，驗(yàn)證了模型的可行性.

由于航班在實(shí)際的運(yùn)營(yíng)中會(huì)受到各種干擾，給航空公司造成很大的經(jīng)濟(jì)損失.為減輕這種干擾造成的損失，近來(lái)，魯棒性的研究備受關(guān)注.EhrgottandRyan[7]對(duì)沒(méi)有足夠時(shí)間來(lái)吸收延遲的銜接進(jìn)行懲罰，求解了一個(gè)最小化總成本和總懲罰成本的多目標(biāo)最優(yōu)問(wèn)題.ShebalovandKlabjan[8]定義了移動(dòng)機(jī)組來(lái)作為取得魯棒性的一種方式，既在運(yùn)營(yíng)過(guò)程中，機(jī)組之間的計(jì)劃可以進(jìn)行交換.牟德一和張婧[9]在確定性經(jīng)典模型的基礎(chǔ)上，提出了具有魯棒性的機(jī)組配對(duì)問(wèn)題的隨機(jī)規(guī)劃模型.牟德一和王志新[10]建立了基于機(jī)組延誤概率最小的魯棒性機(jī)組配對(duì)模型并用Matlab進(jìn)行了求解，結(jié)果表明模型產(chǎn)生的機(jī)組配對(duì)在應(yīng)對(duì)干擾時(shí)更具魯棒性.Schaefer等[11]以最小化期望總成本為目標(biāo)函數(shù)來(lái)解決機(jī)組配對(duì)問(wèn)題.YenandBirge[12]考慮了不確定性條件下的機(jī)組配對(duì)問(wèn)題，把機(jī)組配對(duì)問(wèn)題描述為一個(gè)兩階段的隨機(jī)規(guī)劃問(wèn)題且探討了兩個(gè)連續(xù)航班之間的銜接時(shí)間對(duì)解的魯棒性的影響.

然而，目前絕大部分的文獻(xiàn)集中在航空公司的大規(guī)模問(wèn)題上[13-14]，忽視了中小型航空公司的需求，這些需求之一是對(duì)臨時(shí)的外加航班的管理.外加航班出現(xiàn)的原因有很多，例如某旅游路線的游客大增或包機(jī)等.目前，這種干擾是通過(guò)在運(yùn)行中應(yīng)用恢復(fù)程序進(jìn)行處理[15].本文研究的是在機(jī)組配對(duì)的生成階段考慮這些航班的插入，力求所得配對(duì)更具魯棒性，使得在實(shí)際運(yùn)行中有更多的方案來(lái)應(yīng)對(duì)這種干擾.

1 機(jī)組配對(duì)問(wèn)題

一個(gè)機(jī)組配對(duì)是由在機(jī)場(chǎng)的銜接時(shí)間和在每一個(gè)工作日結(jié)束后的休息時(shí)間間隔開(kāi)來(lái)的一系列航班.一個(gè)配對(duì)可能跨越幾個(gè)工作日并且由一個(gè)單獨(dú)的機(jī)組執(zhí)飛.在機(jī)組配對(duì)問(wèn)題中，目的是要從所有可行配對(duì)中選擇一個(gè)子集來(lái)覆蓋航班計(jì)劃表中的每一個(gè)航班并且每一個(gè)航班僅能被覆蓋一次，同時(shí)還要保持機(jī)組總成本最小.這個(gè)問(wèn)題可以看作一個(gè)集劃分問(wèn)題，如下所示：

(1)

yp∈{0,1},p∈p*，

(2)

式中，F(xiàn)是所有航班的集合，p*是所有可行配對(duì)的集合，cp是配對(duì)p∈p*的成本，參數(shù)aip=1，如果配對(duì)p覆蓋了航班i；否則，aip=0.決策變量yp=1，如果配對(duì)p是解的一部分，否則，yp=0.目標(biāo)函數(shù)是最小化所選配對(duì)的總成本.等式約束(1)確保每個(gè)航班有且僅能被覆蓋一次.

2 問(wèn)題描述和解決方法

在生成機(jī)組配對(duì)時(shí)需要遵守一系列復(fù)雜的規(guī)則，本部分要用到的標(biāo)號(hào)如下.

圖1 外加航班k的時(shí)間窗Fig.1 The time window for the extra flight k

由于事先不知道可能的外加航班的準(zhǔn)確時(shí)間，可以假設(shè)一個(gè)外加航班可能被插入的時(shí)間窗.通常，時(shí)間窗的信息可以由過(guò)去的經(jīng)驗(yàn)或通過(guò)挖掘歷史數(shù)據(jù)獲得.圖1是一個(gè)外加航班k的時(shí)間窗.在圖中，橫線表示起飛和抵達(dá)的城市，從左到右的箭頭表示時(shí)間的推移.為了表示航班最早起飛和最晚抵達(dá)的時(shí)間，采用兩個(gè)虛構(gòu)的航班k′航班k″和表示.

為了覆蓋外加航班，航空公司通常使用置位機(jī)組.然而，使用多于兩個(gè)置位機(jī)組去覆蓋一個(gè)外加航班是不可取的.因此，我們假設(shè)在一個(gè)方案中只允許不多于兩個(gè)置位機(jī)組的情況出現(xiàn).根據(jù)規(guī)定，花費(fèi)在機(jī)組置位期間的時(shí)間會(huì)部分地算作勤務(wù)期內(nèi)的飛行時(shí)間.允許機(jī)組置位時(shí)間th(i,j)與相應(yīng)的實(shí)際飛行時(shí)間不同.而且，置位機(jī)組的最小等待和休息時(shí)間可以與機(jī)組執(zhí)飛正常航班時(shí)的不同.

為了處理外加航班的問(wèn)題，測(cè)試了至多帶有兩個(gè)機(jī)組置位的所有可能的恢復(fù)選擇，解決方案可分為如下兩種類(lèi)型：

A類(lèi)型：兩個(gè)配對(duì)被選擇以用于在運(yùn)行過(guò)程中交換執(zhí)行這些配對(duì)的機(jī)組來(lái)覆蓋一個(gè)外加航班.

B類(lèi)型：只有一個(gè)配對(duì)被選擇，配對(duì)中兩個(gè)連續(xù)的航班之間必須有足夠的時(shí)間來(lái)覆蓋外加航班.

如果一個(gè)方案可以被執(zhí)行，那么它必須滿(mǎn)足一系列可行性的條件.這些條件與銜接時(shí)間、總飛行時(shí)間和總運(yùn)行時(shí)間有關(guān).當(dāng)一個(gè)機(jī)組配對(duì)模型可以得到大量的這種可行性方案時(shí)，就認(rèn)為該模型具有魯棒性.由于方案背后的主要思想以及相應(yīng)的可行性條件是相似的，因此只列舉一種A類(lèi)型的方案和一種B類(lèi)型的方案.

兩個(gè)配對(duì)要形成一個(gè)A類(lèi)型的方案，當(dāng)且僅當(dāng)這些配對(duì)在交換后是可行的.用p∈p表示連續(xù)覆蓋航班i1和i2的配對(duì)，q∈p表示連續(xù)覆蓋航班j1和j2的配對(duì)(見(jiàn)圖2).如果這兩個(gè)配對(duì)的機(jī)組來(lái)自于相同的基地，并且它們也滿(mǎn)足某些可行性條件，主要是關(guān)于相對(duì)的抵達(dá)和起飛時(shí)間和交換航班之間的銜接時(shí)間，則p和q為外加航班k形成一個(gè)A類(lèi)型的方案.交換之后，第一個(gè)配對(duì)由航班i1之前的航班、航班i2以及航班j2及其之后的航班組成，這里外加航班k被插入在航班i2和j2之間.同樣，第二個(gè)配對(duì)由航班j1之前的航班、航班j1以及航班i2及其之后的航班組成.我們用pA(k)表示為外加航班k形成可行的A類(lèi)型方案的配對(duì)對(duì)(p，q)的集合：

pA(k)={(p,q):q∈p為外加航班k形成一個(gè)A類(lèi)型方案}.

圖2中列舉了一種帶有一個(gè)置位機(jī)組的A類(lèi)型方案.只有配對(duì)對(duì)(p，q)滿(mǎn)足下面的可行條件，方案(A.1)才可以被執(zhí)行.

(A.1)

在(A.1)中前兩個(gè)條件保證航班i2和外加航班k之間的銜接時(shí)間和航班k和隨后的航班j2之間的銜接時(shí)間都在可允許的限制范圍之內(nèi).第三個(gè)條件對(duì)原始配對(duì)p的總飛行時(shí)間和總運(yùn)行時(shí)間施加限制.最后一個(gè)條件是對(duì)原始配對(duì)q的總飛行時(shí)間和總運(yùn)行時(shí)間的限制.

圖2 帶有一個(gè)置位機(jī)組的A類(lèi)型方案(A.1)Fig.2 A sample (A.1) solution on the flight network with one deadhead

B類(lèi)型方案只需要一個(gè)配對(duì).如果一個(gè)被選擇的配對(duì)有充足的銜接時(shí)間來(lái)覆蓋外加航班，并且配對(duì)涉及的機(jī)組的剩余工作計(jì)劃不會(huì)違反相關(guān)約束，那么這個(gè)配對(duì)就構(gòu)造了一個(gè)B類(lèi)型的方案.同樣，通過(guò)檢查各種不同的可行性規(guī)則來(lái)確保一個(gè)方案的有效性.為外加航班k形成B類(lèi)型方案的配對(duì)集合可以表示為：

pB(k)={p∈p:配對(duì)p為外加航班k

形成一個(gè)B類(lèi)型方案}.

圖3舉例說(shuō)明了B類(lèi)型方案的一種情況.只有配對(duì)滿(mǎn)足下面可行性條件時(shí)，方案(B.1)才能夠被實(shí)施.

(B.1)

圖3 一種B類(lèi)型解決方案(B.1)Fig.3 A sample (B.1) solution on the network with one deadhead

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

在文中，提出了兩種旨在安置外加航班的魯棒性模型，模型的目標(biāo)是使最優(yōu)解中的配對(duì)盡可能多地為外加航班構(gòu)造A或B類(lèi)型的方案.隱含的假設(shè)是：隨著最優(yōu)解中配對(duì)構(gòu)造的A或B類(lèi)型方案數(shù)量的增加，計(jì)劃在應(yīng)對(duì)外加航班時(shí)將更具有魯棒性.然而，該做法將導(dǎo)致在被選擇的配對(duì)中會(huì)有更長(zhǎng)的銜接時(shí)間，結(jié)果將導(dǎo)致總成本比傳統(tǒng)模型(1)的要更高.為了權(quán)衡這兩個(gè)方面，首先求解傳統(tǒng)的機(jī)組配對(duì)模型(1)，得到它的最優(yōu)目標(biāo)函數(shù)值，用Copt表示.然后增加一個(gè)總成本約束到改進(jìn)后的魯棒性模型中，使得被選擇配對(duì)的總成本不超過(guò)Copt的某個(gè)百分比，這個(gè)百分比是人為設(shè)定的.

在模型中，配對(duì)p的成本cp用公式cp=max{fp*Te(p),nd*mg.∑d∈pcd}計(jì)算，Te(p)是配對(duì)p的總運(yùn)行時(shí)間，fp是一個(gè)純小數(shù)，nd是配對(duì)p中勤務(wù)的數(shù)量，mg是一個(gè)勤務(wù)期的最小保證時(shí)間，cd是配對(duì)中勤務(wù)d的成本.同樣，勤務(wù)期的成本cd=max{Tf(d),fd*Te(d),mg}，Tf(d)和Te(d)分別表示勤務(wù)期d的總飛行時(shí)間和總運(yùn)行時(shí)間.注意到一個(gè)配對(duì)的成本都是由時(shí)間定義的.則魯棒性模型為：

(3)

(4)

(5)

(6)

(7)

(8)

yp∈{0,1},p∈p.

(9)

模型(2)的目標(biāo)函數(shù)是最大化A類(lèi)型和B類(lèi)型方案的總數(shù)量.約束(3)是集劃分約束；約束(4)是確定A類(lèi)型方案形成的條件，(p,q)∈pA(k)且配對(duì)p和q是解的一部分；約束(5)是確定B類(lèi)型方案形成的條件，p∈pB(k)且配對(duì)p是解的一部分；約束(6)是使所選配對(duì)的總成本在一個(gè)可接受的范圍內(nèi).

模型(2)并沒(méi)有試著為每一個(gè)外加航班提供一個(gè)解決方案，而且雖然模型的最優(yōu)解可能會(huì)為某些外加航班提供幾種解決方案，但它可能不會(huì)為某個(gè)外加航班提供任何解決方案，即使這種可供選擇的最優(yōu)方案存在.在這種情況下，可以把下面的約束加入到模型(2)中，nblow表示每一個(gè)外加航班所需要的解決方案數(shù)量的一個(gè)下界.

作為一種選擇，也可以求解模型(3)，它把最大的值作為最優(yōu)化目標(biāo)函數(shù)值.該目標(biāo)函數(shù)旨在盡可能公平地為外加航班分配解決方案.相比于模型(2)，模型(3)的目標(biāo)函數(shù)和增加的約束如下：

maxz

(10)

注意到模型(2)和(3)都沒(méi)有考慮任何防止一個(gè)配對(duì)出現(xiàn)在幾個(gè)A或B類(lèi)型的方案中的約束.當(dāng)一個(gè)外加航班的兩種不同的解決方案共享一個(gè)配對(duì)時(shí)，不會(huì)產(chǎn)生沖突.然而，如果一個(gè)配對(duì)不止為一個(gè)外加航班構(gòu)成解決方案時(shí)，將面臨兩個(gè)外加航班在同一天被插入到航班計(jì)劃表中的問(wèn)題.這個(gè)問(wèn)題稱(chēng)作重復(fù)計(jì)算.圖4是一個(gè)重復(fù)計(jì)算的例子，有三個(gè)配對(duì)A，B和C，分別覆蓋航班a1-a2，b1-b2和c1-c2，外加航班由k1和k2表示.在這個(gè)例子中，配對(duì)C和配對(duì)A為外加航班構(gòu)造了一個(gè)A類(lèi)型方案，同時(shí)配對(duì)C和配對(duì)B也為外加航班構(gòu)造了一個(gè)A類(lèi)型方案.在模型(2)中這兩種方案將分別計(jì)入方案總數(shù)中.然而，如果航班和必須在同一天執(zhí)飛，那么只能用配對(duì)C來(lái)覆蓋其中的一個(gè)外加航班.

圖4 一個(gè)重復(fù)計(jì)算的例子Fig.4 An illustration of the double counting problem

(11)

(12)

模型(4)與模型(2)一樣都是最大化A和B類(lèi)型解決方案形成的數(shù)量，但是模型(4)限制了一個(gè)給定配對(duì)怎樣為一個(gè)給定外加航班和多個(gè)外加航班形成解決方案.約束(11)使一個(gè)配對(duì)至多只能出現(xiàn)在個(gè)解決方案中；約束(12)表示一個(gè)配對(duì)只能出現(xiàn)在一個(gè)外加航班的解決方案中.與模型(3)相比，模型(5)增加的新約束有：

(13)

(14)

4 算例分析

本文的研究在于證明處理外加航班的魯棒性模型的價(jià)值而不是求解大規(guī)模的數(shù)學(xué)規(guī)劃問(wèn)題，因此本文沒(méi)有嘗試用大規(guī)模的數(shù)學(xué)規(guī)劃技術(shù)來(lái)求解模型.算例規(guī)模很小以致允許找到所有可行的配對(duì).只考慮周期為一天的配對(duì).文中的一些參數(shù)如表1所示.

在案例中，有58個(gè)航班往返于SH、NJ、LYG、HF、JN、HZ和FZ七個(gè)城市之間，其中SH是僅有的機(jī)組基地，共有10架飛機(jī).航班時(shí)刻表如表2所示.

表1 配對(duì)形成中用到的參數(shù)

在這個(gè)問(wèn)題中，從SH到NJ的航班和SH到HF的航班分別在15∶00和11∶25有很高的需求.為了滿(mǎn)足這種需求，航空公司準(zhǔn)備臨時(shí)增開(kāi)兩個(gè)外加航班(SH-NJ)和(SH-HF)，兩個(gè)外加航班的時(shí)間窗分別為15∶00-16∶30和11∶40-13∶30.

表2 58個(gè)航班的數(shù)據(jù)

用CPLEX 11.0在處理器為2.53GHz，內(nèi)存為2GB的計(jì)算機(jī)上進(jìn)行算例的求解.求得的結(jié)果如表3所示.從表中可以看到，魯棒性模型得到的配對(duì)成本都比傳統(tǒng)模型的高，但是都不高于傳統(tǒng)模型的1.7%.在外加航班的覆蓋上，CM(1)得到的最優(yōu)化配對(duì)只能為外加航班k2構(gòu)造方案；RM(2)則兩個(gè)航班都可以被覆蓋，但是需要注意的是，如果兩個(gè)航班k1和k2同時(shí)被插入進(jìn)來(lái)，那么航班k2只能用(91，970)來(lái)覆蓋，因?yàn)?2108，1039)需要用來(lái)覆蓋航班k2；RM(3)的解遇到了重復(fù)計(jì)算的問(wèn)題，在兩個(gè)航班需要同時(shí)插入時(shí)，它只能滿(mǎn)足一個(gè)航班的需要.RM(4)和RM(5)都考慮了重復(fù)計(jì)算的問(wèn)題，RM(4)得到的方案數(shù)量較多，但是有航班沒(méi)能覆蓋；RM(5)盡可能公平地分配方案，兩個(gè)航班可以同時(shí)被插入.

從結(jié)果的分析可以得出，決策者可以根據(jù)遇到的實(shí)際情況來(lái)選擇合適的模型.一方面，當(dāng)所有航班不可能同時(shí)插入到航班計(jì)劃中時(shí)，決策者可以選擇忽視重復(fù)計(jì)算的模型以獲得盡可能多的備選方案；另一方面，當(dāng)同時(shí)覆蓋所有航班對(duì)航空公司來(lái)說(shuō)很重要時(shí)，決策者可以選擇考慮重復(fù)計(jì)算的模型以獲得盡可能覆蓋所有航班的方案.同時(shí)，從表中可以看到模型的求解時(shí)間都很短，完全在航空公司可接受的范圍內(nèi).

表3 由傳統(tǒng)模型和各魯棒性模型提供的恢復(fù)選擇

5 結(jié)論及展望

本文在機(jī)組配對(duì)生成的計(jì)劃階段考慮了運(yùn)營(yíng)中可能遇到的臨時(shí)航班加入的情況，構(gòu)造了兩種具有魯棒性的數(shù)學(xué)模型.通過(guò)算例對(duì)模型進(jìn)行驗(yàn)證，結(jié)果表明在為外加航班構(gòu)造更多解決方案的同時(shí)，魯棒性模型的機(jī)組配對(duì)成本均不超過(guò)傳統(tǒng)模型的1.7%.同時(shí)，魯棒性模型的求解時(shí)間在航空公司應(yīng)對(duì)緊急情況的時(shí)間要求范圍之內(nèi).不過(guò)，模型沒(méi)有考慮外加航班對(duì)飛機(jī)排班和維修計(jì)劃的影響，在今后可以把這方面的因素考慮進(jìn)去做進(jìn)一步研究.此外，文章還可以針對(duì)運(yùn)用列生成算法求解大規(guī)模的機(jī)組配對(duì)模型做出一個(gè)更深層次的探索.

[1] Marsten R E， Shepardson F. Exact solution of crew scheduling problems using the set partitioning model: Recent successful applications[J]. Networks， 1981， 11(2): 165-177．

[2] Lavoie S， Minoux M， Odier E. A new approach for crew pairing problems by column generation with an application to air transportation[J]. European Journal of Operational Research， 1988， 35(1): 45-58．

[3] Beasley J E， Chu P C. A genetic algorithm for the set covering problem[J]. European Journal of Operational Research， 1996， 94(2): 392-404．

[4] 李耀華， 譚 娜. 飛機(jī)排班調(diào)度中機(jī)組指派優(yōu)化模型及算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用， 2008， 44(34): 243-245．

[5] 肖真真. 基于任務(wù)均衡的航空公司機(jī)組人員指派問(wèn)題研究[D]. 四川：中國(guó)民用航空飛行學(xué)院，2012．

[6] 魯紅珍. 航空公司機(jī)組航班任務(wù)串優(yōu)化方法研究[D]. 四川：中國(guó)民用航空飛行學(xué)院，2012．

[7] Ehrgott M， Ryan D M. Constructing robust crew schedules with bicriteria optimization[J]. Journal of Multi-Criteria Decision Analysis， 2002， 11(3): 139-150．

[8] Shebalov S， Klabjan D. Robust airline crew pairing: Move-up crews[J]. Transportation Science， 2006， 40(3): 300-312．

[9] 牟德一， 張 婧. 具有魯棒性的機(jī)組配對(duì)問(wèn)題的隨機(jī)規(guī)劃模型[J].中國(guó)管理科學(xué)，2009， 17(6)：22-27．

[10] 牟德一， 王志新， 等. 基于機(jī)組延誤概率的魯棒性機(jī)組配對(duì)問(wèn)題[J].系統(tǒng)管理學(xué)報(bào)，2011， 20(2)：207-212．

[11] Schaefer A J， Johnson E L， Kleywegt A J， et al. Airline crew scheduling under uncertainty[J]. Transportation Science， 2005， 39(3): 340-348．

[12] Yen J W， Birge J R. A stochastic programming approach to the airline crew scheduling problem[J]. Transportation Science， 2006， 40(1): 3-14．

[13] Anbil R， Gelman E， Patty B， et al. Recent advances in crew-pairing optimization at American Airlines[J]. Interfaces， 1991， 21(1): 62-74．

[14] Vance P H， Atamturk A， Barnhart C， et al. A heuristic branch-and-price approach for the airline crew pairing problem[J]. preprint， 1997，43(9):43-49．

Study on crew pairing for managing extra flights based on robustness

LE Meilong， ZOU Kaizhong

(Logistics Research Center， Shanghai Maritime University， Shanghai 201306)

In order to improve the service level of small and medium-sized airlines， enhance its flexibility to cope with extra flights， the article designs a new crew pairing solutions for extra flights. Based on the traditional model of the crew pairing， meeting the requirements of crew pairing for extra flights， we propose robust crew pairing model. Then through the example analysis， we used CPLEX software to solve the model， obtained the optimal solutions. Finally， through the comparison of different results， revealing the advantage of robust modeling method and showing that the proposed robust models provide natural options to recovery without disrupting the existing flights at a relatively small incremental cost， and providing meaningful reference for the small and medium-sized airline in the problem of coping with extra flights．

small and medium-sized airlines; extra flights; crew pairing; robustness

2014-09-03.

國(guó)家自然科學(xué)基金項(xiàng)目(71471110)．

樂(lè)美龍(1964-)，男，浙江寧波人，教授，博士生導(dǎo)師，主要從事物流管理與工程的研究.

*通訊聯(lián)系人. E-mail: zzkkzzyy@163.com.

1000-1190(2015)02-0307-07

F550.74

A