A feasible timetable generator simulation modelling framework and simulation integrated genetic and hybrid genetic algorithms for train scheduling problem

Abstract

Demiryolu sistemlerinin yönetiminde önemli bir problem tren çizelgeleme problemidir (TrnÇzgPrb). Bu bir küme tren için ray kapasitelerini ihlal etmeyen ve eylemsel kısıtları tatmin eden bir tarife belirleme problemidir. Bu tezde, bir olurlu tarife üretici stokastik benzetim modelleme yapısı geliştirilmiştir. Amaç sistemdeki tüm trenler için bir olurlu tren tarifesi elde etmektir. Olurlu tren tarifesi hesaplanmış ortalama tren seyahat süresi ile birlikte tüm ziyaret edilen istasyonlar için tren geliş ve hareket zamanlarını içerir. Bir olurlu tarife elde etmenin yanında, ortalama tren seyahat süresini minimize etmek amacıyla melez algoritmalar geliştirilmiştir. İlk melez, benzetim ve genetik algoritma (GA) bütünleştirilerek elde edilmiştir, diğer üç melez ise üç yerel arama algoritmasından her birinin benzetimle bütünleşik GA içerisine gömülmesiyle elde edilmiştir. Bu tezde geliştirilen benzetim modelleme yapısı gerçek bir demiryolu hat sisteminden esinlenmiş altyapı tabanlı bir tek ray koridorlu TrnÇzgPrb için uygulanmıştır. Benzetim tarafından bulunan olurlu tarifeler kümesi geliştirilen melez GA'ların başlangıç çözüm alanını oluşturmaktadır. Bu melez GA'lar eniyi ortalama tren seyahat süresiyle birlikte bir olurlu tren tarifesi elde etmek için çalıştırılmıştır. Melez GA'lar tarafından bulunan en iyi ortalama tren seyahat süreleri karşılaştırılmış ve sonuçlar tartışılmıştır. Bu tez tren çizelgeleme/tarife oluşturma problemine odaklandığı halde, geliştirilen benzetimle bütünleşik yapı, eğer gerçek zamanlı veriler ile beslenebilirse, aynı zamanda yeniden tren çizelgeleme/sevk etme problemi için de kullanılabilir. An important problem in management of railway systems is train scheduling problem (TrnSchPrb). This is the problem of determining a timetable for a set of trains that does not violate track capacities and satisfies operational constraints. In this thesis, a feasible timetable generator stochastic simulation modelling framework is developed. The objective is to obtain a feasible train timetable for all trains in the system. The feasible train timetable includes train arrival and departure times at all visited stations with calculated average train travel time. In addition to obtaining a feasible timetable, hybrid algorithms are developed with the objective of minimizing the average train travel time. The first hybrid is obtained by integrating simulation and genetic algorithm (GA), and the other three hybrids are obtained by embedding each of three local search algorithms in simulation integrated GA. The simulation modelling framework developed in this thesis is implemented for a TrnSchPrb based on an infrastructure which was inspired by a real railway line system with single track corridor. The set of feasible timetables found by simulation forms the initial solution space of the developed hybrid GAs. These hybrid GAs are run for getting a feasible train timetable with optimum average train travel time. The optimum average train travel times found by the hybrid GAs are compared, and the results are discussed. Although this thesis focuses on train scheduling/timetabling problem, the developed simulation integrated framework can also be used for train rescheduling/dispatching problem if this framework can be fed by real time data.