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
- Tez No: 255897
- Danışmanlar: PROF. DR. TANER BİLGİÇ
- 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: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 87
Özet
Havayolu personeli görev çizelgesi oluşturma problemi, problemin karmaşıklığı ve skalasına bağlı olarak yöneylem araştırması araştırmacıları tarafından oldukça ilgi gören önemli bir problemdir. Ayrıca, havayolu personeli görev çizelgesi oluşturma problemi, değişken sayısının çok fazla olması sebebiyle matematiksel olarak zor çözümlenebilen bir problemdir. Sütun üretme yöntemi, sınırlı sayıda değişken ile en iyi sonucu verebildiği için bu tür problemlerin çözümünde etkin bir yöntem olarak bilinmektedir. Sütun üretme yöntemi uygulamalarında problem, ana problem ve yardımcı problem olarak iki parçaya ayırılır. Sınırlı sayıda değişken ile problemin çözümüne başlanıldığı zaman, ana problemin çözümü, her bir tekrarda sınırlı sayıdaki değişken için en iyi sonucu verir; yardımcı problemin çözümüyse, her bir tekrarda ana probleme eklenecek değişkeni (görev çizelgesini) verir. Havayolu personeli için uçuş çizelgesi oluşturma probleminin sütun üretme yöntemiyle çözümünde, yardımcı problemin çözümü ana problemin çözümünden çok daha fazla zaman almaktadır. Bunun sonucu olarak, yardımcı problem üzerinde yapılan geliştirmelerin genel problemin çözümüne olan katkısı oldukça büyük olacaktır.Yaptığımız bu çalışmanın katkısı iki yönlü olmaktadır. Bunlardan birincisinde, yardımcı problemin çözümünü, ön işlem yaparak ve kısıtlı en kısa yol problemini (RCSP) kısıtsız en kısa yol problemine (SPP) dönüştürerek daha etkin hale getirmeye odaklandık. Bu işlemler daha önceden bazı araştırmacılar tarafından geliştirilmiş olup üç kademeli yaklaşım olarak adlandırılmıştır. Bu 3 kademe, (1) ön işlem süreci, (2) problemin genişletilmesi süreci ve (3) tekrarlanan problem çözümü süreci olmaktadır. Bu yöntemdeki aşamaların içerisindeki bazı işlemleri eleyerek, bu yöntemin havayolu personeli görev çizelgeleri oluşturma problemine daha uyumlu olmasını sağladık. İkinci olarak, kaynakların vektörel olarak karşılaştırılmasını temel alan vektörel biçimli üç kademeli yaklaşım yöntemini tasarladık. Bu tezin içeriğinde, vektörel biçimli üç kademeli yaklaşımın normal üç kademeli yaklaşıma göre olanaklı olmayan ağ oklarının elenmesinde daha etkin olduğunu yaptığımız testlerle gösterdik. Her iki yöntemin verimini de hesaplama çalışmalarının altında analiz ettik.
Özet (Çeviri)
Airline crew scheduling problems are one of the most important problems in airline industry that have received considerable attention in operations research literature due to the complexity and the size of the problem. Solving this type of problems optimally is very challenging since the number of variables cannot be counted in most times. Column generation method is very successful in solving this type of problems because it provides the possibility to work with a limited number of variables and ensures to obtain the optimal result at the end of the process. Applying the column generation method, airline crew scheduling problems are divided into two parts as -(1) master problem and -(2) subproblem. Starting with a small number of variables, the master problem, which is an optimization problem, provides the optimal solution for the limited number of variables at each iteration, whereas the subproblem is a resource constrained shortest path problem (RCSP), in which the solution corresponds to the variable (roster) to be added to the master problem at each iteration. During the column generation process, the time consumption for solving the subproblem is larger than that of the master problem. As a result, improvements made on the solution procedure of the subproblem contribute a great deal to the overall efficiency of the column generation method.The contribution of this thesis is two-fold. First, we concentrate on the improvements of the subproblem by attaching a preprocessing algorithm at the very begining of the problem, and transforming RCSP into shortest path problem (SPP). This process was previously suggested in the literature and dened as three stage approach (TSA), in which the network reduction, network expansion and iterative solution stages are involved. In this thesis, TSA is modied by eliminating some steps in some stages in order to make this method more compatible for airline crew scheduling applications. Second, TSA in vectorial form (TSA-V), which is developed in this thesis, is proposed in which the network reduction stage is processed by vectorial comparison of the resources. Computational results also show that TSA-V is more effective in eliminating the infeasible edges. The efficiencies of both methods are also compared based on the conducted experiments at the computational study part.
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
- Sürdürülebilir toplu konut yerleşmesi tasarımı için Pareto genetik algoritmaya dayalı bir model önerisi: SSPM
A model for sustainable site layout design with pareto genetic algorithm: SSPM
YAZGI AKSOY
- Deprem etkisindeki yapıların aktif kontrolü
Active control of structures under seismic excitation
BEKİR BORA GÖZÜKIZIL
- A new approach to crew pairing problem with parallelization
Ekip eşleme problemine paralel yöntemle yeni bir yaklaşım
OSMAN ÖZGÜN ALTUNKAYA
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ NAZIM KEMAL ÜRE
- An application of the vehicle routing problem to a glass manufacturing firm
Bir cam imalat firması için araç rotalama problemi uygulaması
İPEK SEYRAN
Yüksek Lisans
İngilizce
2006
Endüstri ve Endüstri MühendisliğiÇankaya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ÜMİT YÜCEER