Aircraft parking optimization using genetic algorithm

Havacılığın büyümesi bir çok yeni probleme neden oldu. Bu problemlerden bir tanesi de GAP (Kapı Atama Problemi [Gate Assignment Problem]) dir. Uçak sayısındaki artı¸sın sebep oldu˘gu yoğunluk havalimanlarının verimli şekilde kullanılmasını zorunlu kılmaktadır. Uçakların park pozisyonları operasyonel maliyetleri etkilediği gibi transit yolcuların ve yolculara ait bagajların bir sonraki uçağa yetişebilmesini de etkilemektedir. GAP in amacı uçakları en uygun şekilde park ettirerek havalimanının verimli kullanılmasını sağlamaktır. Literatürde, ilk olarak toplam yürüme mesafesi hedef fonksiyon olarak, ardından toplam yürüme mesafesi ve bagajların bir sonraki uçuşa olan uzaklıkları hedef fonksiyon olarak kullanıldı. GAP, Babic ve diğerleri [2] tarafından 1980'lerde tam-sayılı program kullanılarak araştırılmaya başlandı ve bu konuda yapılan araştırmalar sürdü. İlerleyen yıllarda, deterministik model yerine istatistiksel modeller tercih edildi. Çeşitli simulasyon modelleri Yu Cheng tarafından problemin çözümü olarak önerildi [3]. Bolat [4] ise hedef fonksiyonunu transit yolcu ya da bagaj uzaklığı almayıp operasyonel maliyetleri hedef fonksiyonu seçmiştir. İlk defa 1998'de GA (Genetik Algoritma [Genetic Algorithm]) , GAP için kullanıldı [5]. Bu karma¸sık problemin hesaplanması GA ile kısaltılmıştır. 2001 yılında çoklu hedef fonksiyonu önerildi [6]. Bağlantı (Linkage) ve düzenli dağılım metodu GAP için Paolo [7] tarafından kullanıldı. Bu tezde, GAP, GA yöntemi kullanılarak çözüldü. Toplam transit yolcu yürüme mesafesi hedef fonksiyon olarak seçildi. Bu metod havacılık maliyetlerini dü¸sürmeyi ve mü¸steri memnuniyetini yükseltmeyi hedeflemektedir. Bu da gecikmeleri ve geciken uçak sayısını azaltmaktadır. GA uygulaması herhangi bir hazır program kullanmadan GAP için, web arayüzü kullanılarak "http://genetik1.netf13.com/home" üzerinde geliştirildi. Bu tezde özellikle aktarma merkezi olan havalimanları için operasyon maliyetlerini minimize edecek ¸sekilde uçak yerleştirme optimizasyonu yapıldı. GAP'in uçak yerleştirme süreci yeterince dikkatli takip edilmezse havalimanlarının programları etkilenebilmektedir. Benzer çalışmalar daha önce yapılmış olsa da bu çalışma uygulama web arayüzü ile etkile¸simli bir programdır. Bu çalışmada, GA'nın doğadan ilham aldığı vurgulanmaktadır. Bu tarz programlar doğanın doğal seçim kurallarından etkilenerek çalı¸sırlar. Genetik algoritma evrimsel bir algoritma olup uygun parametreler ile çalışmaktadır. Bu parametreler GAP'e uygun ve problemin veri hacmine göre seçilmiştir. Geliştirilmiş Permütasyon kodlama bu çalı¸sma için uygundur çünkü normal permütasyon kodlama boş değerlerin gösteriminde yetersiz kalmaktadır. OX (Düzenli parça değişimi [Ordered Crossing over]) ve PMX (kısmi eşleştirmeli parça değişimi PMX [Partially Mapped Crossing-over]) permütasyon kodlama için uygundur fakat OX tekniği boş değerler içeren permütasyon kodlama için daha iyidir. Bu çalışmada PHP programı algoritma için, HTML ise GUI (kullanıcı arayüzü [Graphic User Interface]) için ve MySQL4 ise veritabanı için kullanılmıştır. Bu programda GUI olduğundan kullanıcılar web sitesini ekileşimli şekilde kullanabilir. Kullacı istediği parametreleri kullanarak, en iyi 5 çözüme ulaşabilir, bu çözümleri analiz edebilir ve inceleyebilir. Tablo, '0data_set_gate' bir kare matris olup kapılar arasındaki uzaklı˘gı göstermektedir. 'data_set_plane' matrisi kare matris olup uçaklar arasındaki transit yolcu sayısını göstermektedir. Buna ek olarak "açık" tablo programın kolay kullanılması ve parametrelerin hafızada tutulması ve küme olarak kullanılabilmesi içindir. Son olarak, parametreler ve sonuçlar "stat" tablosunda tutulmaktadır. Program arka planda veritabanı ile haberleşmekte, algoritmayı çalıştırmaya başlamadan parametreleri kontrol etmekte ve son olarak PHP ile çalıştırılmaktadır. PHP kodları Burak Durukan tarafından, algoritma tasarımı ise Burak Güler tarafından yapılmıştır. Program testlerinde, en son adım metodu sonuç bulmak için kullanıldı˘gında sonuçlar büyük bir rassallık göstermektedir. Algoritma çok net sonuçlar vermemektedir. Algoritma'nın yapay zeka gibi çalı¸sıyor olması için durgun adım (stagnant step) parametresi kullamalıdır. Durgun adım parametresi kullanıldığında algoritma, çok büyük adımlara gelmeden de sonuç bulabilmektedir. Durgun adımlar parametresi ile en iyi sonuçları erken adımlarda bulabiliyoruz. Bu çalışma durgun adım parametresinin, final adım sayısının 1/5 ile 1/9 arasında olduğunu gösterdi. Diğer sonuç süresini etkileyen, kullanılabilir parametre ise mutasyon oranıdır. En iyi mutasyon oranı ise 0,06 ile 0,11 arasındadır. Daha yüksek mutasyon oranı sonuca olumsuz yansır ve çözüm süresini uzatır. Sonucun iyileşmesini sağlayan bir diğer parametre ise elitizmdir. Sonuç olarak benzer çalışmalar yapılmış olsa da bu çalışma halka açık ve web sitesi üzerinde yürütülebilmektedir. Bu program kolayca geliştirilebilirdir çünkü bir sınıfta yapılan değişik sadece ilgili kısmı etkilemekte, programın geri kalanını etkilememektedir.