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: Çizelgeleme, Scheduling
- 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ı: Belirtilmemiş.
Ö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
- 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
- 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
- Simultaneous column-and-row generation for solving large-scale linear programs with column-dependent-rows
Kolon-bağlı-satır problemlerinin çözümü için eşzamanlı kolon-ve-satır türetme
İBRAHİM MUTER
Doktora
İngilizce
2011
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. Ş. İLKER BİRBİL
- Column generation-based methods for the electric vehicle routing problems with time windows
Zaman pencereli elektirikli araç rotalama problemi için sütun türetme algoritmasına dayalı çözüm yöntemleri
ECE NAZ DUMAN
Doktora
İngilizce
2022
UlaşımSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. BÜLENT ÇATAY
DR. ÖĞR. ÜYESİ DUYGU TAŞ KÜTEN