The Library

A ripple-spreading genetic algorithm for the aircraft sequencing problem

Tools

Hu, Xiao-Bing and Di Paolo, Ezequiel A.. (2011) A ripple-spreading genetic algorithm for the aircraft sequencing problem. Evolutionary Computation, Vol.19 (No.1). pp. 77-106. ISSN 1063-6560

Preview

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 memory-efficiency problems. With the aircraft sequencing problem (ASP) as a study case, this paper reports on a novel binary-representation-based 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 ripple-spreading model which transforms the original landing-order-based ASP solutions into value-based ones. In the new scheme, arriving aircraft are projected as points into an artificial space. A deterministic method inspired by the natural phenomenon of ripple-spreading 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 memory-efficiency problems, can then be used to evolve the ripple-spreading related parameters in order to find an optimal sequence. Since the ripple-spreadingmodel is the centerpiece of the new algorithm, it is called the ripple-spreading GA (RSGA). The advantages of the proposed RSGA are illustrated by extensive comparative studies for the case of the ASP.

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:	1063-6560
Date:	2011
Volume:	Vol.19
Number:	No.1
Page Range:	pp. 77-106
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 Romanin-Jacur, 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). Fast-time study of aircraft-influenced 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). Ripple-spreading 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 ripple-spreading 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 fuzzy-rule-based self-adaptive 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 ripple-spreading 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. AGARD-AG-321. 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 reasoning-based 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). Clustering-based 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