Column generation algorithms for airline network revenue management problems
Havayolu gelir yönetimi problemleri için kolon türetme algoritmaları
- Tez No: 392254
- Danışmanlar: PROF. DR. ŞEVKET İLKER BİRBİL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 61
Özet
Havayolu gelir problemlerinin özünde, doğru yolcu kombinasyonlarını bularak karı enbüyükleme amacı olan kapasite dağıtım problemi bulunmaktadır. Problemlemin dinamik doğası yüzünden en iyi kapasite dağılımları rezervasyon süresi boyunca değişiklik gösterir. Rezervasyon süresi boyunca talep ve kapasite değerlerinin değişmesi yüzünden ikincil bilgiye ihtiyacı olan alım fiyatı rezervasyon kontrol stratejisi sürekli olarak güncellenmelidir. Bu sebeplerden ötürü, kapasite dağıtım problemi olabildiğince hızlı çözülmelidir ki, verilerde olan en ufak bir değişiklik ile kapasite dağıtımları güncellenebilsin. Bu çalışma,havayolu gelir yönetimi problemlerine uygulanan kolon türetme algoritmalarını bünyesinde bulundurmaktadır. Ağ esaslı gelir yönetimi problemlerinin çözülmesi, havayolu ağı ne kadar küçük olursa olsun hesaplama yükü bakımından oldukça zordur. Yine de, biz bu çalışmada kendimizi büyük ölçekli havayolu ağlarından oluşan problemleri çözmekle sınadık. Daha verimli hesaplama yapabilmek adına, büyük ölçekli havayolu ağını gün ve zaman bilgisinden yararlanarak daha küçük ağlara böldük. Ayrıca, havayolu ağını başlangıç ve bitiş çiftlerine ayrıştırarak, ağ esaslı problemi her bir çift için tek bacak problemi haline getirdik. Bu işlemler sonunda oluşturduğumuz doğrusal olmayan amaç fonksiyonuna sahip olan modeller (statik, dinamik, deterministik doğrusal programlama) öncelikle Dantzig'in ileri sürdüğü teknik ile doğrusal hale getirildi. Bu teknik fazladan kısıtlama getirmeden doğrusal olmayan amaç fonksiyonunu sadece ilave değişkenler yardımıyla doğrusallaştırır. Daha sonrasında uygulayacağımız kolon türetme algoritması üretilen her kolonla birlikte eklenmesi gereken kısıtlamalarla başa çıkamadığından Dantzig'in yöntemi bizim için oldukça uygundur. Kolon türetme algoritması uygulandıktan sonra, her model için sayısal sonuçlar verildi.
Özet (Çeviri)
At the heart of the airline revenue management problem (ARM) lies the seat allocation problem, which has the ultimate aim of finding the right combination of passengers that will result in maximum profit. Due to the dynamic nature of the problem, optimal seat allocations can change continuously over the reservation period. In addition, widely used bid-price booking control policy which necessitates the dual information is obliged to be updated as the demand and capacity values adjust over the reservation period. Thus, in order to make changes in an interactive basis, it is crucial to solve the seat allocation problem in a small amount of time. This study embodies column generation algorithms applied to ARM problems. Networkbased ARM problems are computationally hard to solve even if the airline network is small. However, in this study we challenged ourselves with large-scale airline networks. For computational efficiency, the network is divided into subnetworks by means of date and time information. The overall network is decomposed to origin destination pairs, so that each pair is treated as a single-leg problem. The resulting seat allocation models (static, dynamic and deterministic linear programming) having a non-linear objective function are linearized by means of the transformation technique proposed by Dantzig which embodies a transformation only by means of additional decision variables. Since column generation can not cope with problems extending row-wise, Dantzigs formulation is the perfect fit. After applying column generation, the numerical results for the models is demonstrated.
Benzer Tezler
- Büyük ölçekli havayolu ekip eşleme problemlerinin çözümü için bir kolon türetme stratejisi
A column generation strategy for large scale airline crew pairing problems
BAHADIR ZEREN
Doktora
Türkçe
2017
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. İBRAHİM OZKOL
- Aksaklıklara karşı dayanıklı Havayolu Ekip Eşleme Problemi için çözüm algoritmaları ve karar destek çerçeve önerisi
Solution algorithms and a decision support framework proposal for Robust Airline Crew Pairing Problem
BÜLENT SOYKAN
Doktora
Türkçe
2015
Endüstri ve Endüstri MühendisliğiKara Harp Okulu KomutanlığıHarekat Araştırması Ana Bilim Dalı
PROF. DR. SERPİL EROL
- A column generation algorithm for robust gate assignment problems
Dayanıklı kapı atama problemi için kolon türetme yöntemi
SONER BEYHAN
Yüksek Lisans
İngilizce
2011
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DİLEK TÜZÜN AKSU
YRD. DOÇ. GÜVENÇ ŞAHİN
- Improvements in column generation methods to solve large scale airline crew scheduling problems
Havayolu personeli görev çizelgesi oluşturma problemlerinin çözülmesinde sütun yaratma metotlarının geliştirilmesi
IŞIK BİÇER
Yüksek Lisans
İngilizce
2010
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. TANER BİLGİÇ
- Pricing by local search in column generation for the airline crew pairing problem
Havayolu ekip eşleme probleminde kolon türetme yönteminin yerel arama ile ücretlendirilmesi
NİMET AKSOY
Yüksek Lisans
İngilizce
2010
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. Ş. İLKER BİRBİL
YRD. DOÇ. DR. KEREM BÜLBÜL