成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	莊偉志 Chuang, Wei-Chih
論文名稱：	多旅行商問題模型應用於機隊指派問題 Multiple Traveling Salesman Problem Model for Fleet Assignment
指導教授：	王大中 Wang, Ta-Chung
學位類別：	碩士 Master
系所名稱：	工學院 - 民航研究所 Institute of Civil Aviation
論文出版年：	2015
畢業學年度：	103
語文別：	英文
論文頁數：	68
中文關鍵詞：	航空公司班表排程、機隊指派、多旅行商問題
外文關鍵詞：	airline planning, fleet assignment, multiple traveling salesman problem
相關次數：	點閱：116 下載：5
分享至:	分享至facebook 分享至twitter

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

機隊指派為航空公司排班的四個主要步驟之一。其主要目的即在航線已知及機隊規模固定的情況下，將適當的機型及數量安排至適當的航線上營運，使得航空業者的總收益最大化或總營運成本最小化，而這種大型規劃問題的求解效率與品質通常隨著複雜度增加而有所下降，所以大部分的研究都著重於使用啟發式演算法(heuristic algorithm)，以尋求近似解作為最佳解來取代精確解，目的在於能夠較有效率地以較少的時間求解出滿意的結果。

本篇研究應用多旅行商問題模型(MTSP Model)，用以描述機隊指派各航段的狀況及排序固定的航班。不同於時空網路模型(Time-Space Network)，此模型將航班離到場時間和機場轉化成點，並將可能航班點連接成線，根據限制式來直接求解出最小的距離成本，且考量限制條件及最小化距離成本來達成航班最佳化排序的目的，並達到機隊指派後能有最大化的獲利。多旅行商這類的規劃問題已經有許多的研究，其技術也已發展成熟，本篇研究透過轉換此種模式來求解機隊指派問題，其問題規模大小跟機隊指派問題是相同的，也有較好的問題求解程序可以加以修改。

本篇的研究提出一個二階段的方法求解機隊指派問題。首先，我們應用基因演算法(Genetic Algorithm)來求解出應用多旅行商問題模型的機隊指派問題，考量到更多彈性時間，在機隊指派問題中加入了返回節線(backward arc)，在允許時間逆流的情況下，尋找一個符合限制且最小距離成本的最佳解，並找出每架飛機應該飛哪些航班，求解出每架飛機有最小距離成本的飛行路徑。接著，根據第一階段的解，我們使用一個線性規劃的數學式取代傳統的時間窗(time window)方式，去調整班表。此方法也像有時間窗的方法一樣能夠允許在航班離開時間有變動下，指派各航段應使用的機型。

Fleet assignment is one of four main steps in airline planning. The objective is to determine which type of aircraft should fly on each flight leg while considering the different features and costs with different fleet types. The main purpose of the fleet assignment problem (FAP) is to maximize total profits or minimize total operating costs. The problem is usually formulated as an integer linear programming problem. The solving efficiency and quality of the massive programming problem will drop with complexity increasing. Due to the size of the FAP, various heuristic algorithms or methods for solving this problem have been studied. The purpose of finding the heuristic solutions for the optimal feasible solution is to find the satistied results more efficient for less time.

This thesis proposes a multiple traveling salesman problem model(MTSP Model) to solve the FAP, and determine which type of aircraft should fly on each flight arc and flights which has the optimal order. It’s different to Time-Space Network model, this model drawing the flight dots by the departure time, departure airport, arrival time and arrival airport, and joining the flight dots to calculate the minimal costs by following the relative constraints. The perpose is to obtain optimal flight order by considering constraints and minimal the costs of distance to get the maximum total profits after fleet assignment procedure. In this thesis, the MTSP Model is choosen because the MTSP is a well-known problem which is solved by many kinds of solver with good solving quality. The MTSP not only has the roughly same problem size comparing to the FAP but also has well-developed technique to be solved.

This thesis proposes a two-phase approach to solving the FAP. First, genetic algorithm is applied to solve MTSP model for FAPs. Cosidering more feasible time, backward arcs are used to solve this problem. By allowing backward time, the optimal feasible solution with the minimum number of rescheduled flight is sought. Some routes, which have minimal costs of distance, are found. Finally, the continuously adjustable flight schedule problem is solved using a integer linear programming model instead of using a time window to change flight schedules. Our method 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.

CONTENTS
ABSTRACT	i
摘要	iii
誌謝	v
CONTENTS	vi
LIST OF TABLES	viii
LIST OF FIGURES	ix
LIST OF NOTATIONS	x
Chapter 1 Introduction	1
1.1 Preface	1
1.2 Motivation and Objective	2
1.3 Fleet Assignment Problem Literature Review	6
1.4 Outline of this Research	7
Chapter 2 FAP Integer Programming	8
2.1 Combinatorial Optimization	8
2.2 Fleet Assignment Problem	9
2.2.1 Basic Fleet Assignment Problem	9
2.2.2 Time-Space Network	9
2.2.3 Mathematical Formulation of the Fleet Assignment Problem	11
2.2.4 Fleet Assignment with Time-Window	19
2.2.5 Backward Arc Technique	26
2.3 Methods for Solving the Fleet Assignment Problem	28
2.3.1 Exact Procedures	28
2.3.2 Approximation Algorithms	31
2.4 Summary	35
Chapter 3 Multiple Traveling Salesman Problem Model for Fleet Assignment	36
3.1 Multiple Traveling Salesman Problem	36
3.2 Multiple Traveling Salesman Problem Model for Fleet Assignment	39
3.3 Using Backward Arc Technique	44
3.4 Summary	46
Chapter 4 Solve MTSP Model for FAP	47
4.1 Appling GA to the MTSP Model for FAP	47
4.2 Adjustiment for Using Backward Arc	51
Chapter 5 Simulation Results	58
5.1 Simulation Data	58
5.2 Simulation Results	59
Chapter 6 Conclusions	65
6.1 Conclusions	65
6.2 Future Reseaech	65
Reference	66

LIST OF TABLES
Table 1: An example of extra connection opportunity if time windows are allowed.	21
Table 2: Method types for solving the FAP.	28
Table 3: Data in an example	51
Table 4: The schedule data sets	59
Table 5: The results of 7 different schedules using the MTSP model for FAP comparing to optimal solution obtained by using LPSolve.	59
Table 6: The results for compared with adding backward arcs	63

LIST OF FIGURES
Figure 1: The trend of oil prices (data from U.S. Energy Information Administration)	1
Figure 2: The plan schedule of airline business	3
Figure 3: Time-space network.	10
Figure 4: Two stations example for flight coverage constraint	13
Figure 5: Two stations example for aircraft balance constraint	13
Figure 6: Six stations example for fleet size constraint	14
Figure 7: Example of passenger spill	16
Figure 8: The demand distribution [20]	17
Figure 9: Example of a time window time-space network for two airports.	20
Figure 10: Node consolidation preprocessing technique	23
Figure 11: Deleted redundant flight arc preprocessing technique.	24
Figure 12 Island preprocessing technique	25
Figure 13: Backward connection arcs	27
Figure 14: The example of multiple traveling salesman problem model for fleet assignment	39
Figure 15: Three situation of distance definition.	41
Figure 16: The distance definition with exponential function.	45
Figure 17: The example of multi-chromosome representation for the number of flight (n = 13) and the number of aircraft (m = 3)	48
Figure 18: The flow chart of using GA.	50
Figure 19: The time-space before/after the adjustable phase.	52
Figure 20: The time-space before/after the adjustable phase for the example.	56
Figure 21: The computation procedure.	58
Figure 22: The profit with compared.	61
Figure 23: The computational time with compared.	61
Figure 24: The profit for compared with adding backward arcs.	64
                                    

[1] C. Jeenanunta, B. Kasemsontitum, and T. Noichawee, "A multi-commodity flow approach for aircraft routing and maintenance problem," Quality and Reliability (ICQR), 2011 IEEE International Conference on, pp. 150-155, 14-17 Sept. 2011 2011.
[2] M. M. Etschmaier. and D. F. X. Mathaisel., "Airline scheduling: an overview," Transportation science, vol. vol. 19, pp. 127-138, 1985.
[3] H. D. Sherali., E. K. Bish., and X. Zhu., "Airline fleet assignment concepts, models, and algorithms," European Journal of Operational Research, vol. vol. 172, pp. 1-30, 2006.
[4] B. Rexing., C. Barnhart., T. S. Kniker., T. A. Jarrah., and N. Krishnamurthy., "Airline fleet assignment with time windows," Transportation Science, vol. 34, pp. 1-20, 2000.
[5] T. C. Wang. and C. M. Li., "Fleet Assignment with a Continuously Adjustable Flight Schedule.," Transportation Journal, vol. 52, pp. 323-343, 2013.
[6] A. Schrijver, Combinatorial optimization polyhedra and efficiency: Springer-Verlag Berlin Heidelberg, 2003.
[7] J. Abara, "Applying integer linear programming to the fleet assignment problem," Interfaces, vol. 19, pp. 20-28, 1989.
[8] C. A. Hane., C. Barnhart., E. L. Johnson., R. E. Marsten., G. L. Nemhauser., and G. Sigismondi., "The fleet assignment problem:Solving a large-scale integer program," Mathematical Programming, vol. 70, pp. 211-232, 1995.
[9] 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, pp. 208-220, 1998.
[10] C. Barnhart., F. Lu., and R. G. Shenoi., "Integrated Airline Schedule Planning," Operations Research in the Airline Industry, 1998.
[11] L. Jun, S. Qirui, Z. Mengchu, and D. Xianzhong, "A New Multiple Traveling Salesman Problem and Its Genetic Algorithm-Based Solution," Systems, Man, and Cybernetics (SMC), 2013 IEEE International Conference on, pp. 627-632, 2013.
[12] S. Yuan, B. Skinner, S. Huang, and D. Liu, "A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms," European Journal of Operational Research, vol. 228, pp. 72-82, 7/1/ 2013.
[13] M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: optimization by a colony of cooperating agents," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 26, pp. 29-41, 1996.
[14] J. Yang, X. Shi, M. Marchese, and Y. Liang, "An ant colony optimization method for generalized TSP problem," Progress in Natural Science, vol. 18, pp. 1417-1422, 11/10/ 2008.
[15] P. Ratprasert, "Ant Colony Optimization Applied On Weekly Fleet Assignment with Time Window Model," 14th Air Transport Research Society World Conference, 2010.
[16] L. Chih-Chung and D. Guang-Feng, "Using Ant Colony Optimization Algorithm to Solve Airline Crew Scheduling Problems," Natural Computation, 2007. ICNC 2007. Third International Conference on, vol. 4, pp. 797-804, 2007.
[17] G. Yang, Proceedings of the 2012 International Conference on Communication, Electronics and Automation Engineering: Springer Berlin Heidelberg, 2012.
[18] S.-M. Chen and C.-Y. Chien, "Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques," Expert Systems with Applications, vol. 38, pp. 14439-14450, 2011.
[19] M. A. H. Akhand, S. Akter, S. Sazzadur Rahman, and M. M. Hafizur Rahman, "Particle Swarm Optimization with partial search to solve Traveling Salesman Problem," Computer and Communication Engineering (ICCCE), 2012 International Conference on, pp. 118-121, 2012.
[20] R. Subramanian, R. P. Scheff, J. D. Quillinan, D. S. Wiper, and R. E. Marsten, "Coldstart: Fleet Assignment at Delta Air Lines," Interfaces, vol. 24, pp. 104-120, 1994.
[21] P. Oberlin, S. Rathinam, and S. Darbha, "A transformation for a Multiple Depot, Multiple Traveling Salesman Problem," American Control Conference, 2009. ACC '09., pp. 2636-2641, 2009.
[22] T. Bektas, "The multiple traveling salesman problem: an overview of formulations and solution procedures," Omega, vol. 34, pp. 209-219, 2006.
[23] A. Kodama and T. Nishi, "Petri net representation for 0-1 integer programming problems," in Industrial Engineering and Engineering Management (IEEM), 2014 IEEE International Conference on, 2014, pp. 729-733.
[24] G. Laporte, "The traveling salesman problem: An overview of exact and approximate algorithms," European Journal of Operational Research, vol. 59, pp. 231-247, 1992/06/10 1992.
[25] R. E. Burkard and E. Cela, "Linear Assignment Problems and Extensions."
[26] H. Dyckhoff, "A typology of cutting and packing problems," European Journal of Operational Research, vol. 44, pp. 145-159, 1990/01/25 1990.
[27] O. Grygorash, Z. Yan, and Z. Jorgensen, "Minimum Spanning Tree Based Clustering Algorithms," Tools with Artificial Intelligence, 2006. ICTAI '06. 18th IEEE International Conference on, pp. 73-81, 2006.
[28] G. Laporte, "The vehicle routing problem: An overview of exact and approximate algorithms," European Journal of Operational Research, vol. 59, pp. 345-358, 6/25/ 1992.
[29] W. Li and J. Reich, "A complete enumeration and classification of two-locus disease models," Human heredity, vol. 50, pp. 334-349, 2000.
[30] P. M. Narendra and K. Fukunaga, "A Branch and Bound Algorithm for Feature Subset Selection," Computers, IEEE Transactions on, vol. C-26, pp. 917-922, 1977.
[31] R. L. Carraway, T. L. Morin, and H. Moskowitz, "Generalized dynamic programming for multicriteria optimization," European Journal of Operational Research, vol. 44, pp. 95-104, 1/5/ 1990.
[32] E. Balas, S. Ceria, and G. Cornuéjols, "A lift-and-project cutting plane algorithm for mixed 0–1 programs," Mathematical programming, vol. 58, pp. 295-324, 1993.
[33] P. C. Chu and J. E. Beasley, "A genetic algorithm for the generalised assignment problem," Computers & Operations Research, vol. 24, pp. 17-23, 1// 1997.
[34] R. A. Rutenbar, "Simulated annealing algorithms: an overview," Circuits and Devices Magazine, IEEE, vol. 5, pp. 19-26, 1989.
[35] J. Kennedy and R. Eberhart, "Particle swarm optimization," Neural Networks, 1995. Proceedings., IEEE International Conference on, vol. 4, pp. 1942-1948 vol.4, Nov/Dec 1995 1995.

校內：2020-09-02公開
校外：2020-09-02公開

簡易檢索 / 詳目顯示

相關論文