Crew recovery optimization through disruption analysis and deep learning driven column generation
Aksaklık analizi ve derin öğrenme tabanlı sütun oluşturma ile ekip kurtarma optimizasyonu
- Tez No: 854860
- Danışmanlar: PROF. ÖZGÜR KABAK
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 153
Özet
Thanks to globalization, new travel opportunities and economic development have increased the interest in the aviation industry and air transport. The increase in the number of passengers and compliance with the regulations on passenger rights make transformation inevitable for the aviation industry and airlines. Airlines are reorganizing and managing all their resources in line with this transformation. The most critical resources of commercial airlines are the crew and aircraft, which together with passengers are key components of operational efficiency. Unforeseen events such as bad weather conditions, aircraft malfunctions and crew absence may result in inefficiency in operations and thus in the utilization of aforementioned resources. These events are called disruptions. As disruptions such as delays are the primary and fundamental factor in passenger satisfaction and the airline's financial conditions, aviation companies devote valuable resources to analyzing disruptions and taking necessary actions. Actions known as recovery actions are the ones decided by the airline operations control center to overcome problems in the execution of plans due to disruptions. The crew recovery problem is a complex optimization problem in the airline industry that involves scheduling and assigning crews to flights while taking into account various constraints such as legal regulations, crew availability, and cost. Several methods have been proposed to solve this problem, including heuristic and metaheuristic algorithms, integer programming, and constraint programming. It is a type of optimization problem that aims to choose the best recovery strategies to overcome crew disruptions. The main goal is to find the minimum cost combination of assignments that solve the problems related with crew plans while considering all constraints, especially flight time limitations. One popular method for solving the crew recovery problem is the column generation algorithm, which involves generating and adding columns to the problem's LP relaxation until an optimal solution is obtained. Other optimization methods include simulated annealing, genetic algorithms, and ant colony optimization. However, despite the various optimization methods proposed, the crew recovery problem remains a challenging and computationally expensive task due to the large number of variables and constraints involved. Furthermore, real-world crew recovery problems are dynamic and uncertain, requiring the ability to adapt quickly to unexpected events. This is where machine learning (ML) can play a crucial role in developing an optimization method with AI support. By leveraging machine learning algorithms, we can learn from past data and experiences to make informed decisions and generate optimized solutions quickly and efficiently. Recovery strategies can be realized by using actions known as recovery actions. Especially during the preparation of recovery models, more effective strategies are produced by using the actions learned from the past disruptions as inputs in the model. The main motivation behind using actions as input is that learning-based approaches have the potential to generate more effective algorithms for large-scale and difficult optimization problems by inferring insights from historic datasets. Especially with the learning process, important points that people may miss in the solution process become easily noticeable and increase the success of the recovery process. In this study, recovery actions provided by a customized deep learning (DL) model are used as input to the proposed optimization model, in which the objective function minimizes the total assignment cost of crew. Crew disruption data including some of the flight disruptions from a large scale airline is analyzed. Based on the analysis of the data, features are generated and recovery actions are extracted. The recovery actions are used as label and supervised learning methodology is used to train a customized deep learning model. Our hypothesis is based on the assumption that deep learning can provide needed insights in order to solve the problem in a shorter time while preserving the optimality at a certain level. The fundamental insight that we derive from the deep learning model is the recovery actions, which will be used while generating new columns. The actions are used in order to configure the columns faster than the classical column generation by either directly modifying the column itself or narrowing down the solution space. The resource or resource groups including crew and aircrafts are filtered according to the information provided by the deep learning. This makes it possible to search for new columns in a narrower solution space, which makes the search time shorter compared to the classical column generation techniques. The primary goal of the study was to develop a model that balances solution quality and speed. Results indicate that the proposed method outperforms the reference model in terms of runtime while maintaining an acceptable level of optimality. This approach can be valuable for airline companies looking to efficiently address crew recovery challenges. Moreover, it contributes to the existing literature by introducing a new mathematical model and approximation method, demonstrating the potential of deep learning and optimization techniques for addressing complex aviation sector optimization problems and offering valuable insights for future research in the field of crew recovery.
Özet (Çeviri)
Küreselleşme sayesinde yeni seyahat olanakları ve ekonomik gelişme, havacılık endüstrisine ve hava taşımacılığına olan ilgiyi artırmıştır. Yolcu sayısındaki artış ve yolcu haklarına ilişkin düzenlemelere uyum, havacılık sektörü ve havayolları için dönüşümü kaçınılmaz kılmaktadır. Havayolları tüm kaynaklarını söz konusu dönüşüme uyumlu olacak şekilde yeniden düzenlemekte ve yönetmektedir. Havayolları, bu dönemde tüm kaynaklarını dönüşüme uyumlu hale getirmek için kullanmaktadır. Bu, hem içsel süreçlerin hem de müşteri hizmetlerinin daha etkin ve rekabetçi bir şekilde yönetilmesini sağlamayı amaçlamaktadır. Havacılık sektöründeki bu dönüşüm süreci, havayollarının hem operasyonel hem de müşteri odaklı stratejilerini gözden geçirmelerini ve küresel taleplere daha etkin bir şekilde yanıt vermelerini sağlamaktadır. Ticari havayollarının etkin yanıt üretmedeki en kritik kaynakları, yolcularla birlikte operasyonel verimliliğin temel bileşenleri olan ekip ve uçaktır. Bu bağlamda, ekip ve uçakların yönetimi, havayolu şirketlerinin bu değişen dinamiklere uyum sağlamalarında kritik bir rol oynamaktadır. Öngörülemeyen olaylar, özellikle kötü hava koşulları, uçak arızaları ve ekip yokluğu gibi durumlar, havacılık sektöründe aksaklıklara neden olabilmektedir. Bu aksaklıklar, operasyonel verimliliği ve bu bağlamda kullanılan kritik kaynakları, yani ekip ve uçakları, etkin bir şekilde kullanamama sonucunu ortaya çıkarmaktadır. Aksaklıklar, havacılık şirketleri için hem yolcu memnuniyeti hem de finansal durum açısından kritik öneme sahiptir. Özellikle gecikmeler gibi aksaklıklar, yolcu memnuniyetini olumsuz etkileyerek havayolu şirketinin itibarını zedeleme potansiyeline sahiptir. Ayrıca, operasyonel planlamalarda meydana gelen aksaklıklar, maliyet artışlarına ve kaynak israfına yol açabilir. Havacılık şirketleri, aksaklıkları etkili bir şekilde yönetmek ve en aza indirmek için önleyici ve iyileştirici tedbirler almak zorundadır. Aksaklıkların analizi, bu olayların nedenlerini anlamak ve gelecekte benzer durumları önceden tahmin etmek adına önemli bir adımdır. Bu analizler, kötü hava koşulları, teknik sorunlar veya personel eksikliği gibi faktörlerin etkilerini değerlendirir ve operasyonel süreçlerin güçlendirilmesi için rehberlik edecek niteliktedir. Aksaklıkların etkili bir şekilde yönetilmesi, havacılık şirketlerinin operasyonel verimliliğini artırmasına ve müşteri memnuniyetini korumasına yardımcı olur. Bu bağlamda, aksaklıkları analiz etmek ve bu olaylara hızlı ve etkili bir şekilde müdahale etmek, havayolu endüstrisinde başarılı bir şekilde faaliyet göstermek için kritik bir gerekliliktir. Havacılık şirketleri aksaklıkları analiz ederek alınması gereken aksiyonları belirlemek için önemli kaynaklar tahsis etmektedir. Kurtarma aksiyonları olarak bilinen aksiyonlar, aksaklıklar nedeniyle planların gerçekleştirilmesinde meydana gelen sorunların üstesinden gelmek için havayolu operasyon kontrol merkezleri tarafından karar verilen eylemlerdir. Ekip kurtarma problemi, ekip aksaklıklarının üstesinden gelmek için en iyi kurtarma aksiyonlarını seçmeyi amaçlayan bir tür optimizasyon problemidir. Ana amaç, uçuş süresi sınırlamaları başta olmak üzere tüm kısıtları dikkate alırken sorunlu ekip planlarını kurtaran minimum maliyetli görev kombinasyonunu bulmaktır. Havayolu endüstrisinde yasal düzenlemeler, mürettebat mevcudiyeti ve maliyet gibi çeşitli kısıtlamaları dikkate alarak çizelgeleme ve uçuşlara ekip atamayı içeren karmaşık bir optimizasyon problemidir. Bu sorunu çözmek için metasezgisel algoritmalar, tamsayı programlama ve kısıtlama programlama dahil olmak üzere çeşitli yöntemler önerilmiştir. Ekip aksaklıklarının üstesinden gelmek için en iyi kurtarma stratejilerini seçmeyi amaçlayan bir optimizasyon problemi türü olan ekip kurtarma probleminde temel amaç, uçuş süresi sınırlamaları başta olmak üzere tüm kısıtlamaları göz önünde bulundurarak, ekip planları ile ilgili sorunları çözen görevlerin minimum maliyetli kombinasyonunu bulmaktır. Ekip kurtarma problemini çözmek için popüler bir yöntem, optimal bir çözüm elde edilene kadar problemin LP gevşemesi ile sütunlar oluşturmayı ve sütunları eklemeyi içeren sütun oluşturma algoritmasıdır. Diğer optimizasyon yöntemleri arasında simüle edilmiş tavlama, genetik algoritmalar ve karınca kolonisi optimizasyonu bulunur. Bununla birlikte, önerilen çeşitli optimizasyon yöntemlerine rağmen, ekip kurtarma problemi, ilgili çok sayıda değişken ve kısıtlama nedeniyle zorlu ve hesaplama açısından maliyetli olmaya devam etmektedir. Ayrıca, gerçek dünyadaki ekip kurtarma sorunları dinamik ve belirsizdir ve beklenmedik olaylara hızla uyum sağlama becerisi gerektirir. Yapay zeka destekli bir optimizasyon yöntemi geliştirmede makine öğreniminin önemli rol oynayabileceği alan da burasıdır. Makine öğrenimi algoritmalarından yararlanarak, bilinçli kararlar almak ve hızlı ve verimli bir şekilde optimize edilmiş çözümler üretmek için geçmiş verilerden ve deneyimlerden ihtiyaç duyulan stratejiler öğrenilebilir. Kurtarma stratejileri, kurtarma eylemleri olarak bilinen eylemler kullanılarak gerçekleştirilebilir. Özellikle çözüm modellerinin hazırlanması aşamasında, geçmiş aksaklıklardan öğrenilen aksiyonlar modelde girdi olarak kullanılarak daha etkin çözümler üretilmektedir. Eylemleri girdi olarak kullanmanın arkasındaki ana motivasyon, öğrenmeye dayalı yaklaşımların, geçmiş veri kümelerinden içgörüler çıkararak büyük ölçekli ve zor optimizasyon sorunları için daha etkili algoritmalar üretme potansiyeline sahip olmasıdır. Özellikle öğrenme süreci ile birlikte kişilerin çözüm sürecinde gözden kaçırabilecekleri önemli noktalar kolayca fark edilir hale gelir ve iyileşme sürecinin başarısını artırır. Bu çalışmada, amaç fonksiyonunun toplam atama maliyetini minimize ederken özelleştirilmiş bir derin öğrenme modeli tarafından sağlanan kurtarma eylemlerini girdi olarak kullanan bir optimizasyon modeli geliştirilmiştir. Büyük ölçekli bir havayolu şirketinden bazı uçuş aksaklıklarını da içeren ekip aksaklık verileri analiz edilmiştir. Veri analizine sonucunda özellik seti üretilmiş ve kurtarma aksiyonları çıkarılmıştır. Kurtarma aksiyonları etiket olarak kullanılmış ve özelleştirilmiş derin öğrenme modelini eğitmek için denetimli öğrenme yöntemi kullanılmıştır. Bu çalışma kapsamında hipotezimiz, derin öğrenmenin optimalliği belirli bir düzeyde korurken problemi daha kısa sürede çözmek için gerekli içgörüleri sağlayabileceği varsayımına dayanmaktadır. Derin öğrenme modelinden çıkardığımız temel içgörü, yeni sütunlar oluşturulurken kullanılacak kurtarma eylemleridir. Eylemler, doğrudan sütunun kendisini değiştirerek veya çözüm alanını daraltarak klasik sütun oluşturmaya göre sütunları daha hızlı yapılandırmak kullanılır. Ekip ve uçak dahil olmak üzere kaynak veya kaynak grupları, derin öğrenme tarafından sağlanan bilgilere göre filtrelenir. Bu da yeni kolonların daha dar bir çözüm uzayında aranmasını mümkün kılmakta, bu da klasik kolon üretme tekniklerine göre arama süresini kısaltmaktadır. Çalışmanın temel hedefi, çözüm kalitesi ile hızını dengeleyen bir model geliştirmektir. Sonuçlar, önerilen yöntemin çalışma süresi açısından referans modelini aştığını ve kabul edilebilir bir düzeyde optimaliteyi sürdürdüğünü göstermektedir. Bu yaklaşım, ekip kurtarma sorununu etkili bir şekilde çözmek isteyen havayolu şirketleri için değerli olabilir. Ayrıca, derin öğrenme ve optimizasyon yöntemlerinin karmaşık havacılık sektörü optimizasyon problemlerini çözme potansiyelini göstererek, mevcut literatüre yeni bir matematiksel model ve yaklaşım sunmakta ve ekip kurtarma alanındaki gelecekteki çalışmalara yönelik değerli görüşler sunmaktadır.
Benzer Tezler
- Konteyner gemilerin yatırım analizi
Başlık çevirisi yok
NEDİM SUKAS
Yüksek Lisans
Türkçe
1998
Gemi Mühendisliğiİstanbul Teknik ÜniversitesiGemi İnşaatı ve Gemi Makineleri Mühendisliği Ana Bilim Dalı
PROF. DR. A. YÜCEL ODABAŞI
- Large scale optimization applications on the aircraft and aircrew recovery problems and their integration
Uçak ve uçuş ekibi yeniden çizelgeleme problemlerinde ve bu problemlerin entegrasyonunda geniş ölçekli optimizasyon uygulamaları
NAZAN ZEYBEKCAN
Doktora
İngilizce
2011
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. HASAN ESKİ
- Airline crew scheduling and rostering problem
Havayolu ekip planlama ve çizelgeleme problemi
VEDAT KILIÇ
Yüksek Lisans
İngilizce
2018
Sivil HavacılıkYıldız Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. UMUT RIFAT TUZKAYA
- Yeniden uçuş çizelgelemede uçuşların veri madenciliği ile analizi ve bir karar destek sistemi önerisi
Analysing flights with data mining and decision support system application in flight schedule recovery
NEVRA YAMAN
Doktora
Türkçe
2023
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. HATİCE EDİZ ATMACA
- Kabin memurlarının hizmet verme yatkınlıklarının hizmet hatası telafisi performanslarına etkisinde personel güçlendirmenin aracı rolü
The mediator role of empowerment in the effect of the cabin staff's service orientation on the service recovery
NİLGÜN ÇAYALAN