基于魯棒性的外加航班機組配對研究

樂美龍， 鄒凱中

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

?

基于魯棒性的外加航班機組配對研究

樂美龍， 鄒凱中*

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

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

中小型航空公司； 外加航班； 機組配對； 魯棒性

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

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

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

1 機組配對問題

一個機組配對是由在機場的銜接時間和在每一個工作日結束后的休息時間間隔開來的一系列航班.一個配對可能跨越幾個工作日并且由一個單獨的機組執飛.在機組配對問題中，目的是要從所有可行配對中選擇一個子集來覆蓋航班計劃表中的每一個航班并且每一個航班僅能被覆蓋一次，同時還要保持機組總成本最小.這個問題可以看作一個集劃分問題，如下所示：

(1)

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

(2)

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

2 問題描述和解決方法

在生成機組配對時需要遵守一系列復雜的規則，本部分要用到的標號如下.

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

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

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

為了處理外加航班的問題，測試了至多帶有兩個機組置位的所有可能的恢復選擇，解決方案可分為如下兩種類型：

A類型：兩個配對被選擇以用于在運行過程中交換執行這些配對的機組來覆蓋一個外加航班.

B類型：只有一個配對被選擇，配對中兩個連續的航班之間必須有足夠的時間來覆蓋外加航班.

如果一個方案可以被執行，那么它必須滿足一系列可行性的條件.這些條件與銜接時間、總飛行時間和總運行時間有關.當一個機組配對模型可以得到大量的這種可行性方案時，就認為該模型具有魯棒性.由于方案背后的主要思想以及相應的可行性條件是相似的，因此只列舉一種A類型的方案和一種B類型的方案.

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

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

圖2中列舉了一種帶有一個置位機組的A類型方案.只有配對對(p，q)滿足下面的可行條件，方案(A.1)才可以被執行.

(A.1)

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

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

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

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

形成一個B類型方案}.

圖3舉例說明了B類型方案的一種情況.只有配對滿足下面可行性條件時，方案(B.1)才能夠被實施.

(B.1)

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

3 數學模型

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

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

(3)

(4)

(5)

(6)

(7)

(8)

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

(9)

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

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

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

maxz

(10)

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

圖4 一個重復計算的例子Fig.4 An illustration of the double counting problem

(11)

(12)

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

(13)

(14)

4 算例分析

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

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

表1 配對形成中用到的參數

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

表2 58個航班的數據

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

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

表3 由傳統模型和各魯棒性模型提供的恢復選擇

5 結論及展望

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

[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]. 計算機工程與應用， 2008， 44(34): 243-245．

[5] 肖真真. 基于任務均衡的航空公司機組人員指派問題研究[D]. 四川：中國民用航空飛行學院，2012．

[6] 魯紅珍. 航空公司機組航班任務串優化方法研究[D]. 四川：中國民用航空飛行學院，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].中國管理科學，2009， 17(6)：22-27．

[10] 牟德一， 王志新， 等. 基于機組延誤概率的魯棒性機組配對問題[J].系統管理學報，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.

國家自然科學基金項目(71471110)．

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

*通訊聯系人. E-mail: zzkkzzyy@163.com.

1000-1190(2015)02-0307-07

F550.74

A