群集智能優化算法及其在機場停機位分配中的應用（簡體書）

目錄
前言
第1章 緒論 1
1.1 停機位分配問題的研究背景和意義 1
1.2 機場停機位分配問題 2
1.3 停機位分配問題的研究現狀 3
1.3.1 停機位靜態分配問題的研究現狀 3
1.3.2 多目標停機位分配問題的研究現狀 4
1.3.3 具有魯棒性的停機位分配問題研究現狀 5
1.3.4 不正常航班停機位動態分配問題的研究現狀 6
1.4 本書的結構及主要內容 7
1.5 本章小結 8
參考文獻 8
第2章 機場停機位分配問題的分析、模型與方法 13
2.1 機場停機位分配問題分析 13
2.1.1 民航機場系統 13
2.1.2 機場停機位特性 15
2.1.3 機場航班特性 16
2.1.4 機場停機位分配特性 17
2.1.5 機場停機位分配規則 18
2.1.6 機場停機位分配約束條件 19
2.1.7 機場停機位實時分配 20
2.1.8 機場停機位與航班之間關係 20
2.2 停機位分配問題域的分析 21
2.2.1 復雜網絡流模型 21
2.2.2 假設條件 22
2.2.3 數據定義 23
2.2.4 復雜網絡流模型構建 23
2.3 機場停機位分配的優化目標函數分析 24
2.3.1 旅客總行走距離之和*短 24
2.3.2 各停機位空閑時間*均衡 25
2.3.3 遠機位停靠航班數量*少 25
2.3.4 停機位占用效率*大 25
2.3.5 航班-機位匹配差異度*小 26
2.3.6 飛機地面滑行油耗*小 26
2.4 停機位分配問題的研究方法 27
2.4.1 精確求解方法 27
2.4.2 近似求解方法 27
2.5 多目標優化問題描述 29
2.6 本章小結 29
參考文獻 29
第3章 多策略蟻群優化算法求解機場停機位分配問題 33
3.1 基本蟻群優化算法 33
3.1.1 蟻群優化算法原理 33
3.1.2 蟻群優化算法流程 34
3.1.3 蟻群優化算法優缺點 36
3.2 多策略蟻群優化算法 36
3.2.1 信息素初始濃度的改進方法 36
3.2.2 轉移概率的改進方法 37
3.2.3 揮發系數的改進方法 37
3.2.4 PSVACO算法的實現 37
3.2.5 PSVACO算法的數值驗證 39
3.3 機場停機位分配多目標優化模型的建立 42
3.3.1 優化目標函數的構建 42
3.3.2 多目標優化模型的無量化 43
3.4 多策略蟻群優化算法求解停機位分配優化模型 44
3.4.1 機場停機位分配優化方法 44
3.4.2 機場停機位分配流程 44
3.5 算例分析 45
3.5.1 實驗數據 45
3.5.2 實驗環境與參數設置 46
3.5.3 實驗結果與分析 46
3.5.4 結果比較與分析 48
3.6 本章小結 49
參考文獻 50
第4章 協同進化蟻群優化算法求解機場停機位分配問題 52
4.1 協同進化算法 52
4.1.1 協同進化算法概述 52
4.1.2 協同進化算法的分類 52
4.1.3 協同進化算法的框架 56
4.1.4 協同進化算法動力學描述 56
4.2 自適應蟻群優化算法 58
4.2.1 信息素更新策略 58
4.2.2 信息素更新約束範圍 59
4.3 協同進化蟻群優化算法 59
4.3.1 協同進化蟻群優化算法思想 59
4.3.2 SCEACO算法模型 59
4.3.3 SCEACO算法描述 60
4.3.4 SCEACO算法求解TSP 61
4.4 SCEACO算法參數自適應調整與協作策略 65
4.4.1 參數自適應調整策略 65
4.4.2 參數協作策略 65
4.5 機場停機位分配多目標優化模型的建立 66
4.5.1 優化目標函數的構建 66
4.5.2 多目標優化模型的無量化 66
4.6 SCEACO算法求解停機位分配優化模型 66
4.6.1 機場停機位分配優化方法 66
4.6.2 機場停機位分配流程 67
4.6.3 機場停機位分配步驟 67
4.7 算例分析 68
4.7.1 實驗數據 68
4.7.2 實驗環境與參數設置 69
4.7.3 實驗結果與分析 70
4.7.4 結果比較與分析 72
4.8 本章小結 75
參考文獻 75
第5章 多策略差分進化算法求解機場停機位分配問題 78
5.1 差分進化算法 78
5.1.1 差分進化算法原理 78
5.1.2 差分進化算法的優缺點 80
5.2 CPOMSDE算法 80
5.2.1 CPOMSDE算法的思想 80
5.2.2 小波基函數改進縮放因子 81
5.2.3 正態分布改進交叉概率 82
5.2.4 *優變異策略 82
5.2.5 CPOMSDE算法模型 84
5.2.6 CPOMSDE算法步驟 85
5.3 數值實驗與分析 85
5.3.1 標準測試函數 85
5.3.2 實驗環境與參數設置 86
5.3.3 實驗結果與分析 87
5.3.4 結果比較與分析 95
5.4 機場停機位分配多目標優化模型的建立 96
5.4.1 優化目標函數的構建 96
5.4.2 多目標優化模型的無量化 97
5.5 CPOMSDE算法求解停機位分配優化模型 98
5.5.1 機場停機位分配優化方法 98
5.5.2 機場停機位分配流程 98
5.5.3 機場停機位分配步驟 99
5.6 算例分析 99
5.6.1 實驗數據與實驗環境 99
5.6.2 實驗結果與分析 101
5.6.3 結果比較與分析 104
5.7 本章小結 104
參考文獻 105
第6章 自適應粒子群優化算法求解機場停機位分配問題 108
6.1 粒子群優化算法 108
6.1.1 粒子群優化算法原理 108
6.1.2 粒子群優化算法的優缺點 109
6.2 分數階微分和Alpha穩定分布理論 110
6.2.1 分數階微分理論 110
6.2.2 Alpha穩定分布理論 111
6.3 自適應粒子群優化算法 112
6.3.1 ADFCAPO算法思想 112
6.3.2 均勻初始化粒子策略 112
6.3.3 Alpha穩定分布隨機函數策略 112
6.3.4 基於動態分數階微分的速度計算策略 114
6.3.5 ADFCAPO算法流程 115
6.4 機場停機位分配多目標優化模型的建立 115
6.4.1 優化目標函數的構建 115
6.4.2 多目標優化函數的無量化 116
6.5 基於ADFCAPO算法的機場停機位分配優化方法 117
6.6 算例分析 118
6.6.1 實驗數據與參數設置 118
6.6.2 實驗結果與分析 120
6.6.3 結果比較與分析 123
6.7 本章小結 125
參考文獻 125
第7章 多策略量子進化算法求解機場停機位分配問題 127
7.1 進化算法 127
7.1.1 進化算法概述 127
7.1.2 進化算法原理 127
7.1.3 進化算法特點 128
7.2 量子計算 129
7.2.1 量子計算概述 129
7.2.2 量子計算原理 129
7.2.3 量子門 130
7.2.4 量子旋轉門 131
7.3 量子進化算法 136
7.3.1 量子進化算法概述 136
7.3.2 量子遺傳算法 137
7.4 多策略量子進化算法 139
7.4.1 NCPQEA思想 139
7.4.2 基於小生境進化策略的QEA種群初始化 140
7.4.3 PSO學習因子的動態確定策略 140
7.4.4 基於改進PSO的量子旋轉門更新策略 141
7.4.5 NCPQEA模型 142
7.4.6 NCPQEA步驟 142
7.5 數值實驗與分析 143
7.5.1 標準測試函數 143
7.5.2 實驗環境與參數設置 144
7.5.3 實驗結果與比較 144
7.6 機場停機位分配多目標優化模型的建立 150
7.6.1 優化目標函數的構建 150
7.6.2 多目標優化模型的無量化 151
7.7 基於NCPQEA的機場停機位分配優化方法 151
7.7.1 機場停機位分配優化方法 151
7.7.2 機場停機位分配流程 151
7.7.3 機場停機位分配步驟 151
7.8 算例分析 152
7.8.1 實驗數據 152
7.8.2 實驗環境與參數設置 154
7.8.3 實驗結果與分析 154
7.8.4 結果比較與分析 159
7.9 本章小結 162
參考文獻 162
第8章 兩階段優化算法求解機場延誤航班停機位分配問題 166
8.1 遺傳算法 166
8.1.1 遺傳算法概述 166
8.1.2 遺傳算法原理 166
8.1.3算法定理及其收斂性 167
8.1.4 遺傳算法的優缺點 168
8.2 兩階段優化算法 168
8.2.1 兩階段優化算法思想 168
8.2.2 兩階段優化算法流程 169
8.2.3 兩階段優化算法步驟 169
8.3 數值實驗與分析 170
8.3.1 TSP問題描述 170
8.3.2 實驗環境與參數設置 171
8.3.3 實驗結果與分析 171
8.4 延誤航班停機位再分配優化模型的建立 173
8.4.1 航班延誤分析 174
8.4.2 停機位再分配描述與分析 174
8.4.3 優化目標函數的構建 176
8.4.4 多目標優化模型的無量化 177
8.5 基於兩階段優化算法的延誤航班停機位再分配方法 177
8.5.1 延誤航班停機位再分配方法 177
8.5.2 延誤航班停機位再分配流程 178
8.6 延誤航班停機位再分配實現過程 178
8.6.1 延誤航班停機位再分配第一階段的實現 178
8.6.2 延誤航班停機位再分配第二階段的實現 186
8.7 實例分析 190
8.7.1 實驗數據 190
8.7.2 實驗環境與參數設置 191
8.7.3 實驗結果與分析 192
8.7.4 結果比較與分析 195
8.8 本章小結 200
參考文獻 200

第1章 緒論
1.1 停機位分配問題的研究背景和意義
隨著國民經濟的快速發展和人民生活水平的提高，航空運輸作為一種方便、舒適、快捷的空中交通方式，乘坐比重愈來愈大。據民航局預計，我國航空運輸總周轉量以年均14%高速增長，到2025年中國民航將實現運輸總周轉量2000億噸公裡以上，航空旅客運輸量將超過8.7億人次，貨郵運量2600萬噸，旅客周轉量在國家綜合交通運輸中的比重達到20%以上[1]，這將導致機場面臨著容量不足的問題。我國《民用運輸機場建設“十三五”規劃中期調整方案》提出，要續建機場30個、新建機場43個、改擴建機場125個和遷建機場17個，但在短期內通過耗時耗資對停機位、跑道、航站樓等關鍵資源進行新建或擴容難以解決機場資源容量的嚴重不足問題[2，3]。因此，在保證航班安全運行的前提下，對機場現有的有限關鍵資源進行優化配置與合理調度，提高關鍵資源利用率和機場服務水平，進而全面提升經濟效益。
停機位作為機場極其稀缺和昂貴的重要資源，是實現航班快速安全停靠、保證航班之間有效銜接、提高整個機場系統容量和服務效率的一個關鍵因素。機場停機位分配問題是針對關鍵資源停機位分配的優化問題，旨在滿足一定約束條件和目標要求的前提下，為每個執行航班分配適當停機位，以保證航班正常和客貨的有效銜接，提高機場的服務質量。該問題具有內在的多目標、多約束和多資源理論復雜屬性，且由航空公司自身原因、流量控制、天氣原因等造成的不正常航班停機位再分配問題更為復雜。停機位已成為繼跑道之後又一個制約機場發展的瓶頸，不合理的停機位分配，不但增加航班的延誤、降低資源的利用率，造成旅客滿意度的下降，而且還增加了航空公司和機場的運營成本[4，5]。因此日益增長的航空運輸需求與航空運輸系統容量之間的矛盾愈加突出，導致機場停機位分配問題的重要性日益凸顯。由此可見，機場停機位分配問題的研究在現實中具有重要意義。
停機位靜態分配只考慮了機場結構、航班數、飛機類型等確定性因素，沒有考慮航班延誤、航班早到、航班新增、航班取消等隨機因素。而現實運行中任何停機位分配都不可避免存在動態不確定因素，如惡劣天氣、飛機機械故障、空中流量控制等，都將導致航班延誤，甚至航班取消。近年來，我國航班不但正常率不斷降低(已低於80%)，而且平均延時也在增加(已達到60分鐘)。根據不正常航班產生原因的分類統計，由航空公司自身原因造成的航班不正常達到40%以上，其次是流量控制約占25%，天氣原因約占20%[6]。天氣和流量控制導致的航班不正常並不是主要原因，也是航空公司無法控制的；而航空公司自身原因導致的航班不正常卻是整個航班不正常的*大貢獻者，有不少研究表明導致航班不正常的主要原因是航空公司的調度設計決策不合理造成的。某一航班的不正常可能對分配到同一停機位的其他航班造成連鎖效應，甚至出現“多米諾效應”，從而導致機場停機位完全重新再分配與調度。航班停機位的改變將對操作人員、安保人員、旅客等造成廣泛的影響。因此，獲得具有魯棒性的停機位分配甚至動態分配的計劃，得到穩定高效的智能調度方案，不僅對機場各部門非常重要，而且還能提升旅客的服務質量，對於實現智能機場的智能化具有重要的理論意義和實際價值。
1.2 機場停機位分配問題
停機位分配問題就是將機場每一架進港的飛機，安排到一個合適的停機位上。其中，每個停機位在同一時刻只能停靠一架允許的機型，並且每個停機位上的飛機都會執行一個到達航班和一個出發航班，這兩個航班由這一架飛機來執行，這兩個航班相互配對形成了一個航班對，這架飛機在此停機位上的停靠時間被稱為機位占用時間。在機位占用時間內，別的飛機不能停靠在此停機位上，在這架飛機離開此停機位後，還要求在一個安全間隔時間以後，才允許將此停機位安排給另外一架飛機使用。
飛機在停機位上的主要作業活動流程圖，如圖1.1所示。
圖1.1 飛機在停機位上的主要作業活動流程圖
停機位分配問題是經典分配問題的一種變形，其中停機位是被分配者，任務是待分配停機位的航班。停機位分配與經典分配的不同之處在於一些被分配者不能執行某些任務、任務比被分配者多，以及任務和被分配者的數量隨時間變化等。停機位分配問題與經典分配問題的主要區別還在於經典分配問題中沒有限定完成任務的準確時間段，而在停機位分配問題中，則明確規定了作為“任務”的完成時間，所以停機位分配問題比經典分配問題要更為復雜。
1.3 停機位分配問題的研究現狀
針對機場有限的停機位資源分配問題，國外學者從20世紀70年代便開始了停機位分配問題的研究，主要通過抽象和歸納停機位分配問題中的約束條件，建立其數學模型，並從數學上研究數學模型的求解。國內開展停機位分配問題的研究起步較晚，約從2004年起，一些專家學者才開展機場停機位分配的研究，主要采用數學規劃法、分支定界法、專家系統、啟發式算法等來實現停機位的分配。作為一類受人類智能、生物群體社會性或自然現象規律的啟發而發展起來的群集智能優化算法，如遺傳算法、粒子群優化算法、禁忌搜索算法、蟻群優化算法、差分進化算法、菌群優化算法、螢火蟲算法等，具有較強的全局優化能力，已成功用於機場停機位資源的優化分配，並取得了較理想的停機位分配結果。這些年來，學術界主要集中在停機位靜態分配的研究，而與實際動態環境更加密切的停機位動態分配與實時再分配的研究相對較少。下面對國內外關於機場停機位分配問題的研究現狀進行分析。
1.3.1 停機位靜態分配問題的研究現狀
停機位靜態分配問題是從20世紀70代開始研究，至今已提出關鍵路徑法、分支定界法、整數規劃法、啟發式算法等研究方法。Braaksma等[7]*早以所有旅客行走距離*小為單一目標，建立了基於關鍵路徑法的仿真模型，以增強停機位的利用率。Babic等[8]以旅客步行距離*短為目標構建了停機位分配模型，利用分支定界法對其求解。Mangoubi等[9]在 Babic模型基礎上構建了以旅客步行總距離*小化的數學規劃模型。針對分支定界、動態規劃、線性松弛等精確算法只能分析小規模問題，提出了元啟發式方法(遺傳算法、禁忌搜索、模擬退火等)用於求解較大規模的停機位分配問題。Haghani等[10]采用啟發式算法求解提出的機場終端停機位分配整數規劃模型。文軍[11]用劃分時間片算法建立了停機位分配的圖論模型，將機場停機位分配問題轉化為圖的 K-頂點著色問題，采用遺傳算法求解圖的 K-頂點著色問題。馮程等[12]建立了以旅客進出機場飛行區時間*短為目標的停機位分配模型，通過沈陽桃仙國際機場實際數據設計了算法和仿真分析。Genc等[13]建立了以停機位占用時間*大為目標的停機位分配模型，采用混合啟發式算法和隨機方法對其求解。Cheng等[14]建立了基於遺傳算法、禁忌搜索和模擬退火相結合的機場停機位分配方法。Kim等[15]提出了旅客過境和飛機滑行加權*小時間的停機位分配模型，並采用遺傳算法對其求解。陳前等[16]考慮到機場系統的安全運行約束，建立了避免衝突的停機位分配模型，采用遺傳算法進行求解，驗證了模型的合理性與有效性。馬思思等[17]基於傳統停機位指派要求和場面運行安全規定以及航空公司約束，以滑行總距離*小為目標函數建立停機位分配模型，采用全局求解器( global solver)進行了求解。李云鵬等[18]根據機場停機位分配的實際規則，以*小化停機位使用數目為優化目標，建立了停機位分配混合整數規劃模型，采用基於屬性匹配的啟發式算法對其進行了求解。Pternea等[19]建立一個考慮機場的布局和航班連接的停機位分配模型，並對其進行了求解。Zhao等[20]以*大分配率為優化目標建立了機場停機位分配模型，采用深度強化學習求解模型。
這些文獻分析表明，當前是以實際運營為導向的停機位分配問題研究，主要運用啟發式算法求解實際航班停機位分配問題。
1.3.2 多目標停機位分配問題的研究現狀
停機位分配是一個復雜的多目標組合優化問題，國內外一些研究者對多目標停機位分配問題進行了探討，多目標機位分配問題已成為近年來的研究熱點。Yan等[21]以*小化旅客行走距離和到達旅客等待時間為目標，建立了多目標0-1整數規劃模型，結合變量產生法、單純型法及分支定界法對其求解。Ding等[22]考慮*小化未分配停機位的航班數量和旅客總計步行距離(進離港航班、轉機)兩個優化目標，建立了受限停機位二次分配模型，運用貪婪算法、模擬退火、禁忌搜索等群集智能優化算法對其求解。Drexl等[23]考慮*小化無停機位的航班數量和旅客行走距離以及*大化航班停機位偏好為優化目標，利用基於 Pareto的模擬退火算法獲得 Pareto前沿優化解。楊文東等[24]以航班延誤和停機位空閑時間線性總和*小為優化目標，提出了停機位航班連結樹的概念和構造方法，利用貪婪算法對其求解。劉長有等[25]為合理分配大型繁忙機場停機位，兼顧安全與效率，建立了基於運行安全的停機位分配問題優化模型，利用遺傳算法對其求解。丁建立等[26]根據不同航班占用停機位的時間衝突約束，建立了基於停機位和航班類型匹配約束的圖權值停機位分配模型，並用蟻群協調算法對其求解。Maharjan等[27]以飛機燃油成本*小、旅客轉機感受*好和轉機時間*短為優化目標，將停機位分配問題建模為網絡流模型，利用分解方法對其求解。Jiang等[28]以所有旅客步行的距離*短和不同航線步行距離平均化為目標，建立了多目標停機位分配模型。陳華群[29]以停機位使用數量*少，航空器在機場滑行距離或時間*短且充分考慮機位均衡利用為目標，建立了機場停機位分配問題的優化模型，設計了基於螞蟻徑路搜索規則的迭代尋優算法對其求解。Yu等[30]建立了具有穩健性、成本*小和乘客滿意度的停機位分配等效 MIP模型，並設計了4個不同算法對其求解。Genc等[31]以*大化停機位分配、*小化旅客步行距離和*大化航班到登機口偏好為優化目標，建立了多目標停機位分配模型，采用進化單步大爆炸優化方法對其求解。Da.[32]以旅客步行距離*短和地面操作*少化為優化目標，建立機場停機位分配的多目標優化模型，並對其求解。Dell'Orco等[33]以旅客步行距離*短和遠機位使用*小化為優化目標，建立機場停機位分配模型，采用模糊蜂群優化算法對其進行求解。徐思敏等[34]分析了停機位指派過程設計的利益主體，以航空公司運行成本旅客步行距離、航班衝突概率*小化以及航空公司之間的公平性*大化為目標，建立了大型機場停機位多目標指派模型，采用第二代非支配排序遺傳算法對模型進行仿真驗證。Seyedmirsajad等[35]考慮直接影響機場多準則決策過程的所有資源和約束，建立了停機位三目標分配數學模型，采用第二代非支配排序遺傳算法對其進行有效求解。Li等[36]考慮到使用的停機位數量和未分配到停機位的航班數量*少，以及未換乘旅客人數*少為目標，建立了停機位分配的多目標0-1規劃模型，采用參數優化的圖著色算法對模型進行了求解。餘朝軍等[37]在考慮航班類型約束、飛機機體類型約束和轉場時間間隔約束的基礎上，以分配在固定登機口的航班數量*多、使用的固定登機口數量*少和乘客換乘緊張度*小為目標，建立了航班－停機位分配的多目標非線性0-1整數規劃模型，並設計了一種改進型基因編碼的遺傳算法以提高求解效率。閆萍等[38]構建基於衝突回避的滑行道與停機位聯合調度模型，並提出改進的自適應差分進化算法求解問題。方健爾等[39]針對不同的優先級建立多目標規劃模型對航班進行優化分配，采用貪心算法和禁忌搜索算法，結合登機口類型、航班時間的約束，逐次對*大化分配航班問題，*小化中轉旅客*短流程時間問題，*小化旅客總體緊張度問題進行建模求解。唐旭等[40]考慮了航站樓擴增對中轉旅客影響，建立了綜合的登機口優化調度的模型，提出基於社群聯盟衝突消解原則的圖著色優化算法，實現了對模型的優化，得到*佳調度方案。文笑雨等[41]針對登機口候機緊張和中轉旅客航班銜接的