Lagrangian relaxation for airport gate assignment problem

Bu çalışmada aprona atanan uçak sayısının en az sayıda tutulmasını sağlayarak yolcuların toplam yürüme mesafesini en küçükleyen havaalanı kapı atama problemi ele alınmaktadır. Literatürde kullanılan formülasyonlara alternatif bir formülasyon kullanılmakta ve sıkı alt sınırlar elde edebilmek için Lagrange gevşetmesine dayalı yöntemler önerilmektedir. Yöntem, aynı zamanda iyi başlangıç üst sınırlarının gücünden faydalanarak iyi kalitede çözümler vermektedir. Bildiğimiz kadarıyla literatürdeki çalışmaların çoğu, sezgisel sonuçlarını performans bazlı üst sınır karşılaştırması ya da doğrusal programlama gevşetmesinden elde edilen alt sınırlardan faydalanarak ölçmektedir. Deneysel sonuçlar, kullanılan Lagrange gevşetmesine dayalı yöntemlerin sıkı alt sınırlar ve iyi kalitede üst sınırlar verdiğini göstermektedir. Elde edilen değerler literatürde var olan sezgisel sonuçların performansını ölçmede kullanılabilir.