A column generation algorithm for robust gate assignment problems

Abstract

Bu çalışmada, homojen ve heterojen kapılı durumlar için Dayanıklı Kapı AtamaProblemi incelenmiştir. Havaalanlarında artan trafik tıkanıklığı nedeniyle, havayolusektöründe operasyonel sorunlara bilimsel yaklaşımlar önem kazanmıştır. Buortamda operasyonel planlama hayati bir öneme sahiptir. Havaalanı yönetimi içinen önemli problem türlerinden biri de kapı atama problemidir. Bu çalışmada sütuntüretme yöntemi, küme kapsama probleminin bir doğrusal programlama rahatlatması olarak formüle edilmiştir. Sütun türetme yaklaşımı için fiyatlandırma alt problemibir ağ yapısı ile temsil edilip en kısa yol yöntemi kullanılarak çözülmüştür.Dayanıklılık ölçütü olarak atıl zaman varyansı kullanıldığında hem homojen hemde heterojen örnekleri için en iyi çözümler bulunmuştur. Dorndorf [1] tarafındanönerilen ekleme kabiliyeti dayanıklılık ölçütü incelenmiş ve atıl zaman varyansı ilekarşılaştırılmıştır. Bolat [2] veri kümeleri üzerinden yapılan sayısal çalışmalar bu ikidayanıklılık ölçütü arasında negatif bağlantı olduğunu göstermektedir.

This study adresses the Robust Gate Assignment Problem (RGAP) for the caseof both homogeneous and heterogeneous gates. Due to the increased trac andcongestion at airports, scientic approaches to operational problems have gainedimportance in the airline industry. Operations planning has a vital importance inthis environment. One of the most important problem types for the airport managementis the well known gate assignment problem (GAP). In this study, a columngeneration (CG) algorithm is proposed to solve GAP and the algorithm is formulatedas a linear programming relaxation of the set covering problem. The pricingsubproblem (PSP) for the CG approach is represented with a network structure andsolved using the shortest path algorithm. Results show that for both homogeneousand heterogeneous instances, the proposed CG algorithm provides optimal LP solutionsaccording to the idle time of variance robustness measure. Insert capabilitysuggested by Dorndorf [1] is also investigated as a robustness measure and comparedto variance of idle time. A computational study performed on data sets fromBolat [2] indicate that the two robustness measures are negatively correlated.