Railway traffic optimization by advanced scheduling and rerouting algorithms

Railway traffic optimization by advanced 

scheduling   and rerouting algorithms

Why study algorithms

Abstract

In the last years, real-time railway traffic optimization experienced an increasing interest due to the expected growth of traffic and the limited possibilities of enhancing the infrastructure, which ask for a more efficient use of resources and the application of more advanced decision support tools. This paper presents a computerized train dispatching system, called ROMA (Railway traffic Optimization by Means of Alternative graphs), for supporting railway traffic controllers during operations. Innovative scheduling and rerouting algorithms have been developed in order to globally optimize disturbed railway traffic conditions. ROMA can anticipate the evolution of traffic, including the propagation of delays in a regional railway network, and can estimate the effects of different dispatching measures during a period of about 15 minutes ahead. Therefore, ROMA would enable traffic controllers to frequently perform incremental changes to the actual timetable to accommodate changes in traffic patterns due to disturbances, such as train delays and blocked tracks. An extensive computational study is carried out, based on a dispatching area of the Dutch railway network, to show the high potential of our train dispatching system as a support tool to improve punctuality.

Introduction

Regulation of railway traffic aims at ensuring safe, seamless and as much as possible punctual train operations. Due to the strict time limits for computing a new timetable in presence of disturbances, train dispatchers usually perform manually only a few timetable modifications while the efficiency of the chosen measures is often unknown. Some computerized dispatching support systems have been developed, so far, which can provide good solutions for small instances and simple perturbations.

Advanced real-time traffic management systems should take into account the whole traffic in a larger area, detecting future conflicts among train movements (that have direct impact on the level of punctuality), automatically calculating optimal traffic flow and suggesting possible change of orders or routes to the dispatcher, as well as displaying advisory speeds to the train drivers. This kind of systems must operate sufficiently in advance with the aim to correctly quantify the effects of different dispatching measures and enable traffic controllers to frequently perform incremental modifications of the actual timetable in order to adapt to sudden traffic disturbances.

 Here, we compare two dispatching support systems. The first is based on local information, a common practice in railway real-time management, and is similar to the ARI system used in the Netherlands. The second makes use of advanced scheduling and rerouting algorithms that have been implemented in the recently developed ROMA (Railway traffic Optimization by Means of Alternative graphs) software, an optimization tool based on global information

ROMA dispatching support system

• Train speed coordination module : Given the schedule computed by the previous module, check if the solution is consistent with the train dynamics and if the blocking time of each train in each block section overlaps with those of the following trains, i.e., if the distance headway between two or more trains is not respected. In case of an overlap of blocking times, perform an iterative procedure to compute acceptable train speed profiles on the basis of the actual signal aspects, infrastructure and rolling stock characteristics.

 The data loading module (i.e., subproblem (i)) is in charge to gather all the information, which is required by the other modules. This module loads static data (off-line data such as infrastructure and timetable information) and dynamic data (train detection and other real-time information that varies in time) from the field. The operational timetable contains a list of arrival/departure times for a set of relevant points in the network, including all the station platforms visited by each train. The infrastructure consists of a set of available block sections delimited by signals. Infrastructure data includes the status and length of each block section and other characteristics, such as speed limitations and the traversing direction. The data associated with each train includes speed and position at its entrance of the network, acceleration and braking curves (calculated on the basis of traction force/speed diagrams and maximum speeds) and a prioritized list of routing options (the most evident and frequently used alternative routes are selected by the dispatcher and given to the dispatching support system). At any time a route, i.e., a sequence of block sections, is feasible if none of its block section is blocked. Finally, the blocking time for each pair (train, block section) is computed by this module on the basis of current rolling stock characteristics and infrastructure data.

This module is dedicated to perform the following sub-tasks: (a) given a feasible route for each train, define a schedule for each train, i.e., define its entrance time on each block section; (b) given the train schedules, search for routing options potentially leading to better schedules. The two sub-tasks are executed iteratively until no improvement is possible within a time limit of computation

As for solution algorithms in ROMA dispatching system, task (a) can be achieved by two optional scheduling algorithms. Both algorithms require that a routing for each train is given and a fixed traversing time of each block section is known in advance, except for a possible additional waiting time between operations in order to solve train conflicts. The first scheduling algorithm is the branch and bound algorithm described in which is able to sequencing instances of practical size within short computation times. This is an advanced scheduling algorithm with the aim of

Minimizing the propagation of train delays. The second scheduling algorithm, described in simulates the practice of traffic management adopted in the Netherlands. This algorithm is based on the ARI system a semi-automated system which detects and solves train conflicts one at a time. Our implementation is a completely automated version of the ARI system, simulating the behaviour of the human dispatchers using priority rules.

Task can be achieved by a tabu search algorithm (TS) in order to select an alternative route for some trains with the aim of further reducing train delays .Given the schedule of task, the procedure analyses all the feasible routes of each train, searching for a train route that enables a reduction of train delays and a better use of the available rail capacity in presence of timetable disturbances. Whenever a better schedule is found, the new route is set as default route and the search is repeated, until no improving routes are found or a given time limit is reached.

In the ROMA dispatching support system, the solution to sub problem presents deterministic blocking and waiting times and thus does not model explicitly the dynamic consequences of braking and subsequent acceleration imposed to avoid headway conflicts between trains running in the network. For the Dutch signalling system, this means that the traversing time of each train on each block section is computed assuming green signal aspects.

Conclusions

The real time train dispatching is in charge of solving disturbances in the traffic flow adjusting the time table of each train in terms of routing and timing. The main goal is to minimize consecutive delays (i.e., the difference between the arrival time at each relevant point in the new schedule and that in the timetable) while satisfying the traffic regulation constraints and the compatibility with the real-time position of each train. The computational results show the effectiveness of using real-time railway traffic optimization algorithms with respect to simple and local dispatching procedures. We now point out the potential and limitations of the proposed dispatching support system.