A General Simulation Modelling Framework for Train Timetabling Problem

Introduction

Management of railway systems is an important issue of transport systems. One of the important problems in management of railway systems is the train timetabling (scheduling) problem. This is the problem of determining a timetable for sets of trains that does not violate track capacities and satisfy some operational constraints of the railway system. Several variations of the problem can be considered, mainly depending on the objective function to be optimized, decision variables, constraints and complexity of the studied railway network. Several names have been given to the problem widely using three-word phrases:

• beginning with Train / Railway

• going on with Timetabling / Scheduling / Dispatching / Rescheduling / Planning / Pathing

• and ending with Problem

• words with a few exceptions.

A general most common train timetabling problem in the literature considers a single track linking two major stations with a number of intermediate stations in between (Caprara et al., 2002). It is assumed that S = {1, …, s} represents the set of stations, numbered according to the order in which they appear along the rail line. In particular, 1 and s denote the initial and final stations, respectively. Analogously, it is assumed that T = {1, …, t} denotes the set of trains which are candidate to be run in a given time horizon. For each train j ∈ T, a starting station f_j and an ending station l_j (l_j > f_j) are given. Let S^j = {f_j, …, l_j} ⊆ S be the ordered set of stations visited by train j. A timetable defines, for each train j ∈ T, the arrival and departure times for the stations f_j, f_j+1, …l_j−1, l_j. The running time of train j in the timetable is the time elapsed between origin station and destination station of the train (Caprara et al., 2002). This general problem can be more sophisticated by adding some real life behaviour of railway systems or relaxing some assumptions made related with the railway system under consideration.

The problem has been studied by researchers and so far many efforts have been spent on it. In early years, due to the limitations of computers’ abilities and the complexity of the problem, the problem was relaxed by unrealistic assumptions and generally deterministic models were studied. Depending on the increasing computer capabilities more realistic models were developed. Although simulation for modelling has been used in some articles, none of them includes a comprehensive framework. This has been the main motivation for the authors to develop a feasible timetable generator simulation modelling framework.

In this chapter, a feasible timetable generator framework for stochastic simulation modelling is developed for obtaining a feasible train timetable for all trains in a railway system. This framework includes train arrival and departure times for all stations visited by each train and calculated average train travel time. A general stochastic simulation modelling framework is developed and explained step by step in order to guide to researchers who aim to develop a simulation model of railway transportation systems. By using this framework all the railway systems can be modelled with only problem and infrastructure specific modifications and feasible solutions are easily obtained. In order to avoid a deadlock, a general blockage preventive algorithm is also developed and embedded into the simulation model.

In next section the literature on the problem is given. After that, the simulation modelling framework is demonstrated in detail on a hypothetic problem. Next, the obtained results are discussed. Concluding remarks and future work directions are exhibited in the last parts of the chapter.