臺灣博碩士論文加值系統

In this research, the Gate Assignment Problem (GAP) is considered with reference to two objectives. The first objective is to minimize total walking distance of passengers to departure gates, check-in counters, and connection flights. The second one is to minimize number of flights assigned to the apron. Essentially, the GAP seeks the optimal flight-to-gate assignments so that total passenger walking distances and consequent connection times are minimized. A weighted sum of two objectives to the GAP is used by adding a penalty to flights assigned to the apron. An algorithm is used based on the Ant Colony Optimization (ACO) method to minimize our bi-objective gate assignment problem. Our goal is to apply the ACO to the GAP by achieving a near optimal solution. The behavior of each ant is critical for fast convergence to (near) optimal solutions of the GAP. The numerical experiments investigate whether the ACO approach is an efficient method to obtain good solutions in our proposed GAP model. The performance of this approach is evaluated in a variety of test problems. The commercial Gurobi Solver and a First Come First Served heuristic algorithm are used as baselines to compare our ACO results for small and large size instances, respectively. An instance generator was used to generate data for arrival and departure times, and additional specifications of flights.

In this research, the Gate Assignment Problem (GAP) is considered with reference to two objectives. The first objective is to minimize total walking distance of passengers to departure gates, check-in counters, and connection flights. The second one is to minimize number of flights assigned to the apron. Essentially, the GAP seeks the optimal flight-to-gate assignments so that total passenger walking distances and consequent connection times are minimized. A weighted sum of two objectives to the GAP is used by adding a penalty to flights assigned to the apron. An algorithm is used based on the Ant Colony Optimization (ACO) method to minimize our bi-objective gate assignment problem. Our goal is to apply the ACO to the GAP by achieving a near optimal solution. The behavior of each ant is critical for fast convergence to (near) optimal solutions of the GAP. The numerical experiments investigate whether the ACO approach is an efficient method to obtain good solutions in our proposed GAP model. The performance of this approach is evaluated in a variety of test problems. The commercial Gurobi Solver and a First Come First Served heuristic algorithm are used as baselines to compare our ACO results for small and large size instances, respectively. An instance generator was used to generate data for arrival and departure times, and additional specifications of flights.

ACKNOWLEDGEMENTS ii
Abstract iii
Table of Contents v
List of Figures viii
List of Tables ix
Chapter 1 Introduction 1
1.1 Research Background 1
1.2 Research Motivation 3
1.3 Research Objectives 5
1.4 Thesis Organization 6
Chapter 2 Literature Review 7
2.1 Quadratic Assignment Problem 7
2.2 Gate Assignment Problem 12
2.3 Multiple-Objective Gate Assignment Problem 15
2.4 Exact Methods and Heuristic Algorithms Applied to the GAP 18
2.4.1 Linear Programming 18
2.4.2 Branch and Bound 22
2.4.3 Genetic Algorithms for the GAP 23
2.5 Ant Colonies for the GAP 24
2.5.1 The Original Ant System 24
2.5.2 Max-Min Ant System 26
2.5.3 Ant Colony System 27
2.5.4 Rank-based Ant System 28
2.5.5 Ant Colonies for the QAP 28
2.5.6 Ant Colony Optimization Approach to Multiple Objectives 30
2.6 Summary 31
Chapter 3 Research Methodology 33
3.1 Quadratic Assignment Problem 33
3.1.1 Assumptions and Problem Formulation 33
3.1.2 Model Formulation 34
3.1.3 Ant Colony System for the QAP 34
3.2 Gate Assignment Problem 39
3.2.1 Assumptions and Problem Formulation 40
3.2.2 Ant Colony System for the GAP 42
3.3 The Multi-Objective Gate Assignment Problem 49
3.4 Summary 53
Chapter 4 Computational Experiments 55
4.1 QAP Instances 55
4.1.1 Parameter Sensitivity Analysis 56
4.1.2 QAP Results 60
4.2 Single Objective GAP Test Problems 62
4.2.1 Parameter Sensitivity Analysis of ACO-GAP 67
4.2.2 GAP Results 70
4.3 Multi-objective Gate Assignment Problem 77
4.4 Summary 91
Chapter 5 CONCLUSIONS 94
5.1 Major Findings 95
5.2 Recommendations 96
5.3 Directions for Future Research 98
REFERENCES 99
APPENDIX 110

1.Abbiw-Jackson, R., Golden, B., Raghavan, S. and Wasil, E. (2006) “A Divide-and-Conquer Local Search Heuristic for Data Visualization,” Computers & Operations Research, Vol. 33, 3070-3087.
2.Adams, W. P., Guignard, M., Hahn, P. and Hightower, W. L. (2007), “A Level 2 Reformulation-linearization Technique Bound for the Quadratic Assignment Problem,” European Journal of Operational Research, Vol.180, 983-996.
3.Adenso-Diaz, B., Garcia-Carbajal, S. and Lozano, S. (2006) “An Empirical Investigation on Parallelization Strategies for Scatter Search,” European Journal of Operational Research, Vol. 169, 490-507.
4.Ahuja, R.K., Orlin, J.B. and Tiwari, A. (2000) “A Greedy Genetic Algorithm for the QAP,” Computers & Operations Research, Vol. 27, 917-934.
5.Ahyaningsih, F., Mawengkang, H. and Suwilo, S. (2006) “An Improved Strategy for Solving Quadratic Assignment Problem,” Proceedings of the 2nd IMT-GT Regional Conference on Mathematics, Statistics and Applications, 1-10.
6.Aiex, R.M.,Resende, M.G.C. and Ribeiro, C.C. (2002) “Probability Distribution of Solution Time in GRASP: An Experimental Investigation,” Journal of Heuristics, Vol. 8, 343-373.
7.Angel, E. and Zissimopoulos, V. (1998) “On the Quality of Local Search for the Quadratic Assignment Problem,” Discrete Applied Mathematics, Vol. 82, 15-25.
8.Anghinoli, D. and Paolucci, M. (2008) “A New Ant Colony Optimization Approach for the Single Machine Total Weighted Tardiness Scheduling Problem,” International Journal of Operations Research, Vol. 5, 44-60.
9.Arostegui, Jr. M.A., Kadipasaoglu, S.N. and Khumawala, B.M. (2006) “An Empiricalcomparison of Tabu Search, Simulated Annealing and Genetic Algorithms for Facilities Location Problems,” International Journal of Production Economics, Vol. 103, 742-754.
10.Babic, O., Teodoric, D. and Tosic, V. (1984) “Aircraft Stand Assignment to Minimize Walking,” Journal of Transportation, Vol. 110, 55-56.
11.Bartolomei-Suarez, S. M. and Egbeleu, P. J. (2000) “Quadratic Assignment Problem QAP with Adaptable Material Handling Devices,” International Journal of Production Research, Vol. 38, 855-873.
12.Barr, R., Golden, B.L., Kelly, J.P., Resende, M.G.C. and Stewart, W.R., Jr. (1995) “Designing and Reporting on Computational Experiments with Heuristics Methods,” Journal of Heuristics, Vol. 1, 9-32.
13.Ben-David, G. and Malah, D. (2005) “Bounds on the Performance of Vector-quantizers under Channel Errors,” IEEE Transactions on Information Theory, Vol. 51, 2227-2235.
14.Benjaafar, S. (2002) “Modeling and Analysis of Congestion in the Design of Facility Layouts,” Management Science, Vol. 48, 679-704.
15.Bennell, A. J., Mesgarpour, M. and Pitts, N. C. (2011) “Airport Runway Scheduling,” Operations Research, Vol. 9, 115-138
16.Bolat, A. (1999) “Assigning Arriving Flights at an Airport to the Available Gates,” Journal of the Operational Research Society, Vol. 50, 23-34
17.Brown, E. L. (1995) “A Quadratic Partial Assignment and Packing Model and Algorithm for the Airport Gate Assignment Problem,” Unpublished Master Thesis, Industrial and Systems Engineering Department, Virginia Polytechnic Institute and State University, Blacksburg, Virginia, U.S.A.
18.Brusco, M. J. and Stahl, S. (2000) “Using Quadratic Assignment Methods to Generate Initial Permutations for Least-squares Unidimensional Scaling of Symmetric Proximity Matrices,” Journal of Classification, Vol. 50, 197-223.
19.Burkard, R.E., Cela, E., Rote, G. and Woeginger, G.J. (1996a) “The Quadratic Assignment Problem with a Monotone Anti-Monge and a Symmetric Toeplitz Matrix,” Lecture Notes in Computer Science, Vol. 1084, 204-218.
20.Burkard, R.E., Rudolf, R. and Woeginger, G.J. (1996b) “Three-dimensional Axial Assignment Problems with Decomposable Cost Coefficients,” Discrete Applied Mathematics, Vol. 65, 123-139.
21.Cela, E. (1998) “The Quadratic Assignment Problem: Theory and Algorithms,” Du, D.Z. and Perdalos, P. (Editors), Combinatorial Optimization, Kluwer Academic Publishers, Dordrecht.
22.Chen, B. (1995), “Special Cases of the Quadratic Assignment Problem,” European Journal of Operational Research, Vol. 81, 410-419.
23.Chwif, L., Marcos, R., Barretto, P. and Moscato, L.A. (1998) “A Solution to the Facility Layout Problem Using Simulated Annealing,” Computers in Industry, Vol. 36, 125-132.
24.Ciriani, V., Pisanti, N. and Bernasconi, A. (2004) “Room Allocation: A Polynomial Sub-case of the Quadratic Assignment Problem,” Discrete Applied Mathematics, Vol. 144, 263-269.
25.Ding, H., Lim, A., Rodrigues, B., and Zhu, Y. (2004) “Aircraft and Gate Scheduling Optimization at Airports,” Proceedings of the 34th Hawaii International Conference on System Sciences, 1-8.
26.Ding, H., Lim, A., Rodrigues, B., and Zhu, Y. (2005) “The Over-constrained Airport Gate Assignment Problem,” Computers & Operations Research, Vol. 32, 1867-1880.
27.Dorigo, M. and Blum, C. (2005) “Ant Colony Optimization Theory: A Survey,” Theoretical Computer Science, Vol. 344, 243-278.
28.Dorigo, M., Maniezzo, V. and Colorini, A. (1996) “Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transactions on Systems, Man, and Cybernetics Part B, Vol. 26, 29-41.
29.Dorndorf, U., Drexl, A., Nikulin, Y. and Pesch, E. (2007) “Flight Gate Scheduling: State-of-the-art and Recent Developments,” Omega, Vol. 35, 326-334.
30.Drexel, A. and Nikulin, Y. (2008) “Multicriteria Airport Gate Assignment and Pareto Simulating Annealing,” IIE Transactions, Vol. 40, 385-397.
31.El-Bouri, A., Azizi, N. and Zolfaghari, S. (2007) “A Comparative Study of a New Heuristic based on Adaptive Memory Programming and Simulated Annealing: The Case of Job Shop Scheduling,” European Journal of Operational Research, Vol. 177, 1894-1910.
32.Gambardella, L. M. and Dorigo, M. (1996) “Solving Symmetric and Asymmetric TSPs by Ant Colonies,” Proceedings of IEEE Conference on Evolutionary Computation, 622-627.
33.Gambardella, L. M. and Dorigo, M. (1997) “Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem,” Accessed April 12, 2010 http://www.idsia.ch/~luca/acs-ec97.pdf.
34.Gambardella, L. M., Taillard, E. D. and Dorigo, M. (1999) “Ant Colonies for the Quadratic Assignment Problem,” Journal of the Operational Research Society, Vol. 50, 167-176.
35.Garcia, H. A and Quintero, M. E. (2011) “Strategy for attending takeoffs and landings to reduce the airport operating costs and the Passenger Delays,” European Journal of Transport and Infrastructure Research, Vol.11, 219-233.
36.Geoffrion, A.M. and Graves, G.W. (1976) “Scheduling Parallel Production Lines with Changeover Costs: Practical Applications of a Quadratic Assignment/LP approach,” Operations Research, Vol. 24, 595-610.
37.Gong, D., Yamazaki, G., Gen, M. and Xu, W. (1999) “A Genetic Algorithm Method for One-dimensional Machine Location Problems,” International Journal of Production Economics, Vol. 60, 337-342.
38.Greistorfer, P. (2003) “A Tabu Scatter Search Metaheuristic for the ARC Routing Problem,” Computers & Industrial Engineering, Vol. 44, 249-266.
39.Gu, Y. and Chung, C.A. (1999) “Genetic Algorithm Approach to Aircraft Gate Reassignment Problem,” Journal of Transportation Engineering, Vol. 125, 384-389.
40.Haghani, A. and Chen, M.C. (1998) “Optimizing Gate Assignments at Airport Terminals,” Transportation Research Part A, Vol. 32, 437-454.
41.Hahn, P.M. and Krarup, J. (2001) “A Hospital Facility Layout Problem Finally Solved,” Journal of Intelligent Manufacturing, Vol. 12, 487-496.
42.Heinonen, J. and Petterson, F. (2007) “Hybrid Ant Colony Optimization and Visibility Studies Applied to a Job-shop Scheduling Problem,” Applied Mathematics and Computation, Vol. 187, 989-998.
43.Ho, Y. C. and Moodie, C. L. (2000) “A Hybrid Approach for Concurrent Layout Design of Cells and Their Flow Paths in a Tree Configuration,” International Journal of Production Research, Vol. 38, 895-928.
44.Holland, J.H. (1975) “Adaptation in Natural and Artificial Systems. An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence,” University of Michigan Press, Ann Arbor, Michigan, U.S.A.
45.Hubert, L. (1987) “Assignment Methods in Combinatorial Data Analysis,” Statistics, Textbooks and Monographs, Vol. 73, American Educational Research Association and America Statistical Association, Publisher.
46.Hu, X.B. and Paolo, D.E. (2008) “Genetic Algorithms for the Airport Gate Assignment Problem: Linkage, Representation and Uniform Crossover,” Linkage in Evolution Computation, Vol. 157, 361-387.
47.James, T., Rego, C., Glover, F.(2009) “A Cooperative Parallel Tabu Search Algorithm for the QAP,” European Journal of Operational Research, Vol. 195, 810-826.
48.Koopmans, T. C. and Beckmann, M. J. (1957) “Assignment Problems and the Location of Economic Activities,” Econometrica, Vol. 25, 53-76.
49.Leahy, J. (2010), “Airbus Global Market Forecast 2010-2029”, Accessed http://www.airbus.com/company/market/gmf2010/
50.Lhotska, L., Macaŝ, M. and Burŝa, M. (2006) “PSO and ACO in Optimization Problems,” Lecture Notes in Computer Science, Vol. 4224, 1390-1398.
51.Li, C. (2008), “Airport Gate Assignment: New Model and Implementation,” Accessed January 10, 2010 http://arxiv.org/ftp/arxiv/papers/0811/0811.1618.pdf.
52.Loiola, E. M., Abreu, N. M. M., Boaventura-Netto, P. O., Hahn, P. and Querido, T. (2007) “A Survey for the Quadratic Assignment Problem,” European Journal of Operational Research, Vol. 176, 657-690.
53.Mangoubi, R. S. and Mathaisel, D. F. X. (1985) “Optimizing Gate Assignments at Airport Terminals,” Transportation Science, Vol. 19, 173-188.
54.Marler, R. T and Arora, J. S. (2004) “Survey of Multi-Objective Optimization Methods for Engineering,” Structural and Multidisciplinary Optimization, Vol. 26, 369-395.
55.Martinez, C. G., Cordon, O. and Herrera, F. (2004) “An Emprical Analysis of Multiple Objective Ant Colony Optimization Algorithms for the Bi-criteria TSP,” Lecture Notes in Computer Science, Vol. 3172, 61-72.
56.Mavridou, T., Pardalos, P.M., Pitsoulis, L.S. and Resende M.G.C. (1998) “A GRASP for the Biquadratic Assignment Problem,” European Journal of Operational Research, Vol. 105, 613-621.
57.Mckendall, A.R. and Jaramillo J.R. (2006) “A Tabu Search Heuristic for the Dynamic Space Allocation Problem,” Computers & Operations Research, Vol. 33, 768-789.
58.Mckendall, Jr. A.R. (2008) “Improved Tabu Search Heuristics for the Dynamic Space Allocation Problem,” Computers & Operations Research, Vol. 35, 3347-3359.
59.Misevicius, A. (2004) “An Improved Hybrid Genetic Algorithm: New results for the QAP,” Knowledge-Based Systems, Vol. 17, 65-73.
60.Mullen, R. J., Monekosso, D., Barman, S. and Remagnino, P. (2009), “A Review of Ant Algorithms,” Expert Systems with Applications, Vol. 36, 9608-9617.
61.Neumaier, A. (2003) “Complete Search in Continuous Global Optimization and Constraint Satisfaction,” Accessed April, 20, 2010 http://old.ict.nsc.ru/interval/Library/Thematic/GlobOptim/CompleteSearch.pdf
62.Obata, T. (1979) “The Quadratic Assignment Problem: Evaluation of Exact and Heuristic Algorithms,” Technical Reports TRS-7901, Rensselaer Polytechnic Institute, Troy, New York, U.S.A.
63.Oliveira, C.A.S., Pardalos, P.M. and Resende, M.G.C. (2004) “GRASP with Path-Rethinking for the Quadratic Assignment Problem,” Lecture Notes in Computer Science, Vol. 3059, 356-368.
64.Palubeckis, G. (1999) “Generating Hard Test Instances with Known Optimal Solution for the Rectilinear Quadratic Assignment Problem,” Journal of Global Optimization, Vol. 15, 127-156.
65.Palubeckis, G. (2000) “An Algorithm for Construction of Test Cases for the Quadratic Assignment Problem,” Informatica, Vol. 11, No. 3, 281-296
66.Pintea, C.M. and Vescan, A. (2007) “Component-based Ant System for a Biobjective Assignment Problem,” Artificial Intelligence, Vol. LII, 21-32.
67.Pintea, C. M., Pop, P. C., Chira, C. and Dumitrescu, D. (2008), “Hybridization of a Bio-inspired Algorithm for an Over-constrained Assignment Problem,” Computational Intelligence Reports No.6, 1-6.
68.Pintea, C. M., Pop, P. C., Chira, C. and Dumitrescu, D. (2008), “A Hybrid Ant-Based System for Gate Assignment Problem,” Lecture Notes for Artificial Intelligence, Vol. 5271, 273-280.
69.Pinto, D. and Baran, B. (2005) “Solving Multi-objective Multicast Routing Problem with a new Ant Colony Optimization approach,” Accessed July 12, 2010 www.cnc.una.py/cms/invest/download.php?id=274695,108,4.
70.Rossin, D.F., Springer, M.C. and Klein, B.D. (1999) “New Complexity measures for the Facility Layout Problem: An Empirical Study Using Traditional and Neural Network Analysis,” Computers & Industrial Engineering, Vol. 36, 585-602.
71.Rajasekharan, M., Peters, B.A. and Yang, T. (1998) “A Genetic Algorithm for Facility Layout Design in Flexible Manufacturing Systems,” International Journal of Production Research, Vol. 36, 95-110.
72.Satheesh Kumar, R.M., Asokan, P.K., Kumanan, S. and Varma, B. (2008) “Scatter Search Algorithm for Single Row Layout Problem in FMS,” Advances in Production Engineering and Management, Vol. 3, 193-204.
73.Schaub, M. A. and Mermoud, G. (2008) “Ant Colony Optimization for Quadratic Assignment Problem,” Accessed February 2, 2010 2010http://icwww.epfl.ch/~gmermoud/files/publications/PSO_for_QAP_SC741.pdf.
74.Siu, F. and Chang, R.K.C. (2002) “Effectiveness of Optimal Node Assignments in Wavelength Division Multiplexing Networks with Fixed Regular Topologies,” Computer Networks, Vol. 38, 61-74.
75.Solimanpur, M., Vrat, P. and Shankar, R. (2004) “Ant Colony Optimization Algorithm to the Inter-cell Layout Problem in Cellular Manufacturing,” European Journal of Operational Research, Vol. 157, 592-606.
76.Souilah, A. (1995) “Simulated Annealing for Manufacturing Systems Layout Design,” European Journal of Operational Research, Vol. 82, 592-614.
77.Steinberg, L. (1961) “The Backboard Wiring Problem: A Placement Algorithm,” SIAM Review, Vol. 3, 37-50.
78.Stutzle, T. and Dorigo, M. (1999), “ACO Algorithms for the Quadratic Assignment Problem,” Advanced Topics in Computer Science Series, Citeseer, Mcgraw-Hill Ltd. Publishers, 33-50
79.Stutzle, T. and Fernandes, S. (2004) “New Benchmark Instances for the QAP and the Experimental Analysis of Algorithms,” Lecture Notes in Computer Science, Vol. 3004, 199-209.
80.Tate, D.M. and Smith, A.E. (1995) “A Genetic Approach to the QAP,” Computers & Operations Research, Vol. 22, 73-83.
81.Urban, T.L., Chiang, W.C. and Russell, R.A. (2000) “The Integrated Machine Allocation and Layout Problem,” International Journal of Production Research, Vol. 38, 2911-2930.
82.Wang, S.J. and Sarker, B.R. (2002) “Locating Cells with Bottleneck machines in Cellular Manufacturing Systems,” International Journal of Production Research, Vol. 40, 403-424.
83.Wess, B. and Zeitlhofer, T. (2004) “On the Phase Coupling Problem between Data Memory Layout Generation and Address Pointer Assignment,” Lecture Notes in Computer Science, Vol. 3199, 152-166.
84.Wong, K. Y. and See, P. C. (2009), “A New Minimum Pheromone Threshold Strategy (MPTS) for Max-Min Ant System,” Applied Soft Computing, Vol. 9, 882-888.
85.Xu, J. and Bailey, G. (2001) “The Airport Gate Assignment Problem: Mathematical Model and a Tabu Search Algorithm,”Proceedings of the 34th Hawaii International Conference on System Sciences, 1-10.
86.Yan, S. and Huo, C.M. (2001) “Optimization of multiple objective gate assignments,” Transporation Research Part A, Vol. 35, 413-432.
87.Youssef, H., Sait, S.M. and Ali, H. (2003) “Fuzzy Simulated Evolution Algorithm for VLSI cell Placement,” Computers& Industrial Engineering, Vol. 44, 227-247.
88.Yu, V. F., Murty, K. G., Wan, Y. W., Dann, J. and Lee, R. (2009) “Developing a DSS for Allocating Gates to Flights at an International Airport,” International Journal of Decision Support System, Vol.1, 46-68.
89.Zalila, F. (2002) “An Empirical Study of Rollout Algorithms, Beam Search and Multi-Start Memory Programming for the Airport Gate Assignment Problem,” Unpublished Ph.D Dissertation, Bauer College of Business, University of Houston, U.S.A.