A real-time schedule method for aircraft landing scheduling problem based on cellular automaton

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A real-time schedule method for aircraft landing scheduling problem based on cellular automaton

Full text

Pdf (1.57 MB)

Source

ACM/SIGEVO Summit on Genetic and Evolutionary Computation archive
Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation table of contents

Shanghai, China

SESSION: Full papers table of contents

Pages 717-724

Year of Publication: 2009

ISBN:978-1-60558-326-6

Authors

Shengpeng Yu	Department of Computer Science and Technology, University of Science and Technology of China, Hefei, China
Xianbin Cao	Department of Computer Science and Technology, University of Science and Technology of China, Hefei, China
Maobin Hu	School of Engineering Science, University of Science and Technology of China, Hefei, China
Wenbo Du	Department of Computer Science and Technology, University of Science and Technology of China, Hefei, China
Jun Zhang	School of Electronic and Information Engineering, Beihang University, Beijing, China

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 43, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1543834.1543932 What is a DOI?

ABSTRACT

The Aircraft Landing Scheduling (ALS) problem is a typical hard multi-constraint optimization problem. In real applications, it is not most important to find the best solution but to provide a feasible landing schedule in an acceptable time. We propose a novel approach which can effectively solve the ALS while satisfying the real-time need. It consists of two steps: (i) Use CA to simulate the landing process in the terminal airspace and to find a considerably good landing sequence; (ii) a simple Genetic Algorithm associated with a Relaxation Operator is used to obtain a better result based on the CA result. Experiments have shown that our method is much faster and suitable for real-time ALS problem compared with traditional optimization methods. For all the 13 data sets, the proposed approach can find satisfactory solutions in less than 2 seconds.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	J. E. Beasley , M. Krishnamoorthy , Y. M. Sharaiha , D. Abramson, Scheduling Aircraft Landings--The Static Case, Transportation Science, v.34 n.2, p.180-197, May 2000 [doi>10.1287/trsc.34.2.180.12302]
	2	Balakrishnan, H. and Chandran, B. 2006. Scheduling aircraft landings under constrained position shifting. In Proceedings of the AIAA Guidance, Navigation and Control Conference, Keystone, Colorado, (Aug).
	3	Randall, M. 2002. Scheduling Aircraft Landings with Ant Colony Optimisation. In Proceedings of the International Conference Artificial Intelligence and Soft Computing, pp. 129--133.
	4	Ciesielski, V. and Scerri,P. 1998. Real time genetic scheduling of aircraft landing times. Proceedings of the 1998 IEEE International Conference on Evolutionary Computation (ICEC98), IEEE, New York USA (1998), 360--364.
	5	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, 5 (May 2001), 483--493.
	6	Pinol, H. and Beasley, J.E. 2006. Scatter Search and Bionomic Algorithms for the aircraft landing problem. European Journal of Operational Research 171 (2006) 439--462
	7	Xiao-Bing Hu and Wen-Hua Chen. 2005. Genetic algorithm based on receding horizon control for arrival sequencing and scheduling. Engineering Applications of Artificial Intelligence, 18 (2005), 633--642.
	8	Guo Y P, Cao X B, Zhang J. 2008 Multi objective evolutionary algorithm with constraint handling for aircraft landing scheduling. Proceedings of IEEE World Congress on Evolutionary Computation, (2008), 3657--3662.
	9	Tang K, Wang Z, Cao X B, Zhang J. 2008 A multi-objective evolutionary approach to aircraft landing scheduling problems. Proceedings of IEEE World Congress on Evolutionary Computation, (2008), 3650--3656.
	10	Palash Sarkar, A brief history of cellular automata, ACM Computing Surveys (CSUR), v.32 n.1, p.80-107, March 2000 [doi>10.1145/349194.349202]
	11	Beasley, J. E., Krishnamoorthy, M. Sharaiha, Y. M. and Abramson, D. 2004. Displacement problem and dynamically scheduling aircraft landings. Journal of the Operational Research Society (2004) 55, 54--64
	12	Andreas T. Ernst, Mohan Krishnamoorthy and Robert, H. Storer. 1999. Heuristic and Exact Algorithms for Scheduling Aircraft Landings. Networks. 34, 2(Sep 1999), 229--241.
	13	Irene Moser and Tim Hendtlass. 2007. Solving Dynamic Single-Runway Aircraft Landing Problems With Extremal Optimisation. Proceedings of the 2007 IEEE Symposium on Computational Intelligence in Scheduling (CI-Sched 2007)
	14	Xiaobai Li, Qingsong Wu, and Rui Jiang. 2001. Cellular automaton model considering the velocity effect of a car on the successive car. PHYSICAL REVIEW E, VOLUME 64, 066128.
	15	Kai Nagel and Michael Schreckenberg. 1992. Cellular automaton model for freeway traffic. J. Phys. I France 2 (1992), 2221--2229.
	16	Jia B, Jiang R, Wu QS and Hu MB. 2005. Honk effect in the two-lane cellular automaton model for traffic flow. Physica A 348 (2005), 544--552.