Tez No	İndirme	Tez Künye	Durumu
565959		A new approach to crew pairing problem with parallelization / Ekip eşleme problemine paralel yöntemle yeni bir yaklaşım Yazar:OSMAN ÖZGÜN ALTUNKAYA Danışman: DR. ÖĞR. ÜYESİ NAZIM KEMAL ÜRE Yer Bilgisi: İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Uçak ve Uzay Mühendisliği Ana Bilim Dalı / Uçak ve Uzay Mühendisliği Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering ; Matematik = Mathematics Dizin:	Onaylandı Yüksek Lisans İngilizce 2019 75 s.
Hava yolları operasyonları ile ilgili bir sürü alt problem olup, ekip zaman çizelgesi genel olarak iki alt problemde çözülür: Ekip eşleme ve ekip atama. Bu iki alt problem de başlı başına kompleks ve ayrı incelenmesi gereken problem olduğu için, bu çalışmada ekip eşleme problemi incelenmiştir. Aynı zamanda bu çalışmada, önceki metodlara ek olarak, bunların modifiye edilmiş varyasyonları geliştirilmi¸stir. Ekip eşleme problemi, onlarca yıllardır literatürde uygunlanıp, hâlâ geliştirilmekte olan bir problem olup, temelinde havacılık otoriterlerinin koymuş olduğu kurallara ˘ bağlı kalıp, en uygun bir şekilde ekip eşleme yapmaktır. Eski metodlarda, ve ˘ geliştirilen metodlarda da kullanılan ortak ve en etkili metod ise sütün üretme metodudur. Bunun temel amacı ise, problem dogası gere ˘ gi çok büyük oldu ˘ gundan ˘ mütevellit, optimizasyon problemindeki bütün degi¸skenlerin bir anda üretilip ˘ çözülebilmesi mümkün olmamaktadır. Bunun yerine, sezgisel ve kesin metodlar kullanarak, bu optimizasyon probleminin iterasyon iterasyon çözülmesi algoritma çalışma süresi olarak çok fazla zaman kazandırmaktadır. 1970'ler ve 1980'lerden beri literatürde ve sanayide kullanılan metod da aynı zamanda bu sütun metodunun bir varyasyonu veya sütun üretme metodunun bir şekilde probleme entegre edilmesinden oluşmaktadır. Problemin ilk çözülmeye başlandıgı yıllarda, çözümler genellikle daha ˘ fazla sezgisel, ve dolayısıyla global olarak en iyi sonucu garanti vermeyen, ve de kullanılan işlemcilerden kaynaklı hem yavaş, hem de paralel olarak çalışmayan algoritmalar kullanılıyordu. Hava trafiğinin büyümesi ve günlük, haftalık ve aylık uçuş ˘ sayılarının çok fazla sayıda artması sebebi ile var olan algoritmalar paralelleştirilmeye, ve de global veya globale yakın bir sonucu vermek üzere geliştirilmeye başlandı. Her ne kadar teknolojinin gelişmesiyle, daha hızlı ve paralel işlem yapabilen işlemciler üretilse de, günümüzde orta-büyük havayolu firmalarının aylık 20,000 - 30,000 kadar uçuşu olabilmekte ve olası değişken sayısı bu tarz problemler için ˘ milyarlar mertebesinde olduğundan bu algoritmalar genellikle yine bütün değişkenleri ˘ üretmekten ziyade, en iyi değişkenleri en kısa sürede üretme ile ilgilendiler. ˘ Problem çok spesifik olduğu için öncelikle bu çalışmada kullanılan bazı terminolojiler ˘ belirtilmiş olup, daha sonradan problem ile ilgili küçük bir örnek verilip, değişkenlerin ˘ nasıl oluşturulduğu, optimizasyon probleminde kullanılan amaç fonksiyonunda ˘ bulunan ücret vektörünün her değişken için nasıl oluşturulduğu, problemin temel ˘ olarak nasıl çözüldüğü ve sonuçların neyi ifade ettiği yine örnekle gösterilmiştir. ˘ Aynı zamanda değişkenlerin oluşturulması için gerekli diğer adımlar, örneğin görev ˘ süresinin oluşturulması da anlatılmıştır, ve bunları oluştururuken kullanılan "ağ"˘ modelleri anlatılıp, avantajları ve dezavantajları sunulmuştur. Daha sonra, eski ve halen kullanılmakta olan metodlar bahsedilmiş olup, bunların dezavantajlarından bahsedilmiştir. Kullanılan bazı metodlar, örneğin genetik algoritmalar, hala çalışmakta da olsa, büyük ölçekli problemlerde çalışmadığından her ˘ zaman anlam ifade etmeyebiliyor. Bu çalışmada ise, yine sütün metodu kullanılmış olup, var olan sütun metodlardan farklı bir yolda değişken aranması geliştirilmiş olup, bu metodun paralelleştirilmesi ˘ anlatılmıştır. Geliştirilen metodlardan biri, en kısa yolu bulma metodu olan Dijkstra'nın algoritması ile beraber çalışması için geliştirilmiştir. Bunu yapabilmek için ise öncelikle sütün oluşturma yönteminde kullanılan alt problemin lineer program versiyonun çözülüp, buradan elde edilen asıl ve ikincil değerlerin anlamlandırılıp, ˘ buna yönlük problemi geliştireceği düşünülen uçuşların belirlenir. Bu seçme işlemi ˘ en iyi ilk 100 uçuş ¸seklinde yapılabileceği gibi, istatiksel olarak ikincil değerlerden ˘ oluşturulan bir dağılımdan da seçilebilir. Çalışmada da anlatıldığı üzere, bu seçme ˘ işlemini istatiksel olarak yapmanın, her ne kadar başlarda problemin yakınsama hızını biraz yavaşlatsa da, problemin spesifik uçuşlara egilimini azalttığı için, daha ˘ sonraki iterasyonlarda yakınsama işlemi hem gerçeklemiş, hem de daha hızlı olduğu˘ gözlenebiliyor. Seçilen bu uçuşlar, daha sonra görev süresilerinin belirlenmesinde kullanılır. Dijkstra'nın algoritmasının çalışması için bir başlangıc bir de bitiş düğümleri lazım ˘ olduğundan, bunlara uygun görevlerin bulunması gerekir. Algoritmadan çıkacak ˘ sonuç bizim için optimizasyonda kullanılacak değişken, yani eşlemeler olacağından, ˘ başlangıç ve biti¸s dügümlerinin de eşleştirme kurallarına uygun olması gerekir. ˘ Örneğin, başlangıç görev düğümünün ilk uçuşunun kalktığı havaalanı ile biti¸s görev ˘ düğümününün son uçuşunun indiği havaalanın aynı olması gerekir, ve aynı zamanda ˘ bu havaalanının havayolu şirketi tarafından daha önce belirlenen kabin üssü olması gerekir. Dolayısıyla, bu görev ikililerini (ba¸slangıç ve biti¸s) bulurken daha önceden bulmuş olduğumuz bu uçuşları içeren görevleri bulup, bunlardan kabin üssünde olanlar ˘ seçilir. Daha sonra, uygun yöntemlerle bu iki nokta arasında legal bir yol olup olmadığı aranır, ve böylelikle arama işlemine başlanabilir. Bunu yaparken, geleneksel ˘ metodlarda tek CPU veya ekip üssü sayısı kadar çekirdek kullanılabiliyorken, yeni algoritma ile paralel ve istenildiği kadar çekirdek kullanılabiliyor. Örne ˘ gin, e ˘ ger bir ˘ problemde 10 tane ekip üssü varsa, geleneksel algoritmalarda 10 tane çekirdek aynı anda i¸slem yapabilme kapasitesine sahip oluyor. Fakat bu metodun dogası gere ˘ gi, ˘ istenildigi kadar çekirdek (core) ve i¸s parçacacı ˘ gı (thread) kullanılabilmekte. Bu yeni ˘ algoritma ile mümkün kılınabiliyor çünkü önceki adımda bulunan ba¸slangıç ve biti¸s dügüm ikileleri birbirinden ba ˘ gımsız oldu ˘ gu için, aynı çekirdekde de seri olarak i¸slem ˘ görmek zorunda kalmıyor, böylelikle istenildigi kadar çekirdek kullanılabiliyor. Fakat, ˘ burada yine çekirdek sayısı ile algoritma çalışma süresinde optimizasyon yapılması gerekiyor, çünkü Amdahl'ın kanunu gereği çekirdek sayısının artması, direkt olarak ˘ algoritma süresinin artması anlamına gelmiyor her zaman. Örneğin, probleme göre, ˘ çekirdek sayısının artması problemin yavaşlaması anlamına bile gelebilmekte. O yüzden burada da kendi içinde minik bir optimizasyon problemi oluşmakta. Problemde değişkenleri bulmak için arama metodlarından derin öncelikli arama ˘ yerine Dijkstra veya Bellman-Ford algoritmaları kullanılmıştır, çünkü problemde amaç en kısa sürede en iyi değişkenleri oluşturmak olduğundan, ve bu kaliteli aramayı ˘ derin öncelikli aramada iki düğüm arası ağırlık olmadığından düzgün bir şekilde ˘ belirtilemiceğinden, düğüm arası ağırlıkları kullanabilen Dijkstra ve Bellman-Ford ˘ algoritmaları tercih edilmiştir. Daha sonra problem, belli bir boyutu açmamak koşuluyla adım adım tekrar yeni üretilen bu değişkenlerle çözülüp, yeni uçu¸slar aranır. 1 haftalık 400 uçu¸s verisi için algoritma 1 i¸s parçacığında 36 dakika gibi bir sürede ˘ çalı¸sırken, 18 iç parçacığında bu süre 2 dakika olup, 36 i¸s parçacığında 1.5 dakikaya ˘ kadar düşmektedir. Buradan da görüldüğü üzere, iş parçacığı sayısını arttırmak her ˘ ne kadar genel manada algoritmanın çalışma süresini kısaltsa da, bu kısaltma doğrusal ˘ olmayıp, belli bir sayı üzerinde de bir değere yakınsayabilmekte.
Airline operations have many subproblems, and crew scheduling is usually divided into two sub problems: Crew pairing and crew assignment. In this study, in addition to previous methods, modifications to those methods have been developed. Crew pairing problem has been in use in the literature for decades, and is in still the development stage where in its essence the main idea is to obtain the most optimal crew pairings by satisfying the rules enforced by authorities. In the previous methods, as well as the developed methods, the most significant method is the column generation method. The main idea of this method is that, since by the nature of the problem the problem is very large, generating all pairings and solving them at the same time is not possible. Instead, with some heuristic and exact methods, the small subproblem is solved repeatedly at each iteration. In addition to old methods, dual variables and with the improvement of high end CPUs have been made us of, and the results are given. Also, the method to transition from linear programming to integer programming is described, and some ways to relax the transition process is explained with examples.