
系統識別號 
U00260207201814495000 
論文名稱(中文) 
應用改良之基因演算法於機隊規劃與維修排程問題 
論文名稱(英文) 
An Improved Genetic Algorithm for Fleet Assignment and Maintenance Routing Problems 
校院名稱 
成功大學 
系所名稱(中) 
民航研究所 
系所名稱(英) 
Institute of Civil Aviation 
學年度 
106 
學期 
2 
出版年 
107 
研究生(中文) 
張育瑄 
研究生(英文) 
YuHsuan Chang 
學號 
Q46054025 
學位類別 
碩士 
語文別 
英文 
論文頁數 
77頁 
口試委員 
指導教授王大中 口試委員詹劭勳 口試委員林東盈

中文關鍵字 
雜交
基因演算法
機隊規劃
航機維修排程

英文關鍵字 
crossover
Genetic Algorithm
aircraft routing
fleet assignment

學科別分類 

中文摘要 
航班的設計規劃在航空公司營運上是非常重要的一個環節，其中包含許多決策因子和變數，像是航班的銜接、航機的指派、航機定期維修的需求和機組人員的排班等等。由於每項決策彼此都有緊密的關聯，而導致整個航班的設計規劃問題變得相當的龐大且複雜。面對這樣棘手的問題，早期的研究將其分割成五個具有邏輯順序的子問題，分別是:制訂航線、航班規劃、機隊指派、維修排程和機組人員排班，並求得各自的區域最佳解。本篇研究著重於整合機隊規劃與航機維修排程問題，目標為考慮不同性能的航機在符合定期維修的要求下達到適當的使用率，同時最大化獲利。研究方法的部分則是由一部份的整數規劃混和改良過的基因演算法，其中，染色體由指派給每架航機的航班串連而形成，並在應用特殊設計的基因雜交及突變步驟的情況下，順利的求得逼近全域最佳的解。本篇研究使用航空公司的資料來進行結果模擬以呈現所提出的研究方法。

英文摘要 
Airline scheduling consists of several decisionmaking tasks. The entire problem scale is large and these decision tasks are closely related. This makes optimally solving the entire problem a challenging problem. Former researchers have divided the problem into five subproblems which could be solved sequentially while sacrificing the global optimality. The ordering of these five subproblems are route development, flight scheduling, fleet assignment problem (FAP), aircraft maintenance routing problem (AMRP), and crew scheduling. In this study, we aim to deal with a problem of solving FAP and AMRP simultaneously. A specially designed GA and integer linear programming are combined for such problem. In the improved GA, the chromosomes are arranged to represent the flight paths for each aircraft. New crossover and mutation processes can then be conducted in a more effective way to finding nearoptimal solutions. Real data from airlines are used to demonstrate the effectiveness of the improved method.

論文目次 
摘要 I
Abstract II
誌謝 III
Contents IV
List of Tables VI
List of Figures VII
Nomenclature IX
Acronyms XII
Chapter 1 Introduction 1
1.1 Motivation and Objective 1
1.2 Literature Review 5
1.3 Outline of this Thesis 10
Chapter 2 Integration of Fleet Assignment and Aircraft Maintenance Routing Problem 11
2.1 Fleet Assignment Problem (FAP) 11
2.1.1 Networks for FAP 11
2.2 Aircraft Maintenance Routing Problem (AMRP) 17
2.2.1 Heuristic Method for AMRP 19
2.3 Fleet Assignment and Maintenance Routing Problem (FAMRP) 24
2.3.1 Integer Linear Programming Model for FAMRP 28
Chapter 3 Genetic Algorithm for FAMRP 31
3.1 General Genetic Algorithm 31
3.1.1 The Basic Structure of a Genetic Algorithm 32
3.2 Improved Genetic Algorithm for FAMRP 42
3.3 The Mixture of Integer Linear Program and Improved GA 57
Chapter 4 Simulation Results 58
4.1 Simulation Data and Environment 58
4.2 Parameters Decision 61
4.3 Simulation Result 62
Chapter 5 Conclusions and Future Research 73
5.1 Conclusion 73
5.2 Future Research 74
References 75

參考文獻 
References
[1] IATA, 2017, "2036 Forecast Reveals Air Passengers Will Nearly Double to 7.8 Billion," http://www.iata.org/pressroom/pr/Pages/2017102401.aspx.
[2] IATA, 2017, "ECONOMIC PERFORMANCE OF THE AIRLINE INDUSTRY," http://www.iata.org/publications/economics/Reports/IndustryEconPerformance/IATAEconomicPerformanceoftheIndustryendyear2017report.pdf.
[3] Abara, J., 1989, "Applying integer programming to the fleet assignment problem," Interfaces, 19(4), pp. 2028.
[4] Daskin, M. S., and Panayotopoulos, N. D., 1989, "A Lagrangian relaxation approach to assigning aircraft to routes in hub and spoke networks," Transportation Science, 23(2), pp. 9199.
[5] Sherali, H. D., Bish, E. K., and Zhu, X., 2006, "Airline fleet assignment concepts, models, and algorithms," European Journal of Operational Research, 172(1), pp. 130.
[6] Ratprasert, P., 2010, "Ant Colony Optimization Applied on Weekly Fleet Assignment with Time Window Model," The Thesis of Institute of Civil Aviation, National Chen Kung University, pp. 162.
[7] Li, Y., and Tan, N., 2013, "Study on Fleet Assignment Problem Model and Algorithm," Mathematical Problems in Engineering, 2013, pp. 15.
[8] Guy, D., Jacques, D., Yvan, D., Marius M, S., and François, S., 1997, "Daily aircraft routing and scheduling," Management Science, 43(6), pp. 841855.
[9] Clarke, L., Johnson, E., Nemhauser, G., and Zhu, Z., 1997, "The aircraft rotation problem," Annals of Operations Research, 69, pp. 3346.
[10] BartholomewBiggs, M. C., Parkhurst, S. C., and Wilson, S. P., 2002, "Global optimization approaches to an aircraft routing problem," European Journal of Operational Research, 146, pp. 417431.
[11] LacasseGuay, E., Desaulniers, G., and Soumis, F., 2010, "Aircraft routing under different business processes," Journal of Air Transport Management, 16(5), pp. 258263.
[12] Feo, T. A., and Bard, J. F., 1989, "Flight scheduling and maintenance base planning," Management Science, 35(12), pp. 14151432.
[13] Gopalan, R., and Talluri, K. T., 1998, "The Aircraft Maintenance Routing Problem," Operations Research, 46(2), pp. 260271.
[14] Chellappan, S., and Ali, H., 2003, "An optimization model for aircraft maintenance scheduling and reassignment," Transportation Research Part A, 37, pp. 2948.
[15] Başdere, M., and Bilge, Ü., 2014, "Operational aircraft maintenance routing problem with remaining time consideration," European Journal of Operational Research, 235(1), pp. 315328.
[16] AlThani, N. A., Ben Ahmed, M., and Haouari, M., 2016, "A model and optimizationbased heuristic for the operational aircraft maintenance routing problem," Transportation Research Part C: Emerging Technologies, 72, pp. 2944.
[17] Barnhart, C., Boland, N. L., Clarke, L. W., Johnson, E. L., Nemhauser, G. L., and Shenoi, R. G., 1998, "Flight String Models for Aircraft Fleeting and Routing," Transportation Science, 32(3), pp. 208220.
[18] Dong, Z., Chuhang, Y., and Lau, H. Y. K. H., 2016, "An integrated flight scheduling and fleet assignment method based on a discrete choice model," Computers & Industrial Engineering, 98, pp. 195210.
[19] Jamili, A., 2017, "A robust mathematical model and heuristic algorithms for integrated aircraft routing and scheduling, with consideration of fleet assignment problem," Journal of Air Transport Management, 58, pp. 2130.
[20] Chen, K. Y., 2016, "A modified genetic algorithm for fleet assignment and routing with flight hour accumulation consideration," National Cheng Kung University
[21] Panda, S., and Padhy, N. P., 2008, "Comparison of particle swarm optimization and genetic algorithm for FACTSbased controller design," Applied soft computing, 8(4), pp. 14181427.
[22] Haroun, S. A., and Jamal, B., 2015, "A performance comparison of GA and ACO applied to TSP," International Journal of Computer Applications, 117(20).
[23] Hane, C. A., Barnhart, C., Johnson, E. L., Marsten, R. E., Nemhauser, G. L., and Sigismondi, G., 1995, "The fleet assignment problem_solving a largescale integer program," Mathematical Programming, 70, pp. 211232.
[24] Talluri, K. T., 1998, "The FourDay Aircraft Maintenance Routing Problem," Transportation Science, 32(1), pp. 4353.
[25] Goldberg, D. E., and Holland, J. H., 1988, "Genetic Algorithms and Machine Learning," Machine Learning, 3(23), pp. 9599.
[26] McCall, J., 2005, "Genetic algorithms for modelling and optimisation," Journal of Computational and Applied Mathematics, 184(1), pp. 205222.
[27] Goldberg, D. E., 1989, "Genetic algorithms in search, optimization, and machine learning, 1989," Reading: AddisonWesley.
[28] Bate, S. T., and Jones, B., 2008, "A review of uniform crossover designs," Journal of Statistical Planning and Inference, 138(2), pp. 336351.
[29] Grefenstette, J. J., 1986, "Optimization of Control Parameters for Genetic Algorithms," IEEE Transactions on Systems, Man, and Cybernetics, 16(1), pp. 122128.
[30] Király, A., and Abonyi, J., 2011, "Optimization of multiple traveling salesmen problem by a novel representation based genetic algorithm," Intelligent Computational Optimization in Engineering, Springer, pp. 241269.
[31] Reeves, C. R., 1995, "A genetic algorithm for flow shop sequencing," Computers & Operations Research, 22(1), pp. 513.

論文全文使用權限 
同意授權校內瀏覽/列印電子全文服務，於20180807起公開。同意授權校外瀏覽/列印電子全文服務，於20180807起公開。 


