Fleet assignment consists of deciding on the type of aircraft that will operate on each specific flight. The objective of this scheduling stage is to minimize total cost or maximize total profit. The inherent complexity of the fleet assignment problem normally has resulted in the development of an integer programming based model or various heuristic solution procedures. In this research we use the Max-Min ant system (MMAS), one of the ant colony optimization heuristic methods (ACO), to solve a large scale weekly fleet assignment model in which variable departure times are considered. By adjusting new departure times, this model provides more schedule flexibility. This thesis also provides some experimental results in order to compare the ant colony optimization method with one exact solution method, “branch and cut”. Using data from real major airlines, the result from the implementation shows that the proposed MMAS approach not only can solve an airline fleet assignment problem with less than 5% error from an exact solution method but also can extend to simultaneously solving fleet assignment problems along with aircraft routing problems.

[1] Etschmaier, M., and Mathaisel, D., 1985, "Airline Scheduling:An Overview," Transportation Science, 19, pp. 127-138.
[2] Sherali, H. D., Bish, E. K., and Zhu, X., 2006, "Airline Fleet Assignment Concepts, Models, and Algorithms," European Journal of Operational Research, 172(1), pp. 1-30.
[3] Dorigo, M., 1992, "Optimization, Learning, and Natural Algorithms," Ph.D., Politecnico di Milano, Italy.
[4] Hane, C. A., 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 70, pp. 211-232.
[5] Abara, J., 1989, "Applying Integer Linear Programming to the Fleet Assignment Problem," Interfaces, 19(4), pp. 20-28.
[6] Barnhart, C., Boland, N. L., Clarke, L. W., Johnson, E. L., Nemhauser, G. L., and Shenoi, R. G., 1998, "Flight String Models for Aircraft Fleeting and Routing," Transportation Science INFORMS, Institute for Operations Research and the Management Sciences (INFORMS), Linthicum, Maryland, USA, pp. 208-220.
[7] Barnhart, C., Lu, F., and Shenoi, R. G., 1998, "Integrated Airline Schedule Planning," Operations Research in the Airline Industry, G. Yu, ed., Kluwer Academic, Boston.
[8] Rexing, B., Barnhart, C., Kniker, T. S., Jarrah, T. A., and Krishnamurthy, N., 2000, "Airline Fleet Assignment with Time Windows," Transportation Science, 34, pp. 1-20.
[9] Sakkout, E., 1995, "Modelling Fleet Assignment in a Flexible Environment," Proceedings of the Second International Conference on the Practical Application of Constraint Technology (PACT 96), pp. 27-39.
[10] Kliewer, G., and Tschoke, S., 2000, "A General Parallel Simulated Annealing Library and its Application in Airline Industry” Parallel and Distributed Processing Symposium, 2000. IPDPS 2000. 14th International Cancun pp. 55-61.
[11] Tae, C. J., and Chung, J., 2002, "Airline Fleet Assignment Using. Genetic Algorithms," GECCO2002, 2002 Genetic and Evolutionary Computation ConferenceNew York, pp. 255-262.
[12] Sosnowska, D., 2000, "Optimization of a Simplified Fleet Assignment Problem with Metaheuristics: Simulated annealing and GRASP. In: Pardalos, P.M. (Ed.)," Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, Kluwer Academic Publishers, Dordrecht, The Netherlands, pp. 477-488.
[13] Subramanian, R., Scheff, R. P., Quillinan, J. D., Wiper, D. S., and Marsten, R. E., 1994, "Coldstart: Fleet Assignment at Delta Air Lines," Interfaces, 24(1), pp. 104-120.
[14] Dorigo, M., Maniezzo, V., and Colorni, A., 1996, "Ant System: Optimization by a Colony of Cooperating Agents," IEEE Transactions on Systems, Man, and Cybernetics, 26,(1), pp. 29-41.
[15] Bullnheimer, B., Hartl, R. F., and Strauss, C., 1999, "A New Rank-Based Version of the Ant System:a Computational Study," Central European Journal for Operations Research and Economics, 7(1), pp. 25-38.
[16] Stützle, T., and Hoos, H., 2000, "MAX-MIN Ant System," Future Generation Computer Systems 16(9), pp. 889-914.
[17] Dorigo, M., and Gambardella, L. M., 1997, "Ant Colony System: a Cooperative Learning Approach to the Traveling Salesman Problem," IEEE Transactions on Evolutionary Computation, 1, pp. 53-66.
[18] Dorigo, M., and Stutzle, T., 2004, Ant Colony Optimization, Bradford Book, Messachusetts.
[19] Baker, J., "Reducing Bias and Inefficiency in the Selection Algorithm," Proc. the 2nd Conference on Genetic Algorithms, pp. 14-21.
[20] Holland, J., 1975, Adaptation In Natural and Artificial Systems, The University of Michigan Press, Ann Arbour.
[21] Maniezzo, V., and Colorni, A., 1999, "The Ant System Applied to the Quadratic Assignment Problem," IEEE Transactions on Knowledge and Data Engineering 11(5), pp. 769-778.
[22] Stützle, T., and Dorigo, M., 1999, "ACO Algorithms for the Quadratic Assignment Problem " Mcgraw-Hill'S Advanced Topics In Computer Science Series archive New ideas in optimization McGraw-Hill Ltd, England pp. 33-50.
[23] Randall, M., "Heuristics for Ant Colony Optimisation using the Generalised Assignment Problem," Proc. Evolutionary Computation, 2004. CEC2004, pp. 1916-1923.
[24] Chih, C. L., and Guang, F. D., "Using Ant Colony Optimization Algorithm to Solve Airline Crew Scheduling Problems," Proc. The Third International Conference on Natural Computation (ICNC2007) IEEE Computer Society Washington, DC, USA pp. 797-804.
[25] Ghoseiri, K., and Morshedsolouk, F., 2006, "ACS-TS: Train Scheduling using Ant Colony System," Journal of Applied Mathematics and Decision Sciences, 2006, pp. 1-28.
[26] Gasbaoui, B., and Allaoua, B., 2009, "Ant Colony Optimization Applied on Combinatorial Problem for Optimal Power Flow Solution," Leonardo Journal of Sciences, 8(14), pp. 1-17.
[27] Blum, C., 2005, "Ant Colony Optimization: Introduction and Recent Trends," Physics of Life Reviews, 2(4), pp. 353-373.
[28] Dorigo, M., Maniezzo, V., and Colorni, A., 1991, "Positive Feedback as a Search Strategy,"Technical Report 91-016, Dipartimento di Elettronica,Politecnico di Milano, Italy.
[29] Maniezzo, V., 1999, "Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem," INFORMS Journal on Computing 11(4), pp. 358-369.
[30] Stützle, T., "An Ant Approach to the Flow Shop Problem," Proc. 6th European Congress on Intelligent Techniques and Soft Computing (EUFIT'98), pp. 1560-1564.
[31] Den Besten, M., Stützle, T., and Dorigo, M., "Ant Colony Optimization for the Total Weighted Tardiness Problem," Proc. 6th International Conference on Parallel Problem Solving from Nature Springer-Verlag London, UK pp. 611-620.
[32] Gagné, C., Price, W. L., and Gravel, M., 2002, "Comparing an ACO Algorithm with Other Heuristic for the Single Machine Scheduling Problem with Sequence-Dependent Setup Times," Journal of the Operational Research Society 53, pp. 895-906.
[33] Merkle, D., Middendorf, M., and Schmeck, H., 2002, "Ant Colony Optimization for Resource-Constrained Project Scheduling," IEEE Transactions,Evolutionary Computation, 4(6), pp. 333-346.
[34] Blum, C., 2005, "Beam-ACO: Hybridizing Ant Colony Optimization with Beam Search: an Application to Open Shop Scheduling," Computers and Operations Research 32(6), pp. 1565-1591.
[35] Blum, C., and Sampels, M., 2004, "An Ant Colony Optimization Algorithm for Shop Scheduling Problems " Journal of Mathematical Modelling and Algorithms, 3(3), pp. 285-308.
[36] Gambardella, L. M., Taillard, E., and Agazzi, G., 1999, "MACS-VRPTW: a Multiple Ant Colony System for Vehicle Routing Problems with Time Windows," Mcgraw-Hill'S Advanced Topics In Computer Science Series archive New ideas in optimization McGraw-Hill Ltd., UK Maidenhead, UK, England
[37] Reimann, M., Doerner, K., and Hartl, R. F., 2004, "D-ants: Savings Based Ants Divide and Conquer the Vehicle Routing Problems," Computers & Operations Research, 31(4), pp. 563-591.
[38] Socha, K., Sampels, M., and Manfrin, M., 2003, "Ant Algorithms for the University Course Timetabling Problem with Regard to the State-of-the-Art," Applications of Evolutionary Computing, Springer Berlin / Heidelberg, pp. 334-345.
[39] Gandibleux, X., Delorme, X., and T’Kindt, V., 2004, "An Ant Colony Optimisation Algorithm for the Set Packing Problem " Ant Colony, Optimization and Swarm Intelligence, Springer Berlin / Heidelberg, pp. 478-481.
[40] Costa, D., and Hertz, A., 1997, "Ants Can Color Graphs," Journal of the Operational Research Society 48, pp. 295-305.
[41] Michel, R., and Middendorf, M., "An Island Model Based Ant System with Lookahead for the Shortest Supersequence Problem," Proc. the 5th International Conference on Parallel Problem Solving from Nature pp. 692-701.
[42] Gambardella, L. M., and Dorigo, M., 2000, "An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem," INFORMS Journal on Computing 12(3), pp. 237-255.
[43] Solon, C., 2002, "Ants Can Solve Constraint Satisfaction Problems," IEEE Transactions on Evolutionary Computation, 6(4), pp. 347-357.
[44] Parpinelli, R. S., Lopes, H. S., and Freitas, A. A., 2002, "Data Mining with an Ant Colony Optimization Algorithm," IEEE Transaction on Evolutionary Computation, 6(4), pp. 321-332.
[45] Bui, T. N., and Rizzo, J. R., 2004, "Finding Maximum Cliques with Distributed Ants," Genetic and Evolutionary Computation – GECCO 2004, Springer Berlin / Heidelberg, pp. 24-25.
[46] Blesa, M., and Blum, C., 2004, "Ant Colony Optimization for the Maximum Edge-Disjoint Paths Problem," Applications of Evolutionary Computing, Springer Berlin / Heidelberg, pp. 160-169.
[47] Alupoaei, S., and Katkoori, S., 2004, "Ant Colony System Application to Macrocell Overlap Removal," IEEE Transactions on Very Large Scale Integration (VLSI) Systems 12(10), pp. 1118-1122.
[48] Maniezzo, V., Boschetti, M., and Jelasity, M., 2004, "An Ant Approach to Membership Overlay Design " Ant Colony, Optimization and Swarm Intelligence, Springer, Berlin, pp. 326-343.
[49] Shmygelska, A., Aguirre-Hernández, R., and Hoos, H. H., "An Ant Colony Optimization Algorithm for the 2D HP Protein Folding Problem," Proc. 3rd International Workshop on Ant Algorithms Springer, pp. 40-53.
[50] Moss, J. D., and Johnson, C. G., 2003, "An Ant Colony Algorithm for Multiple Sequence Alignment in Bioinformatics," Artificial neural networks and genetic algorithms, Springer, Berlin.
[51] Karpenko, O., Shi, J., and Dai, Y., 2005, "Prediction of MHC Class II Binders Using the Ant Colony Search Strategy," Artificial Intelligence in Medicine 35(1-2), pp. 147-156.
[52] Shmygelska, A., and Hoos, H. H., 2005, "An Ant Colony Optimisation Algorithm for the 2D and 3D Hydrophobic Polar Protein Folding Problem," BMC Bioinformatics, 6(30), pp. 1-22.
[53] Bautista, J., and Pereira, J., 2002, "Ant Algorithms for Assembly Line Balancing " Ant Algorithms, Springer, Berlin, pp. 49-61.
[54] Silva, C. A., Runkler, T. A., Sousa, J. M., and Palm, R., "Ant Colonies as Logistic Processes Optimizers," Proc. 3rd International Workshop on Ant Algorithms Springer, pp. 76-87.
[55] Gottlieb, J., Puchta, M., and Solnon, C., 2003, "A Study of Greedy, Local Search, and Ant Colony Optimization Approaches for Car Sequencing Problems," Applications of evolutionary computing Springer, Berlin, pp. 246-257.
[56] Corry, P., and Kozan, E., 2004, "Ant Colony Optimisation for Machine Layout Problems " Computational Optimization and Applications, 28(3), pp. 287-310.
[57] Guntsch, M., and Middendorf, M., "Solving Multi-Objective Permutation Problems with Population Based ACO (EMO2003)," Proc. 2nd Conference on Evolutionary Multi-Criterion Optimization Spinger, pp. 464-478.
[58] López-Ibáñez, M., Paquete, L., and Stützle, T., 2004, "On the Design of ACO for the Biobjective Quadratic Assignment Problem," Ant Colony, Optimization and Swarm Intelligence, Spinger, Berlin, pp. 436-459.
[59] Doerner, K., Gutjahr, W. J., Hartl, R. F., Strauss, C., and Stummer, C., 2004, "Pareto Ant Colony Optimization: A Metaheuristic Approach to Multiobjective Portfolio Selection " Annals of Operations Research, 131, pp. 79-99.
[60] Guntsch, M., and Middendorf, M., 2001, "Pheromone Modification Strategies for Ant Algorithms Applied to Dynamic TSP " Applications of Evolutionary Computing, Springer, Berlin, pp. 213-222.
[61] Bianchi, L., Gambardella, L. M., and Dorigo, M., "An Ant Colony Optimization Approach to the Probabilistic Traveling Salesman Problem," Proc. the 7th International Conference on Parallel Problem Solving from Nature
[62] Guéret, C., Monmarché, N., and Slimane, M., 2004, "Ants Can Play Music " Ant Colony, Optimization and Swarm Intelligence, Spinger, Berlin, pp. 310-317.
[63] Ralphs, T. K., Ladányi, L., and Saltzman, M. J., 2003, "Parallel Branch, Cut, and Price for Large-Scale Discrete Optimization," Mathematical Programming, Springer Berlin / Heidelberg, pp. 253-280.