Improvements in column generation methods to solve large scale airline crew scheduling problems
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye
Tezin Onay Tarihi: 2010
Tezin Dili: İngilizce
Öğrenci: IŞIK BİÇER
Danışman: TANER BİLGİÇ
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Ö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.