Column generation approaches to a robust airline crew pairing model for managing extra flights

Abstract

Klasik ekip eşleme probleminde amaç uçuş çizelgesinde yer alan uçuşlar kapsayan,belirli kısıtlar altında en az maliyetli olan ekip eşlemelerinin bulunmasıdır. Son yıllardahava yolu şirketleri planlanan çizelgelerini uygulamakta zorlanmaktadırlar. Ç izelgedensapılmasının nedenlerinden biri çizelgeye eklenen ek uçuşlardır. Çizelgeye yeni eklenenuçuşun kapsanması operasyonel seviyede gerçekleşir. Dayanıklı ekip eşleme problemimiziçizelgemizde gerçekleşebilecek olan bu ek uçuşları göz önünde bulunduraraktanımladık. Planlama aşamasında bilinen bu ek uçuşları olabildiğince uçuş rotalarınıçıkarırken ele almaya çalıştık. Bu sayede ek uçuşlar gerçekleştirildikleri zaman, dahaönceden çıkardığımız rotaları en az maliyetle kullanabilmeyi amaçladık. Önerdiğimizdayanıklı ekip eşleme problemi modelinde yeni eklenen kolonlar (eşlemeler) satır vesütun olarak problemin büyümesine neden olabilmektedir. Biz problemdeki satır vesütun büyümelerini de dikkate alarak klasik ekip eşlemesinde de sık kullanılan birmetod olan kolon türetme metodu ile iki tane çözüm yöntemi önerdik. Bu çözümyöntemlerinde amacımız ya kolon türetme metoduna başlamadan önce ya da kolontüretme metodunu bitirdikten sonra dinamik büyümeye neden olan kısıtları eklemektir.Etkili kolon türetme metodu için kolon havuzları da tanıttık. Önerdiğimiz yöntemleriyerel bir firmanın datalarında denedik.

A typical airline crew pairing problem aims at selecting a set of flight sequences(pairings) for crews such that each flight in the regular schedule is covered by one crew.In this thesis, we consider the management of potential extra flights that can possiblybe introduced to the regular flight schedule during operation at a later point in time.Without delaying or canceling any existing flight, we try to handle these extra flightswithin the regular schedule and refer to the resulting mathematical model as a robustairline crew pairing model. The objective function of the robust model involves not onlythe regular pairing costs but also the opportunity costs for failing to cover the extraflights. Due to the large number of variables (pairings), a typical crew pairing modelis usually solved by column generation methods. Before applying column generationto the proposed robust model, we first discuss several procedures to cover the extraflights by a given set of feasible pairings. However, these procedures introduce extracolumn-dependent constraints to the model. That is, as new columns are added bycolumn generation to the model, the number of constraints may also increase. Similarlyif a column is removed from the model, then some of these extra constraints may bedeleted. To handle this dynamic change both in the number of constraints and variableswe propose two approaches. The main idea behind these approaches is to generate aset of pairings (column pool) so that the number of constraints can be fixed. To thisend, we flag the pairings that can be used for covering the extra flights and keep themin a special pool. We illustrate the proposed column generation approaches on a set ofactual data acquired from a local airline.