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

Airline scheduling consists of several decision-making 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 sub-problems which could be solved sequentially while sacrificing the global optimality. The ordering of these five sub-problems 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 near-optimal solutions. Real data from airlines are used to demonstrate the effectiveness of the improved method.

References
[1] IATA, 2017, "2036 Forecast Reveals Air Passengers Will Nearly Double to 7.8 Billion," http://www.iata.org/pressroom/pr/Pages/2017-10-24-01.aspx.
[2] IATA, 2017, "ECONOMIC PERFORMANCE OF THE AIRLINE INDUSTRY," http://www.iata.org/publications/economics/Reports/Industry-Econ-Performance/IATA-Economic-Performance-of-the-Industry-end-year-2017-report.pdf.
[3] Abara, J., 1989, "Applying integer programming to the fleet assignment problem," Interfaces, 19(4), pp. 20-28.
[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. 91-99.
[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. 1-30.
[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. 1-62.
[7] Li, Y., and Tan, N., 2013, "Study on Fleet Assignment Problem Model and Algorithm," Mathematical Problems in Engineering, 2013, pp. 1-5.
[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. 841-855.
[9] Clarke, L., Johnson, E., Nemhauser, G., and Zhu, Z., 1997, "The aircraft rotation problem," Annals of Operations Research, 69, pp. 33-46.
[10] Bartholomew-Biggs, 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. 417-431.
[11] Lacasse-Guay, E., Desaulniers, G., and Soumis, F., 2010, "Aircraft routing under different business processes," Journal of Air Transport Management, 16(5), pp. 258-263.
[12] Feo, T. A., and Bard, J. F., 1989, "Flight scheduling and maintenance base planning," Management Science, 35(12), pp. 1415-1432.
[13] Gopalan, R., and Talluri, K. T., 1998, "The Aircraft Maintenance Routing Problem," Operations Research, 46(2), pp. 260-271.
[14] Chellappan, S., and Ali, H., 2003, "An optimization model for aircraft maintenance scheduling and re-assignment," Transportation Research Part A, 37, pp. 29-48.
[15] Başdere, M., and Bilge, Ü., 2014, "Operational aircraft maintenance routing problem with remaining time consideration," European Journal of Operational Research, 235(1), pp. 315-328.
[16] Al-Thani, N. A., Ben Ahmed, M., and Haouari, M., 2016, "A model and optimization-based heuristic for the operational aircraft maintenance routing problem," Transportation Research Part C: Emerging Technologies, 72, pp. 29-44.
[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. 208-220.
[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. 195-210.
[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. 21-30.
[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 FACTS-based controller design," Applied soft computing, 8(4), pp. 1418-1427.
[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 large-scale integer program," Mathematical Programming, 70, pp. 211-232.
[24] Talluri, K. T., 1998, "The Four-Day Aircraft Maintenance Routing Problem," Transportation Science, 32(1), pp. 43-53.
[25] Goldberg, D. E., and Holland, J. H., 1988, "Genetic Algorithms and Machine Learning," Machine Learning, 3(2-3), pp. 95-99.
[26] McCall, J., 2005, "Genetic algorithms for modelling and optimisation," Journal of Computational and Applied Mathematics, 184(1), pp. 205-222.
[27] Goldberg, D. E., 1989, "Genetic algorithms in search, optimization, and machine learning, 1989," Reading: Addison-Wesley.
[28] Bate, S. T., and Jones, B., 2008, "A review of uniform cross-over designs," Journal of Statistical Planning and Inference, 138(2), pp. 336-351.
[29] Grefenstette, J. J., 1986, "Optimization of Control Parameters for Genetic Algorithms," IEEE Transactions on Systems, Man, and Cybernetics, 16(1), pp. 122-128.
[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. 241-269.
[31] Reeves, C. R., 1995, "A genetic algorithm for flow shop sequencing," Computers & Operations Research, 22(1), pp. 5-13.