Tren çizelgelemesi problemi
Train scheduling problem
Yazar: GÖKÇE AYDIN
Danışman: DOÇ. DR. İSMAİL ŞAHİN
Yıldız Teknik Üniversitesi / Fen Bilimleri Enstitüsü / İnşaat Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2009
Konu: Ulaşım = Transportation
Dizin: Demir yolları = Railways ; Demir yolu taşımacılığı = Railway transportation ; Tren = Train ; Çizelgeleme = Scheduling

Özet:
Bu çalışmada tren çizelgelemesi problemi üzerinde durulmuştur. Pratikteki uygulamada tren çizelgelemesi insanlar tarafından elle yapılmaktadır ve bu durum genelde alt optimum çizelgeler üretilmesine yol açmaktadır. Alt optimum çizelgeler demiryollarındaki hizmet düzeyinin düşmesine, yatırım ve işletim maliyetlerinin artmasına sebep olmaktadır. Bilgisayar temelli karar destek sistemlerinin kullanımıyla daha kaliteli çizelgeler üretilebilmesinin ve böylece demiryolu işletiminin hizmet düzeyinin ve ekonomik verimliliğinin arttırılabilmesinin mümkün olduğu vurgulanmıştır. Çalışmada öncelikli olarak tren çizelgelemesi problemi ile ilgili geniş bir literatür araştırmasına yer verilmiştir. Tren çizelgeleme etkinlikleri, kendi içerisinde taktik düzeyde çizelgeleme ve operasyonel düzeyde çizelgeleme olarak ikiye ayrılmaktadır. Taktik düzeyde çizelgeleme, dönemsel olarak hazırlanan işletim planının parçalarındandır. Operasyonel düzeyde çizelgeleme ise işletim sırasında meydana gelen gecikmeler sonucu işletim planından sapan sistem için yeniden bir işletim planı yapılmasıdır. Literatür araştırmasında taktik ve operasyonel çizelgeleme arasındaki farklılıklara ve bu farklılıkların bilgisayar destekli çizelgeleme modellerinin oluşturulması üzerindeki etkilerine değinilmiştir. Son bölümde, hayali bir hatta operasyonel çizelgeleme konusunda sayısal bir uygulama yapılmıştır. Çizelgeleme problemleri kombinatoryel problemler olduklarından, problem boyutu büyüdükçe çözüm süresinin kabul edilemez seviyelere ulaşması, bilgisayar destekli tren çizelgelemesinde karşılaşılan ve üstesinden gelinmeye çalışılan en önemli sorundur. Yapılan uygulamada tamsayı programlaması şeklinde formüle edilen problem için sezgisel bir indirgeme algoritması geliştirilmiştir. Bu algoritmanın geliştirilmesinde, günlük işletimde operasyonel çizelgelemeyi elle gerçekleştirmekte olan tren dispeçerlerinin karar davranışlarının modellemesinden faydalanılmış; ayrıca algoritmanın verdiği sonuçlar bu matematiksel modelin verdiği sonuçlarla karşılaştırılmıştır. Sonuçta, ele alınan hatta, modelin 5 ? 6 saatlik zaman penceresi içerisinde iki yönde toplam 8'e kadar tren içeren problemlerde dispeçerlere göre daha iyi çözümleri kabul edilebilir süreler içerisinde ürettiği görülmüştür.

Abstract:
This study is focused on train scheduling problem. In practice, train scheduling is done by humans by hand. This usually leads to suboptimal decisions, reducing level of service and cost ? effectiveness of rail transport. It is emphasized that use of computer ? based decision support systems may lead to higher ? quality decisions, which would enhance the level of service and economical efficiency of rail transport. In this study, a comprehensive survey of literature about train scheduling was done. Train scheduling is separated into two sub ? categories: Tactical scheduling and operational scheduling. Former involves preparing timetables that are valid for a pre ? determined period. Latter is generation of new schedules in case of real ? time delays. In the literature survey, differences between them and their effects on scheduling models was searched. In the last part, a numerical example on a hypothetical line was solved. Since scheduling problems are combinatorial problems, a huge increase of solution time with increasing problem size is a frustrating factor, so a heuristic problem reduction algorithm is devised for the integer programming model. This algorithm is based on mathematical modeling of decision behaviours of train dispatchers, who, in practice, do the operational scheduling by hand. Also, results of the integer programming model solution were compared to those produced by this mathematical model. It was seen that, the model can produce better results than train dispatchers do in a reasonable duration, for a traffic of up to 8 trains in two directions within 5 ? 6 hours of time window.