A column generation strategy for large scale airline crew pairing Problems

Tez (Doktora) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2017Thesis (Ph.D.) -- İstanbul Technical University, Institute of Science and Technology, 2017Bir ekip eşlemesi (crew pairing); aynı ikamet merkezinde (domicile) başlayan ve biten, birbirini takip eden uçuşların oluşturduğu dizidir. Ekip eşleme planlaması ise havayolu ekip planlama sürecinin en önemli maliyet belirleyici aşamasıdır. Dolayısıyla ekip eşleme optimizasyonu, operasyonel ekip maliyetlerini minimize eden ve ekiplerin verimli kullanımını maksimize eden oldukça önemli bir süreçtir. Ekip eşlemesi üretimi sürecinde gözönünde bulundurulması ve uyulması gereken, resmi yönetmelikler veya şirket prosedürleri kaynaklı birçok kısıtlama ve kural bulunmaktadır. Optimizasyonun temel amacı, bu kural ve kısıtlamaları gözönünde bulundurarak, havayolu tarifesinde bulunan tüm uçuşları kapsayan düşük maliyetli ve sivil havacılık kurallarına uygun ekip eşleme kümeleri üretmektir. Bu araştırma ve geliştirme çalışmasında, ekip eşleme optimizasyonu ile ilgili var olan çalışmalar incelenmiş ve öncelikle ekip eşleme problemini çözmek üzere bir genetik algoritma yaklaşımı geliştirilmiştir. Genetik algoritmalar, yöneylem alanındaki bir çok farklı optimizasyon probleminin çözümünde kullanılan güçlü bir metasezgisel (metaheuristics) tekniktir. Çalışmanın bu aşamasında, genetik algoritmanın performansını arttırmak üzere yeni operatörler/sezgisel metodlar geliştirilmiş ve küçük ve orta ölçekli filolar için başarılı sonuçlar elde edilmiştir. Fakat büyük ölçekli filolar için, geliştirilen genetik algoritmanın paralelleştirilmiş versiyonu bile matematiksel yöntemlerin ürettiği sonuçlara tercih edilebilir kalitede çözüm üretememiştir. Elde edilen bu bulguları takiben, çalışma, özellikle dinamik kolon türetme teknikleri (dynamic column generation) kullanan matematiksel yaklaşımların üzerinde yoğunlaştırılmıştır. Ve bu bağlamda bilimsel literatüre katkı niteliğinde olan; yeni bir kolon türetme stratejisi, bir ücretlendirme ağı (pricing network) tasarımı ve ekip eşlemesi eliminasyonu için kullanılan bir sezgiseli (heuristics) geliştirilmiştir. Önerilen stratejide, ana problem küme-kapsama (set-covering) problemi, ücretlendirme alt problemi (pricing sub problem) ise en kısa yol (shortest-path) problemi olarak modellenmiş; sezgisel ve kesin (exact) algoritmaların birarada kullanımı ile görev-uçuş yatı bağlantısı çizgesi (duty-flight overnight connection graph) üzerinde verimli bir şekilde çözülmüştür. Önerilen strateji, Türk Hava Yolları’ndan elde edilen gerçek dünya verileri ile test edilmiş ve bu çalışmada sunulan test sonuçlarından da anlaşılacağı üzere Türk Hava Yolları’nda hali hazırda kullanılan sistem ile karşılaştırıldığında yüksek kalitede ve son derece rekabetçi çözümler üretebilme yeteneğine sahip oluduğu görülmüştür. Aynı zamanda önerilen çözüm yaklaşımının, amaç fonksiyonundaki (objective/fitness function) ceza katsayılarına olan hassasiyeti, daha az pas (deadhead) uçuş üretmesi, daha hafif donanımlar ve tek kanallı (single-threaded) bir yazılım ile neredeyse aynı sürelerde sonuç üretebilme gibi avantajları olduğu da görülmektedir.A crew pairing is a sequence of flight legs beginning and ending at the same crew domicile hub. Crew pairing planning is the primary cost-determining phase in airline crew scheduling. Therefore, optimizing crew pairings of an airline timetable is an extremely important process which helps to minimize operational crew costs and to maximize crew utilization. There are various restrictions imposed by regulations or company policies that must be considered and satisfied in crew pairing generation process. Keeping these restrictions and regulations in mind, the main goal of the optimization is the generation of low cost sets of valid crew pairings which cover all flights in airline's timetable. And the ultimate aim of airline crew scheduling is assignment of crew members to flights so as to satisfy all crew need of all flights in airline’s timetable. There are some important key performance indicators (KPI) of outputs of crew scheduling processes like total man day, number of overnights, deadhead time, ground time etc. It is always desired to reduce these KPI values as much as possible. By doing this company can increase the crew utilization and basically keep crew on air as much as possible and avoid losing time because of other reasons except flights. There are two main sub processes of strategic crew scheduling. First one is crew pairing generation that constitutes the main topic of this study. In crew pairing generation process, flight sequences that constitute flight duties and then crew pairings are generated so as to cover all flights in airline’s timetable. Optimization methods play very important role in crew pairing generation process because of critical cost factors that must be minimized. Crew costs are the second biggest cost after fuel costs for airline companies. This situation makes crew scheduling and especially crew pairing optimization significantly important operation that must be carried out carefully. Even small amount of percentages can cost millions of dollars. The second sub process is crew rostering process. In this phase, crew assignment to all crew pairings generated in previous crew pairing generation phase is done. Crew rostering has less impact on total crew costs compared to crew pairing generation process. It mainly affects workload balance between crew members and aims to increase fairness of the plan for crew members. Some US companies does not carry out rostering process. Instead, crew assignment is done by a seniority based bidding process and then a market style system that provides possibility of trip trading. Eventually the importance of optimum crew scheduling cannot be overstated as all airlines operate in a very complex environment. In addition, with increasing competitiveness in the marketplace, airline companies are in a position to better manage their expenses using effective flight and crew scheduling techniques. In literature, airline crew pairing problem is mostly modeled as set-covering or set-partitioning problems. These models perfectly fit almost all optimization modeling needs that arise in airline crew scheduling. Both of them are combinatorial and are proven to be NP-complete. In literature, airline crew pairing problem is mostly modeled as set-covering or set-partitioning problems. These models perfectly fit almost all optimization modeling needs that arise in airline crew scheduling. Both of them are combinatorial and are proven to be NP-complete. There are two main approaches to solve these kind of problems: Heuristic methods and mathematical (LP based) methods. The most widely used heuristic method in this field is genetic algorithms which is basically a search heuristic that mimics the process of natural selection. There are two main column generation strategies used in GA approaches. The first strategy is offline column generation which is based on generating huge amount of columns (crew pairings) just before optimization phase. Then optimization phase takes place and the best subset of these pre-generated columns is selected. The other strategy is based on generating columns during optimization phase. In this strategy columns are generated from choromosomes (represent solutions in GA context) using special heuristic. Nevertheless metaheuristics can give high quality solutions for only small sized problems. On the mathematical side, different column generation strategies exist as is seen in heuristic approaches. Some earlier studies which rely on mathematical methods implemented partial enumeration for large scale problems. Thus they increased performance by reducing problem size. The second strategy which is called “column generation” or “dynamic column generation” is the most widely used and studied technic in last two decades. It provides a very efficient way to generate only necessary columns to improve objective value further. Column generation method divides whole problem into two parts: Master problem and sub (pricing) problem. In this study master problem is modeled as set-covering problem and the dual variable information (shadow price) of each row (flight leg) is calculated by solving it. The pricing sub problem is modeled as shortest-path problem and new columns (crew pairings) are generated by finding columns with least negative reduced cost using dual information obtained from master problem. Even though set-covering and set-partitioning problems require integer solutions at the end, the core mechanism of column generation relies on LP. Calculation of dual variables and reduced costs etc. require LP solutions. There are a few strategies that are used to obtain integer solutions for such problems. A very largely used approach is based on using some special heuristic which eliminate or select pairings based on their linear variable values and reduced costs. Another approach is based on using branch and bound algorithm to get integer solution at the end of column generation phase. But this implementation fails for large sized problems if there is no special performance increasing heuristic. The most popular strategy for last two decades is the branch and price approach which is based on generating columns on a branch and bound tree. Branch and price is an exact method that guarantees finding global optima but requires employment of special heuristic for performance improvements with a little loss in solution quality. But even with special heuristics, it is a relatively more time consuming technic according to some test results published. It also requires parallel programming tech-nics which are more sophisticated and relatively difficult to implement. For this research study, already existing works related to crew pairing optimization are examined and first a genetic algorithm approach is developed to solve crew pairing problems. Genetic algorithms which is a powerful metaheuristics that is used in wide variety of optimization problems in the area of operations research. During this phase of the study, additional operators/heruristics are developed to improve genetic algorithms’s performance and it produced succesful results for small and middle sized fleets. A parallel implementation of the improved genetic algorithm approach was developed to be able to solve large sized instances of crew pairing problem. This parallel implementation was developed based on island parallel genetic algorithm model which is efficient in working both on tcp-ip networks or on a massively parallel high-tech servers. After comprehensive tests and experiments it is seen that for large sized fleets, even a parrallel implementation of the improved genetic algorithm approach has not been able to generate preferable solutions compared to mathematical approachs. After this point of time, the study has been shifted to work on mathematical approachs, especially ones that use dynamic column generation technics and a new column generation strategy, a pricing network design and a pairing elimination heuristics are developed as a contribution to the previous studies. In the proposed strategy, the main problem is modeled and solved as a set-covering problem and the pricing sub problem is modeled as a shortest-path problem which is efficiently solved over a duty-flight overnight connection graph by the combined usage of heuristic and exact algorithms. The proposed strategy has been tested with real world data obtained from Turkish Airlines and it is seen that it is capable of generating very competitive solutions compared to current practices in Turkish Airlines. It is also observed that there are various advantages of the proposed solution approach such as sensitivity to penalty coefficients, generating less deadheads, very close solution times with a single threaded software and light weight hardware.DoktoraPh.D