方杰博士學位論文答辯課件

2024/8/18精選課件ppt1突發(fā)情況下應急運力調度理論與方法研究

答辯人：方杰指導教師：夏洪山教授

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

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

2024/8/18精選課件ppt20應急飛機調度時空網絡圖2024/8/18精選課件ppt212.1.3應急飛機調度問題數學模型2024/8/18精選課件ppt22解限制主問題的基本步驟為：Step1選擇一條最短飛機路徑加入至限制主問題中，為保證限制主問題有解，飛機路徑唯一性約束式（3.8）加入人工變量

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

，則可將

和

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

，生成網絡圖中每個航班和飛機相對應的對偶變量

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

，若

，則將相關最小的動態(tài)飛機路徑加入到限制主問題中，轉Step5；否則

，算法結束，當前得到的解為飛機動態(tài)調度最優(yōu)解。Step5重新用單純形法計算，生成列所對應的單純形表值S

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

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

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

，其中（3）Markov鏈的長度Markov鏈的長度應該隨著相應的控制參數的變小而增加（4）接受概率本文的實驗采用固定值法，當接受概率小于一個

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

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

，每個控制參數值的Markov置換次數為

；（2）對

做（3）步；（3）產生一個新狀態(tài)

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

。計算當前狀態(tài)解與新狀態(tài)解值的差，隨機生成的數

，判斷Boltzmann因子

是否大于

，若

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

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

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

。（4）

T逐漸減少，減少遵循的函數為

，其中

當

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

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

被唯一的機組路徑

包含，即

。若機組調度方案包含機組路徑

，則包含了航班

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

、包含了該航班

，則兩個機組路徑相排斥，通過判定相關機組路徑

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

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

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

和

，則可將

、

和

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

以及基變量的對應成本

，生成網絡圖中每個航班航段和飛機相對應的對偶變量

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

；Step4：假設簡約成本

，若

，則將相關簡約成本最小的飛機路徑或機組路徑加入到限制主問題中，轉Step5；否則

，算法結束，當前得到的解為應急運力回歸調度的最優(yōu)解，轉Step6；2024/8/18精選課件ppt73Step5：采用重啟動技術，用

和限制主問題的解

，計算出加入列所對應的單純形表值

，并假設該列為入基變量，則

，根據最小比值原則判定

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