2018年優(yōu)秀論文優(yōu)秀論文c題c10248117

1、 華為杯第十四屆中國(guó)研究生數(shù)學(xué)建模競(jìng)賽參賽（由組委會(huì)填寫）學(xué)校上海交通大學(xué)10248117參賽隊(duì)號(hào)1.陳熠畫隊(duì)員姓名2.吳倩3.李昱 參賽（由組委會(huì)填寫）應(yīng)用時(shí)空網(wǎng)絡(luò)模型解決不正常航班恢復(fù)問題題 目摘由于不可抗阻的自然因素、不可預(yù)測(cè)的突發(fā)要：或是管理手段的落后，會(huì)使得航班無法按原計(jì)劃出行。而飛機(jī)航班網(wǎng)絡(luò)涉及到多機(jī)型的航班、乘客、機(jī)組， 航班的延誤是一個(gè)牽一發(fā)而動(dòng)全身的系統(tǒng)工程問題，會(huì)影響成千上萬旅客的出行。至今，業(yè)界還很少有實(shí)際的應(yīng)用解決方案。 針對(duì)一個(gè)具體的航班恢復(fù)問題，本文進(jìn)行了建模求解。問題主要背景是由于受到暴風(fēng)雪的影響，在 2016 年 4 月 22 日的 18:00 到 21:00

2、之間關(guān)閉機(jī)場(chǎng) OVS。在該時(shí)間段內(nèi)該機(jī)場(chǎng)不能起飛或降落任何航班，需要合理安排飛機(jī)的起降、延誤甚至取消等措施以最小成本實(shí)現(xiàn)航班的恢復(fù)。 本文創(chuàng)造性地采用在時(shí)空網(wǎng)絡(luò)模型中引入飛機(jī)連續(xù)性的判斷來解決單機(jī)型、多機(jī)型的不正常航班恢復(fù)，結(jié)合該整數(shù)規(guī)劃模型，采用 Gurobi 優(yōu)化軟件進(jìn)行求解。 對(duì)于問題一，只考慮機(jī)型 9 的所有航班，在機(jī)型 9 的原定航班盡可能不被取消的前提下，不考慮旅客信息，保證機(jī)型 9 的所有航班總體延誤時(shí)間最短。我們調(diào)整航班分配，重新規(guī)劃?rùn)C(jī)型 9 的航班計(jì)劃，制定出合理的起飛時(shí)刻表。我們可以得到機(jī)型 9 的所有航班總體延誤時(shí)間最短為 1104 分鐘。 在問題一的基礎(chǔ)上，問題二需要考

3、慮不同機(jī)型是否可以進(jìn)行置換來盡可能縮 短所有航班的總體延誤時(shí)間，因此在目標(biāo)函數(shù)中增加了因機(jī)型置換產(chǎn)生的額外時(shí)間延誤項(xiàng)。不同機(jī)型之間的航班置換等價(jià)于航空延誤半個(gè)小時(shí)額外成本。我們?cè)诓豢紤]旅客信息，在不取消航班的前提下，我們優(yōu)先考慮同組機(jī)型之間的相互置換，同時(shí)考慮飛機(jī)之后執(zhí)行航班的可能延誤時(shí)間總和，合理安排航班與飛機(jī)置換， 重新規(guī)劃飛機(jī)航班，可以得到在 OVS 機(jī)場(chǎng)起飛或降落的所有航班總體延誤時(shí)間最短為12787 分鐘。 在問題三中添加了飛機(jī)的載客量因素，需要考慮旅客信息，假定旅客行程都是直達(dá)的，并假設(shè)所有航班都是 100%的上座率，假設(shè)在不同機(jī)型間調(diào)整航班的成本除了航班本身延誤半小時(shí)外，還要加上

4、不能登機(jī)旅客的成本，假設(shè)一名旅客無法登機(jī)與該旅客延誤 2 小時(shí)的成本相當(dāng)。因此在目標(biāo)函數(shù)中增加了因機(jī)型置換產(chǎn)生的額外旅客無法登機(jī)的時(shí)間延誤項(xiàng)。我們?cè)诓蝗∠桨嗟那疤嵯?，我們?yōu)先考慮同組機(jī)型之間的相互置換，同時(shí)考慮飛機(jī)之后執(zhí)行航班的可能延誤時(shí)間總和，合理安排航班與飛機(jī)置換，重新規(guī)劃飛機(jī)航班，可以得到在 OVS 機(jī)場(chǎng)起飛或降落的所有航班總體延誤時(shí)間最短為 2012620 分鐘。 在第四問中，假設(shè)在不同機(jī)型間調(diào)整航班不考慮成本，但在旅客數(shù)據(jù)中提供了旅客的行程信息，包括旅客號(hào)，同行旅客數(shù)量，和相應(yīng)的航班。每個(gè)旅客行程中的相連航班間最少需要 45 分鐘間隔時(shí)間用于中轉(zhuǎn)，旅客的延誤按照旅客計(jì)劃到達(dá)最終目的

5、地時(shí)間為基準(zhǔn)計(jì)算。我們靈活并合理調(diào)整航班和置換飛機(jī)，重新規(guī)劃在 OVS 起飛或降落的航班計(jì)劃，制定了新起飛時(shí)刻表，可以使所有航班總體延誤時(shí)間最短為 14303305 分鐘。 目錄問題重述1模型假設(shè)3符號(hào)說明與名詞解釋43.1 符號(hào)說明43.2 名詞解釋4問題一模型建立與提出6一二三四問題提出6問題分析6模型建立與求解64.3.1 模型建立64.3.2 模型求解7結(jié)論與分析84.4五問題二模型建立與提出問題提出9問題分析9模型建立與求解95.3.1 模型建立95.3.2 模型求解11結(jié)論與分析115.4六問題三模型建立與提出問題提出13

6、問題分析13模型建立與求解136.3.1 模型建立136.3.2 模型求解15結(jié)論與分析156.4七問題四模型建立與提出問題提出16問題分析16模型建立與求解167.3.1 模型建立167.3.2 模型求解18結(jié)論與分析187.4八總結(jié)20 問題重述隨著經(jīng)濟(jì)的發(fā)展，飛機(jī)已經(jīng)成為主要交通工具，航空出行已成為越來越多旅客的選擇。但飛機(jī)出行具有許多不確定性，由于種種因素，航班可能無法按原計(jì)劃出行。有不可抗阻的自然因素，如暴風(fēng)雪、颶風(fēng)等，有些是不可預(yù)測(cè)的突發(fā)，如突發(fā)恐怖、飛機(jī)機(jī)械故障等等，還有些是因?yàn)楣芾硎侄蔚穆浜螅热顼w行員缺位、空中管制。表 1 是 FlightStats 網(wǎng)

7、站公布的 2016 年 2 月份世界主要航空公司和部分中國(guó)航空公司航班準(zhǔn)點(diǎn)率的比較?？梢钥闯觯m然中國(guó)的航班準(zhǔn)點(diǎn)率很低，但其他國(guó)家和地區(qū)也不樂觀，比如美國(guó)本土的平均航班準(zhǔn)點(diǎn)率也只有77%。但眾所周知，飛機(jī)航班如果不能按原計(jì)劃執(zhí)行，不僅會(huì)給航空公司造成巨大的經(jīng)濟(jì)損失，同時(shí)還會(huì)給旅客出行帶來極大的不便。世界范圍內(nèi)，近年來快速增長(zhǎng)的航空旅客數(shù)量已超過了很多主要機(jī)場(chǎng)的容量，加上近年氣候的反常變化和安全突發(fā)的增多，航班恢復(fù)問題越來越受到各國(guó)民航管理機(jī)構(gòu)和各大航空公司的重視，中國(guó)主要航空公司也已經(jīng)把航班恢復(fù)的自動(dòng)化提到了議事日程上了。 所以，在盡量不取消航班的基礎(chǔ)上，如何減少經(jīng)濟(jì)損失是如今需要考慮的問題。

8、 表 1-1 2016 年 2 月份世界主要航空公司和部分中國(guó)航空公司航班準(zhǔn)點(diǎn)率 現(xiàn)在由于受到暴風(fēng)雪的影響，管理部門決定在 2016 年 4 月 22 日的 18:00 到 21:00 之間關(guān)閉機(jī)場(chǎng) OVS。在該時(shí)間段內(nèi)該機(jī)場(chǎng)不能起飛或降落任何航班，而該時(shí)間段之前的所有航班都處于正常狀態(tài)，該時(shí)間段之后機(jī)場(chǎng)可立即恢復(fù)正常起降。因此，原定在該日 18:00 至 21:00 之間（不包括 18：00 和 21：00 這兩個(gè)時(shí)刻）起降的所有航班都需要重新安排，而且它們的重新安排可能造成關(guān)閉后其它航班的重新安排。由于 OVS 機(jī)場(chǎng)的跑道限制，該機(jī)場(chǎng)每 5 分鐘最多能起飛 5 架飛機(jī)，同時(shí)降落 5 架飛機(jī)

9、。 需要研究以下問題： （1） 不考慮旅客信息，如何重新規(guī)劃?rùn)C(jī)型 9（不考慮其他機(jī)型）的航班計(jì)劃，制定起飛時(shí)間表（給出延誤分鐘），使得所有原計(jì)劃安排給機(jī)型 9 的航班盡可能不被取消，同時(shí)保證機(jī)型 9 的所有航班總體延誤時(shí)間最短？ （2） 不考慮旅客信息，假定同一機(jī)型的所有飛機(jī)的載客量相同，其間航班調(diào)整沒有成本，但在不同機(jī)型間調(diào)整有成本。比方說飛機(jī) DIBPV 屬于 320 機(jī)型， 飛機(jī) COBPV 屬于 321 機(jī)型，航班 174774110 原計(jì)劃是安排給飛機(jī) DIBPV 執(zhí)行， 如果將 174774110 分配給飛機(jī) COBPV 執(zhí)行則需要產(chǎn)生額外的成本。假設(shè)此額外成本等價(jià)于航班延誤半小時(shí)

10、（置換和延誤有可能會(huì)同時(shí)發(fā)生，則成本疊加）。在這樣的假設(shè)下如何重新規(guī)劃飛機(jī)航班（包括所有機(jī)型的所有航班），制定起飛時(shí)間表（給出延誤分鐘）使原計(jì)劃航班盡可能不被取消，同時(shí)保證所有航班總體延誤時(shí)間最短？ （3） 進(jìn)一步考慮飛機(jī)的載客量，假設(shè)在不同機(jī)型間調(diào)整航班的成本除了航班本身延誤半小時(shí)外，還要加上不能登機(jī)旅客的成本（這里仍不考慮旅客的聯(lián)程 1航空公司 名次 準(zhǔn)點(diǎn)率%航空公司 名次 準(zhǔn)點(diǎn)率%Iberia192.45United (美聯(lián)航)1981.99Singapore (新航)288.14%Cathy Pacific (國(guó)泰)3075.03Delta (美三角)387.54Air China (

11、國(guó)航)3866.55American (美航)686.2China Eastern (東航)3961.74 信息，即假定旅客行程都是直達(dá)的，并假設(shè)所有航班都是 100%的上座率）。比如飛機(jī) DIBPV 的載客量是 140 人，COBPV 的載客量是 170 人。如果將飛機(jī)COBPV 的航班分給 DIBPV 去執(zhí)行，將會(huì)有 30 名旅客因沒有座位而無法登機(jī)。但如果將 DIBPV 的原計(jì)劃航班分配給 COBPV 去執(zhí)行則沒有這種情況。假設(shè)一名旅客無法登機(jī)與該旅客延誤 2 小時(shí)的成本相當(dāng)，該如何重新規(guī)劃航班以保證旅客總體延誤時(shí)間最短？ （4）在第二題的基礎(chǔ)上，假設(shè)在不同機(jī)型間調(diào)整航班不考慮成本。我們

12、在旅客數(shù)據(jù)中提供了旅客的行程信息，包括旅客號(hào)，同行旅客數(shù)量，和相應(yīng)的航班。每個(gè)旅客行程中的相連航班間最少需要 45 分鐘間隔時(shí)間用于中轉(zhuǎn)，如 23 日的航班 174778458（02:05 JOG03:00 OVS）與 23 日的航班 174777524 (05:50 OVS 08:10 XVS) 的間隔時(shí)間為 2 小時(shí) 50 分鐘。旅客的延誤按照旅客計(jì)劃到達(dá)最終目的地時(shí)間為基準(zhǔn)計(jì)算。例如在案例中旅客號(hào)為 6 的旅客計(jì)劃到達(dá) XVS 時(shí)間是 23 日 08:10，如果不晚于該時(shí)間到達(dá)則延誤為 0，如果到達(dá) XVS 時(shí)間是 23 日 08:40 則延誤時(shí)間是 30 分鐘，考慮旅客號(hào)為 6 的同行

13、旅客數(shù)量為 8，則總體延誤時(shí)間是 8*30=240 分鐘。假定旅客號(hào)為 6 的旅客最終不能到達(dá)目的地相當(dāng)于總體延誤了 8*24 小時(shí)。該如何重新規(guī)劃航班以保證旅客總體延誤時(shí)間最短？如果某旅客號(hào)對(duì)應(yīng)的航班號(hào)在航班表里找不到相應(yīng)記錄則不需要考慮該旅客。如果某航班沒有對(duì)應(yīng)的旅客信息，可認(rèn)為該航班目前沒有乘客，則延誤該航班沒有成本代價(jià)。 2 二 模型假設(shè)根據(jù)題意，提出以下假設(shè)： 除暴風(fēng)雪影響造成OVS 機(jī)場(chǎng)在 2016 年 4 月 22 日 18:00 到 21:00 期間關(guān)閉之外，之后不考慮其他影響因素，如不可預(yù)測(cè)突發(fā)和管理手段落后等。 不考慮機(jī)場(chǎng)可停留飛機(jī)的容量，機(jī)場(chǎng)可 24 小時(shí)工作。OVS 機(jī)

14、場(chǎng)每 5 分鐘最多能起飛 5 架飛機(jī)，同時(shí)降落 5 架飛機(jī)，其他機(jī)場(chǎng)無跑道限制。 假設(shè)飛機(jī)的飛行時(shí)間不會(huì)因延誤而受影響。所有飛機(jī)的第一個(gè)航班的起飛機(jī)場(chǎng)與飛機(jī)的起點(diǎn)機(jī)場(chǎng)一致，航班的起飛時(shí)間不早于飛機(jī)的最早可用時(shí)間。所有飛機(jī)的最后一個(gè)航班的到達(dá)時(shí)間不能晚于飛機(jī)的最晚可用時(shí)間。 假設(shè)所有航班只能延誤，不能提前。最早起飛時(shí)間不能早于原計(jì)劃的起飛時(shí)間，且航班的起飛機(jī)場(chǎng)與飛機(jī)的起飛機(jī)場(chǎng)一致。每架飛機(jī)的連續(xù)航班的前一航班的到達(dá)機(jī)場(chǎng)與后一航班的起飛機(jī)場(chǎng)必須相同，而且前一航班到達(dá)時(shí)間與后一航班起飛時(shí)間之間的最小間隔時(shí)間為 45 分鐘。 假設(shè)航班延誤的決策時(shí)間點(diǎn)間隔為 5 分鐘。 假設(shè)有一起訂票并且行程完全一致的

15、旅客，他們共享同一個(gè)旅客號(hào)，并作為一個(gè)整體考慮，不能分乘不同的航班。 3 三 符號(hào)說明與名詞解釋3.1符號(hào)說明 T: 時(shí)間軸上所考慮時(shí)間點(diǎn)的集合 F: 所有航班的集合A: 所有飛機(jī)的集合P: 所有乘客的集合 Fp: 乘客 p 所乘航班的集合Fin : 到達(dá) OVS 機(jī)場(chǎng)的所有航班集合 Fout : 離開 OVS 機(jī)場(chǎng)的所有航班集合Finn :從機(jī)場(chǎng) n 出發(fā)到達(dá) OVS 機(jī)場(chǎng)的所有航班集合Foutn : 從 OVS 機(jī)場(chǎng)到 n 機(jī)場(chǎng)的所有航班集合Cf : 航班 f 的原載客量 CAf :航班 f 的現(xiàn)載客量dTf : 航班 f 的原計(jì)劃起飛時(shí)間Flyf : 航班 f 的飛行時(shí)間 Tf : 航班

16、 f 的所有可起飛時(shí)間集合Af :AP :航班 f 的運(yùn)營(yíng)飛機(jī)序號(hào) 與 OVS 機(jī)場(chǎng)有來往的機(jī)場(chǎng)合集Tin : 所有到達(dá) OVS 機(jī)場(chǎng)航班的降落時(shí)間 Tout : 所有離開 OVS 機(jī)場(chǎng)航班的起飛時(shí)間 flastP : 旅客 p 的最后一個(gè)航班序號(hào)dTflastP:NumP :旅客 p 原計(jì)劃起飛時(shí)間 旅客 p 的人數(shù) CancelCost : 取消航班 的成本 Xf : 0-1 變量，表示航班 f 是否取消，取消為 1Xft : 0-1 變量，表示航班 f 是否在 t 時(shí)刻起飛，起飛為 13.2名詞解釋 1、航班恢復(fù)問題：本質(zhì)上是運(yùn)營(yíng)恢復(fù)問題的一部分。或者說，廣義的航班恢復(fù)就是運(yùn)營(yíng)恢復(fù)，包括

17、（狹義的）航班恢復(fù)（Flight Recovery）、機(jī)組恢復(fù)（Crew4 Recovery）和旅客行程重新規(guī)劃（Passenger Re-accommodation）三部分，它們相互約束，構(gòu)成一個(gè)整體上超大規(guī)模的運(yùn)籌優(yōu)化問題。針對(duì)航班恢復(fù)問題，通常有三種航班調(diào)整方法：航班延誤、飛機(jī)置換和航班取消。航班延誤和飛機(jī)置換可以同時(shí)發(fā)生。 2、航班延誤：航班無法在原定的時(shí)間起飛，通常航空公司對(duì)延誤都有最大延誤時(shí)間約束，規(guī)定航班最大延誤時(shí)間為 5 小時(shí)，即延誤超過 5 小時(shí)時(shí)一定取消該航班。航班延誤的代價(jià)除了旅客滿意度降低外，更重要的是聯(lián)程旅客可能趕不上下趟航班。 3、飛機(jī)置換：將航班安排給不同于原計(jì)劃

18、執(zhí)行飛機(jī)的其他飛機(jī)去執(zhí)行。如按計(jì)劃，航班 1 連接航班 3 由飛機(jī) A 執(zhí)行，航班 2 連接航班 4 由飛機(jī) B 執(zhí)行。但由于延誤，飛機(jī) A 執(zhí)行完航班 1 后沒有足夠時(shí)間間隔，無法及時(shí)執(zhí)行航班 3。于是，調(diào)度員將航班 3 安排給飛機(jī) B，航班 4 安排給飛機(jī) A 去執(zhí)行。飛機(jī)置換并不需要在完全相同的飛機(jī)之間進(jìn)行，航空公司可以安排給滿足約束條件的任何其它飛機(jī)。飛機(jī)置換通常是最佳航班恢復(fù)方案，只要能滿足最小飛機(jī)間隔時(shí)間就行。但這種機(jī)會(huì)不總是存在。 4、航班取消：原定航班取消飛行。航班取消的代價(jià)最為嚴(yán)重，所以在解決航班恢復(fù)問題時(shí)需要盡可能不取消航班。 5 四 問題一模型建立與提出4.1 問題提出

19、由于受到暴風(fēng)雪的影響，OVS 機(jī)場(chǎng)不得不于 18:00 至 21:00 期間停飛所有航班，這不僅會(huì)給航空公司造成巨大的經(jīng)濟(jì)損失，同時(shí)還會(huì)給旅客出行帶來極大的不便。為了盡可能減少航空公司的損失和保證旅客的出行，問題一只考慮機(jī)型 9的所有航班，在機(jī)型 9 的原定航班盡可能不被取消的前提下，不考慮旅客信息， 保證機(jī)型 9 的所有航班總體延誤時(shí)間最短，我們需要靈活合理調(diào)整航班分配，重新規(guī)劃?rùn)C(jī)型 9 的航班計(jì)劃，制定出起飛時(shí)刻表。 4.2 問題分析 在 18:00 到 21:00 期間，OVS 機(jī)場(chǎng)將會(huì)關(guān)閉，因而在起期間原定機(jī)型 9 航班無法起飛，并且原定機(jī)型 9 航班因無法在 OVS 機(jī)場(chǎng)降落而停滯在

20、前一機(jī)場(chǎng)。當(dāng)21:00 后，機(jī)場(chǎng)正常開放時(shí)，需要解決航班恢復(fù)問題。對(duì)于在 OVS 機(jī)場(chǎng)起飛的航班，可合理考慮飛機(jī)置換，即考慮安排停在 OVS 機(jī)場(chǎng)的機(jī)型 9 的空閑飛機(jī)代替航班原定的未到機(jī)場(chǎng)的飛機(jī)執(zhí)行之前所延誤的原定航班飛行任務(wù)。對(duì)于在 OVS 機(jī)場(chǎng)降落的航班，需要考慮 OVS 機(jī)場(chǎng)跑道限制及降落的機(jī)型 9 飛機(jī)之后的航班執(zhí)行任務(wù)，合理安排停留在前一機(jī)場(chǎng)的飛機(jī)到達(dá)OVS 機(jī)場(chǎng)的時(shí)間。另外需考慮OVS 的起飛和降落時(shí)的跑道限制、最小飛機(jī)間隔時(shí)間、航班的連續(xù)性和航班延誤的最大時(shí)間等。 4.3 模型建立與求解4.3.1 模型建立 在求解的過程中，我們的目標(biāo)包括航班延誤成本和航班取消成本。模型的目標(biāo)是

21、使機(jī)場(chǎng)的總的延誤（到達(dá)延誤加上出發(fā)延誤）最小化。 目標(biāo)函數(shù)可設(shè)為： CancelCost f x f + (Tf - (1- x f )dTf ) Cf(4-1)minf Ff F在式（4-1）中，可設(shè) CancelCostf 為一最大整數(shù)。約束條件有： 1）航班是否取消ftx+ x= 1，f F(4-2)f tTf2）共計(jì) 16 架飛機(jī)0 Af 16,f F (4-3)6 3）如果航班取消，則 Tf=0t xtf = Tf , f FtTf(4-4)4）航班起飛時(shí)間為機(jī)型 9 飛機(jī)可用時(shí)間(1- x ) SAT T (1- x ) EAT , f F,SAT , EAT 為飛機(jī)可用時(shí)間 (4

22、-5)fafffafafaf5）由于 OVS 機(jī)場(chǎng)跑道限制，每 5 分鐘最多能起飛 5 架機(jī)型 9 飛機(jī)，同時(shí)降落 5 架機(jī)型 9 飛機(jī) NIi = 1 5T intTin T int/ 5=i(4-6)NOi =1 5TouttTout Toutt / 5=i6）Nian 為機(jī)型 9 飛機(jī) a 從 n 機(jī)場(chǎng)飛往 OVS 機(jī)場(chǎng)的次數(shù)Nian = (1- x f )(4-7)aA f FinnAf =a7）Noan 為機(jī)型 9 飛機(jī) a 從 OVS 機(jī)場(chǎng)飛往 n 機(jī)場(chǎng)的次數(shù)Noan = (1- x f )(4-8)aA f FoutnAf =a8）為保證航班的連續(xù)性，fin 和 fout 必須間

23、隔出現(xiàn)Nian - Noan 1,a A,n AP(4-9)= NoanNian , Nian(1- x )(1- x )-(1- x )(1- x ) =0, Ni No(4-10)fifofifoanfi Finn fo Foutnfi Finn fo FoutnanAfi =a Afo =a,Tfi Tfo9）為保證每架機(jī)型 9 飛機(jī)從降落和再次起飛之間間隔 45 分鐘Tfi + Flyt fi - Tfo 45, fi Finn , fi Foutn , Afi = a, Afo = a, a A, n AP(4-11)4.3.2 模型求解 模型既有二進(jìn)制，也有非二進(jìn)制的整數(shù)變量。在短

24、期流量管理中，通常情況 7 下是幾個(gè)小時(shí)范圍內(nèi)的航班調(diào)度問題。而且將時(shí)間劃分成若干時(shí)間段，每段約 5 分鐘，該模型是一個(gè)整數(shù)規(guī)劃模型。 本文建立了單機(jī)型的時(shí)空網(wǎng)絡(luò)模型，結(jié)合數(shù)學(xué)模型，采用 Gurobi 優(yōu)化軟件進(jìn)行求解。Gurobi 優(yōu)化軟件采用的是最新優(yōu)化技術(shù)，其充分利用了多核處理器的優(yōu)勢(shì)，采用方便輕巧的接口，可支持 C+, Java, Python, .Net 開發(fā)，可支持Windows, Linux, Mac OSX 支 持 AMPL 、 GAMS 、 AIMMS 和 Windows Solver Foundation 建模環(huán)境單一版本等平臺(tái)，具有較高的性價(jià)比，可方便各種需求，具有 Ma

25、tlab 的技術(shù)支持，Gurobi 提供中英文雙語技術(shù)支持，同時(shí)可支持多目標(biāo)處理，能夠靈活確定目標(biāo)優(yōu)先級(jí)并有效求解，可以更高效而便捷地建立數(shù)學(xué)模型， 可以直接輸入Min, Max, Abs, 邏輯條件（AND, OR）等約束，而不必人為轉(zhuǎn)換為線性約束1。 4.4 結(jié)論與分析 我們可得結(jié)果如附件 Excel 表格所示，不考慮旅客信息，不取消航班的前提下，我們可以得到機(jī)型 9 的所有航班總體延誤時(shí)間最短為 1104 分鐘。篩選出因OVS 機(jī)場(chǎng)在 18:00 到 21:00 關(guān)閉所造成的航班延誤數(shù)據(jù)，如圖 4-1 所示。 圖 4-1 因 OVS 機(jī)場(chǎng)在 18:00 到 21:00 關(guān)閉所造成的 9

26、機(jī)型航班延誤數(shù)據(jù) 如航班 174773380 原計(jì)劃在 18:01 分降落，但由于 OVS 機(jī)場(chǎng)關(guān)閉，所以航班 174773380 原定的尾號(hào) 64098 飛機(jī)只能在 18:14 分在 MJT 機(jī)場(chǎng)起飛并且推遲到 21:05 分在 OVS 機(jī)場(chǎng)降落，而 174773432 航班原計(jì)劃在 20:50 分由 OVS 機(jī)場(chǎng)起飛，為減少延誤時(shí)間，且 174773432 航班原定的尾號(hào) 64098 飛機(jī) 21:05 分在 OVS 機(jī)場(chǎng)降落，由于飛機(jī)降落與再次起飛之間時(shí)間間隔只少要 45 分鐘，所以可進(jìn)行飛機(jī)置換，考慮到尾號(hào) 46098 飛機(jī)在 15:37 分降落在 OVS 機(jī)場(chǎng)，所以可以將 174773

27、432 航班原定的尾號(hào) 64098 飛機(jī)置換為尾號(hào) 46098 飛機(jī)，由尾號(hào) 46098飛機(jī)執(zhí)行航班飛行任務(wù)。而之后尾號(hào) 46098 飛機(jī)在 21:50 分將要執(zhí)行航班 174773536 的飛行任務(wù)，這時(shí)尾號(hào) 64098 飛機(jī)已經(jīng)在 21:05 分降落在 OVS 機(jī)場(chǎng)，所以可以替換尾號(hào) 46098 飛機(jī)，執(zhí)行航班 174773536 的飛行任務(wù)。另外，需要注 意由于 OVS 機(jī)場(chǎng)的跑道限制，每 5 分鐘只能有 5 架飛機(jī)起飛和 5 架飛機(jī)降落。 在這種調(diào)整制度下，在不取消原計(jì)劃安排給機(jī)型 9 的航班的前提下，靈活并 合理調(diào)整航班和置換飛機(jī)，重新規(guī)劃?rùn)C(jī)型 9 的航班計(jì)劃，制定了新起飛時(shí)刻表，可

28、以使得機(jī)型 9 的所有航班總體延誤時(shí)間最短為 1104 分鐘。 8 五 問題二模型建立與提出5.1 問題提出 由于 OVS 機(jī)場(chǎng)在 18:00 至 21:00 關(guān)閉，該機(jī)場(chǎng)在此期間所有航班都將無法正常飛行，航班可由不同機(jī)型的飛機(jī)執(zhí)行飛行任務(wù)，所以合理的情況下可以考慮進(jìn)行不同機(jī)型航班之間置換，但不同航班之間進(jìn)行置換時(shí)會(huì)造成額外成本，由于不考慮旅客信息，在問題二中額外成本等價(jià)于航空延誤半個(gè)小時(shí)，同時(shí)置換和延誤可能同時(shí)發(fā)生，則成本將會(huì)疊加。假設(shè)同一機(jī)型的飛機(jī)之間相互置換時(shí)無額外成本，所以問題二需要在問題一的基礎(chǔ)上考慮不同機(jī)型是否可以進(jìn)行置換來盡可能縮短所有航班的總體延誤時(shí)間。 5.2 問題分析 在

29、18:00 到 21:00 期間，OVS 機(jī)場(chǎng)將會(huì)關(guān)閉，因而在起期間所有航班無法起飛，并且所有航班因無法在 OVS 機(jī)場(chǎng)降落而停滯在前一機(jī)場(chǎng)。當(dāng) 21:00 后，機(jī)場(chǎng)正常開放時(shí)，需要解決航班恢復(fù)問題。對(duì)于在 OVS 機(jī)場(chǎng)起飛的航班，可考慮飛機(jī)置換，即考慮安排停在 OVS 機(jī)場(chǎng)的同機(jī)型及不同機(jī)型的空閑飛機(jī)代替航班原定的未到機(jī)場(chǎng)的飛機(jī)執(zhí)行之前所延誤的原定航班飛行任務(wù)，但不同機(jī)型飛機(jī)置換時(shí)將會(huì)產(chǎn)生額外成本，所以，在飛機(jī)置換時(shí)需優(yōu)先考慮同組機(jī)型飛機(jī)之間是否可以置換，當(dāng)無法進(jìn)行置換時(shí)，再考慮當(dāng)合理安排航班起飛時(shí)間后，其所推遲時(shí)間， 即現(xiàn)在的起飛時(shí)間與可置換不同機(jī)型飛機(jī)的起飛時(shí)間之間是否會(huì)超過半小時(shí)，從而

30、進(jìn)行優(yōu)化。對(duì)于在 OVS 機(jī)場(chǎng)降落的航班，需要考慮 OVS 機(jī)場(chǎng)的跑道限制，同時(shí)需要考慮降落飛機(jī)之后的執(zhí)行任務(wù)及延誤時(shí)間，來合理安排停留在前一機(jī)場(chǎng)的飛機(jī)到達(dá)OVS 機(jī)場(chǎng)的時(shí)間。另外需考慮OVS 的起飛和降落時(shí)的跑道限制、航班的連續(xù)性、最小飛機(jī)間隔時(shí)間和航班延誤的最大時(shí)間等。 5.3 模型建立與求解5.3.1 模型建立 在求解的過程中，我們的目標(biāo)包括航班延誤成本，航班取消成本和置換不同機(jī)型的飛機(jī)時(shí)所產(chǎn)生的額外成本。在盡可能不取消原定航班的前提下，模型的目標(biāo)是使機(jī)場(chǎng)的總的延誤（到達(dá)延誤加上出發(fā)延誤）最小化。 目標(biāo)函數(shù)可設(shè)為： - (1 - x )dT ) C CancelCostf xf + (T

31、f fF + 30 Cf minfff fF fF Tyf TyAf (5-1)在式（5-1）中，可設(shè) CancelCostf 為一最大整數(shù)。約束條件有： 1）航班是否取消 9 ftx+ x= 1，f F(5-2)f tTf2）共計(jì) 151 架飛機(jī)0 Af 151, f F(5-3)3） 如果航班取消，則 Tf=0t xtf = Tf , f FtTf4） 航班起飛時(shí)間為飛機(jī)可用時(shí)間(5-4)(1- x ) SAT T (1- x ) EAT , f F,SAT ,EAT 為飛機(jī)可用時(shí)間(5-5)fafffafafaf5）由于 OVS 機(jī)場(chǎng)跑道限制，每 5 分鐘最多能起飛 5 架飛機(jī)，同時(shí)降落

32、 5 架飛機(jī) NIi = 1 5T intTin T int/ 5=i(5-6)NOi =1 5TouttTout Toutt / 5=i6）Nian 為飛機(jī) a 從 n 機(jī)場(chǎng)飛往 OVS 機(jī)場(chǎng)的次數(shù)Nian = (1- x f )(5-7)aA f FinnAf =a7）Noan 為飛機(jī) a 從 OVS 機(jī)場(chǎng)飛往 n 機(jī)場(chǎng)的次數(shù)Noan = (1- x f )(5-8)aA f FoutnAf =a8）為保證航班的連續(xù)性，fin 和 fout 必須間隔出現(xiàn)Nian - Noan 1,a A,n AP(5-9)= NoanNian , Nian(1- x )(1- x )-(1- x )(1-

33、 x ) =(5-10)0, Ni Nofifofifoanfi Finn fo Foutnfi Finn fo FoutnanAf i =a Af o =a,Tfi Tfo9）為保證每架飛機(jī)從降落和再次起飛之間間隔 45 分鐘Tfi + Flytfi - Tfo 45,fi Finn , fi Foutn , Afi = a, Afo = a, a A, n AP(5-11)10 5.3.2 模型求解 模型和問題一一樣，既有二進(jìn)制，也有非二進(jìn)制的整數(shù)變量。在短期流量管理中，通常情況下也是幾個(gè)小時(shí)范圍內(nèi)的航班調(diào)度問題。而且將時(shí)間劃分成若干時(shí)間段，每段約 5 分鐘，該模型是一個(gè)整數(shù)規(guī)劃模型。 本

34、文建立了單機(jī)型和多機(jī)型的時(shí)空網(wǎng)絡(luò)模型，結(jié)合數(shù)學(xué)模型，同樣采用 Gurobi 優(yōu)化軟件進(jìn)行求解。 5.4 結(jié)論與分析 我們可得結(jié)果如附件 Excel 表格所示，不考慮旅客信息，在不取消航班的前提下，我們優(yōu)先考慮同組機(jī)型之間的相互置換，同時(shí)考慮飛機(jī)之后執(zhí)行航班的可能延誤時(shí)間總和，合理安排航班與飛機(jī)置換，重新規(guī)劃飛機(jī)航班，可以得到在OVS 機(jī)場(chǎng)起飛或降落的所有航班總體延誤時(shí)間最短為 12787 分鐘。篩選并選取出因OVS 機(jī)場(chǎng)在 18:00 到 21:00 關(guān)閉所造成的航班延誤數(shù)據(jù)，部分如圖 5-1 所示。 圖 5-1 部分因OVS 機(jī)場(chǎng)在 18:00 到 21:00 關(guān)閉所造成的航班延誤數(shù)據(jù) 由圖

35、 5-1 所示，由于在問題 1 中涉及到飛機(jī)型號(hào) 9 的航班能夠很好地實(shí)現(xiàn)相同機(jī)型的航班置換，使得延誤時(shí)間都是由于 OVS 機(jī)場(chǎng)在 18:00 到 21:00 關(guān)閉而無法實(shí)現(xiàn)的飛機(jī)的起飛以及降落引起的“硬性”延誤時(shí)間，此延誤時(shí)間無法通過航班置換、航班取消等途徑取消。因此，在問題二中對(duì)于飛機(jī)型號(hào) 9 所涉及的航班延誤處理方案基本與問題 1 相同，除了因機(jī)場(chǎng)流量控制而產(chǎn)生的必要的合理飛機(jī)起降時(shí)間調(diào)整。相較而言，若某一飛機(jī)因 OVS 機(jī)場(chǎng)在 18:00 到 21:00 關(guān)閉而無法實(shí)現(xiàn)起飛或者降落的“硬性”延誤引起的該飛機(jī)后續(xù)延誤航班數(shù)越多，應(yīng)該給予其越高的起降優(yōu)先級(jí)，而實(shí)現(xiàn)所有航班總延誤時(shí)長(zhǎng)最短的計(jì)

36、算目標(biāo)。由于前序航班延誤而引起的同一飛機(jī)后續(xù)航班延誤可稱為“軟”延誤，此類延誤可以通過航班置換的方式達(dá)到最小化。在該問題中，對(duì)于原本由 32A 機(jī)型的尾號(hào)為 HSBQV 執(zhí)行的174773464 航班，其先序航班為 174774190，原定起降時(shí)間為 4/22/16 16:20至4/22/16 18:34。由于 OVS 機(jī)場(chǎng)在 18:00 到 21:00 關(guān)閉，其最早降落時(shí)間為 4/22/1621:00，而造成了 146 分鐘的硬性延誤時(shí)間。那么如果不進(jìn)行航班延誤，原定起降時(shí)間為 4/22/16 20:45 至 4/22/16 23:25 的 174773464 航班，必須在先序航班降 落后

37、45 分鐘才能起飛，則至少延誤至 4/22/16 21:45 起飛、4/23/16 0:25 降落。那么對(duì)于 174773464 航班的后續(xù)原定起降時(shí)間為 4/23/16 0:25 至 4/23/16 3:10 的 174777538 航班，至少需要推遲到 4/23/16 1:10 起飛。則 174773464航班會(huì)產(chǎn)生 60+45=105 分鐘的延誤。由圖 5-1 所示，采用 73H 機(jī)型的 DCBPV 航班來執(zhí)行 174773464、174777538 航班。由于 DCBPV 航班的先序航班已于 4/22/16 14:50 降落在 OVS 機(jī)場(chǎng)，故無需等待 45

38、分鐘，可使得 174773464 航班于 4/22/1621:00、4/22/16 23:40 降落，則后續(xù) 174777538 航班可按原計(jì)劃在 4/23/16 0:25 起飛。由于跨機(jī)型飛機(jī)置換成本為 30 分鐘，在此飛機(jī)置換方案下，174773464、174777538 航班僅產(chǎn)生 15+30+30=75 分鐘的延誤，要優(yōu)于不置換、僅延誤的航班恢復(fù)方案。 在這種調(diào)整制度下，靈活并合理調(diào)整航班和置換飛機(jī)，重新規(guī)劃在 OVS 起飛或降落的航班計(jì)劃，制定了新起飛時(shí)刻表，可以使所有航班總體延誤時(shí)間最短為12787 分鐘。 12 六 問題三模型建立與提出6.1 問題提出 由于 OVS 機(jī)場(chǎng)在 18

39、:00 至 21:00 關(guān)閉，該機(jī)場(chǎng)在此期間所有航班都將無法正常飛行，航班可由不同機(jī)型的飛機(jī)執(zhí)行飛行任務(wù)，所以合理的情況下可以考慮進(jìn)行不同機(jī)型航班之間置換，但不同航班之間進(jìn)行置換時(shí)會(huì)造成額外成本，由于添加了飛機(jī)的載客量因素，需要考慮旅客信息，假定旅客行程都是直達(dá)的，并假設(shè)所有航班都是 100%的上座率，假設(shè)在不同機(jī)型間調(diào)整航班的成本除了航班本身延誤半小時(shí)外，還要加上不能登機(jī)旅客的成本，在問題三中置換不同機(jī)型飛機(jī)所產(chǎn)生的額外成本同樣等價(jià)于航空延誤半個(gè)小時(shí)，同時(shí)置換和延誤可能同時(shí)發(fā)生， 則成本將會(huì)疊加，假設(shè)同一機(jī)型的飛機(jī)之間相互置換時(shí)無額外成本，因此相對(duì)于第二題，需另外考慮置換不同機(jī)型所產(chǎn)生的旅客

40、的成本。所以問題三需要在問題二的基礎(chǔ)上考慮不同機(jī)型進(jìn)行置換時(shí)產(chǎn)生的旅客成本，假設(shè)一名旅客無法登機(jī)與該旅客延誤 2 小時(shí)的成本相當(dāng)。 6.2 問題分析 在 18:00 到 21:00 期間，OVS 機(jī)場(chǎng)將會(huì)關(guān)閉，因而在起期間所有航班無法起飛，并且所有航班因無法在 OVS 機(jī)場(chǎng)降落而停滯在前一機(jī)場(chǎng)。當(dāng) 21:00 后，機(jī)場(chǎng)正常開放時(shí)，需要解決航班恢復(fù)問題。對(duì)于在 OVS 機(jī)場(chǎng)起飛的航班，可考慮飛機(jī)置換，即考慮安排停在 OVS 機(jī)場(chǎng)的同機(jī)型及不同機(jī)型的空閑飛機(jī)代替航班原定的未到機(jī)場(chǎng)的飛機(jī)執(zhí)行之前所延誤的原定航班飛行任務(wù)，但不同機(jī)型飛機(jī)置換時(shí)將會(huì)產(chǎn)生額外成本，且不同機(jī)型發(fā)生置換時(shí)由于兩種機(jī)型的載客量不

41、同，會(huì)引起部分乘客由于沒有座位而無法登機(jī)。比如飛機(jī) DIBPV 的載客量是 140 人， COBPV 的載客量是 170 人。如果將飛機(jī) COBPV 的航班分給 DIBPV 去執(zhí)行，將會(huì)有30 名旅客因沒有座位而無法登機(jī)。但如果將DIBPV 的原計(jì)劃航班分配給COBPV 去執(zhí)行則沒有這種情況。所以，在飛機(jī)置換時(shí)需優(yōu)先考慮同組機(jī)型飛機(jī)之間是否可以置換，當(dāng)無法進(jìn)行置換時(shí)，再考慮是否要進(jìn)行不同機(jī)型的置換，或是直接選擇延誤每個(gè)后續(xù)航班從而進(jìn)行優(yōu)化。對(duì)于在 OVS 機(jī)場(chǎng)降落的航班，需要考慮 OVS 機(jī)場(chǎng)的跑道限制，同時(shí)需要考慮降落飛機(jī)之后的執(zhí)行任務(wù)及延誤時(shí)間，來合理安排停留在前一機(jī)場(chǎng)的飛機(jī)到達(dá) OVS

42、機(jī)場(chǎng)的時(shí)間。另外需考慮 OVS 的起飛和降落時(shí)的跑道限制、航班的連續(xù)性、最小飛機(jī)間隔時(shí)間和航班延誤的最大時(shí)間等。 6.3 模型建立與求解6.3.1 模型建立 在求解的過程中，我們的目標(biāo)包括航班延誤成本和航班取消成本。模型的目標(biāo)是使機(jī)場(chǎng)的總的延誤（到達(dá)延誤加上出發(fā)延誤）最小化。 目標(biāo)函數(shù)可設(shè)為： minCancelCosft xf + (Tf - (1 - xf)dTf) Cf +30 Cf + 120 (Cf - CAf)fFfFfF TyfTyAffF CfCAf (6-1)13 在式（6-1）中，可設(shè) CancelCostf 為一最大整數(shù)。約束條件有： 1）航班是否取消 ftx+ x= 1

43、，f F(6-2)f tTf2）共計(jì) 151 架飛機(jī)0 Af 151, f F(6-3)3）如果航班取消，則 Tf=0t xtf = Tf , f FtTf(6-4)4）航班起飛時(shí)間為飛機(jī)可用時(shí)間(1- x ) SAT T (1- x ) EAT , f F,SAT, EAT 為飛機(jī)可用時(shí)間 (6-5)fafffafafaf5）由于 OVS 機(jī)場(chǎng)跑道限制，每 5 分鐘最多能起飛 5 架飛機(jī)，同時(shí)降落 5 架飛機(jī) NIi = 1 5T intTin T int/ 5=i(6-6)NOi =1 5TouttTout Toutt / 5=i6）Nian 為飛機(jī) a 從 n 機(jī)場(chǎng)飛往 OVS 機(jī)場(chǎng)的次

44、數(shù)Nian = (1- x f )(6-7)aA f FinnAf =a7）Noan 為飛機(jī) a 從 OVS 機(jī)場(chǎng)飛往 n 機(jī)場(chǎng)的次數(shù)Noan = (1- x f )(6-8)aA f FoutnAf =a8）為保證航班的連續(xù)性，fin 和 fout 必須間隔出現(xiàn)Nian - Noan 1,a A,n AP(6-9)14 = NoanNian , Nian(1- x )(1- x )-(1- x )(1- x ) =(6-10)0, Ni Nofifofifoanfi Finn fo Foutnfi Finn fo FoutnanAfi =a Afo =a,Tfi Tfo9）為保證每架飛機(jī)從降

45、落和再次起飛之間間隔 45 分鐘Tfi + Flyt fi - Tfo 45, fi Finn , fi Foutn , Afi = a, Afo = a, a A, n AP(6-11)6.3.2 模型求解 模型既有二進(jìn)制，也有非二進(jìn)制的整數(shù)變量。在短期流量管理中，通常情況下是幾個(gè)小時(shí)范圍內(nèi)的航班調(diào)度問題。而且將時(shí)間劃分成若干時(shí)間段，每段約 5 分鐘，該模型是一個(gè)整數(shù)規(guī)劃模型。 本文建立了單機(jī)型的時(shí)空網(wǎng)絡(luò)模型，結(jié)合數(shù)學(xué)模型，采用 Gurobi 優(yōu)化軟件進(jìn)行求解。 6.4 結(jié)論與分析 我們可得結(jié)果如附件 Excel 表格所示，在不取消航班的前提下，我們優(yōu)先考慮同組機(jī)型之間的相互置換，同時(shí)考慮飛

46、機(jī)之后執(zhí)行航班的可能延誤時(shí)間總和， 合理安排航班與飛機(jī)置換，重新規(guī)劃飛機(jī)航班，可以得到在 OVS 機(jī)場(chǎng)起飛或降落的所有航班總體延誤時(shí)間最短為 2012620 分鐘。篩選并選取出因 OVS 機(jī)場(chǎng)在18:00 到 21:00 關(guān)閉所造成的航班延誤數(shù)據(jù)，部分如圖 6-1 所示。 圖 6-1 部分因OVS 機(jī)場(chǎng)在 18:00 到 21:00 關(guān)閉所造成的航班延誤數(shù)據(jù) 在 5.4 中提及的采用 73H 機(jī)型的DCBPV 航班來執(zhí)行原本由 32A 機(jī)型的尾號(hào)HSBQV 飛機(jī)的 174773464、174777538 航班，但由于 73H 機(jī)型和 32A 機(jī)型的座位數(shù)都是 158 座，因此此跨機(jī)型航班置換不

47、會(huì)產(chǎn)生額外的旅客沒有座位而無法登機(jī)的延誤。在圖 6-1 中涉及到的其他航班都是同機(jī)型置換，且與圖 5-1 中所給出的結(jié)果類似，僅多加考慮了機(jī)型的座位數(shù)，以及按每個(gè)航班都滿載情況下旅客的總延誤時(shí)間，故不再贅述。 15 七 問題四模型建立與提出7.1 問題提出 在 OVS 機(jī)場(chǎng) 18:00 至 21:00 關(guān)閉期間，該機(jī)場(chǎng)在此期間所有航班都將無法正常飛行，航班可由不同機(jī)型的飛機(jī)執(zhí)行飛行任務(wù)，所以合理的情況下可以考慮進(jìn)行不同機(jī)型航班之間置換，在第四問中，假設(shè)在不同機(jī)型間調(diào)整航班不考慮成本， 但在旅客數(shù)據(jù)中提供了旅客的行程信息，包括旅客號(hào)，同行旅客數(shù)量，和相應(yīng)的航班。每 個(gè)旅客行程中的相連航班間最少需

48、要 45 分鐘間隔時(shí)間用于中轉(zhuǎn)，旅客的延誤按照旅客計(jì)劃到達(dá)最終目的地時(shí)間為基準(zhǔn)計(jì)算。如果某旅客號(hào)對(duì)應(yīng)的航班號(hào)在航班表里找不到相應(yīng)記錄則不需要考慮該旅客。如果某航班沒有對(duì)應(yīng)的旅客信息，可認(rèn)為該航班目前沒有乘客，則延誤該航班沒有成本代價(jià)。在考慮旅客信息的條件下，不考慮置換飛機(jī)產(chǎn)生的額外成本。假設(shè)飛機(jī)之間相互置換時(shí)無額外成本，所以問題四需要考慮旅客數(shù)據(jù)中提供的旅客的行程信息，包括旅客號(hào)，同行旅客數(shù)量，和相應(yīng)的航班，考慮旅客的延誤時(shí)間。 7.2 問題分析 在 18:00 到 21:00 期間，OVS 機(jī)場(chǎng)將會(huì)關(guān)閉，因而在起期間所有航班無法起飛，并且所有航班因無法在 OVS 機(jī)場(chǎng)降落而停滯在前一機(jī)場(chǎng)。當(dāng)

49、 21:00 后，機(jī)場(chǎng)正常開放時(shí)，需要解決航班恢復(fù)問題。對(duì)于在 OVS 機(jī)場(chǎng)起飛的航班，可考慮飛機(jī)置換，即考慮安排停在 OVS 機(jī)場(chǎng)的同機(jī)型及不同機(jī)型的空閑飛機(jī)代替航班原定的未到機(jī)場(chǎng)的飛機(jī)執(zhí)行之前所延誤的原定航班飛行任務(wù)，此問題中不同機(jī)型飛機(jī)置換時(shí)不考慮額外成本。但在此問題中需要考慮旅客問題，在旅客數(shù)據(jù)中提供了旅客的行程信息，包括旅客號(hào)，同行旅客數(shù)量，和相應(yīng)的航班。每個(gè)旅客行程中的相連航班間最少需要 45 分鐘間隔時(shí)間用于中轉(zhuǎn)，旅客的延誤按照旅客計(jì)劃到達(dá)最終目的地時(shí)間為基準(zhǔn)計(jì)算。如果某旅客號(hào)對(duì)應(yīng)的航班號(hào)在航班表里找不到相應(yīng)記錄則不需要考慮該旅客。如果某航班沒有對(duì)應(yīng)的旅客信息，可認(rèn)為該航班目前沒

50、有乘客，則延誤該航班沒有成本代價(jià)。在考慮旅客信息的條件下，不考慮置換飛機(jī)產(chǎn)生的額外成本。由于 OVS 機(jī)場(chǎng)在 18:00 到 21:00 關(guān)閉期間，引起的延誤航班會(huì)使得乘坐該航班的旅客推遲降落在機(jī)場(chǎng)的時(shí)間，由于旅客趕不上飛機(jī)的后果巨大，故應(yīng)盡可能安排旅客在合理延誤時(shí)間內(nèi)坐上后續(xù)航班。因此旅客乘坐的后序航班需在前序航班延誤的影響下發(fā)生相對(duì)應(yīng)的延誤，而此延誤會(huì)引起該飛機(jī)的后序航班延誤，在某些情況下會(huì)產(chǎn)生較大的連鎖影響。對(duì)于在 OVS 機(jī)場(chǎng)降落的航班，需要考慮 OVS 機(jī)場(chǎng)的跑道限制，同時(shí)需要考慮降落飛機(jī)之后的執(zhí)行任務(wù)及延誤時(shí)間，來合理安排停留在前一機(jī)場(chǎng)的飛機(jī)到達(dá) OVS 機(jī)場(chǎng)的時(shí)間。另外需考慮 O

51、VS 的起飛和降落時(shí)的跑道限制、航班的連續(xù)性、最小飛機(jī)間隔時(shí)間和航班延誤的最大時(shí)間等。 7.3 模型建立與求解 7.3.1 模型建立 在求解的過程中，我們的目標(biāo)包括航班延誤成本和航班取消成本。模型的目標(biāo)是使機(jī)場(chǎng)的總的延誤（到達(dá)延誤加上出發(fā)延誤）最小化。 目標(biāo)函數(shù)可設(shè)為： 16- () CancelCost f x f + Nump (Tflast1- x flast dTflastp(7-1)minppf Ff F在式（7-1）中，可設(shè) CancelCostf 為一最大整數(shù)。約束條件有： 1）航班是否取消ftx+ x= 1，f F(7-2)f tTf2）共計(jì) 151 架飛機(jī)0 Af 151,

52、f F(7-3)3）如果航班取消，則 Tf=0t xtf = Tf , f FtTf(7-4)4）航班起飛時(shí)間為飛機(jī)可用時(shí)間(1- x ) SAT T (1- x ) EAT , f F,SAT, EAT 為飛機(jī)可用時(shí)間(7-5)fafffafafaf5）由于 OVS 機(jī)場(chǎng)跑道限制，每 5 分鐘最多能起飛 5 架飛機(jī)，同時(shí)降落 5 架飛機(jī) NIi = 1 5T intTin T int/ 5=i(7-6)NOi =1 5TouttTout Toutt / 5=i6）Nian 為飛機(jī) a 從 n 機(jī)場(chǎng)飛往 OVS 機(jī)場(chǎng)的次數(shù)Nian = (1- x f )(7-7)aA f FinnAf =a7

53、）Noan 為飛機(jī) a 從 OVS 機(jī)場(chǎng)飛往 n 機(jī)場(chǎng)的次數(shù)Noan = (1- x f )(7-8)aA f FoutnAf =a17 8）為保證航班的連續(xù)性，fin 和 fout 必須間隔出現(xiàn)Nian - Noan 1,a A,n AP(7-9)= Noan) = Nian , Nian(1- x )(1- x )-(1- x )(1-x0, Ni No(7-10)fifofifoanfi Finn fo Foutnfi Finn fo FoutnanAfi =a Afo =a,Tfi Tfo9）為保證每架飛機(jī)從降落和再次起飛之間間隔 45 分鐘Tfi + Flyt fi - Tfo 45, fi Finn , fi Foutn , Afi = a, Afo = a, a A, n AP(7-11)10）中轉(zhuǎn)時(shí)間Tf 1 - (Tf 1 + Flyt f 2 ) 45，p P, f1 Fp , f2 Fp , f1 f2(7-12)11）由于旅客無法到達(dá)目的地的延誤代價(jià)過高，故不考慮不同機(jī)型的置換，添加約束 f F, CA = Cff(7-13)7.3.2 模型求解 模型既有二進(jìn)制，也有非二進(jìn)制的整數(shù)變量。在短期流量管理中，通常情況下是幾個(gè)小時(shí)范圍內(nèi)的航班調(diào)度問題。而且將時(shí)間劃分成若干時(shí)間段，每段約 5 分鐘，該模型是