Geri Dön

Pricing in column generation for a robust airline crew pairing problem

Dayanıklı ekip eşleme probleminde kolon türetme yönteminin ücretlendirilmesi

  1. Tez No: 178693
  2. Yazar: DUYGU TAŞ
  3. Danışmanlar: DOÇ. DR. ŞEVKET İLKER BİRBİL, YRD. DOÇ. DR. KEREM BÜLBÜL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2008
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Bölümü
  12. Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  13. 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

  1. 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

    İngilizce

    2014

    Bilim ve TeknolojiKoç Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. SİNEM ÇÖLERİ ERGEN

  2. 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

    İngilizce

    2006

    Endüstri ve Endüstri MühendisliğiKoç Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. SELÇUK SAVAŞ

    YRD. DOÇ. DR. METİN TÜRKAY

  3. 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

    İngilizce

    2010

    Endüstri ve Endüstri MühendisliğiSabancı Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. Ş. İLKER BİRBİL

    YRD. DOÇ. DR. KEREM BÜLBÜL

  4. Mathematical models for maritime terminal operations

    Kıyı terminali operasyonları için matematiksel modeller

    CELAL ÖZGÜR ÜNSAL

    Doktora

    İngilizce

    İngilizce

    2019

    Endüstri ve Endüstri MühendisliğiKoç Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. CEYDA OĞUZ

  5. Time and reliability in vehicle routing problems

    Başlık çevirisi yok

    DUYGU TAŞ

    Doktora

    İngilizce

    İngilizce

    2013

    Endüstri ve Endüstri MühendisliğiTechnische Universiteit Eindhoven

    PROF. DR. TOM VAN WOENSEL

    DR. NICO DELLAERT

    DR. TON DE KOK