The Library
A ripplespreading genetic algorithm for the aircraft sequencing problem
Tools
Hu, XiaoBing and Di Paolo, Ezequiel A.. (2011) A ripplespreading genetic algorithm for the aircraft sequencing problem. Evolutionary Computation, Vol.19 (No.1). pp. 77106. ISSN 10636560

PDF
WRAP_hu_evco_a_00011.pdf  Published Version  Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (1646Kb) 
Official URL: http://dx.doi.org/10.1162/EVCO_a_00011
Abstract
When genetic algorithms (GAs) are applied to combinatorial problems, permutation representations are usually adopted. Asa result, suchGAsare often confronted with feasibility and memoryefficiency problems. With the aircraft sequencing problem (ASP) as a study case, this paper reports on a novel binaryrepresentationbased GA scheme for combinatorial problems. Unlike existing GAs for the ASP, which typically use permutation representations based on aircraft landing order, the new GA introduces a novel ripplespreading model which transforms the original landingorderbased ASP solutions into valuebased ones. In the new scheme, arriving aircraft are projected as points into an artificial space. A deterministic method inspired by the natural phenomenon of ripplespreading on liquid surfaces is developed, which uses a few parameters as input to connect points on this space to form a landing sequence. A traditional GA, free of feasibility and memoryefficiency problems, can then be used to evolve the ripplespreading related parameters in order to find an optimal sequence. Since the ripplespreadingmodel is the centerpiece of the new algorithm, it is called the ripplespreading GA (RSGA). The advantages of the proposed RSGA are illustrated by extensive comparative studies for the case of the ASP.
[error in script] [error in script]Item Type:  Journal Article 

Subjects:  Q Science > QA Mathematics 
Divisions:  Faculty of Science > Engineering 
Library of Congress Subject Headings (LCSH):  Genetic algorithms, Combinatorial enumeration problems 
Journal or Publication Title:  Evolutionary Computation 
Publisher:  M I T Press 
ISSN:  10636560 
Date:  2011 
Volume:  Vol.19 
Number:  No.1 
Page Range:  pp. 77106 
Identification Number:  10.1162/EVCO_a_00011 
Status:  Peer Reviewed 
Publication Status:  Published 
Funder:  Engineering and Physical Sciences Research Council (EPSRC) 
Grant number:  EP/C51632X/1 (EPSRC) 
References:  Andreatta, G., and RomaninJacur, G. (1987). Aircraft flow management under congestion. Transportation Science, 21(4):249–253. B¨ack, T., Hammel, U., and Schwefel, H.P. (1997). Evolutionary computation: Comments on the history and current state. IEEE Transactions on Evolutionary Computation, 1(1):3–17. Beasley, J. E., Sonander, J., and Havelock, P. (2001). Scheduling aircraft landings at London Heathrow using a population heuristic. Journal of the Operational Research Society, 52(4):483– 493. Bianco, L., Dell’Olmo, P., andOdoni,A. R. (1997). Modelling and simulation in air traffic management. Berlin: Springer Verlag. Bianco, L., and Odoni, A. R. (1993). Large scale computation and information processing in air traffic control. Berlin: Springer Verlag. Bianco, L., Ricciardelli, S., Rinaldi, G., and Sassano, A. (1988). Scheduling task with sequencedependent processing times. Naval Research Logistics, 35(2):177–184. Carr, G. C., Erzberger, H., and Neuman, F. (1999). Delay exchanges in arrival sequencing and scheduling. Journal of Aircraft, 36(5):785–791. Carr, G. C., Neuman, F., and Erzberger, H. (2000). Fasttime study of aircraftinfluenced arrival sequencing and scheduling. Journal of Guidance, Control and Dynamics, 23(3):526–531. Cheng, V. H. L., Crawford, L. S., and Menon, P. K. (1999). Air traffic control using genetic search techniques. In Proceedings of the IEEE International Conference on Control Applications, pp. 643–649. Ciesielski, V., and Scerri, P. (1998). Realtime genetic scheduling of aircraft landing times. In The 1998 IEEE Congress on Evolutionary Computation, pp. 360–364. Dear, R. G. (1976). The dynamic scheduling of aircraft in the near terminal area. Cambridge,MA: MIT Press. Eiben, A. E., and Schoenauer, M. (2002). Evolutionary computing. Information Processing Letters, 82(1):1–6. Eiben, A. E., and Smith, J. E. (2003). Introduction to evolutionary computing. Berlin: Springer Verlag. Hansen, J. V. (2004). Genetic search methods for air traffic control. Computers and Operations Research, 31(3):445–459. Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor, MI: University of Michigan Press. Hu, X., Di Paolo, E., and Barnett, L. (2008). Ripplespreading model and genetic algorithm for random complex networks: Preliminary study. In The 2008 IEEE Congress on Evolutionary Computation (in the 2008 IEEE World Congress on Computational Intelligence), pp. 3642–3649. IEEE Press. Hu, X. B., and Chen,W. H. (2005). Genetic algorithm based on receding horizon control for arrival sequencing and scheduling. Engineering Applications of Artificial Intelligence, 18(5):633–642. Hu, X. B., andDi Paolo, E. (2007). Ahybrid genetic algorithm for the travelling salesman problem. In Nature Inspired Cooperative Strategies for Optimization (NICSO 2007), pp. 357–367. Berlin: Springer. Hu, X. B., and Di Paolo, E. (2008). Binary representation based genetic algorithm for aircraft arrival sequencing and scheduling. IEEE Transactions on Intelligent Transportation Systems, 9(2):301–310. Hu, X. B., and Di Paolo, E. (2009a). An efficient genetic algorithm with uniform crossover for air traffic control. Computers and Operations Research, 36(1):245–259. Hu, X. B., and Di Paolo, E. (2009b). A ripplespreading genetic algorithm for airport gate assignment problem. In The 2009 IEEE Congress on Evolutionary Computation, pp. 1857–1864. Hu, X. B., Di Paolo, E., and Wu, S. F. (2008). A comprehensive fuzzyrulebased selfadaptive genetic algorithm. International Journal of Intelligent Computing and Cybernetics, 1(1):94–109. Hu, X. B., Leeson, M. S., and Hines, E. L. (2010). A ripplespreading genetic algorithm for the network coding problem. In The 2010 IEEE World Congress on Computer Intelligence. Hu, X. B., Wang, M., Leeson, M. S., Hines, E. L., and Di Paolo, E. (2010). A review on ripplespreading genetic algorithms for combinatorial optimization problems. In The 9th IEEE International Conference on Cognitive Informatics, pp. 441–448. Pelegrin, M. (1994). Towards global optimization for air traffic management. AGARDAG321. Psaraftis, H. N. (1978). A dynamic programming approach to the aircraft sequencing problem. Cambridge, MA: MIT Press. Psaraftis, H. N. (1980). A dynamic programming approach for sequencing identical groups of jobs. Operations Research, 28(6):1347–1359. Robinson, J. E., III, Davis, T. J., and Isaacson, D. R. (1997). Fuzzy reasoningbased sequencing of arrival aircraft in the terminal area. In AIAA Guidance, Navigation and Control Conference. Sywerda, G. (1989). Uniform crossover in genetic algorithms. In Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 2–9. Morgan Kaufmann. Venkatakrishnan, C. S., Barnett, A., and Odoni, A. R. (1993). Landings at Logan Airport: Describing and increasing airport capacity. Transportation Science, 27(3):211–227. Zhang, J., Chung, H. S. H., and Lo, W. L. (2007). Clusteringbased adaptive crossover and mutation probabilities for genetic algorithms. IEEE Transactions on Evolutionary Computation, 11(3):326–335. 
URI:  http://wrap.warwick.ac.uk/id/eprint/38615 
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
View Item 