2018年我國設(shè)計研究生數(shù)學(xué)建模競賽C題

...wd......wd......wd...2017年中國研究生數(shù)學(xué)建模競賽C題航班恢復(fù)問題背景隨著經(jīng)濟(jì)的開展，航空出行已成為越來越多旅客的選擇。但眾所周知，飛機(jī)航班如果不能按原方案執(zhí)行，不僅會給航空公司造成巨大的經(jīng)濟(jì)損失，同時還會給旅客出行帶來極大的不便。在造成航班不正常的種種因素中，有些是不可抗阻的自然因素，如暴風(fēng)雪、颶風(fēng)等，有些是不可預(yù)測的突發(fā)事件，如突發(fā)恐懼襲擊、飛機(jī)機(jī)械故障等等，還有些是因?yàn)楣芾硎侄蔚穆浜?，比方飛行員缺位、空中管制，等等。下表是FlightStats網(wǎng)站公布的今年二月份世界主要航空公司和局部中國航空公司航班準(zhǔn)點(diǎn)率的對比?？梢钥闯?，雖然中國的航班準(zhǔn)點(diǎn)率很低，但其他國家和地區(qū)也不樂觀，比方美國外鄉(xiāng)的平均航班準(zhǔn)點(diǎn)率也只有77%。航空公司名次準(zhǔn)點(diǎn)率%航空公司名次準(zhǔn)點(diǎn)率%Iberia192.45United(美聯(lián)航)1981.99Singapore(新航)288.14%CathyPacific(國泰)3075.03Delta(美三角)387.54AirChina(國航)3866.55American(美航)686.2ChinaEastern(東航)3961.74需要指出的是，由于目前中國航空公司在國內(nèi)主要航線上航班安排已經(jīng)對比稠密，一旦某個航班出現(xiàn)故障，就有可能造成一系列的連鎖反響，影響成千上萬旅客的出行。一些航空公司沒有把航班延誤作為要事來抓，缺乏有效應(yīng)對手段。如果抱著“等著瞧〞的消極態(tài)度，不僅可能造成更多的沒有必要的延誤，而且還會導(dǎo)致最終產(chǎn)生一個失敗的決策。例如航空公司在等待3個小時后，最終決定取消該航班，局部旅客被安置到此后2小時以后的某航班上。這樣的結(jié)局顯然不如一開場就宣布取消該航班，把旅客延遲到某航班上。世界范圍內(nèi)，近年來快速增長的航空旅客數(shù)量已超過了很多主要機(jī)場的容量，加上近年氣候的反常變化和安全突發(fā)事件的增多，航班恢復(fù)問題越來越受到各國民航管理機(jī)構(gòu)和各大航空公司的重視，中國主要航空公司也已經(jīng)把航班恢復(fù)的自動化提到了議事日程上了。最近發(fā)生的美國聯(lián)航乘客被打事件，外表上是一個旅客服務(wù)管理問題，但本質(zhì)上是航班恢復(fù)管理不慎造成的結(jié)果。聯(lián)航為了防止外地航班機(jī)組人員缺位，緊急從芝加哥基地調(diào)遣機(jī)組前往。由于機(jī)組缺位造成的航班中斷有擴(kuò)散到整個網(wǎng)絡(luò)的可能，聯(lián)航賦予了他們很高的登機(jī)優(yōu)先級。這些都是正確的決策并且被正確地執(zhí)行了，但在最后環(huán)節(jié)，聯(lián)航工作人員沒有能把座位“拍賣〞堅持到最后時刻，從而導(dǎo)致了世界民航史上的這一重大事件的發(fā)生，給聯(lián)航造成了不可挽回的重大損失。其實(shí)，航班恢復(fù)問題的“難〞除了相關(guān)因素的復(fù)雜，更主要的原因在于恢復(fù)方案的即時性。航班紊亂發(fā)生后，恢復(fù)方案的決定和實(shí)施是越早越好。在手工調(diào)整的情況下，調(diào)度員只能考慮到影響飛行安全的一些基本因素，很難考慮到全局網(wǎng)絡(luò)的優(yōu)化，更別說11了。舉個最簡單的例子，假設(shè)飛行網(wǎng)絡(luò)中有一架飛機(jī)出現(xiàn)故障需要檢修，受影響的航班可能不超過10個，具有多年調(diào)度經(jīng)歷的調(diào)度員大概需要幾十分鐘甚至1~2小時進(jìn)展航班手工調(diào)整。可以想象，如果飛行網(wǎng)絡(luò)出現(xiàn)大面積紊亂，受影響的航班可能有幾十個甚至上百個，期望調(diào)度員手工在十幾分鐘甚至幾分鐘內(nèi)完成整個網(wǎng)絡(luò)的調(diào)整一定是異想天開，但借助于計算機(jī)求解數(shù)學(xué)優(yōu)化模型卻是可行的。要最終可行，還有兩個關(guān)鍵因素必須解決：1.若何創(chuàng)立適宜的數(shù)學(xué)模型；2.若何用適宜的算法快速求解這個數(shù)學(xué)模型。學(xué)術(shù)界研究航班恢復(fù)問題已經(jīng)很久，取得了很好的進(jìn)展，但業(yè)界至今還很少有實(shí)際的應(yīng)用解決方案。因?yàn)槔碚撗芯恳话愣季窒抻谟邢薜臅r間和空間，運(yùn)行約束也僅僅是實(shí)際約束的局部子集，這樣的方法很難被航空公司的運(yùn)控部門采納而直接用于生產(chǎn)實(shí)踐。目前世界上提供解決航班恢復(fù)問題的產(chǎn)品寥寥無幾，具有完整功能、滿足各種實(shí)際需求的產(chǎn)品還只有Sabre一家。本賽題就是針對以上這兩個問題而設(shè)計的。Sabre公司通過在高校開展學(xué)術(shù)競賽來提高學(xué)術(shù)界對不正常航班的恢復(fù)研究的關(guān)注度。更多相關(guān)的資料可以在以下網(wǎng)頁瀏覽下載，://page.sabreairlinesolutions/orcompetitions?？偠灾?，創(chuàng)立適宜的數(shù)學(xué)模型和采用行之有效的算法求解是解決航班恢復(fù)問題的關(guān)鍵。目前，學(xué)術(shù)界一般采用decomposition〔例如Bender’sDecomposition或者ColumnGeneration〕的方法來求解這一類整數(shù)規(guī)劃模型【1】【4】，更好的算法還有待于發(fā)現(xiàn).問題介紹航班恢復(fù)問題本質(zhì)上是運(yùn)營恢復(fù)問題的一局部?；蛘哒f，廣義的航班恢復(fù)就是運(yùn)營恢復(fù)，包括〔狹義的〕航班恢復(fù)〔FlightRecovery〕、機(jī)組恢復(fù)〔CrewRecovery〕和旅客行程重新規(guī)劃〔PassengerRe-accommodation〕三局部，它們相互約束，構(gòu)成一個整體上超大規(guī)模的運(yùn)籌優(yōu)化問題。這個優(yōu)化問題具有難以想象的復(fù)雜度，不是工業(yè)界目前已有計算機(jī)的計算能力所及。在實(shí)際運(yùn)營過程中，航空公司是按流程次序先考慮航班恢復(fù)，然后在此根基上機(jī)組恢復(fù)，最后重新規(guī)劃旅客的行程，把他們送往各自的目的地。相應(yīng)地，采用運(yùn)籌優(yōu)化方法解決運(yùn)營恢復(fù)問題也是按這三步把整個大問題按階段次序分解成子問題【1】，即首先求解航班恢復(fù)問題，在此根基上求解機(jī)組恢復(fù)問題和旅客行程再規(guī)劃問題。需要指出的是，由于缺少信息交互，雖然每個子問題的求解可以到達(dá)局部最優(yōu)，但整體最優(yōu)卻得不到保證，甚至有出現(xiàn)不可行解的可能。已經(jīng)有學(xué)者證明，整合兩個或者三個子問題成一個單一數(shù)學(xué)模型，可以得到更好質(zhì)量的解【4】。所以本賽題作為航班恢復(fù)問題由四個子題目組成，從最基本的單一機(jī)型的航班恢復(fù)，多機(jī)型恢復(fù)，最后到考慮旅客行程重新規(guī)劃的航班恢復(fù)。為了防止過于復(fù)雜化，本賽題不考慮機(jī)組人員的恢復(fù)，也不考慮旅客行程重新規(guī)劃。針對航班恢復(fù)問題，通常有三種航班調(diào)整方法：航班延誤、飛機(jī)置換和航班取消。航班延誤和飛機(jī)置換可以同時發(fā)生。航班延誤如果選擇航班延誤，還需要給出具體的延誤時間〔以分鐘為單位〕。通常航空公司對延誤都有最大延誤時間約束，本賽題規(guī)定航班最大延誤時間為5小時，即延誤超過5小時時一定取消該航班。以間隔10分鐘為一個決策單位，那么一個航班就有30個延誤決策可選。航班延誤的代價除了旅客滿意度降低外，更重要的是聯(lián)程旅客可能趕不上下趟航班。本賽題規(guī)定，飛機(jī)的飛行時間不會因延誤而受影響。飛機(jī)置換飛機(jī)置換就是將航班安排給不同于原方案執(zhí)行飛機(jī)的其他飛機(jī)去執(zhí)行。如以以下列圖所示，按方案，航班1連接航班3由飛機(jī)A執(zhí)行，航班2連接航班4由飛機(jī)B執(zhí)行。但由于延誤，飛機(jī)A執(zhí)行完航班1后沒有足夠時間間隔，無法及時執(zhí)行航班3。于是，調(diào)度員將航班3安排給飛機(jī)B，航班4安排給飛機(jī)A去執(zhí)行。航班1航班1航班3航班2航班4飛機(jī)A飛機(jī)B調(diào)整后：航班1航班3航班2航班4飛機(jī)A飛機(jī)B圖一：飛機(jī)置換飛機(jī)置換并不需要在完全一樣的飛機(jī)之間進(jìn)展，航空公司可以安排給滿足約束條件的任何其它飛機(jī)。實(shí)際操作中，一般安排給同機(jī)型家族〔比方A320〕，或者同子機(jī)型〔比方A320-200〕的任何一架飛機(jī)。飛機(jī)置換通常是最正確航班恢復(fù)方案，只要能滿足最小飛機(jī)間隔時間就行。但這種時機(jī)不總是存在。飛機(jī)間隔時間是指同一架飛機(jī)在執(zhí)行完上一趟航班到執(zhí)行下一趟航班前的地面停留時間。此題規(guī)定最小飛機(jī)間隔時間是45分鐘。航班取消眾所周知航班取消的含義，這里就省略解釋。航班取消的代價顯然是最嚴(yán)重的。數(shù)學(xué)模型例如f1Airporta圖二：時空網(wǎng)絡(luò)〔符號參照數(shù)學(xué)模型〕t1+Flyf1t2t1f2t2+Flyf2TimeAirporta0Airporta1下面給出一個充分簡化了的航班恢復(fù)問題的線性規(guī)劃模型，供參賽者理解fAirporta圖二：時空網(wǎng)絡(luò)〔符號參照數(shù)學(xué)模型〕tttftTimeAirporta0Airporta1最小化f∈F約束條件xxyatp=變量定義xf:0-1變量，用來表示航班f是否xft:0-1變量，用來表示航班f是否在時間點(diǎn)txftp:0-1變量，用來表示航班f是否在時間點(diǎn)t由飛機(jī)yatp:0-1變量，用來表示飛機(jī)p在時間點(diǎn)t是否停在參數(shù)符號T:時間軸上所考慮時間點(diǎn)的集合F:所有航班的集合A:所有機(jī)場的集合P:所有飛機(jī)的集合Tf?T:航班f的所有允許Dptf:航班f的最早允許起飛時間點(diǎn),Flyf:航班fFaI?F:所有到達(dá)機(jī)場為FaO?F:所有CancelCostf:取消航班fDelayCostf:航班f下面舉例說明這個線性規(guī)劃模型的復(fù)雜度。假設(shè)一個擁有P=100架飛機(jī)的子機(jī)型網(wǎng)絡(luò)有600個航班需要執(zhí)行。最大延誤時間5小時，每個航班有Tf=30個延誤選擇，每個延誤選擇可以安排給100架飛機(jī)里的任意一架。這樣大致估計共有F?Tf?P=600*30*100=1.8*106個選擇變量xftp。如果把這樣一個有幾百萬個選擇變量的0-1整數(shù)規(guī)劃問題采用商用求解器〔如CPLEX或GUROBI〕直接求解，絕無可能保證在允許的時間限制內(nèi)求得最優(yōu)解。實(shí)際上，這樣的問題完全有可能運(yùn)行幾天甚或幾年才能完畢。如果我們除了上述時空網(wǎng)絡(luò)的數(shù)學(xué)模型外，也可以將安排給某架飛機(jī)的所有航班考慮為一個有效路徑，用列生成的方法去求解。這樣可以減少因?yàn)檠诱`時間而產(chǎn)生的大量決策變量【2】。賽題本賽題有如下幾個要求和規(guī)定：附件里時間的表達(dá)均為Unix格式，即從1970年1月1日0時0分0秒算起的秒數(shù)。從Unix時間格式到一般時間格式的轉(zhuǎn)換可參考附件中Excel表格里的轉(zhuǎn)換公式，比方(((B2/60)/60)/24)+DATE(1970,1,1)。另外，所有時間均假設(shè)為UTC國際標(biāo)準(zhǔn)時間。所有航班只能延誤，不能提前，最早起飛時間不能早于原方案的起飛時間。各航班的飛行時間是常量，即航班數(shù)據(jù)中的到達(dá)時間減去起飛時間。保證每架飛機(jī)的連續(xù)航班能首尾相連，即前一航班的到達(dá)機(jī)場與后一航班的起飛機(jī)場必須一樣，而且前一航班到達(dá)時間與后一航班起飛時間之間的最小間隔時間為45分鐘。所有飛機(jī)的第一個航班要滿足如下兩個條件：〔1〕航班的起飛機(jī)場與飛機(jī)的起點(diǎn)機(jī)場一致，〔2〕航班的起飛時間不早于飛機(jī)的最早可用時間。所有飛機(jī)的最后一個航班的到達(dá)時間不能晚于飛機(jī)的最晚可用時間。航班延誤的決策時間點(diǎn)間隔為10分鐘〔比方，安排給X飛機(jī)并按方案起飛，安排給X飛機(jī)并延誤10分鐘，安排給X飛機(jī)并延誤20分鐘，安排給X飛機(jī)并延誤30分鐘，以此類推〕。如果參賽者有能力通過其他的數(shù)學(xué)模型找出更靈活的延誤時間可以不考慮這一假設(shè)。不考慮機(jī)場可停留飛機(jī)的容量。理論上所有機(jī)場可以全天24小時工作。同行旅客是指一起訂票并且行程完全一致的旅客，他們共享同一個旅客號，并作為一個整體考慮，即不能分乘不同的航班。所有航班，包括機(jī)場OVS關(guān)閉時段內(nèi)的航班，它們的延誤時間都需要被考慮到。為了最大可能保護(hù)航班，盡量不取消航班。數(shù)據(jù)結(jié)果提交的格式要求：參賽者除了在論文中必須表達(dá)若何解讀結(jié)果外，還必須提交完整的新航班方案并作為附件與論文一起發(fā)送指定郵箱。提交的新航班方案有如下格式要求：〔1〕雖然輸入數(shù)據(jù)的時間都是Unix格式，所有輸出數(shù)據(jù)的時間必須都是一般格式，比方，4/22/1616:15表示2016年4月22日16時15分?！?〕可以在原航班數(shù)據(jù)〔見后〕格式的根基上，添加“新機(jī)型號〞、“新飛機(jī)尾號〞、“新起飛時間〞、“新到達(dá)時間〞和“延誤時間〞。列的次序按下表例如。如有需要，參賽者還可在后面添加新列。新起飛時間和新到達(dá)時間與原時間如有不同，請用亮色標(biāo)出?！?〕將問題一、問題二、問題三、問題四的新航班方案結(jié)果分別放在輸出Excel總表格的Sheet1、Sheet2、Sheet3、Sheet4中。該Excel總表格的文件名為“C參賽隊(duì)號.xls〞。表格各頁的格式如下例如：航班唯一編號起飛時間新起飛時間到達(dá)時間新到達(dá)時間起飛機(jī)場到達(dá)機(jī)場飛機(jī)型號新飛機(jī)型號飛機(jī)尾號新飛機(jī)尾號延誤時間……〔4〕特別注意在該Excel總表格除外部文件名外，表格內(nèi)容中不能有參賽隊(duì)的任何信息，否那么會當(dāng)廢卷處理。另外需要指出，雖然好的算法設(shè)計應(yīng)該考慮到輸入數(shù)據(jù)的各種不同可能性，本賽題局限于求解附件里的具體案例。由于受到暴風(fēng)雪的影響，管理部門決定在2016年4月22日的18:00到21:00之間關(guān)閉機(jī)場OVS。在該時間段內(nèi)該機(jī)場不能起飛或降落任何航班，而該時間段之前的所有航班都處于正常狀態(tài)，該時間段之后機(jī)場可立即恢復(fù)正常起降。因此，原定在該日18:00至21:00之間〔不包括18：00和21：00這兩個時刻〕起降的所有航班都需要重新安排，而且它們的重新安排可能造成關(guān)閉后其它航班的重新安排。由于OVS機(jī)場的跑道限制，該機(jī)場每5分鐘最多能起飛5架飛機(jī)，同時降落5架飛機(jī)。例如在21:00-21:05之間〔不包括21:05時間點(diǎn)〕最多有5個起飛航班和5個降落航班，其起飛和降落時間都可以按21:00計算；在21:05-21:10之間〔不包括21:10時間點(diǎn)〕最多有5個起飛航班和5個降落航班，其起飛和降落時間都可以按21:05計算；以此類推。其它機(jī)場不需要考慮跑道限制。附件中給出了該航空公司在相關(guān)時間段內(nèi)所有航班方案、飛機(jī)和旅客信息。摘錄局部如下以便理解。航班數(shù)據(jù)〔Schedules〕例如航班唯一編號起飛時間到達(dá)時間起飛機(jī)場到達(dá)機(jī)場飛機(jī)型號飛機(jī)尾號……17477415014613417001461348120OVSLEH94109817477412414613510001461356760LEHOVS94109817477750614613939001461399900OVSFUK94109817477748214614032001461409500FUKOVS94109817477757414614134001461422400OVSKMM94109817477399614613255601461335280GAZOVS951098…飛機(jī)數(shù)據(jù)〔Aircrafts〕例如飛機(jī)尾號飛機(jī)型號最早可用時間最晚可用時間起點(diǎn)機(jī)場座位數(shù)……41098914613336001461426000OVS8751098914613255601461426000GAZ8732098914613306601461445800VOR8742098914613022201461424200OVS8782098914613264001461428400OVS8723098914613300001461444600QSM8714098914613268201461428700OVS8744098914613256201461423900OVS8764098914613238801461482400OVS8715098914613262201461510000OVS8775098914613237001461445800OVS87………………旅客數(shù)據(jù)〔Paxinfo〕例如旅客號航班唯一編號同行旅客數(shù)量1174777880141174781120142174773867721747781107317477840610317477771810417477770611417477794211………如果一個旅客號對應(yīng)多個記錄表示該旅客號搭乘多個聯(lián)程航班，例如旅客號1搭乘了航班174777880和航班174781120。如果一個旅客號只對應(yīng)一個記錄那么表示該旅客號只搭乘一個直飛航班。該數(shù)據(jù)只用于求解第四問。流控數(shù)據(jù)〔Airportclosures〕例如機(jī)場關(guān)閉開場時間關(guān)閉完畢時間OVS14613480001461358800第一問：不考慮旅客信息，若何重新規(guī)劃機(jī)型9〔不考慮其他機(jī)型〕的航班方案，制定起飛時間表〔給出延誤分鐘〕，使得所有原方案安排給機(jī)型9的航班盡可能不被取消，同時保證機(jī)型9的所有航班總體延誤時間最短此題可參考文獻(xiàn)【3】。第二問：不考慮旅客信息，假定同一機(jī)型的所有飛機(jī)的載客量一樣，其間航班調(diào)整沒有成本，但在不同機(jī)型間調(diào)整有成本。比方說飛機(jī)DIBPV屬于320機(jī)型，飛機(jī)COBPV屬于321機(jī)型，航班174774110原方案是安排給飛機(jī)DIBPV執(zhí)行，如果將174774110分配給飛機(jī)COBPV執(zhí)行那么需要產(chǎn)生額外的成本。假設(shè)此額外成本等價于航班延誤半小時〔置換和延誤有可能會同時發(fā)生，那么成本疊加〕。在這樣的假設(shè)下若何重新規(guī)劃飛機(jī)航班〔包括所有機(jī)型的所有航班〕，制定起飛時間表〔給出延誤分鐘〕使原方案航班盡可能不被取消，同時保證所有航班總體延誤時間最短第三問：進(jìn)一步考慮飛機(jī)的載客量，假設(shè)在不同機(jī)型間調(diào)整航班的成本除了航班本身延誤半小時外，還要加上不能登機(jī)旅客的成本〔這里仍不考慮旅客的聯(lián)程信息，即假定旅客行程都是直達(dá)的，并假設(shè)所有航班都是100%的上座率〕。比方飛機(jī)DIBPV的載客量是140人，COBPV的載客量是170人。如果將飛機(jī)COBPV的航班分給DIBPV去執(zhí)行，將會有30名旅客因沒有座位而無法登機(jī)。但如果將DIBPV的原方案航班分配給COBPV去執(zhí)行那么沒有這種情況。假設(shè)一名旅客無法登機(jī)與該旅客延誤2小時的成本相當(dāng)，該若何重新規(guī)劃航班以保證旅客總體延誤時間最短第四問：在第二題的根基上，假設(shè)在不同機(jī)型間調(diào)整航班不考慮成本。我們在旅客數(shù)據(jù)中提供了旅客的行程信息，包括旅客號，同行旅客數(shù)量，和相應(yīng)的航班。每個旅客行程中的相連航班間最少需要45分鐘間隔時間用于中轉(zhuǎn)，如23日的航班174778458〔02:05JOG—03:00OVS〕與23日的航班174777524(05:50OVS–08:10XVS)的間隔時間為2小時50分鐘。旅客的延誤按照旅客方案到達(dá)最終目的地時間為基準(zhǔn)計算。例如在案例中旅客號為6的旅客方案到達(dá)XVS時間是23日08:10，如果不晚于該時間到達(dá)那么延誤為0，如果到達(dá)XVS時間是23日08:40那么延誤時間是30分鐘，考慮旅客號為6的同行旅客數(shù)量為