Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/128108
|
| Title: | 遺傳演算法於航空排程之研究
A study of Genetic Algorithms for airline scheduling problems |
| Authors: | 蔡明汶
Tsai, Ming-Wen |
| Contributors: | 林我聰
洪宗貝
Lin, Woo-Tsong
Hong, Tzung-Pei
蔡明汶
Tsai, Ming-Wen |
| Keywords: | 航空排程
次經驗法則
遺傳演算法
二維編碼
任務組合產生
任務組合指派
重新排程
Airline scheduling problem
Meta-heuristic
Genetic algorithm
Two-dimensional representation
Pairing
Rostering
Rescheduling |
| Date: | 2015 |
| Issue Date: | 2020-01-03 15:53:30 (UTC+8) |
| Abstract: | 航空排程問題對航空公司之營運績效扮演著重要角色，同時為了遵循複雜之航空法規要求，航空排程被視為一重要且複雜之組合最佳化問題。過去大部分研究是將航空排程最佳化問題透過數學規劃求解，例如視為集合覆蓋問題或集合分割問題，然而一旦排程問題規模變大或更複雜時，求解時間將大幅增加，如何在合理的時間範圍內或有限資源限制下求出近似最佳解會是一大挑戰。因此本研究利用次經驗法則最佳化技術中的遺傳演算法來解決航空排程問題。遺傳演算法具有於有限時間內求得可行解或近似最佳解的特性，適合解決複雜之組合最佳化問題。發展遺傳演算法第一步驟是將問題解透過適當的編碼呈現，過去大部分研究採用一維的編碼方式，然而實務上，部分問題如航空排程問題，若採用二維的編碼方式求解會更符合問題的特性。本研究提出以二維編碼為解題策略之遺傳演算法，設計對應於二維編碼方式的交配、突變及修復運算並設計加速演化搜尋之經驗法則。透過三個航空排程問題的求解及參數驗證，本研究提出的演算法可有效解決航空排程之問題。
The airline scheduling problem (ASP), which is strongly related to operating cost and is subject to several regulatory constraints, is a difficult combinatorial optimization problem. It is typically formulated as the set cover problem (SCP) or the set partition problem (SPP), which are then usually solved with mathematical programming. However, the problem-solving process becomes very time-consuming as problem size increases. This research thus applies a very popular meta-heuristic optimization approach, genetic algorithms (GAs), to solve ASP. As GAs can provide feasible solutions within reasonable time, they have become increasingly important for solving difficult combinatorial problems. When using GAs to solve a problem, users must first define an appropriate representation to describe problem states. Most previous studies adopted linear, i.e., one-dimensional, representations. Some real-life problems, such as ASP, are very suited in nature to two-dimensional representations. Therefore, this research develops a GA strategy based on two-dimensional encoding to solve several ASP problems. Appropriate two-dimensional crossover and mutation operations are designed as well to generate populations in subsequent generations. Besides, a two-dimensional repair mechanism is also proposed to adjust infeasible chromosomes into feasible chromosomes. Finally, experiments are performed to demonstrate the effectiveness of the proposed GA in solving the three airline scheduling problems. |
| Reference: | [1] G. Aiello, G.. L. Scalia, and M. Enea, "A multi objective genetic algorithm for the facility layout problem based upon slicing structure encoding," Expert Systems with Applications, vol. 39, no. 12, 2012, pp.10352–10358.
[2] P. Alefragis, P. Sanders, T. Takkula, D. Wedelin, "Parallel Integer Optimization for Crew Scheduling," Annals of Operations Research, vol. 99, no. 1-4, 2000, pp.141-166.
[3] T. Andersson, "Solving the flight perturbation problem with meta heuristics", Journal of Heuristics, vol. 12, 2006, pp.37-53.
[4] C. A. Anderson, K. F. Jones, and J. Ryan, "A two-dimensional genetic algorithm for the Ising problem," Complex System, vol. 5, 1991, pp.327–333.
[5] P. J. Angeline and J. B. Pollack, "Evolutionary Module acquisition," Proceedings of 2nd Annual Conference on Evolutionary programming, 1993, pp.154-163.
[6] H. L. Arabeyre, F. Fearrnley, C. Steiger and W. Teather, "The Airline Crew Scheduling Problem: Survey," Transportation Science, vol.3, 1969, pp.140-163.
[7] M. F. Arguello, J. F. Bard, and G. Yu, "A GRASP for Aircraft Routing in Responseto Groundings and Delays," Journal on Combinatorial Optimization, vol. 5, 1997, pp.211-228.
[8] 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, 1998, pp. 208-220.
[9] C. Barnhart, and R. G. Shenoi, "An approximate model and solution approach for the long-haul crew pairing problem", Transportation Science, vol. 32, no. 3, 1998, pp.221-231.
[10] M. C. Bartholomew-Biggs, S. C. Parkhurst, and S. P. Wilsom, "Global optimization approaches to an aircraft routing problem," European Journal of Operational Research, vol. 146, no. 2, 2003, pp.417-431.
[11] L. Bodin, B. Golden, A. Assad and M. Ball, "Routing and Scheduling of Vehcles and Crews – The State of the Art," Computers & Operations Research, vol. 10, No. 2, 1983, pp.125-127.
[12] L. B. Booker, D. E. Goldberg, and J. H. Holland, Classifier Systems and Genetic Algorithms, Technical Report, No. 8, University of Michigan, 1987.
[13] T. N. Bui and B. R. Moon, "On multi-dimensional encoding/crossover," Proceedings of the 6th International Conference on Genetic Algorithms, Pittsburgh, PA, 1995, pp.49–56.
[14] T. Y. Chou, T. K. Liu, C. N. Lee, and C. R. Jeng, "Method of inequality-based multiobjective genetic algorithm for domestic daily aircraft routing," IEEE Transactions on Systems, Man, and Cybernetics — Part A: Systems and Humans, vol. 38, no. 2, 2008, pp.299-308.
[15] L.W. Clarke, E.L. Johnson, G.L. Nemhauser, and Z. Zhu, "The aircraft rotation problem," Annals of Operations Research, Mathematics of Industrial Systems II, vol. 69, 1997, pp.33-46.
[16] J. P. Cohoon and W. Paris, "Genetic placement," Proceedings of the IEEE International Conference on Computer-Aided Design, 1986, pp.422-425.
[17] N. L. Cramer, "A representation for the adaptive generation of simple sequential programs", Proceedings of the 1st International Conference on Genetic Algorithms, 1985, pp.183-187.
[18] B. Crawford, C. Castro, E. Monfroy, "A Constructive Hybrid Algorithm for Crew Pairing Optimization,” Artificial Intelligence: Methodology, Systems, and Applications Lecture Notes in Computer Science, vol. 4183, 2006, pp.45-55.
[19] M. S. Daskin, and N. Panayotopoulos, "A Lagrangian relaxation approach to assigning aircraft to routes in hub and spoke networks," Transportation Science, vol. 23, 1989, pp. 91-99.
[20] D. Datta, A. R. S. Amaralb and J. R. Figueira, "Single row facility layout problem using a permutation-based genetic algorithm," European Journal of Operational Research, vol. 213, no. 2, 2011, pp. 388–394.
[21] L. Davis, Handbook of Genetic Algorithms, Van Nostrand Reinhold, 1991.
[22] K. A. De Jong and W. M. Spears, "An analysis of the interacting roles of population size and crossover in genetic algorithms," Proceedings of the 1st Workshop on Parallel Problem Solving from Nature, vol. 10, 1990, pp.38-47.
[23] G. Desaulniers, J. Desrosiers, Y. Dumas, M. Solomon, and F. Soumis, "Daily aircraft routing and scheduling", Management Science, vol. 43, 1997, pp. 841-855.
[24] M. A. Duarte-Villasenor, E. Tlelo-Cuautle, L. G. de la Fraga, "Binary genetic encoding for the synthesis of mixed-mode circuit topologies," Circuits, Systems, and Signal Processing, vol. 31, no. 3, 2012, pp.849-863.
[25] T. Emden-Weinert, M. Proksch, "Best Practice Simulated Annealing for the Airline Crew Scheduling Problem," Journal of Heuristics, vol. 5, Issue 4, 1999, pp.419-436.
[26] M.M. Etschmaier and D.F.X. Mathaisel, "Aircraft Scheduling - The State of the Art," Proceedings of the AGIFORS 24th Annual Symposium, 1984, pp.181–225.
[27] B. Filipic and D. Juricic, "An interactive genetic algorithm for controller parameter optimization," Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms, Innsbruck, Austria, 1993, pp.458-462.
[28] L. J. Fogel, A. J. Owens, and M. J. Walsh, Artificial Intelligence through Simulated Evolution, Wiley, 1966.
[29] M. Gen and R. Cheng, Genetic Algorithms and Engineering Design, Wiley-Interscience, New York, 1997.
[30] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, 1989.
[31] R. Gopalan, and K.T. Talluri, "The aircraft maintenance routing problem," Operations Research, vol. 46, 1998, pp.260-271.
[32] J. J. Grefenstette, "Optimization of control parameters for genetic algorithms," IEEE Transactions on Systems, Man and Cybernetics, vol. 16, no. 1, 1986, pp.122-128.
[33] Y. Gu and C. Chung, “Genetic algorithm approach to airline gate reassignment problem”. J. of Transportation Engineering, vol. 125, 1999, pp.384–389.
[34] P. Healy, "A Tool for Adjusting the Flight Schedule During High Volume Irregular Operations," Proceedings of the AGIFORS 32nd Annual Symposium, 1992, pp.53-64.
[35] K. Hoffman, M. W. Padberg, "Solving airline crew scheduling problems by branch and cut," Management Science, vol. 39, 1993, pp.657-683.
[36] J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975.
[37] R. Hwang and H. Katayama, "Uniform workload assignments for assembly line by GA-based amelioration approach," International Journal of Production Research, vol. 48, no. 7, 2010, pp.1857–1871.
[38] W. H. Ip, D. Wang, and V. Cho, "Aircraft ground service scheduling problems and their genetic algorithm with hybrid assignment and sequence encoding scheme," IEEE Systems Journal, vol. 7, no. 4, 2013, pp.649 – 657.
[39] A.I. Jarrah, G. Yu, N. Krishnamurthy, and A. Rakshit, "A Decision Support Framework for Airline Flight Cancellations and Delays," Transportation Science, 27(3), 1993, pp.266-280.
[40] D. Jong. An Analysis of the Behavior of a Class of Genetic Adaptive Systems, Ph.D. thesis, University of Michigan, 1975.
[41] D. Jong, "Adaptive system design: a genetic approach," IEEE Transactions on Systems, Man and Cybernetics, vol. 10, 1980, pp.566-574.
[42] N. M. Kabbani and B. W. Patty, "Aircraft routing at American Airlines," Proceedings of the Thirty-Second Annual Symposium of AGIFORS, 1992.
[43] C. L. Karr, "Design of an adaptive fuzzy logic controller using a genetic algorithm," Proceedings of the Fourth International Conference on Genetic Algorithms, 1991, pp.450-457.
[44] H. Kitano, "Empirical studies on the speed of convergence of neural network training using genetic algorithms," Proceedings of the Eighth National Conference on Artificial Intelligence, 1990, pp.789-795.
[45] J. R. Koza, Genetic Programming: on the Programming of Computers by Means of Natural Selection, MIT Press, 1992.
[46] M. Largerholm, C. Peterson, B. Söderberg, "Airline Crew Scheduling Using Potts mean Field Techniques.," European Journal of Operational Research, 2000, vol. 120, pp.81-96.
[47] S. Lavoie, "A new approach for crew pairing problems by column generation with an application to air transportation," European Journal of Operational Research, vol. 35, no. 1, 1988, pp.45–58.
[48] M. A. Lee and H. Takagi, "Dynamic control of genetic algorithms using fuzzy logic techniques," Proceedings of the Fifth International Conference on Genetic Algorithms, 1993, pp.76-83.
[49] L. Lettovsky, Airline Operations Recovery: an Optimization Approach, Ph.D. Dissertation, Georgia Institute of Technology, 1997.
[50] D. Levine, "Application of a hybrid genetic algorithm to airline crew scheduling," Computers & Operations Research, vol. 23, 1996, pp.547-558.
[51] K. T. Lin and P. H. Lin, "Information hiding based on binary encoding methods and crossover mechanism of genetic algorithms," Genetic and Evolutionary Computing Advances in Intelligent Systems and Computing, vol. 238, 2014, pp. 203-212.
[52] G. F. Miller, P. M. Todd, and S. U. Hedge, "Design neural networks using genetic algorithms," Proceedings of the Third International Conference on Genetic Algorithms, 1989, pp.379-384.
[53] M. Minoux, "Column generation techniques in combinatorial optimization: a new application to crew pairing problems," In XXIVth AGIFORS Symposium, 1984.
[54] B. R. Moon and C. Kim, "A two-dimensional embedding of graphs for genetic algorithms," Proceedings of International Conference on Genetic Algorithms, 1997, pp.204–211.
[55] B. R. Moon, Y. S. Lee, and C. K. Kim, "GEORG: VLSI circuit partitioner with a new genetic algorithm framework," Journal of Intelligent Manufacturing, vol. 9, 1998, pp.401–412.
[56] R. Myers and E. R. Hancock, "Genetic algorithm parameter sets for line labelling," Pattern Recognition Letters, vol. 18, 1997, pp.1363-1371.
[57] S. Nakazawa, "Dynamic Scheduling in Operation Control System," AGIFORS 31, 1991.
[58] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1993, New Youk,
[59] J. H. Park, "The effects of airline alliances on markets and economic welfare," Transportation Research, vol. 33, 1997, pp.181-195.
[60] J. M. Rosenberger, E. L. Johnson, and G. L. Nemhauser, "Rerouting airline for airline recovery", Transportation Science, vol. 37, 2003, pp.408 -421.
[61] A. Sadrzadeh, "A genetic algorithm with the heuristic procedure to solve the multi-line layout problem," Computers & Industrial Engineering, vol. 62, no. 4, 2012, pp.1055–1064.
[62] J. D. Schaffer, "A study of control parameters affecting on-line performance of genetic algorithms for function optimization," Proceedings of the Third International Conference on Genetic Algorithms, 1989, pp.675-682.
[63] C. Shaefer, "The ARGOT strategy: adaptive representation genetic optimizer technique," Proceedings of the 2nd International Conference on Genetic algorithms and their application, 1987, pp.50-58.
[64] A. Shtub, L. J. LeBlanc, Z. Cai, "Scheduling Problem with Repeative Projects: A Comparison of a Simulated Annealing , a Genetic and a Pair-Wise Swap Algorithm," European Journal of Operational Research, 1996, pp.124-138.
[65] W. M. Spears and K. A. Dejong, "An analysis of multipoint crossover," the Workshop of the Foundations of Genetic Algorithms, 1991, pp.301-315.
[66] C. Srinivasa, B. R. Reddy, K. Ramji and R. Naveen, "Sensitivity Analysis to Determine the Parameters of Genetic Algorithm for Machine Layout," Proceedings of the 3rd International Conference on Materials Processing and Characterisation, 2014, pp.866-876.
[67] G. Syswerda, "Uniform crossover in genetic algorithms," Proceedings of the Third International Conference on Genetic Algorithms, 1989, pp.2-9.
[68] K. Talluri, "Swapping applications in a daily airline fleet assignment," Transportation Science, vol. 30, 1996, pp.237-248.
[69] D. Teodorovic and G. Stojkovic, "Model for Operational Daily Airline Scheduling," Transportation Planning and Technology, 14, 1990, pp.273-285.
[70] E. Tlelo-Cuautle, I. Guerra-Gomez, M.A. Duarte-Villasenor, Luis G. de la Fraga, G. Flores-Becerra, G. Reyes-Salgado, C.A. Reyes-Garcia and G. Rodriguez-Gomez, "Applications of evolutionary algorithms in the design automation of analog integrated circuits," Journal of Applied Sciences, vol. 10, 2010, pp.1859-1872.
[71] P. Thrift, "Fuzzy logic synthesis with genetic algorithms," Proceedings of the Fourth International Conference on Genetic Algorithms, 1991, pp.509-513.
[72] M. W. Tsai, T. P. Hong, and W. T. Lin, "A Two-Dimensional Genetic Algorithm and Its Application to Aircraft Scheduling Problem," Mathematical Problems in Engineering, vol. 2015, 2015.
[73] P. H. Vance, C. Barnhart, E. L. Johnson, G. L. Nemhauser, "Airline crew scheduling: a new formulation and decomposition algorithm", Operations Research, vol. 45, no. 2, 1997, pp.188-200.
[74] T. M. Vowles," The geographic effects of US airline alliances," Journal of Transport Geography, vol. 8, 2000, pp.277-285.
[75] P. C. Wang and W. Korfhage, "Process scheduling using genetic algorithms," The Seventh IEEE Symposium on Parallel and Distributed Processing, 1995, pp.638.
[76] P. Wark, J. Holt, M. Rönnqvist, D. Ryan, "Airline Schedule Generation Using Repeated Matching," European Journal of Operational Research, 1997, pp.21-35.
[77] S. Yan and J. C. Chang, "Discrete optimization airline cockpit crew scheduling," European Journal of Operational Research, vol. 136, 2002, pp.501-511.
[78] S. Yan and Y.P. Tu, "A network model for airline cabin crew scheduling," European Journal of Operational Research, vol. 140, no. 3, 2002, pp.531-540.
[79] W. Yanga, Felix T.S. Chanb, V. Kumarc, "Optimizing replenishment polices using genetic algorithm for single-warehouse multi-retailer system," Expert Systems with Applications, vol. 39, no. 3, 2012, pp.3081–3086.
[80] G. Yu, Operations Research in the airline industry, Kuuwer Academic Publishers, 1998.
[81] B. Zeren, I. Ozkol, "An Improved Genetic Algorithm for Crew Pairing Optimization," Journal of Intelligent Learning Systems and Applications, vol. 4, 2012, pp.70-80. |
| Description: | 博士
國立政治大學
資訊管理學系
94356503 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0094356503 |
| Data Type: | thesis |
| DOI: | 10.6814/NCCU201901273 |
| Appears in Collections: | [資訊管理學系] 學位論文
|
Files in This Item:
There are no files associated with this item.
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
