跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/07/27 14:14
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:楊東諺
研究生(外文):Tung-Yen Yang
論文名稱:運用遺傳演算法求解機隊指派問題
論文名稱(外文):Fleet Assignment Problems using Genetic Algorithms
指導教授:劉得昌劉得昌引用關係
指導教授(外文):Te-Chang Liu
學位類別:碩士
校院名稱:開南大學
系所名稱:空運管理學系碩士班
學門:運輸服務學門
學類:航空學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:英文
論文頁數:61
中文關鍵詞:機隊指派遺傳演算法排程最佳化
外文關鍵詞:Fleet AssignmentGenetic AlgorithmsSchedulingOptimization
相關次數:
  • 被引用被引用:1
  • 點閱點閱:195
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
航空器首次飛上天至此今已有百年的時間,航空運輸產業的成長已成為全球經濟重要指標的一環。更重要的是,航空產業的逐年發展,已領導全球大規劃運用資訊科技及電腦輔助。
機隊指派是基於有限的設備資源分派飛機於不同的航線班次之中,並考量營運成本及潛在的營收。然而,飛航班次於每日之中皆為數以千計之班次往返,必需倚賴航空公司規劃安排飛航班次表、機組員排班、飛機飛航路徑、機隊維修及收益管理等問題。因此機隊指派是航空公司中相當重要課題與挑戰。
在本研究中,認為機隊指派是一項大規模的求解問題,因此我們需要運用最佳化的方法來求解如此繁複的非線性問題。本研究應用優先順序的遺傳演算法來求解機隊指派問題。因此,我們針對考量到時間空間的基本機隊指派問題進行研究。我們運用優先順序的遺傳演算法進行編碼及解碼來探討飛航網路的問題。時間空間問題的特色在於需要平衡所有進出於網路容量的限制。我們提出了四階段求解問題的程序,並且運用最佳化的遺傳演算法求得機隊指派的最佳解。
During the one hundred years since the first flight of airline, the air transport industry has grown into a major sector of the global economy. Even more importantly, the airline industry has consistently been a leader in the use of information technology and has relied heavily on the intensive use of computers over the years.
The fleet assignment problem (FAP) deals with assigning aircraft types, each having a different capacity, to the scheduled flights, based on equipment capabilities and availabilities, operational costs, and potential revenues. However, due to the large number of flights scheduled each day, which can easily reach thousands for a major airline, and the dependency of the FAP on other airline processes such as schedule design, crew scheduling, aircraft routing, maintenance planning, and revenue management, solving the FAP has always been a challenging task for the airlines.
In this research, the fleet assignment is a large scale problem, than we based the NP-hard problem by using optimization approach to solve it. We proposed a priority Genetic Algorithm (GA) approach to solve FAP. Therefore, we consider the time-space network in basic fleet assignment problems. We used a genetic algorithm approach with priority-based encoding and decoding method to complex flight network problem. The characteristic of the time-space network must satisfy balance constraints that force the aircraft to circulate through the network of flights. We proposed the solution procedure by 4 phases for solving this problem, and we got the optimization result by using GA approach.
Contents

1. Introduction 1
1.1 Introduction of Fleet Assignment Problems 1
1.2 Background and Objective of Study 6
1.3 Organization of the Study 8

2. Airline Fleet Assignment Problems 9
2.1 Aviation Technical 9
2.2 Airline Service 11
2.2.1 Basic Fleet Assignment Models 12
2.2.2 Integrated Fleet Assignment Models 13
2.2.3 Fleet Assignment Models with Addition Consideration 14
2.3 Basic Fleet Assignment Problem 16
2.3.1 Connection Network 16
2.3.2 Time-Space Network 17
2.4 Summary 19

3. Evolutionary Algorithms 20
3.1 Genetic Algorithm 20
3.2 Encoding 23
3.3 Initialization 26
3.4 Selection and Evolution Function 26
3.5 Crossover 28
3.6 Mutation 29
3.7 Summary 29

4. Fleet Assignment Problem with Time-Space Network 31
4.1 Introduction of FAP with Time-Space Network 31
4.2 Mathematical Formulation 36
4.3 Genetic Algorithm Approach for FAP with Time-Space Network 38
4.3.1 Genetic Representation 39
4.3.2 Genetic Operators 50
4.4 Experiments and Discussion 53
4.5 Summary 56

5. Conclusions 57
5.1 Summary 57
5.2 Future Research 58

References 59
References

Abara, J. (1989). “Applying integer linear programming to the fleet assignment problem.” Interfaces, vol. 19, pp. 20-28.
Bandet, P. O. (1994). “Armada-Hub: An adaption of AF fleet assignment model to take into account the hub structure in CDG.” Proceedings of AGIFORS 34th Annual Symposium.
Barnhart, C. Belobaba, P and Odoni, A.R. (2003). “Applications of operations research in the air transport industry.” Transportation Science, vol. 37, pp. 368-391.
Barnhart C, Johnson E.L., Nemhauser, G.L., Savelsbergh M.W.P and Vance P.H. (1998). “Branch-and-Price: column generation for solving huge integer programs.” Operations Research, vol. 46, pp. 316-329.
Barnhart, C., Kniker, T.S. and Lohatepanont, M. (2002). “Itinerary-based airline fleet assignment.” Transportation Science, vol. 36, pp. 199-217.
Belanger, N., Desulniers, G., Soumis, F and Desrosiers, J. (2006) ”Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues.” European Journal of Operational Research, vol. 175, pp. 1754-1766.
Clarke, L.W., Hane, C.A., Johnson, E.L. and Nemhauser, G.L. (1996). “Maintenance and crew considerations in fleet assignment.” Transportation Science, vol. 30, pp. 249-260.
Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M.M. and Soumis, F. (1997). ‘’Daily aircraft routing and scheduling.” Management Science, vol. 43, pp. 841-855.
Desaulniers, G. Deserosiers, J. Solomon, M. M. and Soumis, F. (1994). “Daily aircraft routing and scheduling.” GERAD technical report, Montreal, Quebec, Canada.
Desrochers, M. and Soumis, F. (1988). “A generalized permanent labeling algorithm for the shortest path problem with time windows.” Infor, vol. 26, pp. 191-212.
Ferguson, A. R. and Dantzig, G. B. (1955). “The aircraft routing problem.” Aeronautical Engineering Review, vol. 14, no. 4.
Ferguson, A. R. and Dantzig, G. B. (1956). “The allocation of aircraft to routes– an example of linear programming under uncertain demand.” Management Science, vol. 3, pp. 45-73.
Garey, M.R and Johnson, D.S. (1979). “Computers and intractability: A guide to the theory of NP-completeness.” San Francisco: W.H. Freemean & Company.
Gen, M. and Cheng, R. (1997). “Genetic Algorithms and Engineering Design”, John Wiley, New York.
Gen M. and Cheng, R. (2000). “Genetic Algorithms and Engineering Optimization”, John Wiley, New York.
Goldberg, D. E. (1989). “Genetic Algorithms in Search, Optimization, and Machine Learning.” Addison-Wesley, Reading, Mass.
Gopalan, R. and Talluri, K.T. (1998). “Mathematical models in airline planning: A survey.” Annals of Operations Research, vol. 76, pp. 155-185.
Gu, Z., Johnson, E.L., Nemhauser, G.L., Wang, Y. (1994). “Some properties of the fleet assignment problem.” Operations Research Letters, vol. 15, pp. 59-71.
Hane, C., 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, vol. 70, pp. 211-232.
Holland, J. H. (1975). “Adaptation in Natural and Artificial Systems.” MIT Press, Cambridge, MA.
Ioachim, I., Desrosiers, J., Soumis, F. and Belanger, N. (1999). “Fleet routing with schedule synchronization constraints.“ European Journal of Operational Research, vol. 119, pp. 75-90.
Ioachim, I., Gelinas, S., Desrosiers, J. and Soumis, F. (1998). “A dynamic programming algorithm for the shortest path problem with time windows and linear node costs.“ Networks, vol. 31, pp. 193-204.
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, vol. 177, pp. 1948-1968.
Levin, A. (1971). “Scheduling and fleet routing models for transportation systems.” Transportation Science, vol. 5, pp. 232-255.
Lohatepanont, M and Barnhart, C. (2004). “Airline schedule planning: Integrated models and algorithms for schedule design and fleet assignment.” Transportation Science, vol. 38, pp. 19-32.
Michalewicz, Z. (1996). “Genetic Algorithm + Data Structures = Evolution Programs.” 3rd, revised and extended edition. Springer-Verlag.
Rechenberg, I. (1973). “Evolutionstrategie: Optimieriung Techischer Systeme Nach Prinzipien Der Biologischen Evolution.” Frommann-Holzboog, Stuttgart, Germany.
Rexing, B., Barnhartm, C., Kniker, T., Jarrah, A. and Krishnamurthy, N. (2000). “Airline fleet assignment with time windows.” Transportation Science, vol. 34, pp. 1-20.
Rushmeier, R.A., and Kontogiorgis, S.A. (1997). “Advances in the optimization of airline fleet assignment.” Transportation Science, vol. 31, pp. 159-169.
Schwefel, H. (1995). “Evolution and Optimum Seeking.”, Wiley, New York.
Sherali H.D. Bish, E.K and Zhu. X. (2006). “Airline fleet assignment concepts, models, and algorithms.” European Journal of Operational Research, vol. 172, pp. 1-30.
Simpson, R. W. (1978). “Airline operations class notes.” Massachusetts Institute of Technology, Unpublished.
Stojkovic, M. and Soumis, F. (2001). ”An optimization model for the simultaneous operational flight and pilot scheduling problem.” Management Science, vol. 47, pp. 1290-1305.
Subramanian, R., Scheff, R.P., Quillinan, J.D., Wiper, D.S., and Marsten, R.E. (1994). “Coldstart: Fleet assignment at Delta Air Lines.” Interfaces, vol. 24, pp. 104-120.
Yan, S and Tseng, C.H. (2002). “A passenger demand model for airline flight scheduling and fleet routing.” Computer & Operations Research, vol. 29, pp. 1559-1581.
Yan, S and Young, H.F. (1996). “A decision support framework for multi-fleet routing and multi-shop flight scheduling.” Transportation Research, vol. 30, pp. 379-398.
Yan, S, Tang, C.H and Lee, M.C. (2007). “A flight scheduling model for Taiwan airlines under market competitions.” Omega, vol. 35, pp. 61-74.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top