利用迴旋時空網路求解飛機維護路徑問題的新方法

《利用迴旋時空網路求解飛機維護路徑問題的新方法》是依託同濟大學，由梁哲擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：利用迴旋時空網路求解飛機維護路徑問題的新方法
• 項目類別：青年科學基金項目
• 項目負責人：梁哲
• 依託單位：同濟大學

中文摘要

飛機維護路徑問題是唯一同時涉及利潤和飛行安全的重要航空規劃問題。目前國外以美國為主的飛機維護路徑問題研究普遍假設以天為單位，即假定航班計畫和盈利能力每天相同。此假設不適用於中國以周為單位的航班設計，故考慮以周為單位的飛機維護路徑問題更加全面重要。然而，國內外以周為單位的研究在模型與算法上未取得令學術界和航空業界滿意的結果。相比以天為單位的問題，以周為單位問題的解空間和算法複雜度都呈指數增長，導致求解非常困難。本項目擬提出一種基於迴旋時空網路的新方法來解決以周為單位的飛機維護路徑問題。初步研究經驗表明，提出的模型有兩個優點：1、模型規模隨著航班數量的上升呈線性增長，對大規模實際問題無需分解算法，易於直接求解；2、模型有緊湊的線性規劃鬆弛解，利於快速找到最優或近似最優解。在此基礎上，本項目擬擴展提出的方法用於解決周機型指派與周飛機維護路徑的整合問題，並設計高效最佳化算法求解整合問題。

結題摘要

飛機維護路徑問題（Aircraft Maintenance Routing Problem）是航空運營中的重要問題，其目標是決定飛機的具體航班飛行路線及其維護計畫。根據以往國內外調查分析，飛機維護的欠缺與疏忽是事故發生的主要原因之一。好的飛機維護路徑計畫能為飛機在飛行路徑中安排充足的維護機會，以確保飛行安全。另一方面，飛機維護路徑與航班延誤密切相關。如果飛行航班路線設計合理，則航班的間隙可以有效吸收延誤，降低延誤在航班間的傳播。由此可見，是唯一一個同時涉及安全、利潤和航班延誤的航空規劃問題，具有重要的社會和經濟價值。 目前，以美國為主導的航空運營管理，特別是飛機維護路徑問題的研究中，一個基本假設是“以天為單位”，即假定航班計畫每天相同，類似我國高鐵。然而，我國航班一周中每天有較大差異，例如：某些小城市並非每天都有航班。歐洲航班與中國類似，“以天為單位”的假設也不適用。 “以周為單位”的航空規劃可執行性更強，能更準確的反映飛機的飛行路線，對國內和國際航空業都具有重要意義。 本課題提出了一個“以周為單位”的迴旋時空網路用於構建混合整數規劃模型求解周飛機維護路徑問題，此迴旋時空網路以維護弧連線7個以天為單位的子時空網路。此模型延續了迴旋時空網路的特性：即模型變數數量隨航班數的增加呈線性增加，且此模型具有緊湊的線性鬆弛解，可在15分鐘內對超過300架飛機、周航班數超過10000的大規模算例得到最優解。值得一提的是，此大規模算例與世界最大的機隊規模相當（美國西南航空公司波音737-700機隊），適用於我國所有的航空公司機隊。“以周為單位”的迴旋時空網路也對其它周期性的網路路由問題有一定借鑑意義。 本課題的相關研究結果共發表在6篇SCI論文上，其中3篇高水平論文分別發表在Transportation Science （2篇）和Transportation Research Part B上，項目負責人均為第一作者。其中發表在 Transportation Science 2013 和 Transportation Research Part B 2015 年的文章被美國、中國、新加坡、香港的多位學者引用並正面評價，顯示本項目的工作具有一定的學術價值和科學意義。