進階搜尋

學院別 > 成功大學 > 工學院 > 民航研究所

下載電子全文  
系統識別號 U0026-2008201616223400
論文名稱(中文) 應用基因演算法於累計飛行時數下考慮機隊規劃與排程
論文名稱(英文) A Modified Genetic Algorithm for Fleet Assignment and Routing with Flight Hour Accumulation Consideration
校院名稱 成功大學
系所名稱(中) 民航研究所
系所名稱(英) Institute of Civil Aviation
學年度 104
學期 2
出版年 105
研究生(中文) 陳昆逸
研究生(英文) Kun-Yi Chen
學號 q46034033
學位類別 碩士
語文別 英文
論文頁數 72頁
口試委員 指導教授-王大中
口試委員-林清一
口試委員-林東盈
中文關鍵字 飛行時數累加  機隊規劃與排程  基因演算法  多旅行商問題 
英文關鍵字 flight hour accumulation  fleet assignment and routing  genetic algorithm  multiple traveling salesman problem 
學科別分類
中文摘要 機隊規劃與排程問題為航空公司營運管理上占重要一環，其目的為根據航線來選擇合適機種與航機再分配至各航班達到最低成本或最大獲利。由於這類問題規模較大，傳統做法則分為機隊規劃與航機維修排程兩方面求解，然而求得的解並非全域最佳解。本篇研究著重於整合機隊規劃與航機維修排程，其目標為在考慮各不同機型的航機在選擇較好的累加飛行時數下來最大化獲利。本研究則應用多旅行商問題(MTSP)模型來描述機隊中的航機指派各航班的狀況及排序。在模型架構上，則以不同的累加飛行時數下來決定維修航班節點的存在或消失，並依此來連接航班節點。在研究方法方面，我們採用基因演算法(GA)為基礎，在部分修改為適合求解該整合性問題。在結果模擬方面，我們使用航空公司的資料來展現本研究所提出的方法。
英文摘要 One essential problem for airline management is to maximize the total profits or minimize the total operating costs through suitable selection of the aircraft from different fleet types for each flight leg. Due to the scale of such problem, most of previous studies considered dividing the entire problem into two smaller problems, fleet assignment problems (FAPs) and aircraft maintenance routing problems (AMRPs), which tend to yield non-global optimal solutions. This research tries to integrate the FAP and AMRP. The objectives are considered about the profit maximizing with the better level aircraft utilization with accumulated flight hour. A multiple traveling salesmen problem (MTSP) model is used to describe the sequence of flights assigned to each aircraft. Maintenance nodes are added based on the flight hour accumulation for each aircraft. A heuristic Genetic Algorithm (GA) is modified for being proper to solve the combined problem. Real data from airlines are used to demonstrate the proposed approach.
論文目次 摘要 I
Abstract II
誌謝 III
Contents IV
List of Tables VI
List of Figures VII
Nomenclature IX
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Literature Review 4
1.3 Outline of this Research 6
Chapter 2 Fleet Assignment Problem (FAP) 7
2.1 The Objective function in FAPs 7
2.2 FAP with Connection Network 11
2.3 FAP with Time-Space Network 13
2.4 FAP with Backward Arc Technology 16
2.5 FAP with MTSP Model 18
Chapter 3 Aircraft Maintenance Routing Problem (AMRP) 21
3.1 The Objective function in AMRPs 21
3.2 AMRP with Connection Network 23
3.3 AMRP with Time-Space Network 25
3.4 AMRP with Rotation Discussion 26
Chapter 4 Fleet Assignment and Maintenance Routing Problem (FAMRP) 29
4.1 The Comparison with Solving FAMRP 29
4.2 Problem Integration for FAP and AMRP 34
4.3 Model for FAMRP 35
4.4 Genetic Algorithm for the Model 43
4.4.1 Genetic Algorithm 43
4.4.2 Modified Genetic Algorithm in Model for FAMRP 49
4.5 Formulation for Exact Solution in FAMRP 55
Chapter 5 Simulation Results 58
5.1 Simulation Data and Implementation 58
5.2 Determining the Proper Parameters and Feasibility Check 59
5.3 Simulation Result of Applying Modified GA to FAMRP 62
5.4 Discussion 65
Chapter 6 Conclusions and Future Research 68
6.1 Conclusion 68
6.2 Future Research 69
References 70
參考文獻 [1] AIRBUS. (2015). Global Market Forecast 2015-2034. Available: http://www.airbus.com/company/market/forecast/?eID=maglisting_push&tx_maglisting_pi1%5BdocID%5D=86756
[2] C. Barnhart and A. Cohn, "Airline schedule planning: Accomplishments and opportunities," Manufacturing & Service Operations Management, vol. 6, no. 1, pp. 3-22, Apr. 2004.
[3] H. D. Sherali, E. K. Bish, and X. Zhu, "Airline fleet assignment concepts, models, and algorithms," European Journal of Operational Research, vol. 172, no. 1, pp. 1-30, Jul. 2006.
[4] C. Sriram and A. Haghani, "An optimization model for aircraft maintenance scheduling and re-assignment," Transportation Research Part A: Policy and Practice, vol. 37, no. 1, pp. 29-48, Jan. 2003.
[5] C. Barnhart, P. Belobaba, and A. R. Odoni, "Applications of operations research in the air transport industry," Transportation Science, vol. 37, no. 4, pp. 368-391, Nov. 2003.
[6] J. Abara, "Applying integer linear programming to the fleet assignment problem," Interfaces, vol. 19, no. 4, pp. 20-28, Aug. 1989.
[7] C. A. Hane, C. Barnhart, E. L. Johnson, R. E. Marsten, G. L. Nemhauser, and G. Sigismondi, "The fleet assignment problem: Solving a large-scale integer program," Mathematical Programming, vol. 70, no. 1-3, pp. 211-232, Oct. 1995.
[8] A. Levin, "Scheduling and Fleet Routing Models for Transportation Systems," Transportation Science, vol. 5, no. 3, pp. 232-255, Aug. 1971.
[9] B. Rexing, C. Barnhart, T. Kniker, A. Jarrah, and N. Krishnamurthy, "Airline fleet assignment with time windows," Transportation Science, vol. 34, no. 1, pp. 1-20, Feb. 2000.
[10] T.-C. Wang and C.-M. Li, "Fleet Assignment with a Continuously Adjustable Flight Schedule," Transportation Journal, vol. 52, no. 3, pp. 323-343, Summer 2013.
[11] T. Chung and J. Chung, "Airline fleet assignment using genetic algorithms," in In Proc. 2002 Genetic and Evolutionary Computation Conference, New York, USA, 2002, p. 255.
[12] P. Ratprasert, "Ant Colony Optimization Applied on Weekly Fleet Assignment with Time Window Model," in In Proc. 14th Air Transport Research Society World Conference, Porto, Portugal, 2010, pp. 1-62.
[13] L. Clarke, E. Johnson, G. Nemhauser, and Z. Zhu, "The aircraft rotation problem," Annals of Operations Research, vol. 69, pp. 33-46, Jan. 1997.
[14] J. A. Bondy and U. S. R. Murty, Graph theory with applications. vol. 290. Oxford, UK: Elsevier Science Ltd., 1976.
[15] C. Barnhart, N. L. Boland, L. W. Clarke, E. L. Johnson, G. L. Nemhauser, and R. G. Shenoi, "Flight String Models for Aircraft Fleeting and Routing," Transportation Science, vol. 32, no. 3, pp. 208-220, Aug. 1998.
[16] Z. Liang, W. A. Chaovalitwongse, H. C. Huang, and E. L. Johnson, "On a new rotation tour network model for aircraft maintenance routing problem," Transportation Science, vol. 45, no. 1, pp. 109-120, Feb. 2011.
[17] Z. Liang and W. A. Chaovalitwongse, The aircraft maintenance routing problem vol. 30. New York: Springer, 2009.
[18] A. Sarac, R. Batta, and C. M. Rump, "A branch-and-price approach for operational aircraft maintenance routing," European Journal of Operational Research, vol. 175, no. 3, pp. 1850-1869, Dec. 2006.
[19] M. Başdere and Ü. Bilge, "Operational aircraft maintenance routing problem with remaining time consideration," European Journal of Operational Research, vol. 235, no. 1, pp. 315-328, May 2014.
[20] J. Díaz-Ramírez, J. I. Huertas, and F. Trigos, "Simultaneous schedule design & routing with maintenance constraints for single fleet airlines," International Journal of Engineering, vol. 2, no. 2, pp. 2305-8269, Feb. 2013.
[21] L. W. Clarke, C. A. Hane, E. L. Johnson, and G. L. Nemhauser, "Maintenance and crew considerations in fleet assignment," Transportation Science, vol. 30, no. 3, pp. 249-260, Aug. 1996.
[22] Z. Liang and W. A. Chaovalitwongse, "A network-based model for the integrated weekly aircraft maintenance routing and fleet assignment problem," Transportation Science, vol. 47, no. 4, pp. 493-507, Nov. 2013.
[23] M. Lohatepanont and C. Barnhart, "Airline schedule planning: Integrated models and algorithms for schedule design and fleet assignment," Transportation Science, vol. 38, no. 1, pp. 19-32, Feb. 2004.
[24] H. D. Sherali, K.-H. Bae, and M. Haouari, "Integrated airline schedule design and fleet assignment: Polyhedral analysis and Benders' decomposition approach," INFORMS Journal on Computing, vol. 22, no. 4, pp. 500-513, Fall 2010.
[25] J. Díaz-Ramírez, J. I. Huertas, and F. Trigos, "Aircraft maintenance, routing, and crew scheduling planning for airlines with a single fleet and a single maintenance and crew base," Computers & Industrial Engineering, vol. 75, pp. 68-78, Sep. 2014.
[26] A. Mercier and F. Soumis, "An integrated aircraft routing, crew scheduling and flight retiming model," Computers & Operations Research, vol. 34 , no. 8, pp. 2251-2265, Aug. 2007.
[27] B. C. Smith, J. F. Leimkuhler, and R. M. Darrow, "Yield management at American airlines," interfaces, vol. 22, no. 1, pp. 8-31, Jan.-Feb. 1992.
[28] P. P. Belobaba, "Survey paper-airline yield management an overview of seat inventory control," Transportation Science, vol. 21, no. 2, pp. 63-73, May 1987.
[29] R. Subramanian, R. P. Scheff, J. D. Quillinan, D. S. Wiper, and R. E. Marsten, "Coldstart: Fleet assignment at delta air lines," Interfaces, vol. 24, no.1, pp. 104-120, Jan.-Feb. 1994.
[30] W.-C. Chuang, "Multiple Traveling Salesman Problem Model for Fleet Assignment," Institute of Civil Aviation, National Cheng Kung University, Taiwan, 2015.
[31] T. Bektas, "The multiple traveling salesman problem: an overview of formulations and solution procedures," Omega, vol. 34, no. 3, pp. 209-219, Jun. 2006.
[32] R. Gopalan and K. T. Talluri, "The Aircraft Maintenance Routing Problem," Operations Research, vol. 46, no. 2, pp. 260-271, Mar.-Apr. 1998.
[33] R. Saltoğlu, N. Humaira, and G. İnalhan, "Aircraft Scheduled Airframe Maintenance and Downtime Integrated Cost Model," Advances in Operations Research, vol. 2016, Feb. 2016.
[34] J. McCall, "Genetic algorithms for modelling and optimisation," Journal of Computational and Applied Mathematics, vol. 184, no. 1, pp. 205-222, Dec. 2005.
[35] D. E. Goldberg and J. H. Holland, "Genetic algorithms and machine learning," Machine Learning, vol. 3, no. 2, pp. 95-99, Oct. 1988.
[36] T. Blickle and L. Thiele, "A comparison of selection schemes used in evolutionary algorithms," Evolutionary Computation, vol. 4, no. 4, pp. 361-394, Winter 1996.
[37] S. Bate and B. Jones, "A review of uniform cross-over designs," Journal of Statistical Planning and Inference, vol. 138, no. 2, pp. 336-351, Feb. 2008.
[38] A. Király and J. Abonyi, Optimization of multiple traveling salesmen problem by a novel representation based genetic algorithm vol. 366. Berlin, Heidelberg: Springer, 2011.
[39] Y. Elhaddad and O. Sallabi, "A new hybrid genetic and simulated annealing algorithm to solve the traveling salesman problem," in in Proc. The World Congress on Engineering, London, U.K., 2010, pp. 11-14.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務，於2019-03-18起公開。
  • 同意授權校外瀏覽/列印電子全文服務，於2020-03-18起公開。
    		•

    如您有疑問，請聯絡圖書館
    聯絡電話：(06)2757575#65773
    聯絡E-mail：etds@email.ncku.edu.tw