飛機(jī)路線恢復(fù)問題的兩階段隨機(jī)規(guī)劃方法研究

朱 博，朱金福，吳薇薇

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

?

飛機(jī)路線恢復(fù)問題的兩階段隨機(jī)規(guī)劃方法研究

朱 博，朱金福，吳薇薇

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

針對(duì)飛機(jī)故障修復(fù)時(shí)間的不確定性，建立了飛機(jī)路線恢復(fù)的兩階段隨機(jī)優(yōu)化模型:第一階段模型為飛機(jī)資源指派模型，以延誤和取消成本之和最小為目標(biāo)函數(shù)；第二階段補(bǔ)償模型根據(jù)飛機(jī)故障修復(fù)時(shí)間的隨機(jī)情景，以航班時(shí)間重排恢復(fù)策略的期望成本最小為目標(biāo)函數(shù)。針對(duì)隨機(jī)模型的結(jié)構(gòu)，設(shè)計(jì)隨機(jī)啟發(fā)式算法。算例結(jié)果表明，采用隨機(jī)模型和算法可以有效地提高不正常航班恢復(fù)方案的可行性，比確定型模型節(jié)約5.8%左右的恢復(fù)成本。

航班計(jì)劃運(yùn)行；飛機(jī)路線恢復(fù)；兩階段隨機(jī)模型；貪婪模擬算法

航空公司的航班計(jì)劃是在假設(shè)其能正常實(shí)施的前提下制定的，然而實(shí)際運(yùn)行中，航空運(yùn)輸系統(tǒng)會(huì)面臨各種不確定因素的擾動(dòng)，使得航班無法按原計(jì)劃執(zhí)行，大大增加了航空公司的運(yùn)行成本，給旅客帶來極大不便，降低了航空運(yùn)輸系統(tǒng)的運(yùn)行效率。對(duì)不正常航班恢復(fù)的研究至今已有約60年的歷史，其中飛機(jī)故障造成短缺情況下的飛機(jī)路線恢復(fù)問題(aircraft rerouting problem, ARP)是研究的重點(diǎn)之一。TEODOROVIC等建立了受擾航班網(wǎng)絡(luò)，對(duì)飛機(jī)故障時(shí)的路線恢復(fù)問題進(jìn)行了研究，設(shè)計(jì)分支定界算法求解模型，是對(duì)擾動(dòng)問題的開創(chuàng)性研究之一[1]。YAN等在動(dòng)態(tài)網(wǎng)絡(luò)計(jì)劃擾動(dòng)模型的基礎(chǔ)上，利用網(wǎng)絡(luò)流算法、拉格朗日松弛和次梯度法進(jìn)行求解[2]。ARGüELLO等采用貪婪隨機(jī)自適應(yīng)搜索算法(GRASP)對(duì)飛機(jī)路線進(jìn)行重排，目標(biāo)函數(shù)是航班收益損失和旅客延誤損失最小[3]。THENGVALL等在飛機(jī)短缺的恢復(fù)模型中加入與原計(jì)劃偏離的懲罰成本，在線性規(guī)劃松弛未得到整數(shù)解的情況下用啟發(fā)式算法得到整數(shù)解[4]。ANDERSSON等建立了帶邊約束的混合整數(shù)多商品流模型，利用Dantzig-Wolfe分解方法將其轉(zhuǎn)化為集合劃分模型[5]。趙秀麗等構(gòu)建了以延誤成本最小或延誤時(shí)間最短為目標(biāo)函數(shù)的飛機(jī)路線恢復(fù)模型，采用啟發(fā)式方法并調(diào)用匈牙利算法對(duì)其求解[6]。唐小衛(wèi)等在文獻(xiàn)[3]的基礎(chǔ)上，設(shè)計(jì)了貪婪模擬退火(greedy simulated annealing，GSA)算法，對(duì)飛機(jī)路線恢復(fù)問題進(jìn)行了研究[7]。VOS等建立了動(dòng)態(tài)模型框架，使用了平行時(shí)空網(wǎng)絡(luò)來追蹤飛機(jī)的狀態(tài)，該框架依賴于飛機(jī)選擇算法和一個(gè)線性規(guī)劃模型[8]。

盡管國內(nèi)外對(duì)飛機(jī)路線恢復(fù)的研究已經(jīng)取得了不錯(cuò)的成果，但這些研究成果卻未能在實(shí)際中很好地應(yīng)用，這是由于：①假設(shè)飛機(jī)故障的情形是確定的，如飛機(jī)故障修復(fù)時(shí)間在決策前是已知的，而在實(shí)際運(yùn)行中，這個(gè)值常常是很難預(yù)測的；②確定型飛機(jī)路線恢復(fù)研究給出的恢復(fù)方案在執(zhí)行過程中缺乏魯棒性，可能隨著干擾因素的隨機(jī)變化而變得不可行。因此，研究不正常航班恢復(fù)問題的隨機(jī)優(yōu)化理論和方法非常必要。不確定優(yōu)化在航空運(yùn)輸規(guī)劃與管理的一些領(lǐng)域已有一定的研究，如航線網(wǎng)絡(luò)的設(shè)計(jì)和優(yōu)化[9]、航班計(jì)劃的制定等[10-11];而在航班計(jì)劃運(yùn)行層面，目前僅有一些利用仿真軟件進(jìn)行延誤控制的研究[12]，并未考慮擾動(dòng)因素的隨機(jī)性。

1 問題的描述和模型的建立

1.1 問題描述

以兩架飛機(jī)在一天的簡單航班計(jì)劃為例，給出了一個(gè)典型的飛機(jī)路線和故障修復(fù)時(shí)間示意圖，如圖1所示。圓角矩形表示航班，其中冒號(hào)前的數(shù)字表示航班號(hào)，冒號(hào)后的字母表示起降機(jī)場?；疑珔^(qū)域表示飛機(jī)A2在07:30時(shí)刻發(fā)現(xiàn)故障，預(yù)計(jì)故障修復(fù)時(shí)間為13:15。航空公司簽派員可有多種恢復(fù)方案：取消航班4和航班5；直接將飛機(jī)A2預(yù)計(jì)執(zhí)行的航班4～航班7全部順延；在08:00交換飛機(jī)A1和A2的航班任務(wù)等。這是一個(gè)典型的優(yōu)化問題，恢復(fù)方案在制定時(shí)假設(shè)故障修復(fù)時(shí)間為已知。

圖1 飛機(jī)路線和故障修復(fù)時(shí)間示意圖

然而，上述故障修復(fù)時(shí)間只是機(jī)務(wù)維修人員給出的期望值，該期望值很少與實(shí)際修復(fù)時(shí)間相同，可能導(dǎo)致其制定的恢復(fù)方案不優(yōu)甚至不可行。例如，當(dāng)簽派員在7:30時(shí)將航班4延誤至13:15，但13:15時(shí)發(fā)現(xiàn)飛機(jī)A2并沒有恢復(fù)使用，此時(shí)會(huì)引發(fā)更多的延誤和取消；還可能是飛機(jī)A2早于13:15修復(fù)完畢，那么可以指定和使用比當(dāng)前更好的恢復(fù)方案。隨著擾動(dòng)信息頻繁地更新，不斷重新優(yōu)化會(huì)是一個(gè)非常費(fèi)時(shí)的過程。若能制定一個(gè)魯棒恢復(fù)方案，當(dāng)隨機(jī)的恢復(fù)時(shí)間確定后，該方案只需進(jìn)行簡單的調(diào)整便可。

1.2 飛機(jī)路線恢復(fù)的隨機(jī)規(guī)劃模型

在確定型ARP研究中，資源指派模型可以準(zhǔn)確簡潔地描述問題，是最為常見的模型之一，該模型參考了文獻(xiàn)[3]中的恢復(fù)模型，其中的隱含工作是可行的飛機(jī)路線已經(jīng)生成。模型中的記號(hào)定義如下：①集合。F為航班集合，下標(biāo)為i；K為可用飛機(jī)集合，下標(biāo)為k；A為機(jī)場集合，下標(biāo)為a；P為可行的飛機(jī)路線集合，下標(biāo)為j。②參數(shù)。當(dāng)航班i包含在路徑j(luò)中時(shí)，aij等于1，否則等于0；當(dāng)路徑j(luò)在機(jī)場a終止時(shí)，bja等于1，否則等于0；ci為取消航班i的成本；ha表示恢復(fù)期結(jié)束時(shí)，為執(zhí)行正常航班計(jì)劃機(jī)場a需要的飛機(jī)架數(shù)；dkj為將飛機(jī)k指派給路徑j(luò)的延誤成本。③決策變量。當(dāng)飛機(jī)k指派給路徑j(luò)時(shí)，xkj等于1，否則等于0；航班i取消時(shí)，yi等于1，否則等于0。則建立ARP的第一階段資源指派模型為：

(1)

(2)

(3)

(4)

(5)

(6)

式(1)為目標(biāo)函數(shù)，要求航班延誤成本和取消成本之和最??；式(2)為航班覆蓋約束，對(duì)任一航班來說，其要么被取消，要么被指派給一個(gè)航班路徑；式(3)為飛機(jī)流平衡約束，為了保證航班的正常運(yùn)行，要求恢復(fù)期結(jié)束后各機(jī)場的飛機(jī)數(shù)滿足一定數(shù)量；式(4)規(guī)定了一架飛機(jī)只能指派給一條可行的路徑；式(5)和式(6)為變量非負(fù)約束。

該確定型模型有一個(gè)隱含的工作，即在假設(shè)飛機(jī)故障修復(fù)時(shí)間確定的情況下生成可行的飛機(jī)路線。然而，在實(shí)際運(yùn)行中飛機(jī)故障修復(fù)時(shí)間是很難確定的，許多飛機(jī)可靠性和維修性的研究也證明了這一點(diǎn)[13]。因此，引入隨機(jī)故障修復(fù)時(shí)間的概念，建立了兩階段的航班恢復(fù)隨機(jī)優(yōu)化模型。兩階段補(bǔ)償模型的意義在于選擇確定一種決策，使得當(dāng)前的決策成本和以后補(bǔ)償?shù)某杀酒谕底钚?。?duì)航班恢復(fù)問題來說，在優(yōu)化模型中加入由隨機(jī)性引起的期望調(diào)整成本；期望成本可通過建立補(bǔ)償模型求解得到，反映了第一階段恢復(fù)方案可能發(fā)生的變化，從而選擇確定穩(wěn)健性、可行性高的恢復(fù)方案。第一階段模型即為上述ARP的確定型資源指派模型；第二階段補(bǔ)償模型是針對(duì)飛機(jī)故障修復(fù)的隨機(jī)情景，對(duì)第一階段的可行恢復(fù)方案進(jìn)行調(diào)整,其采用的策略為不改變其飛機(jī)路線，單純地重新安排航班時(shí)刻。這保證了補(bǔ)償模型的可行性，其簡單的線性形式也確保了求解的速度。第二階段補(bǔ)償模型也可以包括取消航班、交換飛機(jī)等較復(fù)雜的恢復(fù)策略，但并不改變模型的本質(zhì)。帶補(bǔ)償?shù)膬呻A段隨機(jī)ARP模型形式為：

RP=minW=min(Z+Q(x,y))

(7)

(8)

(9)

隨機(jī)模型的目標(biāo)函數(shù)由兩部分組成，第一部分為式(1)，第二部分Q(x,y)為第一階段恢復(fù)方案在執(zhí)行過程中進(jìn)行調(diào)整補(bǔ)償決策的期望成本；x和y分別為決策變量xkj和yi的簡化表達(dá)形式；式(8)為式(2)～式(4)的抽象形式；式(9)為模型的非負(fù)0-1約束。

1.3 補(bǔ)償模型

圖2給出了圖1例子在第一階段模型中得到的一個(gè)恢復(fù)方案示意圖，其采用的恢復(fù)方案是A1和A2交換飛機(jī)路線，并延誤航班1～航班3。顯然，恢復(fù)方案制訂是以灰色的故障修復(fù)時(shí)間期望值為初始條件。然而實(shí)際運(yùn)行中，A2的故障修復(fù)時(shí)間會(huì)是一個(gè)隨機(jī)變量，取值在ΔT范圍內(nèi)。若A2的最終故障修復(fù)時(shí)間為14:00，則該恢復(fù)方案中航班1～航班3 需依次順延；若航班3預(yù)計(jì)降落時(shí)間超出了機(jī)場AAA的宵禁開始時(shí)間，則該航班或被取消，或延誤到宵禁時(shí)間結(jié)束，這兩種方案都會(huì)造成很大的成本損失。這些情況會(huì)在第二階段補(bǔ)償模型的目標(biāo)函數(shù)中以風(fēng)險(xiǎn)成本的形式表示。

確定型ARP模型的求解十分復(fù)雜。對(duì)兩階段隨機(jī)規(guī)劃模型，第一階段的每一個(gè)可行解都對(duì)應(yīng)著一系列的補(bǔ)償模型需要求解，這就要求補(bǔ)償模型的建立和求解盡量簡單。令T表示飛機(jī)故障修復(fù)時(shí)間隨機(jī)變量組成的向量，其包含了可被視為連續(xù)變量的受擾動(dòng)飛機(jī)的恢復(fù)時(shí)間、被視為常量的未受擾動(dòng)飛機(jī)的可用時(shí)間。則補(bǔ)償模型的目標(biāo)函數(shù)可用Q(x,y)= ∫q(x,y,T)dT表示。該目標(biāo)函數(shù)是非線性且連續(xù)隨機(jī)變量的概率分布函數(shù)，不易獲得，因此可以不失準(zhǔn)確度的情況下將飛機(jī)恢復(fù)時(shí)間進(jìn)行離散化處理。每架受擾飛機(jī)隨機(jī)變量的離散點(diǎn)組合可以構(gòu)成一個(gè)有界的情景集Ω，令ω∈Ω表示一種情景，Pr(ω)為ω的概率，則第一階段可行恢復(fù)方案的期望補(bǔ)償為：

圖2 飛機(jī)路線恢復(fù)和隨機(jī)故障修復(fù)時(shí)間示意圖

(10)

(12)

(13)

(14)

(15)

(18)

(19)

2 求解算法

盡管確定型ARP模型的求解已經(jīng)非常復(fù)雜，對(duì)其算法的研究還是取得了許多成果。無論是精確算法如列生成，還是啟發(fā)式算法如GRASP、貪婪模擬退火算法GSA，都可以在較短的時(shí)間內(nèi)給出滿意的解。將ARP問題由確定型拓展為隨機(jī)型，問題規(guī)模的增加會(huì)使得求解更加困難。若第二階段模型是線性的，且隨機(jī)情景數(shù)量有限，則模型總可以轉(zhuǎn)化為確定型的等價(jià)形式。但是，問題的規(guī)模也會(huì)隨之變得更大。與一般的長期計(jì)劃問題不同，對(duì)運(yùn)行階段的恢復(fù)優(yōu)化來說，求解的速度是決策者關(guān)注的重點(diǎn)。忽略隨機(jī)規(guī)劃模型結(jié)構(gòu)的通用算法將會(huì)降低效率，為了有效地求解兩階段隨機(jī)模型，筆者根據(jù)隨機(jī)模型的結(jié)構(gòu)，結(jié)合GSA和簡單的貪婪時(shí)間調(diào)整策略，設(shè)計(jì)了隨機(jī)算法的求解框架。

對(duì)于第一階段模型，決策變量x和y可以使用GSA算法進(jìn)行求解。文獻(xiàn)[7]給出了該算法的3個(gè)基本步驟：①通過順延受擾飛機(jī)路線構(gòu)建初始可行解；②對(duì)受擾飛機(jī)路線對(duì)進(jìn)行5種操作，構(gòu)建鄰域解。受擾飛機(jī)路線對(duì)由兩條飛機(jī)路線構(gòu)成，為了保護(hù)未受擾的飛機(jī)路線免受不必要的調(diào)整，受擾飛機(jī)路線對(duì)中至少要有一條受擾飛機(jī)路線。對(duì)每個(gè)受擾飛機(jī)路線對(duì)的5種操作包括：航班環(huán)插入、航班串插入路線尾部、航班串交換、為航班串交換、航班環(huán)取消。③從受限候選表(包含成本下降的鄰域解)和反向受限候選表(包含成本上升的鄰域解)中選擇若干鄰域解替代當(dāng)前解的相應(yīng)部分。

當(dāng)?shù)谝浑A段的解傳入第二階段模型中，后者將按照情景數(shù)量退化為若干個(gè)易解的線性優(yōu)化補(bǔ)償模型。在補(bǔ)償模型中飛機(jī)路線上的航班是固定不變的，因此對(duì)恢復(fù)方案的唯一調(diào)整就是對(duì)航班時(shí)刻表的重排；在保證其可行且滿足MTT要求的基礎(chǔ)上，貪婪地將航班時(shí)間緊湊調(diào)整。如果時(shí)間重排的策略無法得出可行解，唯一的可能就是宵禁約束無法滿足，對(duì)該情況有兩種解決方案：一是取消違反該約束的航班，二是延誤航班直到宵禁結(jié)束。違反宵禁約束的成本以參數(shù)φi表示。因此，對(duì)每個(gè)情景ω∈Ω可得到q(x,y,ω),由于情景間互相獨(dú)立，Q(x,y)可根據(jù)式(10)計(jì)算得到。

3 算例分析

表1所示為某航空公司原計(jì)劃飛機(jī)路線，該算例共有6架飛機(jī)，原計(jì)劃執(zhí)行航班23個(gè)。假設(shè)航班延誤單位成本ρi為20元/min；取消航班造成的成本等于航班延誤8 h帶來的成本，即9 600元；飛機(jī)路線超宵禁的成本φi為10 000元。國內(nèi)所有機(jī)場的宵禁時(shí)間窗為每天[02:00,06:00]，國際機(jī)場如VVNB暫不考慮宵禁。飛機(jī)D在當(dāng)前時(shí)刻11:40發(fā)現(xiàn)臨時(shí)故障，機(jī)務(wù)人員對(duì)故障類型和嚴(yán)重程度進(jìn)行判斷，給出故障修復(fù)時(shí)間的期望值為320 min，即D在17:00可投入使用；根據(jù)歷史統(tǒng)計(jì)信息，得出離散的故障修復(fù)時(shí)間的概率分布，如表2所示。

表1 原計(jì)劃飛機(jī)路線

表2 飛機(jī)D故障修復(fù)時(shí)間的概率分布

在求解EV中，飛機(jī)D的故障修復(fù)時(shí)間為常量320min，即D到17:00可投入使用。用GSM算法從步驟①～步驟⑥求解EV模型，設(shè)置算法終止條件為計(jì)算時(shí)間達(dá)到5min或生成300個(gè)執(zhí)行解。表3列出了該確定型模型的解，總延誤成本為EV=Z=15 900元。確定解的期望補(bǔ)償成本為Q=5 928元，表示當(dāng)確定解實(shí)施時(shí)由于隨機(jī)性引起的調(diào)整成本。因此，確定解的隨機(jī)期望成本為EEV=W=Z+Q=21 828元。對(duì)WS模型使用類似的求解方法，每個(gè)隨機(jī)飛機(jī)修復(fù)時(shí)間的離散值被視為常量輸入第一階段模型；進(jìn)行優(yōu)化并根據(jù)表2的概率計(jì)算出期望值后，得到WS=16 007元，表示優(yōu)化前若能得到隨機(jī)變量確定值時(shí)決策的期望目標(biāo)值。

對(duì)兩階段隨機(jī)模型RP進(jìn)行求解，結(jié)束條件設(shè)置為計(jì)算時(shí)間達(dá)到10min或得到300個(gè)執(zhí)行解。隨機(jī)恢復(fù)方案同樣在表3中列出，延誤成本Z=16 300元，第二階段補(bǔ)償模型的成本為Q=4 257元，所以隨機(jī)模型的目標(biāo)函數(shù)值RP=W=Z+Q=20 557元。

若不考慮飛機(jī)恢復(fù)時(shí)間的不確定性，則確定型模型的恢復(fù)方案延誤成本(15 900元)比隨機(jī)模型中的恢復(fù)方案(16 300元)小。但是，確定型模型方案中的飛機(jī)D會(huì)執(zhí)行航班F24，該航班預(yù)計(jì)在凌晨02:00降落在ZSPD，F(xiàn)24有50%的概率會(huì)由于違反宵禁約束而被取消或長時(shí)間延誤，從而引起更多的運(yùn)行成本和旅客損失。因此，在考慮對(duì)不確定性進(jìn)行補(bǔ)償?shù)那闆r下，隨機(jī)恢復(fù)方案的成本(20 557元)比確定解的恢復(fù)方案成本(21 828元)少；隨機(jī)模型解中，大部分飛機(jī)在當(dāng)天降落停場機(jī)場前有一定的緩沖時(shí)間，可以吸收不確定性帶來的變化，所以恢復(fù)方案更為魯棒和靈活。定義完美信息的期望成本(expectedvalueofperfectinformation，EVPI)EVPI=RP-WS，表示隨機(jī)模型中不確定性的影響。定義隨機(jī)解價(jià)值(valueofstochasticsolution，VSS)VSS=EEV-RP，表示確定解的隨機(jī)期望成本與隨機(jī)解的目標(biāo)函數(shù)值之差。在該算例中，EVPI=RP-WS=20 557-16 007=4 550元，可見不確定性給恢復(fù)方案帶來了許多額外的成本。對(duì)比確定解情景分析的期望值與兩階段隨機(jī)模型的目標(biāo)函數(shù)值，得到VSS=EEV-RP=21 828-20 557=1 271元。隨機(jī)模型得到的解比確定模型的解降低約5.8%的成本。

表3 兩種模型的恢復(fù)方案對(duì)比

4 結(jié)論

飛機(jī)臨時(shí)故障導(dǎo)致的運(yùn)力資源短缺是造成航班不正常的主要擾動(dòng)因素之一。針對(duì)飛機(jī)故障修復(fù)時(shí)間的不確定性，在確定型航班恢復(fù)研究的基礎(chǔ)上，建立了兩階段的隨機(jī)航班恢復(fù)模型。該模型提供了在飛機(jī)故障修復(fù)時(shí)間不確定的情況下做出恢復(fù)方案成本的估計(jì)，在本質(zhì)上通過對(duì)補(bǔ)償問題的評(píng)估增強(qiáng)了已有恢復(fù)方案的可行性。由于模型的復(fù)雜性和對(duì)計(jì)算時(shí)間的要求，設(shè)計(jì)了隨機(jī)貪婪模擬退火算法，結(jié)合傳統(tǒng)的啟發(fā)式算法框架和簡單的貪婪補(bǔ)償方法，有效地對(duì)飛機(jī)故障的隨機(jī)恢復(fù)問題進(jìn)行求解。通過算例測試，體現(xiàn)了航班恢復(fù)問題中考慮隨機(jī)因素的重要性，隨機(jī)解價(jià)值的計(jì)算也體現(xiàn)了準(zhǔn)確信息的重要性和隨機(jī)規(guī)劃模型的現(xiàn)實(shí)意義。

[1] TEODOROVIC D, GUBERINIC S. Optimal dispatching strategy on an airline network after a schedule perturbation[J]. European Journal of Operational Research,1984,15(2):178-182.

[2] YAN S, YANG D H. A decision support framework for handling schedule perturbation[J]. Transportation Research Part B Methodological,1996,30(6):405-419.

[3] ARGüELLO M F, BARD J F, YU G. A GRASP for aircraft routing in response to groundings and delays[J]. Journal of Combinatorial Optimization,1997,1(3):211-228.

[4] THENGVALL B G, BARD J F, YU G. Balancing user preferences for aircraft schedule recovery during irregular operations[J]. IIE Transaction on Operations Engineering,2000,32(3):181-193.

[5] ANDERSSON T, VRBRAND P. The flight perturbation problem[J]. Transportation Planning and Technology,2004,27(2):91-117.

[6] 趙秀麗,朱金福,郭梅.不正常航班延誤調(diào)度模型及算法[J].系統(tǒng)工程理論與實(shí)踐,2008,28(4):129-134.

[7] 唐小衛(wèi),高強(qiáng),朱金福.不正常航班恢復(fù)模型的貪婪模擬退火算法研究[J].預(yù)測,2010,29(1):66-70.

[8] VOS H W M, SANTOS B F, OMONDI T. Aircraft schedule recovery problem: a dynamic modeling framework for daily operations[J]. Transportation Research Procedia,2015(10):931-940.

[9] 葛偉,朱金福,吳薇薇,等.基于無容量限制的P：樞紐眾位問題的隨機(jī)優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐,2013,33(10):2674-2678.

[10] SCHAEFER A J, JOHNSON E L, KLEYWEGT A J, et al.Airline crew scheduling under uncertainty[J]. Transportation Science.2005,39(3):340-348.

[11] YEN J W, BIRGE J R. A stochastic programming approach to the airline crew scheduling problem[J]. Transportation Science,2006,40(1):3-14.

[12] ROSENBERGER J M,SCHAEFER A J, GOLDSMAN D, et al. A stochastic model of airline operations[J]. Transportation Science,2002,36(4):357-377.

[13] SOHN S Y, YOON K B, CHANG I S. Random effects model for the reliability management of modules of a fighter aircraft[J]. Reliability Engineering and System Safety,2006,91(4):433-437.

[14] BIRGE J R. The value of the stochastic solution in stochastic linear programs with fixed recourse[J]. Mathematical Programming,1982,24(1):314-325.Two-stage Stochastic Programming in Aircraft Routing Recovery Problem

ZHU Bo:Doctorial Candidate; College of Civil Aviation ,Nanjing University of Aeronautics and Astronautics, Nanjing 211106,China.

ZHUBo,ZHUJinfu,WUWeiwei

To deal with the intrinsic uncertainty of the repair time, this paper established a two-stage stochastic flight recovery model. The first stage model is an aircraft resource assignment model, with the objective function of minimizing delay and cancellation cost. Based on stochastic scenes of aircraft restoration time, the second recourse model uses re-timing strategy, with the objective function of minimizing the expectation cost on recourse decision. In accordance with the structure of the stochastic model, a stochastic heuristic algorithm was designed to solve the model. The computational results indicates that the proposed stochastic model and algorithm can effectively improve the feasibility of the recovery solutions, and can save 5.8% operational cost compared with the deterministic model.

flight schedule operation; aircraft routing recovery; two-stage stochastic programming model; greedy simulated annealing algorithm

2095-3852(2016)05-0591-06

A

2016-06-04.

朱博(1987-)，女，江蘇鎮(zhèn)江人，南京航空航天大學(xué)民航學(xué)院博士研究生.

國家自然科學(xué)基金項(xiàng)目(71171111；71201081)；南京航空航天大學(xué)博士學(xué)位論文創(chuàng)新與創(chuàng)優(yōu)基金項(xiàng)目(BCXJ13-14)；江蘇省研究生培養(yǎng)創(chuàng)新工程資金項(xiàng)目(CXZZ13_0174).

V355.2 DOI：10.3963/j.issn.2095-3852.2016.05.016