Pricing in column generation for a robust airline crew pairing problem
Dayanıklı ekip eşleme probleminde kolon türetme yönteminin ücretlendirilmesi
- Tez No: 178693
- Danışmanlar: DOÇ. DR. ŞEVKET İLKER BİRBİL, YRD. DOÇ. DR. KEREM BÜLBÜ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: 2008
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Bölümü
- Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Sayfa Sayısı: 94
Özet
Ekip eşleme problemi uçuş çizelgesindeki her bir uçuşun kapsanmasını sağlayacak şekilde en az maliyetli eşleme kümesinin bulunması problemidir. Bu çalışmada, dayanıklı ekip eşleme problemi ele alınmıştır. Bu problemde, seçilen eşlemeler olağan uçuşları kapsamakta ve operasyon sırasında tanıtılabilecek bazı ekstra uçuşların kapsanmasını da sağlamaktadır. Ekip eşleme problemi genellikle kolon türetme yöntemiyle çözülmektedir ve bu yöntemin alt problemi çok takılı en kısa yol problemi olmaktadır. Dayanıklı ekip eşleme problemi için Çoban [10] tarafından önerilmiş olan iki model bulunmaktadır ve çok takılı en kısa yol probleminde bu modellerin çözümü için bazı değişiklikler gerekmektedir. Ücretlendirme problemindeki bu değişiklikler, ilişkilendirilmiş takılar ve baskı yöntemleriyle beraber aktarılmıştır.Çok takılı en kısa yol probleminin karmaşıklığı, çizelgedeki uçuş (düğüm) sayısı arttıkça üssel bir şekilde artmaktadır. Bu durum iki yaklaşık ve bir pekin kural kullanılarak çözülmektedir. Ayrıca, çok takılı en kısa yol problemini çözmeden uygun bir eşleme bulabilmek için ara kolon havuzu oluşturulmuştur. Çok takılı en kısa yol problemini çözerken, işlenen düğüm üzerindeki yolları ilk olarak temizlemek için puan hesaplamaya dayalı olan yaklaşık kurallar kullanılmaktadır. En iyi çözüm yaklaşık kuralların kaba yapısından dolayı kaçırılabilir. Eğer yaklaşık kurallar kullanılarak amaç fonksiyonunu geliştirecek bir eşleme bulunamazsa, uygulanan kural pekin kural olarak değiştirilmektedir. Diğer bir yaklaşım, hem pekin hem de yaklaşık kuralların aynı iterasyonda kullanıldığı melez yöntemdir. Bu yöntemde de eniyi sonuç bulunabilmektedir. Yerel bir havayolu şirketinden alınan veriler doğrultusunda bu çözüm yaklaşımlarının sayısal sonuçları sunulmuştur.
Özet (Çeviri)
The crew pairing problem is to find the least costly set of pairings so that each flight given in the flight schedule is covered. In this study, the robust crew pairing problem is considered. That is, the selected pairings cover the regular flights and also provide solutions to cover some extra flights which may be introduced into the flight schedule during the operation at a later point in time. The crew pairing problem is usually solved by column generation in which the pricing subproblem becomes a multi-label shortest path problem. For the robust crew pairing problem the multi-label shortest path problem requires some modifications to solve two column generation approaches proposed by Çoban [10]. These modifications of the pricing problem with associated labels and the domination rules are presented.The complexity of the multi-label shortest path problem grows exponentially as the number of flights (nodes) in the flight schedule increases. This curse of dimensionality is solved by using approximate and exact pruning rules. Also, a buffer column pool is formed as an intermediate step in order to find a negative reduced cost pairing without solving the multi-label shortest path problem at every iteration of the column generation algorithm. In the multi-label shortest path problem, the approximate rules based on the score-calculation are used for early pruning of the paths on the processed nodes. The optimal solution may be missed because of the coarse structure of the approximate rules. When a pairing that improves the objective function cannot be found by applying the approximate rules, we switch to the exact pruning. Another method is using a hybrid approach that applies both approximate and exact rules in the same iteration to find the optimal solution. The performance of our solution approach is demonstrated through a computational study by using actual data from a local airline.
Benzer Tezler
- Minimum length scheduling in wireless networks with successive interference cancellation
Ardışık enterferans silme özellikli kablosuz ağlarda çizelgenin optimize edilmesi
MEHMET KONTİK
Yüksek Lisans
İngilizce
2014
Bilim ve TeknolojiKoç ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SİNEM ÇÖLERİ ERGEN
- Algorithms for the vehicle routing problem with time windows and the location-routing problem
Zaman çerçeveli araç rotalama problemi ve yer bulma-rotalama problemi için algoritmalar
SUAT BOĞ
Yüksek Lisans
İngilizce
2006
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SELÇUK SAVAŞ
YRD. DOÇ. DR. METİN TÜRKAY
- 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
- Mathematical models for maritime terminal operations
Kıyı terminali operasyonları için matematiksel modeller
CELAL ÖZGÜR ÜNSAL
Doktora
İngilizce
2019
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. CEYDA OĞUZ
- Time and reliability in vehicle routing problems
Başlık çevirisi yok
DUYGU TAŞ
Doktora
İngilizce
2013
Endüstri ve Endüstri MühendisliğiTechnische Universiteit EindhovenPROF. DR. TOM VAN WOENSEL
DR. NICO DELLAERT
DR. TON DE KOK