A General Simulation Modelling Framework for Train Timetabling Problem

A General Simulation Modelling Framework for Train Timetabling Problem

Özgür Yalçınkaya (Dokuz Eylül University, Turkey)
DOI: 10.4018/978-1-5225-0084-1.ch015
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

One of the most important problems encountered and needed to be solved in railway systems is train timetabling (scheduling) problem. This is the problem of determining a feasible timetable for sets of trains which does not violate track capacities and additionally satisfies some operational constraints of the railway system. In this chapter, a feasible timetable generator framework for stochastic simulation modelling is introduced. The objective is to obtain a feasible train timetable for all trains in the railway system, which includes train arrival and departure times at all visited stations and calculated average train travel time. Although this chapter focuses on train timetabling (scheduling) problem, the developed general framework can also be used for train dispatching (rescheduling) problem if the model can be fed by the real-time data. Since, the developed simulation model includes stochastic events, and it can easily cope with the disturbances that occur in the railway systems, it can be used for dispatching.
Chapter Preview
Top

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 jT, a starting station fj and an ending station lj (lj > fj) are given. Let Sj = {fj, …, lj} ⊆ S be the ordered set of stations visited by train j. A timetable defines, for each train jT, the arrival and departure times for the stations fj, fj+1, …lj−1, lj. 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.

Key Terms in this Chapter

Dwell Time: The elapsed time that a train stops in a station for boarding and alighting events.

Simulation Model: A representation of a system that can be used to mimic the processes of the system under varying circumstances. It is usually operated subject to stochastic disturbances.

Schedule: The designation of train description, day, route, speed, arrival and departure times of a train.

Feasible Solution: An assignment of values to the decision variables such that none of the constraints is violated.

Modelling of Railway Infrastructure: The transition of real world railway infrastructure into a computerized infrastructure model.

Headway: The space or time interval between two successive trains.

Timetable: A document that contains the schedules of all trains of a line.

Complete Chapter List

Search this Book:
Reset