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

Year 2018, Volume: 5 Issue: 1, 127 - 148, 25.05.2018

Yakup Çelikbilek

https://doi.org/10.17336/igusbd.367106

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

• 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.
• 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.
• BEASLEY, J. E., Krishnamoorthy, M., Sharaiha, Y. M., & Abramson, D., “Scheduling aircraft landings—the static case”, Transportation Science, 34(2), 2000, 180-197.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• FAYE, A., “Solving the aircraft landing problem with time discretization approach”, European Journal of Operational Research, 242(3), 2015, 1028-1038.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• OR–Library, http://people.brunel.ac.uk/~mastjjb/jeb/orlib/air landinfo.html, Accessed 01.02.2017.
• 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.
• 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.
• 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.
• SALEHIPOUR, A., MODARRES, M., & NAENI, L. M., “An efficient hybrid meta-heuristic for aircraft landing problem”, Computers & Operations Research, 40(1), 2013, 207-213.
• 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.
• 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.
• ZADEH, L. A., Fuzzy sets, Information and Control, 8, 1965, 338-353.