Stochastic airport gate assignment problem

Abstract

Uçuşların kalkış ve varış trafiğine özgü belirsizlikler uçuşların planlanan kapılara atanması gerektiğinde kapıların atamaya müsait olmamasına yol açabilmektedir. Teknik arızalar, uygunsuz hava koşulları, havaalanındaki trafik yoğunluğu girdi verisindeki belirsizliklerin tipik sebeplerinden bazılarıdır. Bu rassal aksaklıklar verimli uçuş-kapı atama planları oluşturulmasında büyük öneme sahiptir. Havaalanı kapı atama problemi uçuşların kalkış ve varış zamanlarındaki belirsizlikler gözönüne alınarak incelenmiştir ve bu belirsiz parametrelere dair rassallık bir senaryo kümesi ile ifade edilmiştir. Olası rassal aksaklıklara karşı dayanıklı bir atama elde etmek amacıyla senaryo tabanlı bir yaklaşım kullanılarak alternatif dayanıklılık ölçütlerini içeren yeni rassal programlama modelleri geliştirilmiştir. Özellikle odaklanılan dayanıklılık ölçütleri çakışan uçuş sayısı, tampon ve boş zamanlardır. Boş zamanların kapılar arası düzgün dağılımını sağlayıp olası çakışmaların önüne geçebilmek amacıyla atıl zamanların varyansının ya da atıl zamanların belirli bir tampon değerden toplam sapmalarının beklenen değerinin enküçüklenmesi önerilen modellerde hedeflenen amaçlara örnek olarak verilebilir. Önerilen rassal programlama modelleri çözümü zor olan büyük ölçekli karışık tamsayılı programlama olarak yazılmıştır. Daha kısa hesaplama süresi içerisinde olurlu ve iyi sonuçlar elde edebilmek amacıyla tabu arama sezgisel yöntemleri geliştirilmiştir. Önerilen alternatif formülasyonları analiz etmek ve önerilen çözüm yöntemlerinin hesaplama etkinliğini göstermek amacıyla kapsamlı bir sayısal çalışma yapılmıştır.

The uncertainties inherent in the airport flight arrival and departure traffic may lead to the unavailability of gates when needed to accommodate scheduled flights. Mechanical failures, severe weather conditions, heavy traffic volume at the airport are some typical causes of the uncertainties in the input data. Incorporating such random disruptions is crucial in constructing effective flight-gate assignment plans. We consider the flight-gate assignment problem in the presence of uncertainty in arrival and departure times of the flights and represent the randomness associated with these uncertain parameters by a finite set of scenarios. Using the scenario-based approach, we develop new stochastic programming models incorporating alternate robustness measures to obtain assignments that would perform well under potential random disruptions. In particular, we focus on the number of conflicting flights, the buffer and idle times as robustness measures. Minimizing the expected variance of idle times or the expected semi-deviation of idle times from a buffer time value are some examples of the objectives that we incorporate in our models to appropriately distribute the idle times among gates, and by this way, to decrease the number of potential flight conflicts. The proposed stochastic optimization models are formulated as computationally expensive large-scale mixed-integer programming problems, which are hard to solve. In order to find good feasible solutions in reasonably short CPU times, we employ tabu search algorithms. We conduct an extensive computational study to analyze the proposed alternate formulations and show the computational effectiveness of the proposed solution methods.