Robust crew pairing for managing extra flights

Abstract

ü Ë Ë ËşË ËEK UCUSLARIN YONETIMI ICIN DAYANIKLI EKIP ESLEMEşş şHatice TekinerEndüstri Mühendisliği, Yüksek Lisans Tezi, 2006u u g uşËTez Danışmanı: Doş. Dr. S. Ilker Birbils cAnahtar kelimeler: ekip eşleme, dayanıklılık, yeni ucuş, ekip değiştirme, ülü uşuş,s s gs ou c ssayısal analiz sonuşlarıcüOzetHava yolları endüstrisi uşuş planlama, ï¬lo atama, ekip planlama gibi bir şok opti-u cs cmizasyon problemi ile karsılaşmaktadır. Ekip maliyeti hava yolu şirketlerinin operasy-s sonel maliyetleri işinde şok büyük bir paya sahip olduğu işin, ekip planlama problemic c uu gcbelirtilen problemler işinde en şok şalışılan problemdir. Literatürde, ekip maliyetini enc ccs uaza indirmeyi amaşlayan bir şok model bulmak mümkündür. Bu modellerin şoğundac c uuu cgekip planlama problemi iki kısımda şüzülmektedir, ekip eşleme problemi ve ekip atamaco u sproblemi. Burada şalıştığımız ekip eşleme problemi bütün uşuşları bir kez kapsayanc sg s uu c sen az maliyete sahip eşlemeleri seşmeyi amaşlamaktadır.s c cEkip eşleme problemi işin bir şok yaklaşım olmasına rağmen, şoğu yaklaşım op-s c c s g cg serasyon sürecinde herhangi bir aksaklığın yaşanmadığını varsaymaktadır. Ancak, havau g s gyolu operasyonlarında hava durumu, bakım problemleri gibi nedenlerden dolayı kay-naklanan aksaklıkların yaşanması yaygın bir problemdir ve pratikteki ekip maliyetininsplanlanandan daha yüksek olmasına neden olmaktadır. Bu aksaklıklar mevcut uşuşu csplanında yer alan bazı uşuşların gecikmesine veya iptal edilmesine neden olabilmek-cstedir. Ancak, yerel hava yolları şirketlerinin karşılaştığı başka bir aksaklık daha bu-s s sg slunmaktadır. Bu aksaklık kısaca var olan ucuş programına yeni bir uşuşun eklenmesis csolarak tanımlanabilir. Bu şalışmada, bu tip bir aksamaya dayanıklı olabilecek bircsekip eşleme modeli ünerilmektedir. Eklenebilecek bütün uşuşların bilindiği veya tah-s o uu c s gË şeşit şüzüm yaklaşımı matematiksel modellerimin edilebildiği varsayılmaktadır. Iki c s co ug sile birlikte ünerilmiştir. Sunulan modelin amacı ekip eşleme maliyetini kabuledilebiliro s sbir seviyede tutarak, toplam şüzüm sayısını maksimum yapmaktır. Calışmamızda,co u şsekip eşleme problemi ünerilen model ve geleneksel model kullanılarak şüzülmüş ves o co u ussunduğumuz modelin faydalarını güstermek işin sayısal sonuşları verilmiştir.g o c c s

ROBUST CREW PAIRING FOR MANAGING EXTRA FLIGHTSHatice TekinerIndustrial Engineering, MS Thesis, 2006şËThesis Supervisor: Assoc. Prof. Dr. S. Ilker BirbilKeywords: crew pairing, robustness, extra ï¬ight, crew swapping, deadhead,computational results.AbstractThe airline industry encounters many optimization problems such as schedulingï¬ights, assigning the ï¬eet, scheduling the crew. Among them, the crew schedulingproblem is the most studied one. The main reason is that the crew cost is one of thelargest components of the operational cost for an airline company. Therefore, there aremany models proposed in the literature to ï¬nd a cost eï¬cient crew schedule. Most ofthose models divide the crew scheduling problem into two separate problems, namelythe crew pairing and the crew assignment problems. The crew pairing problem that westudy here aims at ï¬nding the least costly subset of pairings, which cover the scheduledï¬ights.Although there are many approaches to solve the crew pairing problem, most ofthem assume no disruptions during the operation. However disruptions due to weatherconditions, maintenance problems, and so on are common problems leading to higheroperational crew cost in practice. These kinds of disruptions result in delaying orcanceling some scheduled ï¬ights. Another disruption that local airline companies faceis adding an extra ï¬ight to predetermined (regular) ï¬ight schedule. In this study, wepropose a model that provides robust crew pairing schedule in the case of adding anextra ï¬ight to the regular ï¬ight schedule. Two solution approaches are along with themathematical model are proposed. The objective of the proposed model is to maximizethe total number of solutions, while maintaining the increase in the crew cost at anacceptable level. A crew pairing problem is then solved by both the proposed modeland the conventional model. Finally, computational experiments are conducted todemonstrate the beneï¬ts of the proposed model.