本文關(guān)鍵詞：無初始解的大規(guī)模機組排班問題建模與求解優(yōu)化

  更多相關(guān)文章： 大規(guī)模 飛行員排班 列生成算法 日任務(wù)

【摘要】：航空任務(wù)排班是航空企業(yè)運營管理的重要部分，直接決定了企業(yè)的管理水平高低。飛行員排班是航空任務(wù)排班中的重要組成部分，好的飛行員排班計劃能夠合理的應(yīng)用企業(yè)資源，降低成本，使飛行員這一重要人力資源得到高效率使用。探索不同的求解優(yōu)化方法對獲得更快的求解速度、更高的求解質(zhì)量有重要意義。 本文對大規(guī)模的飛行員排班任務(wù)復(fù)雜性進行了分析，對無初始解情況的求解方法進行了設(shè)計與優(yōu)化。首先對問題的輸入輸出信息與約束條件進行了闡述，并將其建模為集合分割問題。進而對求解特殊矩陣的列生成算法進行了詳盡的剖析，展示了算法原理，給出了列生成法獲得的松弛問題解的最優(yōu)性證明。本文用罰函數(shù)法解決了無初始解的情況，探索出高質(zhì)量的初始列并用啟發(fā)式搜索輸入給列生成法，實現(xiàn)了對算法求解質(zhì)量的優(yōu)化，并對子問題設(shè)計了加快收斂的列生成策略。針對求解松弛問題的數(shù)學(xué)規(guī)劃方法，根據(jù)多種方法收斂特性，找到一種綜合使用牛頓障礙法與對偶單純形法的最優(yōu)求解組合方法。隨后設(shè)計了基于日任務(wù)的求解架構(gòu)，對問題進行了新的建模，應(yīng)用啟發(fā)式搜索法與罰因子法構(gòu)造初始可行解，子問題轉(zhuǎn)化為兩個含有負權(quán)與時間約束的最短路問題。通過大量計算實驗探索了這種方法的求解性能，找到了平衡計算資源的方法。隨后應(yīng)用D-W分解對基于日任務(wù)的方法進行了變換，嘗試對求解方法進行優(yōu)化設(shè)計，對問題的求解進行了拆解后，研究了在大量可行日任務(wù)的基礎(chǔ)上如何更好獲得最優(yōu)排班解的方法。通過添加機場節(jié)點流約束能夠使日任務(wù)集合被排班覆蓋，實現(xiàn)了優(yōu)化。在計算實驗中本文使用了來自國內(nèi)一家航空公司的一周運營的實際數(shù)據(jù)，航班多達1190架次，并且沒有已知的可行解。分析中通過調(diào)節(jié)計算參數(shù)對以上不同求解方法的各類性質(zhì)進行了對比分析，最終的計算結(jié)果證實這種求解方法在一定意義上具有可行性，，其求解速度、質(zhì)量均在可接受的范圍內(nèi)。最后給出了這種求解方法中存在的不足以及可能的改進方向。
【關(guān)鍵詞】：大規(guī)模 飛行員排班 列生成算法 日任務(wù)
【學(xué)位授予單位】：清華大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：F561
【目錄】：

• 摘要3-4
• Abstract4-7
• 第1章 緒論7-14
• 1.1 選題背景7-8
• 1.2 文獻綜述8-12
• 1.3 研究內(nèi)容與研究方法12-13
• 1.3.1 研究內(nèi)容12-13
• 1.3.2 研究方法13
• 1.4 求解的軟、硬件環(huán)境13-14
• 第2章 排班問題及其模型分析14-25
• 2.1 問題分析14-16
• 2.1.1 飛行員排班問題的任務(wù)14-16
• 2.1.2 飛行員排班問題的復(fù)雜性16
• 2.2 優(yōu)化目標與成本結(jié)構(gòu)16-17
• 2.3 CPP求解約束條件17
• 2.4 CPP求解的數(shù)學(xué)模型與網(wǎng)絡(luò)圖模型17-20
• 2.5 列生成算法20-23
• 2.5.1 算法優(yōu)點20
• 2.5.2 算法思想與原理20-22
• 2.5.3 列生成算法松弛解的最優(yōu)性證明22
• 2.5.4 列生成算法的求解質(zhì)量的一些實驗觀測22-23
• 2.6 最短路子問題（ColumnGenerator：PricingProblem）23-25
• 第3章 無初始解排班問題的算法設(shè)計與優(yōu)化25-39
• 3.1 無初始解大規(guī)模飛行員排班問題的建模25-27
• 3.1.1 求解機組排班問題的列生成算法流程25-26
• 3.1.2 求解策略26
• 3.1.3 基于罰因子法的數(shù)學(xué)模型26-27
• 3.2 子問題建模及其生成策略27-30
• 3.2.1 子問題有向圖建模27-29
• 3.2.2 帶有負權(quán)與時間約束的最短路問題29-30
• 3.3 提高求解質(zhì)量與求解速度的優(yōu)化設(shè)計30-39
• 3.3.1 無初始輸入列的求解30-31
• 3.3.2 探索提高求解質(zhì)量的初始列31-35
• 3.3.3 一種新的求解松弛主問題的優(yōu)化方法35-38
• 3.3.4 優(yōu)化方法的相關(guān)結(jié)論38-39
• 第4章 基于duty-period的無初始解求解方法設(shè)計39-50
• 4.1 基于罰因子法的主問題數(shù)學(xué)模型39-41
• 4.2 兩個最短路子問題與其迭代邏輯41-45
• 4.2.1 Duty生成原理41-42
• 4.2.2 排班路線（pairing）生成原理42-45
• 4.3 求解策略45-47
• 4.3.1 協(xié)調(diào)兩個生成子問題的方法45
• 4.3.2 探索提高求解質(zhì)量的初始列與行45-47
• 4.4 計算結(jié)果與計算性能分析47-50
• 第5章 基于duty-period求解方法的優(yōu)化50-56
• 5.1 基于duty-period方法的矩陣分解50-51
• 5.2 一種Best-Duty-Set求解方法51-54
• 5.3 Pairing列生成問題54
• 5.4 計算結(jié)果與分析54-56
• 第6章 總結(jié)與展望56-58
• 6.1 研究主要成果56
• 6.2 研究主要不足56-57
• 6.3 研究展望57-58
• 參考文獻58-61
• 致謝61-63
• 個人簡歷63

【共引文獻】

中國期刊全文數(shù)據(jù)庫 前3條

1 方磊,何建敏;城市應(yīng)急系統(tǒng)優(yōu)化選址決策模型和算法[J];管理科學(xué)學(xué)報;2005年01期

2 石俊剛;史宏杰;徐瑞華;;城市軌道交通乘務(wù)任務(wù)劃分模型及算法研究[J];鐵道學(xué)報;2014年05期

3 石俊剛;周峰;徐瑞華;;城軌交通乘務(wù)任務(wù)配對的集合分割模型及算法[J];同濟大學(xué)學(xué)報(自然科學(xué)版);2015年02期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前2條

1 楊陽;鋼鐵企業(yè)軋線批調(diào)度問題的建模與最優(yōu)化方法的研究[D];東北大學(xué);2010年

2 狄浩;虛擬網(wǎng)絡(luò)的高效和可靠映射算法研究[D];電子科技大學(xué);2013年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前6條

1 王宏建;分院飛行訓(xùn)練排班系統(tǒng)研究[D];電子科技大學(xué);2010年

2 魯紅珍;航空公司機組航班任務(wù)串優(yōu)化方法研究[D];中國民用航空飛行學(xué)院;2012年

3 張碩;航空公司飛行機組指派問題研究[D];中國民用航空飛行學(xué)院;2013年

4 陳海平;高速鐵路乘務(wù)組織理論與優(yōu)化研究[D];北京交通大學(xué);2013年

5 張余;隨機能力提升下知識型員工調(diào)度問題研究[D];西安電子科技大學(xué);2012年

6 董雪遙;深圳航空機組管理系統(tǒng)的設(shè)計與實現(xiàn)[D];哈爾濱工業(yè)大學(xué);2014年

本文編號：897556