方杰博士學(xué)位論文答辯課件

2024/8/18精選課件ppt1突發(fā)情況下應(yīng)急運(yùn)力調(diào)度理論與方法研究

答辯人：方杰指導(dǎo)教師：夏洪山教授

2024/8/18精選課件ppt2概述2應(yīng)急運(yùn)力調(diào)度問(wèn)題34剩余運(yùn)力調(diào)度問(wèn)題應(yīng)急運(yùn)力回歸調(diào)度問(wèn)題1目錄5工作總結(jié)與展望2024/8/18精選課件ppt3主要研究?jī)?nèi)容研究方法及技術(shù)路線國(guó)內(nèi)外研究現(xiàn)狀研究的目的及意義概述1相關(guān)的概念2024/8/18精選課件ppt4研究的目的及意義“十一五”期間，我國(guó)民航運(yùn)輸總周轉(zhuǎn)量年均增長(zhǎng)率達(dá)15.6％，位居世界第二民航運(yùn)輸大國(guó)。伴隨著飛機(jī)數(shù)目的增多，航班量地增大，民航日常運(yùn)營(yíng)過(guò)程中受到各種突發(fā)情況，如災(zāi)害性天氣、地震、軍運(yùn)和國(guó)際政治等諸多因素需要緊急處置影響的情況日益增多。在這種情況下，就必須根據(jù)實(shí)時(shí)地航班資源分布，對(duì)原有運(yùn)力計(jì)劃進(jìn)行調(diào)整，既要保障新的處突飛行任務(wù)的迅速執(zhí)行，同時(shí)也要保證運(yùn)力調(diào)整后原有航班計(jì)劃的繼續(xù)執(zhí)行。2024/8/18精選課件ppt5與航班運(yùn)行調(diào)度的技術(shù)和概念的區(qū)別飛機(jī)排班和機(jī)組編排是在航班計(jì)劃確定后進(jìn)行的調(diào)度編排，計(jì)劃的編排過(guò)程有充分的時(shí)間進(jìn)行最合理的資源優(yōu)化配置。而在突發(fā)情況下的應(yīng)急調(diào)度由于突發(fā)事件的時(shí)間突然性與事件隨機(jī)性，航空公司必須根據(jù)政府的征召立即中斷部分正常航班計(jì)劃的執(zhí)行，抽調(diào)適合應(yīng)急要求的飛機(jī)（如高原飛行、遠(yuǎn)程、大載重量、例行維修方便等）和機(jī)組人員（特殊環(huán)境下的飛行技術(shù)、航路熟悉程度、通訊語(yǔ)言等），投入到處理突發(fā)事件的應(yīng)急行動(dòng)中。在運(yùn)力調(diào)度計(jì)劃生成并執(zhí)行時(shí)，航空公司就需要根據(jù)調(diào)度后剩余運(yùn)力資源分布的具體情況和現(xiàn)有航班計(jì)劃的執(zhí)行情況，對(duì)飛機(jī)和機(jī)組等資源重新進(jìn)行合理的調(diào)度配置。2024/8/18精選課件ppt6與“不正常航班恢復(fù)”概念的區(qū)別2024/8/18精選課件ppt7民航業(yè)是技術(shù)密集和資金密集型產(chǎn)業(yè)，又是社會(huì)公益型產(chǎn)業(yè)，整體關(guān)聯(lián)性強(qiáng)?，F(xiàn)代民用航空企業(yè)最為注重安全和高效的運(yùn)行管理，在日常運(yùn)行過(guò)程中，只有將航班時(shí)刻、飛機(jī)和機(jī)組等資源以合理的方式組合配置使用，才能夠保證企業(yè)的經(jīng)濟(jì)效益，維持企業(yè)的穩(wěn)定發(fā)展。從國(guó)外引進(jìn)的航班運(yùn)控系統(tǒng)的“航班恢復(fù)功能”模塊，如果按照應(yīng)急運(yùn)力抽調(diào)后的剩余運(yùn)力情況，重新編排運(yùn)力飛行計(jì)劃，無(wú)法評(píng)估和優(yōu)化抽調(diào)的運(yùn)力對(duì)航班的影響，也無(wú)法協(xié)調(diào)應(yīng)急運(yùn)力與剩余運(yùn)力之間的平衡關(guān)系。對(duì)應(yīng)急運(yùn)力調(diào)度主要是依靠緊急抽調(diào)有經(jīng)驗(yàn)的運(yùn)控人員人工編排和調(diào)整。在應(yīng)急時(shí)間緊迫情況下，通常以犧牲航班效益為代價(jià)首先滿足應(yīng)急任務(wù)要求，若因抽調(diào)運(yùn)力影響而又無(wú)法調(diào)整的航班，通常是將航班取消、合并或延誤，這必然給航空公司帶來(lái)經(jīng)濟(jì)損失和旅客不滿。2024/8/18精選課件ppt8相關(guān)概念關(guān)于“突發(fā)情況”的描述根據(jù)《中華人民共和國(guó)突發(fā)事件應(yīng)對(duì)法》的規(guī)定，所謂突發(fā)事件，是指突然發(fā)生，造成或者可能造成嚴(yán)重社會(huì)危害，需要采取應(yīng)急處置措施予以應(yīng)對(duì)的自然災(zāi)害、事故災(zāi)難、公共衛(wèi)生事件和社會(huì)安全事件。自然災(zāi)害搶險(xiǎn)救災(zāi)、地區(qū)撤僑緊急事件、戰(zhàn)爭(zhēng)軍運(yùn)2024/8/18精選課件ppt9應(yīng)急運(yùn)力調(diào)度技術(shù)一套預(yù)案，一套機(jī)制，一套系統(tǒng)系統(tǒng)地對(duì)飛機(jī)和機(jī)組可用資源的調(diào)度，可以盡可能地實(shí)現(xiàn)救災(zāi)運(yùn)輸任務(wù)，又不影響航空公司正常的航班計(jì)劃。盡可能地動(dòng)員相關(guān)人力資源，力求能夠在最短的時(shí)間內(nèi)做出反應(yīng)，以最快的速度將任意地點(diǎn)的相關(guān)航空公司的飛機(jī)投入到理想的區(qū)域之中。在突發(fā)情況發(fā)生，需要完成軍演軍運(yùn)、地震緊急救援等突發(fā)事件處置運(yùn)輸任務(wù)時(shí)，緊急中斷原航班計(jì)劃的執(zhí)行，進(jìn)行機(jī)組和飛機(jī)資源重新配置，安排資源進(jìn)行應(yīng)急運(yùn)輸任務(wù)，同時(shí)完成后續(xù)的航班任務(wù)。人工臨時(shí)進(jìn)行手工調(diào)整帶有主觀性、耗時(shí)長(zhǎng)、準(zhǔn)確性差、很容易出現(xiàn)錯(cuò)誤，保證運(yùn)行安全的前提下以及最小代價(jià)的基礎(chǔ)上進(jìn)行資源的調(diào)度，使得機(jī)組和飛機(jī)資源能夠充分得到利用，這對(duì)于處于激烈市場(chǎng)競(jìng)爭(zhēng)的航空企業(yè)來(lái)說(shuō)十分的重要，同時(shí)也保證了突發(fā)事件處置運(yùn)輸航班任務(wù)的快速安全執(zhí)行。針對(duì)性強(qiáng)，遇到相應(yīng)問(wèn)題的時(shí)候效果明顯，但是，在對(duì)時(shí)間要求十分苛刻的運(yùn)行環(huán)境下，預(yù)案執(zhí)行的效果往往大打折扣，不能合理利用和調(diào)度相關(guān)的航班資源，同時(shí)又造成航班計(jì)劃資源利用的大量浪費(fèi)。2024/8/18精選課件ppt10應(yīng)急運(yùn)力調(diào)度應(yīng)能夠在資源配置上實(shí)現(xiàn)的自動(dòng)化和最優(yōu)化，從而區(qū)分開了我國(guó)與歐美在運(yùn)行管理上的不同，更加符合我國(guó)的國(guó)情，彌補(bǔ)了國(guó)內(nèi)在突發(fā)事件應(yīng)急調(diào)度相關(guān)研究的不足，在理論和實(shí)踐上都具有很高的創(chuàng)新性和研究?jī)r(jià)值。2024/8/18精選課件ppt11國(guó)內(nèi)外研究現(xiàn)狀飛機(jī)排班和機(jī)組排班問(wèn)題航班計(jì)劃編排飛機(jī)編排維修計(jì)劃管理機(jī)組編排不正常航班恢復(fù)問(wèn)題飛機(jī)恢復(fù)機(jī)組恢復(fù)乘客恢復(fù)代表性成果

YuGang等人主持研制的美國(guó)大陸航空公司的CrewSolver決策支持系統(tǒng)，但是這些系統(tǒng)只用于解決突發(fā)性大面積航班延誤的恢復(fù)問(wèn)題2024/8/18精選課件ppt12主要研究?jī)?nèi)容在航空公司日常航班計(jì)劃實(shí)際運(yùn)營(yíng)過(guò)程中，突發(fā)事件隨時(shí)可能發(fā)生，這就需要安排合適的運(yùn)力資源去完成處置運(yùn)輸任務(wù)。同時(shí)，由于航空公司運(yùn)力資源的調(diào)度，勢(shì)必造成原航班計(jì)劃、實(shí)施航班計(jì)劃的飛機(jī)計(jì)劃和機(jī)組計(jì)劃不能繼續(xù)執(zhí)行下去。在突發(fā)事件的處置過(guò)程中，民航相關(guān)單位不僅需要依法履行相關(guān)的責(zé)任和義務(wù)，根據(jù)政府的要求和征召，抽調(diào)符合相關(guān)適航要求的飛機(jī)資源和具備相關(guān)執(zhí)飛資格的機(jī)組資源，執(zhí)行處置突發(fā)事件運(yùn)輸任務(wù)。航空公司還必須快捷有效地根據(jù)當(dāng)時(shí)實(shí)際航班資源配置情況（剩余飛機(jī)和機(jī)組的數(shù)量和分布）重新組織機(jī)組和飛機(jī)等資源，繼續(xù)維持調(diào)整后的航班計(jì)劃的執(zhí)行，這就是應(yīng)急運(yùn)力調(diào)度的主要內(nèi)容。2024/8/18精選課件ppt13問(wèn)題之一：應(yīng)急運(yùn)力調(diào)度問(wèn)題問(wèn)題之二：剩余運(yùn)力調(diào)度問(wèn)題問(wèn)題之三：應(yīng)急運(yùn)力回歸調(diào)度問(wèn)題主要研究?jī)?nèi)容2024/8/18精選課件ppt14技術(shù)路線2024/8/18精選課件ppt15應(yīng)急運(yùn)力調(diào)度問(wèn)題研究22.1應(yīng)急飛機(jī)調(diào)度問(wèn)題2.3本章小結(jié)2.2應(yīng)急機(jī)組調(diào)度問(wèn)題2024/8/18精選課件ppt162.1.1應(yīng)急飛機(jī)調(diào)度問(wèn)題的描述高度優(yōu)化的運(yùn)力計(jì)劃（包括航班計(jì)劃、飛機(jī)計(jì)劃以及機(jī)組計(jì)劃）在突發(fā)情況下其魯棒性顯得極其脆弱。在原先支撐航班運(yùn)行最主要的運(yùn)力飛機(jī)資源和機(jī)組資源被抽調(diào)后，航空公司運(yùn)控中心調(diào)度人員對(duì)運(yùn)力計(jì)劃做出的調(diào)整大多是被迫直接取消相關(guān)航班。當(dāng)突發(fā)情況發(fā)生的時(shí)候，各種計(jì)劃都需要進(jìn)行相應(yīng)的重新修改。根據(jù)實(shí)際情況，航班計(jì)劃和飛機(jī)計(jì)劃一般分開進(jìn)行重新排班。這樣就造成了重新編排的飛機(jī)計(jì)劃可能不滿足新的航班計(jì)劃需求。給航空公司造成了不可估量的效益損失。2024/8/18精選課件ppt17應(yīng)急飛機(jī)調(diào)度流程圖2024/8/18精選課件ppt182.1.2約束分析和網(wǎng)絡(luò)圖的構(gòu)建（1）機(jī)型。（2）數(shù)量。（3）檢修條件。（4）飛行路徑。（5）對(duì)航班計(jì)劃的影響。（6）應(yīng)急飛機(jī)的調(diào)度的目的是使調(diào)度的飛機(jī)運(yùn)力所做出的調(diào)整所產(chǎn)生的總成本最低。參數(shù)定義3個(gè)集合----飛機(jī)集合：；機(jī)場(chǎng)集合：；航班集合：。

2024/8/18精選課件ppt20應(yīng)急飛機(jī)調(diào)度時(shí)空網(wǎng)絡(luò)圖2024/8/18精選課件ppt212.1.3應(yīng)急飛機(jī)調(diào)度問(wèn)題數(shù)學(xué)模型2024/8/18精選課件ppt22解限制主問(wèn)題的基本步驟為：Step1選擇一條最短飛機(jī)路徑加入至限制主問(wèn)題中，為保證限制主問(wèn)題有解，飛機(jī)路徑唯一性約束式（3.8）加入人工變量

，同時(shí)，航班覆蓋唯一性約束式（3.7）由于已存在變量

，則可將

和

同時(shí)作為初始基變量生成。Step2由改進(jìn)單純形法求解該限制主問(wèn)題。2.1.4算法與求解2024/8/18精選課件ppt23Step3（子問(wèn)題求解）根據(jù)求解生成的基的逆C以及基變量對(duì)應(yīng)的航班和飛機(jī)成本

，生成網(wǎng)絡(luò)圖中每個(gè)航班和飛機(jī)相對(duì)應(yīng)的對(duì)偶變量

，采用深度優(yōu)先搜索算法，生成最短路徑（最小簡(jiǎn)約成本）：2024/8/18精選課件ppt24Step4假設(shè)

，若

，則將相關(guān)最小的動(dòng)態(tài)飛機(jī)路徑加入到限制主問(wèn)題中，轉(zhuǎn)Step5；否則

，算法結(jié)束，當(dāng)前得到的解為飛機(jī)動(dòng)態(tài)調(diào)度最優(yōu)解。Step5重新用單純形法計(jì)算，生成列所對(duì)應(yīng)的單純形表值S

，判定S中對(duì)應(yīng)的出基變量，轉(zhuǎn)Step2。2024/8/18精選課件ppt25本節(jié)采用國(guó)內(nèi)某航空公司A320與B737機(jī)型的機(jī)隊(duì)一天的航班計(jì)劃和相應(yīng)的飛機(jī)調(diào)度計(jì)劃為基礎(chǔ)數(shù)據(jù)，進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證算法的有效性。當(dāng)天共有25架飛機(jī)執(zhí)行84個(gè)航班任務(wù)。在執(zhí)行當(dāng)天的航班計(jì)劃過(guò)程中，實(shí)驗(yàn)分別模擬了臨時(shí)接到動(dòng)態(tài)調(diào)度任務(wù)，需要在8點(diǎn)至10點(diǎn)（最為忙碌的時(shí)間段）之間某一時(shí)刻之前（12點(diǎn)）分別調(diào)度飛機(jī)運(yùn)力用于執(zhí)行突發(fā)情況下的飛行任務(wù)，調(diào)度的飛機(jī)順帶執(zhí)行相關(guān)的航班后抵達(dá)目的/中轉(zhuǎn)機(jī)場(chǎng)（如北京、上海）。同時(shí)，原航班計(jì)劃中的航班必須盡可能多的被調(diào)度的飛機(jī)在允許的集結(jié)時(shí)間范圍內(nèi)順帶執(zhí)行，以減少航空公司的運(yùn)營(yíng)成本。

2.1.5算例分析2024/8/18精選課件ppt26算法比較結(jié)果表算法調(diào)度飛機(jī)架數(shù)123567順帶執(zhí)行航班數(shù)123588單純形法算法時(shí)間(秒)0．2411．1195.4479.22519.39936.793列生成算法算法時(shí)間(秒)0．3842.2935.2508.36413.23831.5892024/8/18精選課件ppt272.2.1應(yīng)急機(jī)組調(diào)度問(wèn)題的描述首要滿足的條件就是突發(fā)情況下的應(yīng)急調(diào)度需求，即航空公司應(yīng)調(diào)度滿足突發(fā)情況處理需要的機(jī)組前往目的/中轉(zhuǎn)機(jī)場(chǎng)執(zhí)行任務(wù)。減少應(yīng)急調(diào)度對(duì)航空公司日常運(yùn)行保障的影響2024/8/18精選課件ppt282.2.2約束分析和網(wǎng)絡(luò)圖的構(gòu)建（1）機(jī)組資質(zhì)。（2）數(shù)量。（3）法定的執(zhí)勤、飛行和休息時(shí)間限制。（4）機(jī)組飛行路徑。（5）對(duì)航班計(jì)劃的影響。參數(shù)定義3個(gè)集合----機(jī)組集合：；機(jī)場(chǎng)集合：；航班集合：。2024/8/18精選課件ppt30應(yīng)急機(jī)組調(diào)度時(shí)空網(wǎng)絡(luò)圖2024/8/18精選課件ppt312.2.3應(yīng)急飛機(jī)調(diào)度問(wèn)題數(shù)學(xué)模型2024/8/18精選課件ppt32模擬退火算法編碼方法：二進(jìn)制編碼2.2.4算法與求解2024/8/18精選課件ppt33冷卻進(jìn)度表（1）控制參數(shù)

（2）控制參數(shù)的變化函數(shù)控制參數(shù)的變換函數(shù)可以設(shè)置為衰減由大變小的函數(shù)，即

，其中（3）Markov鏈的長(zhǎng)度Markov鏈的長(zhǎng)度應(yīng)該隨著相應(yīng)的控制參數(shù)的變小而增加（4）接受概率本文的實(shí)驗(yàn)采用固定值法，當(dāng)接受概率小于一個(gè)

后終止算法（5）停止準(zhǔn)則2024/8/18精選課件ppt34模擬退火算法流程（1）初始化：設(shè)置控制參數(shù)

（充分大，設(shè)置為2000度），初始解狀態(tài)

，每個(gè)控制參數(shù)值的Markov置換次數(shù)為

；（2）對(duì)

做（3）步；（3）產(chǎn)生一個(gè)新狀態(tài)

j，新狀態(tài)的能量是

。計(jì)算當(dāng)前狀態(tài)解與新狀態(tài)解值的差，隨機(jī)生成的數(shù)

，判斷Boltzmann因子

是否大于

，若

則將狀態(tài)j標(biāo)記為接受狀態(tài)

，將當(dāng)前狀態(tài)解更改為

，否則刪除狀態(tài)j及其狀態(tài)解

。（4）

T逐漸減少，減少遵循的函數(shù)為

，其中

當(dāng)

，時(shí)終止算法，否則轉(zhuǎn)（2）2024/8/18精選課件ppt35本文采用某航空公司A320機(jī)隊(duì)的機(jī)組計(jì)劃為基礎(chǔ)數(shù)據(jù)，進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證算法的有效性。基于調(diào)度的5個(gè)機(jī)組資源，實(shí)驗(yàn)采用了遺傳算法，傳統(tǒng)的模擬退火算法以及啟發(fā)式混合模擬退火算法為進(jìn)行比較?，F(xiàn)在對(duì)70個(gè)航班任務(wù)的數(shù)據(jù)進(jìn)行優(yōu)化。得到的最優(yōu)方案為5個(gè)機(jī)組的調(diào)度能夠順帶執(zhí)行5個(gè)航班任務(wù)。分別把上述的方法與傳統(tǒng)模擬退火算法結(jié)果、遺傳算法結(jié)果比較。2.1.5算例分析2024/8/18精選課件ppt36算法比較結(jié)果表算法調(diào)度機(jī)組數(shù)目12345順帶執(zhí)行航班數(shù)12345遺傳算法算法時(shí)間(秒)0．2772．1345.4357.47519.451模擬退火算法算法時(shí)間(秒)0．3922.4025.5788.0918.768啟發(fā)式模擬退火算法算法時(shí)間(秒)0.3072.0472.2733.2318.5582024/8/18精選課件ppt372.6本章小結(jié)本章首先對(duì)應(yīng)急運(yùn)力調(diào)度問(wèn)題進(jìn)行詳細(xì)闡述，列舉了應(yīng)急運(yùn)力調(diào)度過(guò)程中所需要滿足的各種要求。再分別通過(guò)飛機(jī)和機(jī)組兩種運(yùn)力所涉及到的運(yùn)行過(guò)程，建立相應(yīng)的調(diào)度流程和約束分析網(wǎng)絡(luò)圖。最后根據(jù)各自的特點(diǎn)，提出相應(yīng)的數(shù)學(xué)模型，并進(jìn)行算法設(shè)計(jì)和求解來(lái)完成應(yīng)急飛機(jī)和機(jī)組的調(diào)度過(guò)程。2024/8/18精選課件ppt38剩余運(yùn)力調(diào)度問(wèn)題33.3剩余機(jī)組調(diào)度問(wèn)題3.4本章小結(jié)3.2剩余飛機(jī)調(diào)度問(wèn)題3.1不確定時(shí)間窗概念2024/8/18精選課件ppt393.1不確定時(shí)間窗概念2024/8/18精選課件ppt403.2.1剩余飛機(jī)調(diào)度問(wèn)題描述剩余飛機(jī)調(diào)度的計(jì)劃應(yīng)該能夠盡量滿足航空公司減少運(yùn)營(yíng)成本的目的，使得每架飛機(jī)的可用飛行時(shí)間被充分地利用到航班生產(chǎn)中去，這就需要調(diào)度影響“最小”的飛機(jī)的同時(shí)使得剩余飛機(jī)的利用率最大化。因此，合理安排剩余飛機(jī)的飛行時(shí)間，最大程度地執(zhí)行剩余航班計(jì)劃成為了剩余飛機(jī)調(diào)度的主要目標(biāo)函數(shù)。2024/8/18精選課件ppt41剩余飛機(jī)調(diào)度流程圖2024/8/18精選課件ppt423.2.2剩余飛機(jī)調(diào)度的數(shù)學(xué)模型2024/8/18精選課件ppt43啟發(fā)式預(yù)處理方法在應(yīng)急調(diào)度過(guò)后根據(jù)每架剩余的飛機(jī)運(yùn)力所處的地點(diǎn)和所處的狀態(tài)（主要指的是實(shí)際飛行時(shí)間約束），啟發(fā)式預(yù)處理過(guò)程將剩余航班計(jì)劃中的航段進(jìn)行銜接，并在不確定時(shí)間窗允許的條件下繼續(xù)執(zhí)行飛行任務(wù)。生成的路徑的數(shù)目非常龐大，解空間也非常巨大。但是在列生成算法中，在固定的解空間集合內(nèi)尋找方案的過(guò)程就變成了一個(gè)單純計(jì)算的過(guò)程。從而避免了單純使用列生成算法而需要的重新進(jìn)行無(wú)序組合所耗費(fèi)的計(jì)算重復(fù)時(shí)間，改善了算法的計(jì)算時(shí)間和有效性。3.2.3算法與求解2024/8/18精選課件ppt44啟發(fā)式預(yù)處理方法飛機(jī)路徑集合生成流程圖2024/8/18精選課件ppt45分枝定界策略的應(yīng)用當(dāng)分枝有整數(shù)，則進(jìn)行定界判斷，若為整數(shù)解則不再分枝。從符合整數(shù)條件的分枝中進(jìn)行上界判斷，若大于上界則剪支，若小于上界則定為上界；當(dāng)分枝為分?jǐn)?shù)，找出最優(yōu)目標(biāo)函數(shù)值最小者為下界。進(jìn)行上界判斷，若大于上界剪枝，若小于上界，可繼續(xù)分枝。選擇目標(biāo)函數(shù)值較小的先進(jìn)行分解，對(duì)目標(biāo)值的升降影響最小。2024/8/18精選課件ppt46本文采用國(guó)內(nèi)某航空公司A320與B737機(jī)型的機(jī)隊(duì)一天的航班計(jì)劃和相應(yīng)的飛機(jī)調(diào)度計(jì)劃為基礎(chǔ)數(shù)據(jù)，進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證算法的有效性。在3.2.5節(jié)的實(shí)驗(yàn)基礎(chǔ)上，在調(diào)度了應(yīng)急飛機(jī)運(yùn)力用于并順帶執(zhí)行了相關(guān)航班任務(wù)后，剩余的飛機(jī)運(yùn)力則執(zhí)行剩余的航班計(jì)劃。實(shí)驗(yàn)要求在當(dāng)天機(jī)隊(duì)剩余的飛機(jī)必須盡可能的回到其基地機(jī)場(chǎng)（外場(chǎng)過(guò)夜飛機(jī)應(yīng)回到其原計(jì)劃所在機(jī)場(chǎng)），保證第二天的航班計(jì)劃能夠正常執(zhí)行。實(shí)驗(yàn)并非以當(dāng)天24時(shí)為準(zhǔn)，而是動(dòng)態(tài)地將后續(xù)航班計(jì)劃中最后一個(gè)航班落地的時(shí)間作為時(shí)間窗的截止點(diǎn)進(jìn)行計(jì)算。同時(shí)，后續(xù)航班計(jì)劃中的航班必須盡可能多的執(zhí)行，以減少航空公司的運(yùn)營(yíng)成本。

3.2.4算例結(jié)果與分析2024/8/18精選課件ppt47算法比較結(jié)果表算法飛機(jī)架數(shù)181920222324航班數(shù)767679818283單純形法算法時(shí)間(秒)247.622244.764280．904353．551377.024365.793列生成算法算法時(shí)間(秒)231.691235.246266.301290.763294.213313.589啟發(fā)式重啟動(dòng)列生成算法算法時(shí)間（秒）187.215193.132204.179203.415205.997226.3322024/8/18精選課件ppt483.3.1剩余機(jī)組調(diào)度問(wèn)題描述剩余機(jī)組調(diào)度的主要目的是尋找覆蓋剩余航班計(jì)劃中的所有航班航段的機(jī)組路徑集合并將機(jī)組利用率最大化。在突發(fā)情況下應(yīng)急運(yùn)力被抽到后，航空公司必須保證能夠剩余航班計(jì)劃能夠被盡可能地執(zhí)行，即剩余機(jī)組利用率最大化。剩余機(jī)組調(diào)度生成的方案所覆蓋的路徑必須所需要的機(jī)組數(shù)目最小，同時(shí)其機(jī)組成本最小，而剩余航班計(jì)劃中的航班要盡可能地被執(zhí)行，這些都成為了剩余機(jī)組排班的目標(biāo)函數(shù)。2024/8/18精選課件ppt49剩余機(jī)組調(diào)度示意圖2024/8/18精選課件ppt503.2.2剩余機(jī)組調(diào)度的數(shù)學(xué)模型2024/8/18精選課件ppt51編碼方法與解碼3.2.3算法與求解2024/8/18精選課件ppt52初始種群生成與啟發(fā)式策略的應(yīng)用剩余機(jī)組調(diào)度時(shí)，合理的機(jī)組路徑所包含的航班在時(shí)間和空間上需要滿足嚴(yán)格的銜接性原則，即機(jī)組路徑上的航班時(shí)空上必須具有連續(xù)性，航班間的銜接時(shí)間必須大于或等于相關(guān)機(jī)場(chǎng)規(guī)定的最短過(guò)站時(shí)間，且機(jī)組路徑的飛行時(shí)間和執(zhí)勤時(shí)間不得超過(guò)法規(guī)的最大時(shí)間限制。則若存在航班

被唯一的機(jī)組路徑

包含，即

。若機(jī)組調(diào)度方案包含機(jī)組路徑

，則包含了航班

。根據(jù)航班唯一性原則，若存在另外的機(jī)組路徑

、包含了該航班

，則兩個(gè)機(jī)組路徑相排斥，通過(guò)判定相關(guān)機(jī)組路徑

的的影響因子值，將影響因子值小的機(jī)組路徑排在基因序列末尾，可縮小剩余機(jī)組調(diào)度的解空間規(guī)模。啟發(fā)式策略生成所有的可能的路徑（1）若該機(jī)組已在原始發(fā)基地，則也可停場(chǎng)作為其Routing方案之一（2）采用啟發(fā)式深度優(yōu)先搜索，生成所有可能的路徑遺傳算法（1）生成初始種群，設(shè)置代數(shù)和種群規(guī)模（隨機(jī)生成初始種群個(gè)體500，遺傳代數(shù)500）；（2）計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度（重復(fù)的機(jī)組數(shù)目+丟失的機(jī)組數(shù)目+丟失的航班數(shù)目+重復(fù)的航班數(shù)目+總的使用機(jī)組數(shù)目的權(quán)和/總的飛行時(shí)間）；2024/8/18精選課件ppt53（3）最優(yōu)方案的保存（適應(yīng)度最高的前100個(gè)個(gè)體）；（4）交叉方案（將第一個(gè)與最后一個(gè)個(gè)體，隨機(jī)選取個(gè)體基因位置進(jìn)行斷點(diǎn)交叉250）；（5）變異方案（從交叉和最優(yōu)的種群個(gè)體中隨機(jī)選擇個(gè)體，進(jìn)行0/1變異，并留下150個(gè)個(gè)體）。（6）將最優(yōu)方案、交叉方案和變異方案?jìng)€(gè)體合并成為下一代種群。（7）如果在60代內(nèi)最優(yōu)個(gè)體的適應(yīng)度沒(méi)有變化，退出循環(huán)。（8）遺傳算法500代規(guī)模循環(huán)10次，記錄每次的最優(yōu)個(gè)體。2024/8/18精選課件ppt542024/8/18精選課件ppt55本節(jié)采用某航空公司A320機(jī)隊(duì)的機(jī)組計(jì)劃為基礎(chǔ)數(shù)據(jù)，進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證算法的有效性。在抽調(diào)了5個(gè)機(jī)組資源后，依據(jù)原航班計(jì)劃表的執(zhí)行情況，20個(gè)剩余機(jī)組需要執(zhí)行64個(gè)航班任務(wù)，共生成1310個(gè)機(jī)組路徑。實(shí)驗(yàn)重復(fù)計(jì)算10次，算法計(jì)算時(shí)間跨度分別為533.885779—702.655294秒，設(shè)置代數(shù)為180代，得到的適應(yīng)度跨度為3.2916~3.0769。13個(gè)機(jī)組選擇所需路徑，取消4個(gè)航班，為最優(yōu)解。3.2.4算例結(jié)果與分析2024/8/18精選課件ppt56算例相關(guān)的代數(shù)與適應(yīng)度2024/8/18精選課件ppt573.4本章小結(jié)本章著重闡述航空公司的剩余運(yùn)力調(diào)度理論技術(shù)與方法。通過(guò)啟發(fā)式搜索算法在構(gòu)建的剩余飛機(jī)調(diào)度網(wǎng)絡(luò)圖中，生成相關(guān)剩余飛機(jī)路徑集合，以便能夠高效地進(jìn)行剩余飛機(jī)調(diào)度計(jì)劃的編排。生成的飛機(jī)路徑集合特點(diǎn)是數(shù)據(jù)量大，但是通過(guò)相應(yīng)的啟發(fā)式策略卻能夠有效避免了傳統(tǒng)的列生成算法需要通過(guò)網(wǎng)絡(luò)圖中生成最短路徑算法的不斷迭代過(guò)程。在剩余機(jī)組運(yùn)力調(diào)度過(guò)程中，通過(guò)采用啟發(fā)式處理的方法生成相應(yīng)的種群，有效避免了剩余機(jī)組調(diào)度解空間規(guī)模的擴(kuò)大。最后給出實(shí)例分析，驗(yàn)證模型的可行性和算法的有效性。2024/8/18精選課件ppt58應(yīng)急運(yùn)力回歸調(diào)度問(wèn)題44.2集成一體化回歸問(wèn)題描述4.1問(wèn)題描述4.3集成一體化回歸數(shù)學(xué)模型4.4算法求解及算例分析4.3本章小結(jié)2024/8/18精選課件ppt594.1.1應(yīng)急飛機(jī)運(yùn)力回歸問(wèn)題將應(yīng)急飛機(jī)運(yùn)力以合適的方式切入航班計(jì)劃，航空公司需要根據(jù)現(xiàn)有的飛機(jī)運(yùn)力資源（包含剩余飛機(jī)運(yùn)力與可用應(yīng)急飛機(jī)運(yùn)力），為每一個(gè)航段航班指派具體的執(zhí)行飛機(jī)。應(yīng)急飛機(jī)運(yùn)力回歸就是要求從飛機(jī)路徑集合中選擇一些飛機(jī)路徑，合理安排所有可用飛機(jī)的飛行時(shí)間，覆蓋所有剩余航班計(jì)劃中的航班任務(wù)的同時(shí)能夠讓總維修機(jī)會(huì)數(shù)目最大化。2024/8/18精選課件ppt60應(yīng)急運(yùn)力回歸航線網(wǎng)絡(luò)圖2024/8/18精選課件ppt61若多條連續(xù)的飛機(jī)路徑中都含有同一個(gè)航班，則執(zhí)行該航班任務(wù)的飛機(jī)只能夠完成一條連續(xù)的飛機(jī)路徑任務(wù)，而且出現(xiàn)在最終回歸調(diào)度計(jì)劃中的飛機(jī)任務(wù)路徑中所涉及到所有航班，都不能出現(xiàn)在該回歸調(diào)度計(jì)劃方案的其它飛機(jī)所涉及的飛機(jī)路徑中。應(yīng)急飛機(jī)運(yùn)力回歸就是要求從飛機(jī)路徑集合中選擇一些飛機(jī)路徑，合理安排所有可用飛機(jī)的飛行時(shí)間，覆蓋所有剩余航班計(jì)劃中的航班任務(wù)的同時(shí)能夠讓總維修機(jī)會(huì)數(shù)目最大化。2024/8/18精選課件ppt624.1.2應(yīng)急機(jī)組運(yùn)力回歸問(wèn)題應(yīng)急機(jī)組回歸調(diào)度，需要為每一個(gè)機(jī)組人員安排操縱飛機(jī)的飛行任務(wù)，實(shí)施剩余的航班計(jì)劃。同樣根據(jù)民航當(dāng)局和航空公司的各項(xiàng)規(guī)章制度，必須根據(jù)應(yīng)急回歸機(jī)組的數(shù)量和不同的機(jī)組資質(zhì)，為每個(gè)機(jī)組適當(dāng)?shù)呐渲眠m當(dāng)?shù)暮桨嗪蕉物w行任務(wù)。因此，應(yīng)急機(jī)組回歸調(diào)度是指遵循相關(guān)的民航管理部門所制定的規(guī)章條例，為剩余航班計(jì)劃中的每一個(gè)航班航段具體指派相應(yīng)的可用機(jī)組，使得在運(yùn)力回歸調(diào)度結(jié)束后，能夠根據(jù)每一個(gè)機(jī)組的實(shí)際情況，使其能夠回到相應(yīng)的基地機(jī)場(chǎng)進(jìn)行休整，并能夠在隨后的正常航班計(jì)劃中執(zhí)行飛行任務(wù)。2024/8/18精選課件ppt63應(yīng)急機(jī)組回歸原則（1） 機(jī)型資質(zhì)原則（2） 時(shí)空銜接原則（3） 值勤時(shí)間原則（4） 回歸基地原則2024/8/18精選課件ppt644.2集成一體化回歸問(wèn)題描述在日常航空公司實(shí)際的機(jī)組排班實(shí)踐過(guò)程中，飛機(jī)排班和機(jī)組排班并不是同時(shí)進(jìn)行的，而是先由飛機(jī)管理部門先進(jìn)行飛機(jī)排班，在飛機(jī)排班所生成的飛機(jī)路線基礎(chǔ)上做必要的調(diào)整，生成機(jī)組排班路徑。這種做法的目的是盡可能利用飛機(jī)路線中的合理銜接來(lái)提高機(jī)組排班過(guò)程中的機(jī)組利用率。困難的是，完整的飛機(jī)排班方案中找到完整的機(jī)組路徑，使得這些機(jī)組能夠在適航規(guī)定的限制時(shí)間內(nèi)回到其基地機(jī)場(chǎng)。所以飛機(jī)和機(jī)組運(yùn)力兩者在時(shí)間和空間上具有相互依賴和相互制約的關(guān)系，這就決定了機(jī)組排班若按照順序研究的方法，就必然是在兩者間存在這一個(gè)反復(fù)迭代的過(guò)程。2024/8/18精選課件ppt65應(yīng)急運(yùn)力回歸調(diào)度同樣存在著這樣的問(wèn)題：在應(yīng)急飛機(jī)運(yùn)力方案生成后，應(yīng)急機(jī)組運(yùn)力回歸調(diào)度的安排可能造成飛機(jī)無(wú)相關(guān)機(jī)組人員可以執(zhí)飛，則進(jìn)入了重新進(jìn)行應(yīng)急飛機(jī)運(yùn)力回歸方案的迭代循環(huán)過(guò)程的冗長(zhǎng)過(guò)程中。最優(yōu)化的應(yīng)急飛機(jī)運(yùn)力回歸方案并不能得出最優(yōu)可行的應(yīng)急機(jī)組運(yùn)力回歸方案。兩者間由于變量和約束條件的不同，使得應(yīng)急運(yùn)力一體化回歸調(diào)度存在一定的困難。問(wèn)題規(guī)模和解空間會(huì)隨著飛機(jī)、機(jī)組和剩余航班計(jì)劃中的航班數(shù)量而不斷擴(kuò)大，從而影響問(wèn)題解決的實(shí)時(shí)性。應(yīng)急運(yùn)力一體化回歸調(diào)度是將兩種調(diào)度問(wèn)題綜合在一個(gè)模型中進(jìn)行研究，雖然問(wèn)題依然復(fù)雜，可是其能夠?qū)崿F(xiàn)真正意義上的應(yīng)急運(yùn)力一體化回歸調(diào)度。2024/8/18精選課件ppt664.2集成一體化回歸數(shù)學(xué)模型應(yīng)急運(yùn)力回歸問(wèn)題中飛機(jī)路徑和機(jī)組路徑的生成同樣必須滿足以下原則和約束條件：（1）機(jī)型一致性原則；（2）飛機(jī)可用性原則；（3）機(jī)型適航性原則；（4）飛機(jī)檢修原則；（5）機(jī)型資質(zhì)原則；（6）機(jī)組值勤時(shí)間原則；（7）機(jī)組回歸基地原則；（8）航班航段執(zhí)行唯一性原則；（9）飛機(jī)路徑和機(jī)組路徑時(shí)空銜接性原則。2024/8/18精選課件ppt67應(yīng)急運(yùn)力回歸調(diào)度時(shí)空網(wǎng)絡(luò)圖2024/8/18精選課件ppt68集成一體化回歸數(shù)學(xué)模型2024/8/18精選課件ppt694.2運(yùn)力回歸一體化算法及算例分析啟發(fā)式預(yù)處理方法流程圖2024/8/18精選課件ppt70限制主問(wèn)題2024/8/18精選課件ppt71解限制主問(wèn)題的基本步驟為：Step1：選擇若干條飛機(jī)路徑和機(jī)組路徑加入至限制主問(wèn)題中，為保證限制主問(wèn)題有解，飛機(jī)路徑唯一性約束式（5-18）加入人工變量

，機(jī)組路徑唯一性約束式（5-20）加入人工變量

，同時(shí)，航班覆蓋唯一性約束式（5-17）和式（5-19）由于已存在變量

和

，則可將

、

和

同時(shí)作為初始基變量生成；Step2：由修正單純形法求解限制主問(wèn)題；2024/8/18精選課件ppt72Step3：對(duì)于限制主問(wèn)題所生成的子問(wèn)題的求解，是根據(jù)求解生成的基的逆

以及基變量的對(duì)應(yīng)成本

，生成網(wǎng)絡(luò)圖中每個(gè)航班航段和飛機(jī)相對(duì)應(yīng)的對(duì)偶變量

，根據(jù)預(yù)處理過(guò)程采用的啟發(fā)式深度優(yōu)先搜索算法生成飛機(jī)和機(jī)組路徑表中中每個(gè)路徑所涉及的航班，計(jì)算每條飛機(jī)路徑和機(jī)組路徑的簡(jiǎn)約成本：或

；Step4：假設(shè)簡(jiǎn)約成本

，若

，則將相關(guān)簡(jiǎn)約成本最小的飛機(jī)路徑或機(jī)組路徑加入到限制主問(wèn)題中，轉(zhuǎn)Step5；否則

，算法結(jié)束，當(dāng)前得到的解為應(yīng)急運(yùn)力回歸調(diào)度的最優(yōu)解，轉(zhuǎn)Step6；2024/8/18精選課件ppt73Step5：采用重啟動(dòng)技術(shù)，用

和限制主問(wèn)題的解

，計(jì)算出加入列所對(duì)應(yīng)的單純形表值

，并假設(shè)該列為入基變量，則

，根據(jù)最小比值原則判定

中對(duì)應(yīng)的變量為出基變量。轉(zhuǎn)Step2計(jì)算；Step6：生成的最優(yōu)解若為分?jǐn)?shù)，并非0-1整數(shù)，則采用分枝定界方法計(jì)算；若為整數(shù)則為應(yīng)急運(yùn)力回歸一體化的最優(yōu)方案解。。2024/8/18精選課件ppt74采用國(guó)內(nèi)某航空公司A320與B737機(jī)型的機(jī)隊(duì)的航班計(jì)劃，進(jìn)行仿真實(shí)驗(yàn)以驗(yàn)證上述啟發(fā)式列生成算法的有效性。仿真實(shí)驗(yàn)假設(shè)在當(dāng)天的剩余航班計(jì)劃執(zhí)行過(guò)程中，在中午12時(shí)，航空公司收到應(yīng)急調(diào)度任務(wù)完成的通知，并得到應(yīng)急任務(wù)結(jié)束后各調(diào)度的相當(dāng)于航空公司10%的飛機(jī)運(yùn)力和10%的機(jī)組運(yùn)力所在的集結(jié)機(jī)場(chǎng)和完成時(shí)間。之后航空公司開始制定應(yīng)急運(yùn)力回歸調(diào)度方案，將運(yùn)力切入當(dāng)天12點(diǎn)后執(zhí)行的剩余航班計(jì)劃中。在調(diào)度的飛機(jī)和機(jī)組順帶執(zhí)行完相關(guān)的航班航段后，能夠到達(dá)其原來(lái)的維修機(jī)場(chǎng)和基地機(jī)場(chǎng)。實(shí)驗(yàn)要求在應(yīng)急運(yùn)力回歸過(guò)程中，所有的剩余航班計(jì)劃都必須執(zhí)行，同時(shí)，相應(yīng)被調(diào)度的運(yùn)力可以通過(guò)空飛和調(diào)機(jī)方式，能夠在當(dāng)天24時(shí)回歸到其原既定機(jī)場(chǎng)（原機(jī)場(chǎng)所在的要求的一定數(shù)目的飛機(jī)和機(jī)組），以保證第二天的原航班計(jì)劃的正常執(zhí)行。實(shí)驗(yàn)的主要標(biāo)準(zhǔn)就是運(yùn)力回歸計(jì)劃航空公司所花費(fèi)的運(yùn)營(yíng)成本最?。ūM可能多地執(zhí)行切人航班線、機(jī)組減少空飛、飛機(jī)減少調(diào)機(jī)過(guò)程）。2024/8/18精選課件ppt75算法結(jié)果比較表算法可用飛機(jī)架數(shù)915172025可用機(jī)組數(shù)915253035航班數(shù)2840506070單純形法算法時(shí)間(秒)146．014422.424586.369933.0111175.141列生成算法算法時(shí)間(秒)140.705348.34492．424867.562983.301啟發(fā)式重啟動(dòng)列生成算法算法時(shí)間（秒）122.429235.426400.551465.212582.8812024/8/18精選課件ppt764.2本章小結(jié)本章對(duì)應(yīng)急運(yùn)力回歸問(wèn)