||Multiple Traveling Salesman Problem Model for Fleet Assignment
||Institute of Civil Aviation
multiple traveling salesman problem
本篇研究應用多旅行商問題模型(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.
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
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  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
 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.
 M. M. Etschmaier. and D. F. X. Mathaisel., "Airline scheduling: an overview," Transportation science, vol. vol. 19, pp. 127-138, 1985.
 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.
 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.
 T. C. Wang. and C. M. Li., "Fleet Assignment with a Continuously Adjustable Flight Schedule.," Transportation Journal, vol. 52, pp. 323-343, 2013.
 A. Schrijver, Combinatorial optimization polyhedra and efficiency: Springer-Verlag Berlin Heidelberg, 2003.
 J. Abara, "Applying integer linear programming to the fleet assignment problem," Interfaces, vol. 19, pp. 20-28, 1989.
 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.
 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.
 C. Barnhart., F. Lu., and R. G. Shenoi., "Integrated Airline Schedule Planning," Operations Research in the Airline Industry, 1998.
 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.
 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.
 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.
 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.
 P. Ratprasert, "Ant Colony Optimization Applied On Weekly Fleet Assignment with Time Window Model," 14th Air Transport Research Society World Conference, 2010.
 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.
 G. Yang, Proceedings of the 2012 International Conference on Communication, Electronics and Automation Engineering: Springer Berlin Heidelberg, 2012.
 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.
 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.
 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.
 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.
 T. Bektas, "The multiple traveling salesman problem: an overview of formulations and solution procedures," Omega, vol. 34, pp. 209-219, 2006.
 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.
 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.
 R. E. Burkard and E. Cela, "Linear Assignment Problems and Extensions."
 H. Dyckhoff, "A typology of cutting and packing problems," European Journal of Operational Research, vol. 44, pp. 145-159, 1990/01/25 1990.
 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.
 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.
 W. Li and J. Reich, "A complete enumeration and classification of two-locus disease models," Human heredity, vol. 50, pp. 334-349, 2000.
 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.
 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.
 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.
 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.
 R. A. Rutenbar, "Simulated annealing algorithms: an overview," Circuits and Devices Magazine, IEEE, vol. 5, pp. 19-26, 1989.
 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.