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
- Tez No: 309406
- Danışmanlar: DOÇ. DR. Ş. İ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: 2010
- 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ı: 58
Özet
Havayolu ekip eşleme problemi uçuş çizelgesindeki her bir uçuşun kapsanmasını sağlayacak şekilde en az maliyetli ekip eşlemelerinin bulunmasıdır. Bu problem literatürde genel olarak küme bölüntüleme veya küme kapsama problemi olarak modellenmektedir. Olası eşlemelerin (kolonların) sayısındaki fazlalık nedeniyle bu modellerin kolon türetme yöntemiyle çözülmesi sıkça başvurulan bir yaklaşımdır. Havayolu ekip eşleme problemi için kolon türetme yönteminin ücretlendirme altproblemi uçuş serimi üzerinde çözülen çok takılı en kısa yol problemine karşılık gelmektedir. Uçuş serimi üzerinde çözülen çok takılı en kısa yol problemi NP-zor bir problemdir ve karmaşıklığı orta büyüklükteki çizelgeler için bile üsseldir.Bu çalışmada, havayolu ekip eşleme problemini, ücretlendirme altprobleminin karmaşıklığını azaltmak amacıyla melez bir ücretlendirme prosedürü kullanarak, kolon türetme yöntemiyle çözmekteyiz. Önerdiğimiz melez prosedürde, ücretlendirme altproblemi üç adımdan oluşmaktadır. İlk olarak, kısmi uçuş görev havuzu üzerinde uyguladığımız yerel arama yöntemi ile negatif azaltılmış maliyetli eşlemeler oluşturmaya çalışmaktayız. Yerel arama yönteminin böyle bir eşleme oluşturamadığı durumlarda çok takılı en kısa yol problemini kısmi uçuş görev serimi üzerinde çözmekte ve kısıtlı ana probleme eklemek üzere negatif azaltılmış maliyetli eşlemeler aramaktayız. Bu metodun da kısıtlı ana probleme eklenecek eşleme bulamadığı durumlarda çok takılı en kısa yol problemini uçuş serimi üzerinde çözmekteyiz. Benimsediğimiz melez yaklaşım sayesinde, çok takılı en kısa yol probleminin uçuş serimi üzerinde çözüldüğü kolon türetme iterasyonlarının sayısını ve iterasyon başına düşen çözüm süresi ile toplam çözüm süresini azaltmayı amaçlamaktayız. Yaklaşımımızın etkinliğini yerel bir havayolu şirketinden edindiğimiz örnek problemler üzerinde test etmekte ve sayısal sonuçlar sunmaktayız.
Özet (Çeviri)
The airline crew pairing problem (ACP) is finding the least costly set of crew pairings so that each flight given in the flight schedule is covered. The ACP is traditionally modeled either as a set partitioning problem or a set covering problem. Due to the large number of possible pairings (columns), these models are usually solved by the column generation (CG) method. For the ACP, the pricing subproblem of the CG corresponds to a multi-label shortest path problem (MLSP) typically solved over a flight network. The MLSP over the fight network is NP-hard and it suffers from an exponential complexity even for moderate size flight networks. In order to overcome the complexity of the pricing subproblem, we propose a column generation method to solve the ACP, in which a hybrid pricing procedure is used. In this hybrid procedure, the pricing subproblem consists of three steps. First, we apply a local search mechanism on the partial duty period pool to construct pairings with negative reduced cost. In cases local search mechanism cannot find such a pairing, we execute a heuristic MLSP algorithm over the partial duty network to price out negative reduced cost pairings for the restricted master problem (RMP). If this method also fails, we solve the MLSP over the flight network. By adopting this hybrid approach, we aim to decrease the number of CG iterations where the MLSP is executed over the flight network, and reduce the computation time per iteration as well as the total computation time. We test the efficiency of our approach on real-life instances acquired from a local airline company, and present numerical results.
Benzer Tezler
- Son adım teslimat problemi:Bir e-ticaret firmasında uygulama
Last mile delivery problem: Application in an e-commerce company
FATMA DUYGU YILMAZER
Yüksek Lisans
Türkçe
2024
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. HARUN REŞİT YAZĞAN
- Geliştirilmiş SPEA2 ile envanter probleminin çözümü
Inventory optimization with a novel SPEA2 algorithm
ALİ BAYRAKDAR
Yüksek Lisans
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Aydın ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ILHAM HUSEYINOV
- The search for alpha in emerging markets
Başlık çevirisi yok
KEREM KADER
Yüksek Lisans
İngilizce
2016
MaliyeUniversity of London - London School of Economics and Political Science - Global ekonomide portföy yatırımları analizi
Portfolio investments analysis in global economics
ÖMER KÖROĞLU
- Akıllı şebekelerde yenilenebilir enerji üretimine sahip akıllı evlerin enerji ve yük yönetimi
Energy and load management of smart homes with renewable energy generation in smart grids
CEMAL KELEŞ
Doktora
Türkçe
2017
Elektrik ve Elektronik Mühendisliğiİnönü ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ASİM KAYGUSUZ