WEO啦

国立虎尾科技大学鼓励性研究计画成果报告
收录时间:2022-11-25 21:36:44  浏览:0
1 國立虎尾科技大學鼓勵性研究計畫成果報告 計畫名稱 基因演算法在航空公司機隊維修排程最佳化之應用 Application of the Genetic Algorithm on the Airline Maintenance Scheduling Optimization 計畫類類別 個別型計畫 計畫編號 TCS93251 執行期間 93 08 01 94 07 31 執行單位 國立虎尾科技大學 飛機工程系 計畫主持人 劉 昇 祥 助理教授 本成果報告包括以下應繳交之附件 赴國外出差或研習心得報告一份 赴大陸地區出差或研習心得報告一份 出席國際學術會議心得報告及發表之論文各一份 國際合作研究計畫國外研究報告書一份 中 華 民 國 9 4 年 08 月 3 1 日 2 國立虎尾科技大學鼓勵性研究計畫成果報告 基因演算法在航空公司機隊維修排程最佳化之應用 基因演算法在航空公司機隊維修排程最佳化之應用 Application of the Genetic Algorithm on the Airline Maintenance Scheduling Optimization 計畫編號 TCS93251 執行期限 93 年 08 月 01 日至 94 年 07 月 31 日 主持人 劉昇祥 助理教授 國立虎尾科技大學 飛機工程系 一 中 英文摘要一 中 英文摘要 飛機定期維修排程問題 係在一設定的排程 時間範圍內 依據民航法規要求 原製造廠規範 及其累計飛行時數 安排飛機進廠維修 在實務 上 由於航空公司機隊飛機數量眾多 如何配合 公司營運需求及棚場容量*** 在不違反法規 避免超點營運下拿捏得宜 規劃定期維護時機 以盡量提高其機隊使用率 降低操作成本 是航 空公司所關心的重點 本研究主要目的在發展一個以基因演算法則 為基礎的啟發式演算法 以航空公司觀點 在棚 場容量***下 探討機隊進廠維修的最佳時程 在數學模式中目標函數的設定上 在於提高整體 機隊之使用率 研究結果經由實務案例 與實際 航空公司修護管制人員人工排程結果相驗證 比 較分析排程結果 確能在合理的計算時間內 獲 致較佳排程結果 符合航空業界需求 關鍵詞關鍵詞 維修排程 基因演算法 啟發式演算法 目標函數 Abstract Airline fleet maintenance problems are defined as within a predetermined time domain in the future arranging the due time and durations of the aircrafts for their scheduled maintenance checks in accordance with requirements by civil aviation regulations original manufacturer s criteria and accumulated aircraft flight hours and cycles In practice an airline usually possess a fleet that have various number of aircrafts The key concern is to arrange an optimal maintenance schedule for every aircraft of the fleet under hangar capacity restriction and operation needs without overdue to maximize their utilization rates thus minimizing their operation costs In this study a genetic algorithm based on heuristics is developed to solve fleet maintenance scheduling problems to meet airline needs Under the restrictions of hangar capacities an optimal schedule is built The objective function of the mathematical model is to increase the utilization rate of the fleet The constructed mathematical model is then applied in a practical airline case Computational results are compared with those made by airline maintenance controllers Through comparison on the resultant schedules it is shown that current model can give better result in acceptable computational time and meet airline demands Keywords Maintenance scheduling problems Genetic algorithm Heuristics Objective function 二 緣由與目的 二 緣由與目的 在航空公司營運成本中 飛機維修成本約佔飛 機總使用成本之 18 25 其中飛機 含零組件 修護又佔飛機總維修成本約 69 其餘 31 為航材 庫存成本 佔有相當***例 1 如何在維持飛航 安全及飛機可靠性的前提下 作適當的維修排程 以提高飛機可用率 降低修護成本 提升公司獲 利 是每個航空公司所關心的問題 航空公司飛機進廠維修排程問題存在已久 航 機維護排程問題 係指在一預設的時域內 依據民 航法規要求 原製造廠規範 及各架飛機累計之飛 行時數 起降次數 安排在適當的時間進廠維護 妥 善的進廠排程 除了賦予的單位維修成本降低 更 有利於確保機隊正常調度 消耗性器材庫存管理及 人力資源管理等好處 實務上 許多國籍航空公司 的機隊進廠維修排程 是由專業修護管制人員以人 工的方式完成 然而由於航空公司機隊飛機數量眾 多 排程工作除需同時考量機隊數量 棚廠*** 人力資源 法規要求與修護工作種類等複雜的*** 條件外 還需力求符合營運部門的機隊需求 綜合 來說 這些人工管制方式不但費時耗力 且受限於 ***因素太多 很難去作縝密的長期維護排程規 劃 且排程結果亦僅為一組可行的方案 很難從經 濟層面評估排程結果的良窳 相對而言 如何有效率找出機隊各飛機之最佳 進廠時機 建立可行且長程的排程 對航空修護單 位存在其需要性與重要性 良好的飛機維護排程除 了 可 以 預 防 因 為 人 為 疏 忽 而 發 生 飛 機 超 點 Overdue 營運的違規事件 進廠排程時若能在 操作成本 包含營運及維修成本 最小化的考量 3 下 同時考量排程的合理性等 將可使維修棚廠以 及機隊的營運效益達到最佳狀況 有關航空方面排程管理的研究起源甚早 由於 在實務上 航空公司機隊管理的諸多需求中 如航 路 設 計 fleet routing 班 表 規 劃 flight scheduling 飛機指派 fleet assignment 組員管理 crew scheduling 維 護 排 程 maintenance scheduling 乃至維護工作指派 Job assignment 維護人力規劃 manpower planning 等 從學術的 角度而言 個別的問題均深具研究價值 而當其中 數種需求須合併考量時 研究難度更具挑戰性 因 此吸引國內外許多學者投入相關研究 航 路 設 計 與 班 表 規 劃 fleet routing scheduling 的相關研究是早期學者主要的投入領 領 在這方面的研究包括 Levin 2 以整數規劃 Integer Programming 的數學模式 搭配分歧界 限法 Branch and Bound 演算法 以及 Desaulniers 3 以具時間***之多工流量管制 time constrained multi commodity network flow formulation 法求解 等 在飛機指派 fleet assignment 問題方面 則有包 括 Hane et al 4 Abara 5 及 Subramanian 6 等 以 線性規劃模式搭配不同演算法研究 相較於於其他 領域的研究 單就維護排程方面的研究較少 大多 都是僅針對短期維護搭配其它需求排程 如 Feo Bard 7 以 混 合 整 數 規 劃 Mixed Integer Programming 的數學模式研究含短期維護排程之 班表規劃 Hane et al 4 以線性規劃 Linear Programming 的數學模式搭配不同演算法研究含 短期維護排程之飛機指派問題 結論均表示 當排 程項目數量龐大時 以線性規劃 或整數規劃 的 數學模式求解最佳化排程 無論搭配何種演算法 都會面臨求解困難 或是計算時間過長的缺點 其 它與維護排程之相關研究如文獻 8 11 所示 如同前述 航機維護排程問題在數學模式中目 標函數的建立上 一般而言並非十分困難 但由於 這類最佳化問題的性質 多屬於複雜度甚高的 NP Hard 整數規劃問題 當變數數量龐大時 在求 最佳解時會有求解困難或計算效率不彰的缺點 由 於此類大型問題多係屬應用型研究 在實務上重視 在計算效率與最佳解之間取得平衡 並不特別強調 最佳解 因此目前研究人員廣泛應用各種啟發式演 算法 諸如模擬退火法 Simulated Annealing 12 禁制蒐尋法 Tabu Search 13 基因演算法 Genetic Algorithm 14 等 或 使 用 動 態 規 劃 Dynamic Programming 15 人工智慧 Artificial Intelligence 16 等方法 來改善計算效率 綜上文獻回顧 本研究的目的在於針對目前演 算法應用於大型排程問題的***及飛機定期維護 工作的特性 發展一個以基因演算法為基礎的排程 分析 研究其使用於航機維護排程問題時之效能 作為後續研究的基礎 以應用於航空公司工程管理 決策支援系統之建構 三 結果與討論 三 結果與討論 如圖一所示 飛機維護排程問題 可以定義 為 在一預設的時域範圍 T 內 將 N 項工作在不同 時間點 安排在 M 個處理器執行 的規劃 在這 N 項工作裏 其中有些工作的安排可能有時間順序的 關係 以數學規劃的觀點而言 維護排程最佳化進 行的方式 是設定一個目標函數 在滿足所有資源 ***的條件下 使目標函數極大化或極小化 求取 在此一目標函數值下 各項工作執行的最佳優先順 序 不同目標函數的選擇 排程結果會有不同的 特性 一般而言 考量的因素不外乎從飛機使用 率 棚場使用率 維護成本 或整體操作成本 含 維護及營運成本 等觀點 來設定目標函數 端視 排程管理人員的優先考量因素而定 沒有孰是孰 非 由於本研究探討的問題特性同時涉及機隊之 長 中 短期排程 經過審慎評估 認為在目標函 數的選取上 若純以飛機使用率為考量標準 會忽 略了不同檢查工作所需成本不同的加乘效果 純以 棚場使用率為考量標準 可能造成飛機長期停廠維 修的反效果 至於整體操作成本中 營運成本與短 期維護排程的關聯度較高 對長 中期排程的影響 有限 將之納入一併考量 會大幅增加計算的困難 度 因此 本研究以維護成本的觀點切入 求取兩 次進場維護期間實際飛行時間與最大許可飛行時 間 或起降次數 的差距 換算為維護成本損失 並以機隊整體維護成本損失為目標函數 求取最小 值 經過分析推導 等效之領導統御方程式如下 1 目標函數 Td iijij iJjPi dyumminimize 1 2 ***條件 決策變數*** else WDdDfor dx ijnijnijn ijn 0 1 2 jiNn ijn iJj i dxdy 3 個別飛機工作項目*** 1 jiNn ijn iJj i dxdy 4 棚廠容量*** TdHdx jiNn ijn iJjPi 5 最大維護間距*** ijijnijnnij CWDD 1 6 4 其它*** iJjPiCMm ijijij 7 Td ijnijn dxW 8 其中 P 為機隊所有飛機所成的*** J i 為飛機 i 所有維護檢查工作類別 如 A SA C SC c h e c k s 所成的*** N i j 為飛機 i 在整個排程時域內 屬於工作類 別 j 之維護檢查工作 依時間順序排列所 成的*** T 為整個排程時域之日期 依時間順序排列所成 的*** Mi j 為飛機 i執行工作類別 j之維護檢查工作所 需之維修成本 m i j 為飛機 i執行工作類別 j之維護檢查工作之 單位操作維修成本 Ci j 為飛機 i執行工作類別 j最大允許之維護間 隔時距 u i j 為飛機 i針對工作類別 j每日平均飛行量 FH d a y 或 c y c d a y Wi j n 為飛機 i 執行第 n 次工作類別 j 之維護檢查 工作所需之日曆天 Di j n 為飛機 i 執行第 n 次工作類別 j 之維護檢查 工作之開始日期 H 為維修棚場容量 x i j n d 為二元變數 當在飛機 i執行第 n次工 作類別 j之維護檢查工作之日期區段 時 其值為 1 在整個排程時域內其它日 期時 其值為 0 y i d 為二元變數 當在飛機 i執行維護檢查工 作之日期區段時 其值為 1 在整個排程時 域內其它日期時 其值為 0 本研究採用以基因演算法為基礎之演算法 以求取全域最佳解 G l o b a l Op t i m i z a t i o n 基 因演算法 G e n e t i c A l g o r i t h m G A 是以仿效生物 學領域達爾文之進化論 物競天擇 適者生存 的 概念發展出來的 以生物族群 Po p u l a t i o n 之基因 為基礎的適應性 Fi t n e s s 搜尋的演算法 經由持 續且反覆的在特定的搜尋空間 Se a r c h Sp a c e 裡 對原始族群搜尋適應性更好的新一代族群 期望使 某物種得以保持持續的演化 而終於達成某物種之 最佳化 基因演算法則使用三種主要運算子 即選擇 Se l e c t i o n 交配 Cr o s s o v e r 以及突變 Mu t a t i o n 如圖二所示 其運算步驟如下 1 首先針對問題 設定代表解答之變數 基因 再將所有變數編*** Co d i n g 組合成染色體 Ch r o m o s o m e 的形式 不同的染色體代表不 同的排程結果組合 2 設計目標函數 適應函數 使其能有效反映每 一個體對問題的目標函數值 3 以隨機方式產生 N 個染色體之初始族群 4 將參數解***代入目標函數計算 每個個體的目 標函數值 5 驗證收斂情況是否滿足所設定的終止條件 若 滿足則結束運算 否則進行下一步驟 6 依目標函數值的大小 決定染色體是否留存或 淘汰的機率 依此機率選擇留存的染色體 並 進行交配與突變 7 重複步驟 4 至 6 圖三所示為本研究依據航空公司實際修護資 料 利用基因演算法計算所得之排程結果 與人工 排程結果之差異分析 比較二者 若摒除飛機進廠 前 實際每日排定飛行時數與本研究所使用之平均 每日飛行時數不同所造成差異的因素 可以看出本 研究預計各機進廠執行定期維護的時間 大都較人 工排程結果可明顯的延後執行 意即表示 各機的 維護期限使用率 兩次定期維護間的實際使用時間 法定使用期限 確實獲得有效的提昇 此外 在 B11 的 C2定期維護上 亦發現本研究預計之進 廠維護時間較人工排程結果提前 1 天 由於本研究 排程結果顯示 詳表一 在 B 機隊之 C Ch e c k 整 體維護期限使用率已達 100 無法再延後實施定期 維護 這表示人工排程結果有可能產生超點營運之 違規風險 此一結果 亦可提供航空公司修護管制 人員作風險及差異評估 表一為各機的維護期限使用率的實際量化結 果 依據本研究所計畫之排程 可使各機種維護期 限使用率均超過 9 8 相較於人工排程結果之 7 7 9 4 確能大幅提昇機隊使用率 至於在所需計 算時間方面 本研究測試不同案例結果 約在 15 秒至 5 分鐘間 對實際航空公司運作而言 屬可接 受之範圍 此亦增加了研究成果之實用性 四 計劃成果自評四 計劃成果自評 本研究採用整數規劃之數學模式 配合基因演 算法則 分析航空公司機隊之最佳維修排程 相較 於傳統演算法 基因演算法有下列特性 1 基因演算法是以參數***之編***進行運算而不 是參數本身 因此可以避免搜尋空間之*** 2 基因演算法的運算過程中 是在由參數組合而 成的染色體搜尋空間中尋找合適的點 並由設 定好的適應函數來量化不同個體的目標函數 值 以作為決定下一個合適點的參考 而不需 要其他輔助資訊 因此適用各種型態的目標函 數函數 3 基因演算法同時搜尋空間上多個點而非單一 點 因此可以比較快獲得整體最佳解 並減少 陷入區域最佳解的機會 4 基因演算法是使用機率規則的方式去引導搜尋 方向 而非確定性規則 Deterministic Rules 能符合各種不同類型的最佳化問題 5 基於上述特性 尤其是基因演算法僅需計算目 標函數值 不需要考慮相關函數的微分性 梯度等 特性 使基因演算法適用於各種類型的最佳化問 題 特別是對建構數學模型有困難的規劃排程問題 上 由研究成果顯示 確能在合理的計算時間內大 幅改善人工排程的結果 提昇機隊使用之效益 在 實務應用上為一有價值之研究成果 五 參考文獻 五 參考文獻 1 袁新安 GAMECO 為降低南航維修成本所作 的嘗試與探索 航空維修工程和成本管理國際 研討會 第 3 1 3 5 頁 2000 年 2 Levin A Scheduling and fleet routing models for transport system Transportation Science Vol 5 pp 232 255 1971 3 Desaulniers G Daily aircraft routing and scheduling Management Science Vol 43 pp 841 855 1997 4 Hane C A Barnhart C Johnson E L Marsten R E Nemhauser G L Sigismondi G The fleet assignment problem solving a large scale integer program Mathematical Programming Vol 70 pp 211 231 1995 5 Abara J Applying integer linear programming to the fleet assignment problem Interfaces Vol 19 pp 20 28 1989 6 Subramanian R Scheff Jr R P Quillinan J D Coldstart fleet assignment at Delta Airlines Interfaces Vol 24 pp 104 120 1994 7 Feo A Bard F Flight scheduling and maintenance base planning Operations Research Vol 35 pp 1415 1432 1989 8 Brio M Aircraft and maintenance scheduling support mathematical insights and a proposed interactive system Journal of Advanced Transportation Vol 26 pp 121 130 1992 9 Kabbani N M Patty B W Aircraft routing at American Airlines In Proceedings of the Thirty Second Annual Symposium of the Airline Group of the International Federation of Operational Research Societies Budapest Hungary 1992 10 Talluri K Swapping application in a daily airline fleet assignment Transportation Science Vol 30 pp 237 248 1996 11 Clarke L W Johnson E L Nemhauser G L Zhu Z The aircraft rotation problem Annals of Operations Research Vol 69 pp 33 46 1997 12 Mamalis A G Malagardis I Determination of due dates in job shop scheduling by simulated annealing Computer Integrated Manufacturing Systems Vol 9 No 2 pp 65 72 1996 13 Gopalakrishnan M Mohan S He Z A tabu search heuristic for preventive maintenance scheduling Computers Industrial Engineering Vol 40 pp 149 160 2001 14 Deris S Omatu S Ohta H Kutar S Samat P A Ship maintenance scheduling by genetic algorithm and constraint based reasoning European Journal of Operational Research Vol 112 pp 489 502 1999 15 Moudani W E Felix Mora Camino A dynamic approach for aircraft assignment and maintenance scheduling by airlines J Air Transportation Management Vol 6 pp 233 237 2000 16 Smits S Pracht D MOCA A knowledge based system for airline maintenance scheduling In Smith R G Scott A C Eds Innovative Applications of Artificial Intelligence Ch 3 AAAI Press Menlo Park CA pp 21 38 19
温馨提示:
1. WEO啦仅展示《国立虎尾科技大学鼓励性研究计画成果报告》的部分公开内容,版权归原著者或相关公司所有。
2. 文档内容来源于互联网免费公开的渠道,若文档所含内容侵犯了您的版权或隐私,请通知我们立即删除。
3. 当前页面地址:https://www.weo.la/doc/a0e9906598961117.html 复制内容请保留相关链接。