本研究發展出一個以不等式法為基礎的多目標基因演算法，應用在短程、快速回轉航班之航空排程擾動管理上，以便在短時間內求算出一個具有時間效益之航班排班方式，用以處理航班受擾動後之回復。此一處理方式涵蓋五個最佳化目標，包括：1)地面停等時間、2)航班連結、3)航班互換、4)總航班延誤時間、及5)超過十五分鐘延誤航班數等，以期能在班表變動最小的情況下完成航班擾動之處理作業。
本研究所採行之多目標最佳化基因演算法，係以傳統之基因演算法，加上制約不等式法及多目標最佳化之方法，以便於能同時考慮到許多不同的目標，並找出最佳解。傳統上航班擾動管理的問題都是採用數學規劃的技巧，然而此類方法必須要有精確的數學模式定義。在現實作業中，由於環境的複雜及動態的變化，常常需要同時考慮許多因素，因而使得數學模式的定義變得非常困難。本研究使用實際之航空公司班表來進行驗證，以確認本研究所提出之多目標最佳化航空擾動管理模式，具有在短時間內處理航班擾動問題之能力。此一驗證結果顯示本研究可在幾分鐘內產生高品質的解，未來將能把一模式推廣應用至航空公司之實務運作上，以便爭取決策時效，節省經營成本、增進旅客權益，並且減少環境污染。

This study develops a method of inequality-based multiobjective genetic algorithm (MMGA) to generate efficiently a time-effective multi-fleet aircraft routing in response to the schedule disruption of short-haul, quick turnaround flights, and attempts to optimize objective functions involving ground turnaround time, flight connection, flight swap, total flight delay time and flights over 15-minute delay of original schedules. The MMGA approach, which combines a traditional genetic algorithm with a multiobjective optimization method, can deal with multiple objectives in the same time, and then explores the optimal solution. The airline schedule disruption management problem is traditionally solved by mathematical modeling techniques that always require a precise mathematical model. However, airline operations involve too many factors that must be considered dynamically, making a precise mathematical model will be very difficult to define in time. Empirical analyses based on the real-world airline flight schedules demonstrate that the proposed method, method of inequality-based multiobjective genetic algorithm for airline schedule disruption management, can recover the perturbation efficiently within a very short time. Our results demonstrate that the application can yield high quality solutions in a few minutes and, consequently, can be employed as a real-time decision supporting tool for practical complex airline operations to save operation cost; increase passengers’ convenience and prevent air pollution.

1. Air Transport Association (2008). Economic & Energy Special Topics: Cost of delay. http://www.airlines.org/economics/specialtopics/ATC+Delay+Cost.htm.
2. Association of European Airlines (2008). European airline punctuality report. http://www.aea.be/research/performance/index.html.
3. Abdelghany, K. F., Shah, S. S., Raina, S., & Abdelghany, A. F. (2004). A model for projecting flight delays during irregular operation conditions. Journal of Air Transport Management, 10(6), pp. 385-394.
4. Abdelghany, K. F., Abdelghany, A. F., & Ekollu, G. (2008). An integrated decision support tool for airlines schedule recovery during irregular operations. European Journal of Operational Research, 185(2), pp. 825-848.
5. Adachi, N., Sato, M., & Kobayashi, S. (2004). Application of genetic algorithm to flight schedule planning. Systems and Computers in Japan, 35(12), pp. 888-895.
6. Adenso-Diaz, B., Gonzalez, M. O., & Gonzalez-Torre, P. (1999). On-line timetable re-scheduling in regional train service. Transportation Research Part B, 33(6), pp. 387-398.
7. Ahmed, A. H., & Poojari, C. A. (2008). An overview of the issues in the airline industry and the role of optimization models and algorithms. Journal of the Operational Research Society, 59(3), pp. 267-277.
8. Andersson, T., & Värbrand, P. (2004). The flight perturbation problem. Transportation Planning and Technology, 27(2), pp. 91-117.
9. Anderson, T. (2006). Solving the flight perturbation problem with meta heuristics. Journal of Heuristics, 12(1), pp. 37-53.
10. Argüello, M., Bard, J. & Yu, G. (1997a). A GRASP for aircraft routing in response to groundings and delays. Journal of Combinatorial Optimization, 1(3), pp. 211-28.
11. Argüello, M., Bard, J., & Yu, G. (1997b). Models and methods for managing airline irregular operations aircraft routing. Operations Research in the Airline Industry. Kluwer Academic Publishers, Boston.
12. Aytug, H., Khouja, M., & Vergara, F. E. (2003). Use of genetic algorithms to solve production and operations management problems: a review. International Journal of Production Research, 41(17), pp. 3955-4009.
13. Bard, J. F., Yu, G., & Argüello, M. F. (2001). Optimizing aircraft routings in response to groundings and delays. IIE Transactions, 33(10), pp. 931-947.
14. Barnhart, C., Boland, N., Clarke, L., Johnson, E. L., & Nemhauser, G. L. (1998). Flight string models for aircraft fleeting and routing. Transportation Science, 32(3), pp. 208-220.
15. Barnhart, C., Kniker, T., & Lohatepanont, M. (2002). Itinerary-based airline fleet assignment. Transportation Science, 36(2), pp. 199-217.
16. Barnhart, C., Belobaba, P., & Odoni, A. R. (2003). Applications of operations research in the air transport industry. Transportation Science, 37(4), pp. 368-391.
17. Berge, M., & Hopperstand, C. (1993). Demand driven dispatch: A Method for dynamic aircraft capacity assignment, models and algorithms. Operations Research, 41(1), pp. 153-168.
18. Bratu, S. & Barnhart, C. (2006). Flight operations recovery: New approaches considering passenger recovery. Journal of Scheduling, 9(3), pp. 279-298.
19. Buckles, B. P., & Petry, F. E. (1992). Genetic Algorithms. IEEE Computer Society Press, Los Alamitos, CA.
20. Cao, J. M. & Kanafani, A. (1997a). Real-time decision support for integration of airline flight cancellations and delays part I: mathematical formulations. Transportation Planning and Technology, 20(3), pp. 183-199.
21. Cao, J. M. & Kanafani, A. (1997b). Real-time decision support for integration of airline flight cancellations and delays part II: algorithms and computational experiments. Transportation Planning and Technology, 20(3), pp. 201-217.
22. Carey, M. & Kwiecinski, A. (1994). Stochastic approximation to the effects of headways on knock-on delays of trains. Transportation Research Part B, 28(4), pp. 251-267.
23. Carlier, S., Hustache, J.-C., & Jelinek, F. (2006). Environmental impact of delay. Project report, EUROCONTROL, Brussels, Belgium.
24. Carlier, S., de Lepinay, I., Hustache, J.-C., & Jelinek, F. (2007). Environmental impact of air traffic flow management melays. 7th USA/Europe Air Traffic Management Research and Development Seminar. Barcelona, Spain.
25. Carlsson, F., & Hammar, H. (2002). Incentive-based regulation of CO2 emissions from international aviation. Journal of Air Transport Management, 8(6), pp. 365-372.
26. Chan, F. T. S., Chung S. H. & Chan, P. L. Y. (2006). Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems. International Journal of Production Research, 44(3), pp. 523-543.
27. Chatterjee, S., Carrera, C., & Lynch, L. A. (1996). Genetic algorithms and traveling salesman problems. European Journal of Operational Research, 93(3), pp. 490-510.
28. Chou, D. Y., Liu, T. K., Lee, C. N., & Jeng, C. R. (2008). Method of inequality-Based multiobjective genetic algorithm for domestic daily aircraft routing. IEEE Transactions on Systems Man and Cybernetics Part A-Systems and Humans, 38(2), pp. 299-308.
29. Clarke, M. (1997). The airline schedule recovery problem, Working paper, International Center for Air Transportation, Massachusetts Institute of Technology, Boston, MA.
30. Clarke, M. (1998). Irregular airline operations: a review of the state-of-the-practice in airline operations control centers. Journal of Air Transport Management, 4(2), pp. 67-76.
31. Clarke, M., & Smith, B. (2004). Impact of operations research on the evolution of the airline industry. Journal of Aircraft, 4(1), pp. 62-72.
32. Clausen, J., Hansen, J., Larsen, J., & Larsen, A. (2001). Disruption management, OR/MS Today, 28, pp. 40-43.
33. Coello Coello, C. A. (2000). An updated survey of GA-based multiobjective optimization techniques. ACM Computing Surveys, 32(2), pp. 109-143.
34. Coello Coello, C. A., Van Veldhuizen, D. A., & Lamont, G. B. (2002). Evolutionary Algorithms for Solving Multi-Objective Problems, Kluwer Academic Publishers, New York.
35. Coello Coello, C. A., Aguirre, A. H., & Zitzler, E. (2007). Evolutionary multi-objective optimization. European Journal of Operational Research, 181(3), pp. 1617-1619.
36. Cook, A., Tanner, G., and Anderson, S. (2004). Evaluating the true cost to airlines of one minute of airborne or ground delay. Project report, EUROCONTROL, Brussels, Belgium.
37. Deb, K. (2001). Multi-objective optimization using evolutionary algorithms. John Wiley and Sons Inc., Chichester, U.K.
38. Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), pp. 182-197.
39. De Jong, K. (1988). Learning with genetic algorithms: An overview. Machine Learning, 3(2), pp. 121-138.
40. De Villemeur, E., Ivaldi, M., & Urdanoz, M. (2007). Social costs of air traffic delays. IDEI Working Papers 460, Institut d'Économie Industrielle (IDEI), Toulouse, France.
41. Fonseca, C. M., & Fleming, P. J. (1993). Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization. In Proceedings of the Fifth International Conference on Genetic Algorithms. San Mateo, CA, USA. pp. 416-423.
42. Fonseca, C. M., & Fleming, P. J. (1995). An overview of evolutionary algorithms in multiobjective optimization. Evolutionary Computation, 3(1), pp. 1-16.
43. Fonseca, C. M., & Fleming, P. J. (1995). Multiobjective genetic algorithms made easy: selection sharing and mating restriction. First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, The University of Sheffield, Sheffield, U.K.
44. Fonseca, C. M., & Fleming, P. J. (1998). Multiobjective optimization and multiple constraint handling with evolutionary algorithms - Part I: A unified formulation. IEEE Transactions on Systems Man and Cybernetics Part A-Systems and Humans, 28 (1), pp. 26-37.
45. Gen, M. & Cheng, R. (1997). Genetic algorithms and engineering design, John Wiley and Sons, Inc., New York, NY.
46. Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning, Addison-Wesley Reading, Boston, MA.
47. Hartmann, S. (2002). A self-adapting genetic algorithm for project scheduling under resource constraints. Naval Research Logistics, 49(5), pp. 433-448.
48. Higgins, A. & Kozan, E. (1998). Modeling train delays in urban network. Transportation Science, 32(4), pp. 346-357.
49. Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan, Ann Arbor, MI.
50. Horn, J., Nafpliotis, N., & Goldberg, D. E. (1994). A niched Pareto genetic algorithm for multiobjective optimization. Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence. Orlando, FL., USA.
51. IATA (2007), IATA Economic Briefing – Airline fuel and labor cost share. http://www.iata.org/NR/rdonlyres/4A49F6DA-2B12-48A9-A283-E035AEA5D165/0/Airline_Labour_Cost_Share.pdf.
52. Institut du Transport Aérien (2000), Costs of air transport delay in Europe, Paris, France.
53. Intergovernmental Panel on Climate Change (IPCC) (2006). 2006 IPCC guidelines for national greenhouse gas inventories, Vol. 2, Chapter 3: Mobil combustion. Kanagawa, Japan.
54. Janic, M. (2003). Large scale disruption of an airline network: A model for assessment of the economic consequences. The 81st Transportation Research Board (TRB) Conference. Washington DC, USA.
55. Jarrah, A. I., Yu, G., Krishnamurthy, N. & Rakshit, A. (1993). A decision support framework for airline flight cancellations and delays. Transportation Science, 27(3), pp. 266-280.
56. Joint Economic Committee (2008). Your flight has been delayed again - Flight Delays Cost Passengers, Airlines, and the U.S. Economy Billions. Technology report, U.S. Congress, Washington D.C., U.S.A.
57. Kim, B., Fleming, G., Balasubramanian, S., Malwitz, L., Lee, J., Waitz, I., Klima, K., Locke, M., Holsclaw, C., Morales, A., McQueen, E., & Gillette, W. (2005). System for assessing aviation’s global emissions: Global aviation emissions inventories for 2000 through 2004, Version 1.5, FAA-EE-2005-02, Federal Aviation Administration Office of Environment and Energy, Washington DC, USA.
58. Kohl, N., Larsen, A., Larsen, J., Ross, A., & Tiourine, S. (2007). Airline disruption management - Perspectives, experiences and outlook. Journal of Air Transport Management, 13(3), pp.149-162.
59. Lee, L. H., Lee, C. U., and Tan, Y. P., 2007. A multi-objective genetic algorithm for robust flight scheduling using simulation. European Journal of Operational Research, 177(3), 1948-1968.
60. Liu, T. K., Satoh, T., Ishihara, T., & Inooka, H. (1994). An application of multiobjective genetic algorithms to control system design. Proceedings of the First Asian Control Conference, Tokyo, Japan, pp. 701-704.
61. Liu, T. K., Ishihara, T., & Inooka, H. (1995). Multiobjective control systems design by genetic algorithms. The 34th SICE Annual Conference. SICE '95, Hokkaido, Japan. pp. 1521-1526.
62. Liu, T. K. & Ishihara, T. (2005). Multi-objective genetic algorithms for the method of inequalities, in: V. Zakian (Ed.) Control Systems Design - A New Framework, Chapter 8, pp. 231-248, Springer-Verlag, London, UK.
63. Liu, T. K., Tsai, J. T. & Chou, J. H. (2006). Improved genetic algorithm for the job-shop scheduling problem. International Journal of Advanced Manufacturing Technology, 27(10), pp. 1021-1029.
64. Liu, T. K., Jeng, C. R., & Chang, Y. H. (2008). Disruption management of an inequality-based multi-fleet airline schedule by a multi-objective genetic algorithm. Transportation Planning and Technology, 31(6), pp. 613 - 639.
65. Lohatepanont, M. & Barnhart, C. (2004). Airline schedule planning: Integrated models and algorithms for schedule design and fleet assignment. Transportation Science, 38(1), pp. 19-32.
66. Løve, M., Sørensen, K. R., Larsen J. & Clausen, J. (2001). Using heuristics to solve the dedicated aircraft recovery problem. Technical Report IMM-TR-2001-18, Department of Informatics and Mathematical Modelling, Technical University of Denmark, Lyngbvy, Denmark.
67. Løve, M., Sørensen, K. R., Larsen J. & Clausen J. (2002). Disruption management for an airline - rescheduling of aircraft, in: G. Goos et al. (Ed.) Lecture Notes in Computer Science - Applications of Evolutionary Computing, 2279, pp. 315-324, Springer-Verlag, Berlin, Germany.
68. Løve, M., Sørensen, K. R., Larsen, J. & Clausen, J. (2005). Using heuristics to solve the dedicated aircraft recovery problem. Central European Journal of Operations Research, 13(2), pp. 189-207.
69. Lu, C., & Morrell, P. (2006). Determination and applications of environmental costs at different sized airports - aircraft noise and engine emissions. Transportation, 33(1), pp. 45-61.
70. Lu, C. (2008). The implications of environmental costs on air passenger demand for different airline business models. Journal of Air Transport Management, In Press, Corrected Proof.
71. Luo, S. & Yu, G. (1997). On the airline schedule perturbation problem caused by the ground delay program. Transportation Science, 31(4), pp. 298-311.
72. Marland, G., Boden, T. A., Andres, R. J., Brenkert, A. L., & Johnston, C. A. (2007). Global, regional, and national CO2 emissions. In Trends: A compendium of data on global change. Carbon Dioxide Information Analysis Center, Oak Ridge National Laboratory, U.S. Department of Energy, Oak Ridge, TN., USA.
73. Mathaisel, D. (1996). Decision support for airline system operations control and irregular operations. Computers and Operations Research, 23(11), pp. 1083-1098.
74. Mathaisel, D. (1997). Decision support for airline schedule planning. Journal of Combinatorial Optimization, 1(3), pp. 251-275.
75. Mayer, C., & Sinai, T. (2003). Network effects, congestion externalities, and air traffic delays: or why not all delays are evil. The American Economic Review, 93(4), pp. 1194-1215.
76. Mori, M. & Tseng, C. C. (1997). A genetic algorithm for multi-mode resource constrained project scheduling problem. European Journal of Operational Research, 100(1), pp. 134-141.
77. Morrell, P. (2007). An evaluation of possible EU air transport emissions trading scheme allocation methods. Energy Policy, 35(11), pp. 5562-5570.
78. Murata, T. & Ishibuchi, H. (1995). MOGA: multi-objective genetic algorithms. IEEE International Conference on Evolutionary Computation, Perth, Australia. pp. 289-294.
79. Murata, T., Ishibuchi, H., & Tanaka, H. (1996). Multi-objective genetic algorithm and its applications to flowshop scheduling. Computers & Industrial Engineering, 30(4), pp. 957-968.
80. Niehues, A., Belin, S., Hansson, T., Hauser, R., Mostajo, M., Richter, J. (2001). Punctuality: How Airlines Can Improve On-Time Performance. Booz Allen & Hamilton Inc., McLean, VA., U.S.A.
81. Nombela, G., de Rus, G, & Betancor, O. (2002). Evaluation of congestion costs for Madrid airport. UNITE report, University of Leeds, Leeds, UK.
82. Norman, B. A. & Bean, J. C. (1999). A genetic algorithm methodology for complex scheduling problems. Naval Research Logistics, 46(2), pp. 199-211.
83. Pejovic, T., Noland, R. B., Williams, V., & Toumi, R. (2008). Estimates of UK CO2 emissions from aviation using air traffic data. Climatic Change, 88(3-4), pp. 367-384.
84. Rakshit, A., Krishnamurthy, N., & Yu, G. (1996). System operations advisor: a real-time decision support system for managing airline operations at united airlines. Interfaces, 26(2), pp. 50-58.
85. Rosenberger, J. M., Schaefer, A. J., Goldsman, D., Johnson, E. L., Kleywegt, A. J. & Nemhauser, G. L. (2002). A stochastic model of airline operations. Transportation Science, 36(4), pp. 357-377.
86. Rosenberger, J. M., Johnson E. L. & Nemhauser, G. L. (2003). Rerouting aircraft for airline recovery. Transportation Science, 37(4), pp. 408-421.
87. Rosenberger, J. M., Johnson, E. L. & Nemhauser, G. L (2004). A robust fleet assignment model with hub isolation and short cycles. Transportation Science, 38(3), pp. 357-368.
88. Shavell, Z. A. (2000). The effects of schedule disruptions on the economics of airline operations. 3rd USA/Europe Air Traffic Management R&D Seminar, Napoli, Italy, 13-16 June, 2000.
89. Srinivas, N. & Deb, K. (1994). Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation, 2(3), pp. 221-248.
90. Stojkovic, G., Soumis, F., Desrosiers, J., & Solomon, M. M. (2002). An optimization model for a real-time flight scheduling problem. Transportation Research Part A: Policy and Practice, 36 (9), pp. 779-788.
91. Suzuki, Y. (2000). The relationship between on-time performance and airline market share: A new approach. Transportation Research Part E, 36(2), pp. 139-154.
92. Takebayashi, M., Kuroda, K., Kurosawa, N., & Mizobata, S. (2005). Delay recovery in air transport hub-spokes network system concerning hub-to-hub schedule conflict. Journal of the Eastern Asia Society for Transportation Studies, 5, pp. 679-692.
93. Teodorović, D. & Guberinić, S. (1984). Optimal dispatching strategy on an airline network after a schedule perturbation. European Journal of Operational Research, 15(2), pp. 178-182.
94. Teodorović, D. & Stojković, G. (1990). Model for operational daily airline scheduling. Transportation Planning and Technology, 14(4), pp. 273-285.
95. Teodorovic, D., & Stojkovic, G. (1995). Model to reduce airline schedule disturbances. Journal of Transportation Engineering, 121(4), pp. 324-331.
96. Thengvall, B. G., Bard, J. F., & Yu, G. (2000). Balancing user preferences for aircraft schedule recovery during irregular operations. IIE Transactions, 32(3), pp. 181-193.
97. Thengvall, B. G., Yu, G., & Bard, J. F. (2001). Multiple fleet aircraft schedule recovery following hub closures. Transportation Research Part A, 35(4), pp. 289-308.
98. Tolga, E. (2008). Estimation of engine emissions from commercial aircraft at a midsized Turkish airport. Journal of Environmental Engineering, 134(3), pp. 210-215.
99. Trietsch, D. (1993). Scheduling flights at hub airports. Transportation Research Part B, 27(2), pp. 33-150.
100. Tsai, J. T., Liu, T. K., & Chou, J. H. (2004). Hybrid Taguchi-genetic algorithm for global numerical optimization. IEEE Transactions on Evolutionary Computation, 8(4), pp. 365-377.
101. U.S. Environmental Protection Agency (2008). U.S. inventory of greenhouse gas emissions and sinks: 1990-2006, EPA 430-R-08-005, Washington DC, USA.
102. Wang, P. T. R., Schaefer, L. A., & Wojcik, L. A. (2003). Flight connections and their impacts on delay propagation. The 22nd Digital Avionics Systems Conference. Indianapolis, IN., USA. Vol. 1, pp. 5.B.4-5.1-9.
103. Wu, C. L. & Caves, R. E. (2000). Aircraft operational costs and turnaround efficiency at airports. Journal of Air Transport Management, 6(4), pp. 201-208.
104. Wu, C. L. & Caves, R. E. (2002). Towards the optimisation of the schedule reliability of aircraft rotations. Journal of Air Transport Management, 8(6), pp. 419-426.
105. Wu, C. L. & Caves, R. E. (2003). Flight schedule punctuality control and management: A stochastic approach. Transportation Planning and Technology, 26(4), pp. 313-330.
106. Yan, S. & Yang, D. (1996). A decision support framework for handling schedule perturbations. Transportation Research Part B, 30(6), pp. 405-419.
107. Yan, S. & Lin, C. G. (1997). Airline scheduling for the temporary closure of airports. Transportation Science, 31(1), pp. 72-82.
108. Yan, S. & Tu, Y. (1997). Multifleet routing and multistop flight scheduling for schedule perturbation. European Journal of Operational Research, 103(1), pp. 155-169.
109. Yan, S., Tang, C. H. & Shieh, C. L. (2005). A simulation framework for evaluating airline temporary schedule adjustments following incidents. Transportation Planning and Technology, 28(3), pp. 189-211.
110. Yu, G. (1996). Real-time, mission-critical decision support systems for managing and controlling airlines' operations. Proceedings at the International Conference on Management Science and Economic Development, Hong Kong.
111. Yu, G. (1998). OR in the Airline Industry. Kluwer Academic Publishers, Boston, MA, USA.
112. Yu, G. & Yang, J. (1998). Optimization applications in the airline industry. Handbook of Combinatorial Optimization, Vol. 2. Du, D. Z., Pardalos, P. M. (Eds.) Kluwer Academic Publishers, Boston, MA, USA. pp. 635-726.
113. Yu, G. & Qi, X. (2004). Disruption Management: Framework, Models, Solutions and Applications. World Scientific Publishing, Singapore.
114. Zakian, V., & Al-Naib, U. (1973). Design of dynamical and control systems by the method of inequalities. Proceedings of IEE, 120(11), pp. 1421-1427.
115. Zakian, V. (1996). Perspectives on the Principle of Matching and the Method of Inequalities. International Journal of Control, 65(1), pp.147-175.
116. Zitzler, E., Deb, K., & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), pp. 173-195.