Demiryolu ekip çizelgeleme ve ekip atama problemi için bir uygulama
A case study for railway crew scheduling and crew rostering problem
Yazar: YÜKSEL ÜSTÜNDAĞ
Danışman: PROF. DR. NİHAT YÜZÜGÜLLÜ
Eskişehir Osmangazi Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Yöneylem Araştırması Bilim Dalı
Derece: Yüksek Lisans, 2010
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Ekip çizelgeleme ve ekip atama problemlerinin her biri, demiryolu işletim planlamasında karşılaşılan en karmaşık ve zor problemlerdendir. Personel maliyetleri demiryolu şirketinin kontrol edebileceği büyük giderlerden birisi olduğu için, ekipleri tren seferlerine etkin olarak atamak, demiryolu işletim planlamasında önemli rol oynar. Ekip çizelgeleme probleminde, her tren seferinin en az bir ekip eşleştirmesi tarafından kapsandığı en düşük maliyetli eşleştirmeler kümesi bulunmaya çalışılır. Ancak tüm olası ekip eşleştirmelerini oluşturmak oldukça zordur. Bu çalışmada, ekip çizelgeleme probleminin çözümünde sütun oluşturma algoritması ek olarak, ekip atama probleminin çözümünde ise DELPHI programlama dili ile yazılmış olan rassal atama yöntemi kullanılmıştır. Ekip atama problemi için rassal bir sezgisel kullanmanın gerekçesi, bu sezgiselin kısa sürede en iyiye yakın çözümler üretebilmesidir. Ekip çizelgelemede ana problem küme kapsama problemi, alt problem ise en kısa yol problemi olarak modellenmiştir. Ana problem ve alt problem ardıştırmalı olarak çözülmüştür. Ana problemin çözümünden elde edilen tren seferlerine ilişkin ikil değerler alt problemin amaç fonksiyonunda kullanılmıştır. Ekip çizelgeleme probleminin çözümü, rassal ekip atama probleminin girdileri olarak kullanılmıştır. Ekipler sezgisel olarak atanırken, TCDD'nin belirlediği üç farklı tren sınıfı için personellerin; eğitim durumu, yaş, hizmet süresi ve almış oldukları idari cezalar göz önüne alınmıştır. Önerilen algoritma Türkiye Cumhuriyeti Devlet Demiryollarından alınan verilere uygulanmıştır ve sonuçlar gösterilmiştir.

Abstract:
Crew scheduling and crew assignment problems are both most complicated and hardest problems encountered in railway planning. The assignment of the crew effectively is very important for railway planning, as personnel costs are the great values that can be controlled by the railway firm. In crew scheduling problem, the goal is to find the minimum costly set of pairings in that each journey leg is covered at least by one crew pairing. However, generating all possible crew pairings are quite difficult. In this study, column generation algorithm is used for solving crew scheduling problem in addition, random assignment method that is coded by DELPHI programming language is used for solving the crew assignment problem. The reason for using a heuristic to solve the crew assignment is that this heuristic can generate solutions, which are very close to the optimum solutions. The master problem is formulated as a set covering problem while the subproblem is formulated as a shortest path problem. The master and sub-problems are solved iteratively. Dual values obtained from the solution of the master problem is used in the objective function of the sub-problem. The solutions obtained for crew scheduling are used as inputs for the crew assignment problem. While assigning crew randomly; the education, age, service time and administrative penalties of the crew are taken into account for the three different class of the trains, which are determined by TCDD. The suggested algorithm is applied to the real datas that are taken from the TCDD and the solutions are shown.