OPTIMIZATION OF ARRIVAL SEQUENCING AT SINGLE RUNWAY AIRPORTS USING ARTIFICIAL IMMUNE METAHEURISTIC

YAPAY BAĞIŞIKLIK METASEZGİSELİ İLE TEK PİSTLİ HAVAALANLARINDA İNİŞSIRALAMASININ ENİYİLENMESİ

Abstract

The aircraft arrival sequencing problem is to make sequencing with the required safeseparations for a given set of aircraft with estimated operation times under certainconstraints. In this study, the problem of sequencing aircrafts planning to land on a singlerunway is discussed. Aircraft are allowed to perform pre-defined number of constrainedposition shifting (CPS) in their landing sequence determined by first come first served(FCFS) principle. The objective function is to minimize the completion time of operations(makespan). The Clonal Selection Algorithm (KSA), one of the Artificial Immune System(AIS) algorithms, was used to solve the problem. Artificial immune system is a techniqueused in many areas such as anomaly detection, computer and network security,scheduling, optimization, classification, data mining and is inspired by natural immunesystem. The algorithm has been tested for scenarios with different numbers andcategories of aircraft. The solutions obtained with the algorithm and obtained with a mathematical model solver (GAMS/CPLEX) are compared and solution times are shared.

Özet

İniş uçaklarının sıralanması problemi, tahmini operasyon zamanlarının bulunduğu bir uçak kümesi için belirli kısıtlar altında gerekli emniyet ayırmalarının sağlanarak sıralamanın yapılmasıdır. Bu çalışmada tek piste iniş yapmayı planlayan uçakların sıralanması problemi ele alınmıştır. Uçakların ilk gelen ilk hizmet alır (FCFS) prensibi ile belirlenen sıralamalarına göre sınırlı sayıda yer değiştirmelerine (CPS) izin verilmiştir. Amaç fonksiyonu olarak operasyonların tamamlanma zamanının enküçüklenmesi alınmıştır. Problemin çözümü için Yapay Bağışıklık Sistemi (YBS) algoritmalarından olan Klonal Seçim Algoritması (KSA) kullanılmıştır. YBS anormallik tespiti, bilgisayar ve ağ güvenliği, çizelgeleme, eniyileme, sınıflandırma, veri madenciliği gibi birçok alanda kullanılan ve doğal bağışıklık sisteminden esinlenerek oluşturulan bir tekniktir. Farklı sayıda ve kategoride uçaklardan oluşan senaryolar için algoritma test edilmiştir. Algoritma ile elde edilen çözümler ve bir matematiksel model çözücüsü (GAMS/CPLEX) ile elde edilen çözümler kıyaslanmıştır ve çözüm süreleri de paylaşılmıştır.