Uçak çizelgeleme probleminin karınca kolonileri optimizasyonu ile çözümü

Özet

Havalimanına iniş yapmak üzere havada bulunan uçaklar için iniş sıra ve zamanlarının belirlenmesi özellikle trafiğin yoğun olduğu zaman periyotlarında önemli bir problemdir. Uçak çizelgeleme problemi olarak adlandırılan bu problem temel olarak iş çizelgeleme problemlerine benzemektedir. İşlem zamanları sıralamaya bağımlı olarak değişebilmektedir. Hedef zamanlarında yapılmayan işler için ek maliyet oluşmaktadır. Her uçak için önceden belirlenmiş olan ve iniş yapabileceği zaman aralığım belirleyen alt ve üst sınırlar vardır. Genelde, çizelgeleme sonucunda amaçlanan durum ise uçakların bir veya daha fazla pist için optimum iniş sıralama ve zamanlarının belirlenirken minimum takip mesafelerinin de korunmasıdır. Karınca Kolonileri Optimizasyonu (KKO) metasezgiseli kullanılarak genel amaçlı bir karar verme algoritması geliştirilmiştir. Geliştirilen algoritma tek veya çok pist kullanımında iniş ve kalkışların çizelgelenebilmesi için kullanılabilecektir. Test problemlerinin çözümü sonucunda elde edilen sonuçlar geçmiş çalışmalar ile karşılaştmlmıştır. Ayrıca KKO yönteminin çizelge problemleri için kullanılabilmesi için değişiklik ve yenilikler önerilmiştir.

Abstract

Scheduling aircraft landings is a major problem in air traffic control area of congested airports. It is a special type of machine scheduling problem; processing times are sequence dependent, and there are penalties for jobs that are not completed on target time. Each plane has an allowable predetermined time window for landing. The objective is to optimally land a set of planes on one or several runways in such a way that separation criteria between all pairs of planes are satisfied. If efficient algorithms can be developed to assist the controller who is in charge of making scheduling decisions, then more effective use affixed runway capacity will result. We tried to solve the problem using Ant System metaheuristic, which is gained more popularity in recent years. Using Ant System metaheuristic, we present a generic decision making tool that can be used both for the single runway and the multiple runway landings and takeoffs. Computational results are presented for the standard test problems obtained from literature. Results are compared with the previous works and show that Ant System solutions can be effective in practice.