成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	李靜玫 Li, Ching-Mei
論文名稱：	具航班時間連續性調整之機隊指派問題 Fleet Assignment with Continuously Adjustable Flight Schedule
指導教授：	王大中 Wang, Ta-Chung
學位類別：	碩士 Master
系所名稱：	工學院 - 民航研究所 Institute of Civil Aviation
論文出版年：	2011
畢業學年度：	99
語文別：	英文
論文頁數：	59
中文關鍵詞：	航空公司班表排程、機隊指派、時間窗
外文關鍵詞：	airline planning, fleet assignment, time window
相關次數：	點閱：138 下載：3
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

機隊指派是航空公司排班的四個中主要步驟之一。其主要目的是要求解出每個航段在考慮不同機型的不同性質與成本後，每個航段要指派何種機型飛機。機隊指派問題有兩種形式的目標函式，求解最大化利潤或是最小化總營運成本，通常都會使用整數規劃法來求解此問題。而因為機隊指派是一個大型的整數規劃問題，所以以往的研究都著重在發展 heuristic 方法，以尋求近似解來取代精確解，使得求解的時間能夠在合理的時間內。
本篇的研究提出一個三階段的方法求解機隊指派問題。首先，我們在基本的機隊指派問題中加入了返回節線(backward arc)，在允許時間逆流的情況下，我們尋找一個有最小成本的最佳解。再來，我們根據第一階段的解，更進一步的找出每架飛機應該飛哪些航班，求解出每架飛機有最小成本的飛行路徑。最後，我們使用一個線性規劃的數學式取代傳統的時間窗(time window)方式，去調整班表。我們的方法也像有時間窗的方法一樣能夠在允許航班離開時間有變動下，指派各航段應使用的機型，並且我們還進一步的知道每架飛機指派的路徑。為了證實我們方法的可用性，我們使用真正航空公司的資料去執行。

Fleet assignment is one of the four major steps in airline planning. The objective is to determine which type of aircraft should fly on each flight leg while considering the different characteristics and costs associated with different fleet types. The main purpose of the fleet assignment problem (FAP) is to maximize revenue or minimize total operating cost. The problem is usually formulated as an integer programming problem. Because of the size of the FAP, various heuristic methods for solving this problem have been studied.
This thesis proposes a three-phase approach to solving the FAP. First, backward arcs are used to solve basic FAPs. By allowing backward time, the optimal feasible solution with the minimum number of rescheduled flight is sought. In the next phase some routes from phase one, which have minimal costs, are found. Finally, the continuously adjustable flight schedule problem is solved using a linear programming model instead of using a time window to change flight schedules. Our formulation has a similar level of flexibility as the fleet assignment model with time window (FAMTW), and solves the problem in shorter time than the FAMTW. An approach for solving the aircraft routing problem is also proposed, and to demonstrate the effectiveness of this examples using real data obtained from a major airline are included in this thesis.

CONTENTS
ABSTRACT                                                   I
摘要                                                             III
致謝                                                               V
CONTENTS                                                  VI
LIST OF FIGURES	                                        VIII
LIST OF TABLES                                            IX
Chapter 1 Introduction	                                   1
1.1 Motivation and objective	                           1
1.2 Outline of this research	                           4
Chapter 2 Methods for solving the fleet assignment problem 5
2.1 Integer programming problem	                           5
2.2 Branch-and-bound algorithm                             6
2.3 Genetic algorithm                                      9
2.4 Ant colony optimiz ation                              10
2.5 Summary                                               13
Chapter 3 Fleet Assignment Problem                        14
3.1 Basic fleet assignment problem                        14
3.1.1 Time-space network                                  15
3.1.2 Mathematical formulation of the FAP                 16
3.2 Fleet assignment with time-window                     24
3.2.1 Fleet assignment network preprocessing for FAMTW    25
3.2.2 Mathematical formulation of the FAMTW               26
3.2.3 Backward arc technique                              31
3.3 Summary                                               35
Chapter 4 Fleet Assignment with Continuously Adjustable Flight Schedule	                                          36
4.1 Phase 1                                               36
4.2 Phase 2                                               39
4.3 Phase 3                                               44
Chapter 5 Simulation Results                              50
5.1 Simulation Data                                       50
5.2 Simulation Results                                    51
Chapter 6 Conclusions                                     56
References                                                57
Curriculum Vitae                                          59

LIST OF FIGURES
Figure 1 Airline schedule planning process.                4
Figure 2 The first iterative solution tree in the branching phase.                                                     8
Figure 3 The foraging behavior of real ants.              11
Figure 4 Time-space network.                              16
Figure 5 Two stations example for flight coverage constraint                                                20
Figure 6 Two stations example for aircraft balance constraint                                                20
Figure 7 Six stations example for fleet size constraint   21
Figure 8 The demand distribution [14]                     23
Figure 9 Time-space network for the FAMTW.                26
Figure 10 Node consolidation preprocessing technique      29
Figure 11 Deleted redundant flight arc preprocessing technique.                                                30
Figure 12 Island preprocessing technique                  31
Figure 13 Backward connection arcs                        35
Figure 14 The time-space before/after the adjustable phase.                                                    46
Figure 15 Example of phase 3.                             49
Figure 16 The distribution of different backward arc coefficients within 30 minutes backward time.             54
Figure 17 The distribution of different backward arc coefficients within 20 minutes backward time.             55
Figure 18 The results of different backward arc coefficients within 60, 30, and 20 minutes backward time. 55

LIST OF TABLES
Table 1 Holding rates of aircraft [19]                    43
Table 2 An example of a route                             44
Table 3 Data in an example                                45
Table 4 Description of runs                               50
Table 5 Result of all runs                                53
Table 6 Preprocessing results for Problem 3, Summer 2009 [6]                                                       53
                                    

[1]M. M. Etschmaier and D. F. X. Mathaisel, "Airline scheduling: an overview," Transportation science, vol. 19, pp. 127-138, 1985.
[2]H. D. Sherali, et al., "Airline fleet assignment concepts, models, and algorithms," European Journal of Operational Research, vol. 172, pp. 1-30, 2006.
[3]M. Bazargan, Airline Operations and Scheduling, Ashgate Pub Ltd, 2004.
[4]T.-C. Jung and J. Chung, "Airline Fleet Assignmrnt Using Genetic Algorithm," In Proc. of the Genetic and Evolutionary Computation Conference, New York, 2002, pp. 255-262.
[5]H. E. Sakkout, "Modelling and Solving Fleet Assignment in a Flexible Environment," In Proc. Second International Conference on the Practical Application of Constraint Technology,, 1996, pp. 27-39.
[6]P. Ratprasert, et al., "Ant Colony Optimization Applied On Weekly Fleet Assignment with Time Window Model," In Proc. of 14th Air Transport Research Society World Conference, Portugal, 2010.
[7]B. Rexing, et al., "Airline Fleet Assignment with Time Windows," Transportation Science, vol. 34, pp. 1-20, 2000.
[8]F. S. Hillier and G. J. Lieberman, Introduction to operations research,, 8 ed.: McGraw-Hill, Inc., 2008.
[9]J. Chung, "Application of genetic algorithm on airline schedule," Mechanical, Aerospace and Indutrial Engineering, Ryerson Polytechnix, 2001.
[10]M. Pollack, "Some elements of the airline fleet planning problem," Transportation Research, vol. 11, pp. 301-310, 1977.
[11]B. C. Wallet, et al., "A matrix representation for genetic algorithms," In Proc. of the Automatic Object Recognition VI, Orlando, FL, USA, 1996.
[12]D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning: Addison-Wesley Professional, 1989.
[13]M. Dorigo, et al., "Ant system: optimization by a colony of cooperating agents," IEEE Transactions on System, Man, and Cybernetics, Part B: Cybernetics, vol. 26, pp. 29-41, 1996.
[14]R. Subramanian, et al., "Coldstart: Fleet Assignment at Delta Air Lines," Interfaces, vol. 24, pp. 104-120, 1994.
[15]M. Reimann, et al., "D-Ants: Savings Based Ants divide and conquer the vehicle routing problem," Computers & Operations Research, vol. 31, pp. 563-591, 2004.
[16]J. Abara, "Applying Integer Linear Programming to the Fleet Assignment Problem," Interfaces, vol. 19, pp. 20-28, 1989.
[17]C. A. Hane, et al., "The fleet assignment problem: Solving a large-scale integer program," Mathematical Programming, vol. 70, pp. 211-232, 1995.
[18]C. Barnhart, et al., "Flight String Models for Aircraft Fleeting and Routing," Transportation Science, vol. 32, pp. 208-220, 1998.
[19]L. M. Gambardella, et al. Currently effective eAIS package [Online]. Available at: http://eaip.caa.gov.tw/eaip/history/2011-05-19/html/index-zh-TW.html

校內：立即公開
校外：2013-08-30公開

簡易檢索 / 詳目顯示

相關論文