A Fuzzy Cluster Based Genetic Algorithm Approach for the Aircraft Landing Scheduling Problem

Abstract

Aircraft Landing Scheduling (ALS) problem is one of the most important part of both aviation and air traffic control. The main objective of the problem is determining the landing time of the aircrafts with minimizing the penalty cost under some constraints. Each aircraft has an optimum target landing time based on their specialties related with fuel, airspeed and cost. Deviations from landing time targets increase the penalty cost of both the aircraft and the problem. In this paper, a fuzzy cluster based genetic algorithm approach is given for the solutions of ALS problems. An ALS benchmark, which contains up to 500 aircrafts and five runways, was obtained from OR–library to execute and evaluate the algorithm. Computational results of the proposed algorithm are given in detail and compared with the best results in the literature. The algorithm results show that it is very competitive and have good results when applied to the regarding problem.

Keywords

• Aircraft Landing,Scheduling,Timetabling,Fuzzy Cluster,Genetic Algorithms,Genetic Algorithms

Uçak İniş Probleminin Çizelgelenmesinde Bulanık Küme Temelli Bir Genetik Algoritma Yaklaşımı

Abstract

Uçak İniş Planlaması (UİP) problemi hem havacılığın hem de hava trafik kontrolünün en önemli bölümlerinden birisidir. Problemin esas amacı, bazı kısıtlar altında ihlal maliyetlerinin minimize edilerek uçakların iniş zamanlarının belirlenmesidir. Problemde, uçakların her biri için yakıt, hava hızı ve maliyet ile ilgili iniş zamanlarına dayalı spefikasyonların olduğu optimum hedefler söz konusudur. İniş zamanı hedefinden sapmalar uçağın ve problemin ihlal maliyetlerinin artmasına neden olmaktadır. Bu çalışmada bulanık küme temelli bir genetik algoritma yaklaşımı UİP problemleri için verilmiştir. 500 uçağın ve 5 pistin bulunduğu bir UİP test problemi önerilen tekniğin kullanılması ve değerlendirilmesi için yöneylem araştırması kütüphanesinden elde edilmiştir. Önerilen algoritma ile elde edilen detaylı sonuçlar literatürde yer alan en iyi sonuçlarla kıyaslanmıştır. Önerilen yöntem uygulandığında elde edilen algoritma sonuçları oldukça rekabetçi ve iyi sonuçlardır.

Keywords

• Uçak İniş,Planlama,Çizelgeleme,Bulanık Küme,Genetik Algoritma,Genetik Algoritma

References

1. ABDULLAH, O. S., ABDULLAH, S., & SARIM, H. M., “Harmony Search Algorithm for the Multiple Runways Aircraft Landing Scheduling Problem”, Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 9(3-7), 2017, 59–65.
2. AWASTHI, A., Kramer, O., & LASSIG, J., “Aircraft landing problem: An efficient algorithm for a given landing sequence”, IEEE 16th International Conference on Computational Science and Engineering (CSE), 2013–December, 20-27.
3. BEASLEY, J. E., Krishnamoorthy, M., Sharaiha, Y. M., & Abramson, D., “Scheduling aircraft landings—the static case”, Transportation Science, 34(2), 2000, 180-197.
4. BEASLEY, J. E., KRISHNAMOORTHY, M., SHARAIHA, Y. M., & ABRAMSON, D., “Displacement problem and dynamically scheduling aircraft landings”, Journal of the Operational Research Society, 55(1), 2004, 54-64.
5. BENCHEIKH, G., BOUKACHOUR, J., ALAOUI, A. E. H., & KHOUKHI, F. E., “Hybrid method for aircraft landing scheduling based on a job shop formulation”, International Journal of Computer Science and Network Security, 9(8), 2009, 78-88.
6. BENCHEIKH, G., BOUKACHOUR, J., & ALAOUI, A. E. H., “Improved ant colony algorithm to solve the aircraft landing problem”, International Journal of Computer Theory and Engineering, 3(2), 2011, 224-233.
7. BENCHEIKH, G., EL KHOUKHI, F., BACCOUCHE, M., BOUDEBOUS, D., BELKADI, A., & OUAHMAN, A. A., “Hybrid Algorithms for the Multiple Runway Aircraft Landing Problem”, International Journal of Computer Science and Applications, 10(2), 2013, 53-71.
8. BENCHEIKH, G., BOUKACHOUR, J., & ALAOUI, A. E. H., “A memetic algorithm to solve the dynamic multiple runway aircraft landing problem”, Journal of King Saud University-Computer and Information Sciences, 28(1), 2016, 98-109.

9. DHOUIB, S., “A multi Start adaptive Variable Neighborhood Search metaheuristic for the aircraft landing problem”, 4th International Conference on Logistics (LOGISTIQUA), 2011–May, 197-200.
10. FAYE, A., “Solving the aircraft landing problem with time discretization approach”, European Journal of Operational Research, 242(3), 2015, 1028-1038.
11. GHONIEM, A., & FARHADI, F., “A column generation approach for aircraft sequencing problems: a computational study”, Journal of the Operational Research Society, 66(10), 2015, 1717-1729.
12. GIRISH, B. S., An efficient hybrid particle swarm optimization algorithm in a rolling horizon framework for the aircraft landing problem, Applied Soft Computing, 44, 2016, 200-221.
13. HOLLAND, J. H., Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, Ann Arbor, University of Michigan Press, 1975.
14. JI, X. P., CAO, X. B., & TANG, K., “Sequence searching and evaluation: a unified approach for aircraft arrival sequencing and scheduling problems”, Memetic Computing, 8(2), 2016, 109-123.
15. MAHMOUDIAN, M., AMINNAYERI, M., & MIRZADEH, A., “Aircraft Landing Scheduling Based On Unavailability Of Runway Constraint Through A Time Segment Heuristic Method”, International Journal of Informatics and Communication Technology (IJ-ICT), 2(3), 2013, 175-182.
16. NG, K. K. H., & LEE, C. K. M., “A modified Variable Neighborhood Search for aircraft Landing Problem”, IEEE International Conference on Management of Innovation and Technology (ICMIT), 2016–September, 127-132.
17. OR–Library, http://people.brunel.ac.uk/~mastjjb/jeb/orlib/air landinfo.html, Accessed 01.02.2017.
18. PINOL, H., & BEASLEY, J. E., “Scatter search and bionomic algorithms for the aircraft landing problem”, European Journal of Operational Research, 171(2), 2006, 439-462.
19. SABAR, N. R., & KENDALL, G., “Aircraft landing problem using hybrid differential evolution and simple descent algorithm”, IEEE Congress on Evolutionary Computation (CEC), 2014–July, 520-527.
20. SABAR, N. R., & KENDALL, G., “An iterated local search with multiple perturbation operators and time varying perturbation strength for the aircraft landing problem”, Omega, 56, 2015, 88-98.
21. SALEHIPOUR, A., MODARRES, M., & NAENI, L. M., “An efficient hybrid meta-heuristic for aircraft landing problem”, Computers & Operations Research, 40(1), 2013, 207-213.
22. TANG, K., WANG, Z., CAO, X., & ZHANG, J., “A multi-objective evolutionary approach to aircraft landing scheduling problems”, IEEE World Congress on Computational Intelligence in Evolutionary Computation, CEC 2008, 2008–June, 3650-3656.
23. YU, S. P., CAO, X. B., & ZHANG, J., “A real-time schedule method for Aircraft Landing Scheduling problem based on Cellular Automation”, Applied Soft Computing, 11(4), 2011, 3485-3493.
24. ZADEH, L. A., Fuzzy sets, Information and Control, 8, 1965, 338-353.