trenolab works to remain a real laboratory of railway operations, in which the processes and tools are relentlessly improved. Thus applied research is part of our everyday day life.

In it, we combine the skills learned in the years of PhD and research contracts with the experience gained working on real projects to focus our activity on the challenges that railways face.

We believe that sharing the results of research helps progress in railways, and thus are glad to present them in journals and conferences. Additionally, we support sponsor conferences and other events.

section.png

Automatic timetabling

trenolab is currently developing and updating a tool for automatic timetabling, to be included in the functionalities offered by the TRENOplus module.

The ATMO (Automatic Timetabler with Multiple Objectives) algorithmic framework has been developed to effectively produce Pareto-optimal sets of timetables optimised according to KPIs as, for instance, the travel time, the energy consumption or the number of scheduled trains. ATMO exploits an original Multi-Objective Ant Colony Optimisation algorithm to perform a quick exploration of the solution space, whose results (timetables) are then further refined by an exact Mixed Integer Linear Programming formulation.

As far as we know, the integration between these two types of algorithms is a novel contribution to the field of the solution approaches for the Train Timetabling Problem. The core of the ATMO framework has been developed within the research project “Tools for mathematical optimisation of strategic railway timetable models” funded by Jernbanedirektoratet (Norway) in 2021, and it’s currently under constant updating.

section.png

Analysis of operational data

Understanding how real train operate is a key basis to develop accurate simulations. At trenolab, we receive and analyse data logged on the infrastructure as well as on board of trains.

On-board collected data such as GPS or PTMR are used to fine-tune the behaviour of virtual drivers, while track circuit data are used as input for delays.

Additionally, passenger data coming from AFC systems are used to estimate dynamically and with highest accuracy the number of passengers that would board on each train as function of the time of the day, its delays and the delay of the previous services.

section.png

Microscopic simulation

trenolab leads the way towards a microscopic simulation that is accurate and fast enough to become part of the normal planning process.

To reach this ambitious goal, we work in parallel to: reduce the computation times, streamline the workflow for model preparation and calibration, and increase the accuracy in the representation of humean factors (as described in the paragraph on Analysis of operational data).

One key example of this continuous and successful process is the capability of trenissimo to split the simulation load not only among all computers connected to a local network or a cloud, reducing the simulation time to justa fraction of other tools.

section.jpg

Crew rostering

The TRENOcrew module takes advantage of a novel algorithm for solving the rail Crew Scheduling Problem (CSP). The latter consists in defining a minimal set of daily train crew duties which cover a given set of train services, and can be modelled as an extension of a Capacitated Multi-Depot Vehicle Routing Problem.

For TRENOcrew we adopted a novel Ant Colony Optimisation meta-heuristic algorithm to effectively solve CSP instances of up to medium-large size (some hundreds of daily courses). Decomposition techniques are currently under design and development in order to tackle also large-size instances.

Moreover, further research is carried on to extend the proposed algorithm to solve the Crew Scheduling and Rostering Problem, featuring the additional task to calculate feasible rosters (sequence of daily duties assigned to the same driver over a monthly - or more - period) for the generated daily duties.

Our key research streams

12 Nov 2021

A multi-objective framework for strategic railway timetabling: integration of ant colony optimisation and mixed integer programming

The paper presents an algorithmic framework to perform automatic timetabling, developed within the research project Tools for mathematical optimisation of strategic railway timetable models funded by the Norwegian Railway Directorate and carried out by Trenolab SRLS and Gustave Eiffel University.

A prototype tool to automatically generate timetable drafts is presented, intended to help planners to perform such tasks as capacity studies and strategic timetable planning.

The paper describes the algorithmic core of the tool, called Automatic Timetabler with Multiple Objectives (ATMO). It implements a Paretian multi-objective approach, which returns the user a set of timetables representing the optimal trade-off according to given Key Performance Indicators. ATMO is composed by a Multi-Objective Ant Colony Optimisation (MOACO) algorithm integrated with a Mixed Integer Linear Programming (MILP) formulation.

MOACO performs a fast-but-coarse exploration of the solution space, populating and maintaining a set of Pareto-Optimal timetables.  The timetables generated by MOACO are then fed to a MILP formulation which performs a further refinement, finally providing feasible, high-quality timetables.

The paper describes the framework from an algorithmic perspective, explaining how the proposed approach represents a novel contribution to the field of Automatic Timetabling methods. A series of application tests are discussed as well, based on case studies driven from real practice in Norway.

3 Nov 2021

Trønderbanen Regional Rail 2024 Plan – Using Simulation to Optimize Infrastructure Investment

This paper presents two methods designed to provide quantitative data for analysing the socio-economic impacts of rail network improvements developed for the Finnish Transport Agency. The first is a capacity estimation method; it adapts the UIC 406 method to the characteristics of the Finnish rail network. The second method estimates delay propagation based on the key characteristics of lines; in this case distinct formulas were developed using regression for single- and double-track lines. The proposed methods were evaluated based on actual and simulated data from Finland and the UK. They provide network saturation and delay data for evaluation of capital improvements by network managers. The study results were approved and adopted by the Finnish Transport Agency.

3 Nov 2021

A two-stage framework for strategic railway timetabling based on multi-objective ant colony optimization

The paper presents the algorithmic architecture for automatic timetable generation which is actually under development within the research project “Tools for mathematical optimisation of strategic railway timetable models” funded by the Norwegian Railway Directorate. Main design choices and alternatives are presented and discussed. The framework is composed by two main components, which tackle the Train Timetabling Problem in a macroscopic model of infrastructure and operations.

The first stage is a Multi-Objective Ant Colony Optimisation (MOACO) algorithm which produces a Pareto Optimal Set of solutions. These are timetables optimised with respect to four main objectives, namely: the total travel time, the total energy consumption, the timetable robustness and the total number of scheduled trains. MOACO treats conflict constraints as soft ones and produces strictly periodic traffic patterns.

The second stage is a Mixed Integer Linear Programming (MILP) formulation, which refines timetables produced by MOACO. MILP solutions are conflict-free timetables and can profit of given tolerances on trains periodicity.

30 Sep 2021

Seamless integration of microsimulations and ant colonies: a new tool for automatic timetable generation

Reducing the time spent for designing timetable drafts by at the same time ensuring the highest accuracy of results is crucial in strategic planning, where it is required to develop and evaluate multiple timetable alternatives.

High accuracy is provided by microsimulation, which our original workflow exploits to automatically arrange complete input datasets for a novel multi-objective ACO algorithm for railway timetabling. This presentation will introduce the proposed automatic timetabling tool illustrating its application at the Norwegian Railway Directorate.

16 Sep 2021

Railway freight node capacity evaluation: a timetable-saturation approach and its application to the Novara freight terminal

The paper presents a timetable-based approach to assess the capacity of a railway freight node, based on the microscopic simulation and saturation of the timetable. Saturation is performed by scheduling additional saturation train paths without introducing any traffic conflict, while respecting the required technical and operational constraints, until no more paths can be added. The approach is applied to analyse the potential effects on capacity of some infrastructure improvements planned on the rail freight node of Novara, Italy.

Capacity is evaluated by means of two KPIs computed on saturated timetables: the number of daily pairs of saturation freight trains and the infrastructure Occupancy Time Rate (OTR). The first KPI represents an absolute estimation of the capacity, considering also the presence of buffer times. OTR is computed by the UIC 406R link fiche UIC compression method and it is used to identify local bottlenecks. A method is presented, integrating a Mixed Integer Linear Programming formulation (which performs the actual scheduling of trains into a feasible timetable at a microscopic level) with a saturation strategy layer. The latter considers priorities between the different network areas and the train types to be used during the saturation process.

Relevant results reveal that using a microscopic model to schedule traffic flows on a complex railway node allows for a good accuracy of the timetable, but at a high computational cost.

12 Mar 2020

Reducing Delays on High-Density Railway Lines: London–Shenfield Case Study

This case study describes the development of a new timetable designed to reduce delays on the London–Shenfield regional railway line in the United Kingdom (UK). Reducing delays on high-density railway lines is challenging because frequent service makes it difficult to identify the root cause of delays and there is limited ability to solve delay problems by adding buffer times to timetables. On the other hand, it is very important to reduce delays on high-density lines since they affect many passengers and because a delay on one train can easily affect following trains. In this study, detailed railway operational data was used together with Oyster card ridership data to identify the root cause of delays and help develop an alternative timetable. The alternative timetable was tested and refined using stochastic simulation. The new timetable was placed in service during 2016 and led to a significant reduction in delays: punctuality within 5-min of scheduled arrival time increased by 6.2% during the most critical hour of the morning peak period. The paper describes the methodology, its application, study results, and transferability.

17 Jun 2019

Understanding the Impact of Driving Styles on Reactionary Subthreshold Delays on a Fixed Block Signalling System

Train punctuality in the UK is focussed on measuring the time trains are booked to pass a fixed point and when that event occurs. What is not considered in this measurement of performance is whether the capacity of the system is being optimised. It is posited in this paper that performance needs to consider how closely the delivered train service matches the minimum time signals should be red for that pattern of train services. Any changes to the operation of the system that cause the signals to be red for longer than necessary will decrease system capacity and this will have a detrimental effect on delay per incident. This paper compares on-train data recorders (OTDR) from 2002 and 2018. It shows that average braking rates have declined from 4%g to 3.5%g. This will typically add 4 seconds per stop. Train lengths in the UK have also increased in this time, with a typical train length increase being from 8 to 10 cars. If the slower braking curves and longer trains are combined, and a hypothetical block joint positioned 300m from a stopping point, it can be shown that the signal in rear will take 8 seconds longer to clear on average today than in 2002. While the impact of these changes on time at destination can be easily demonstrated using distance/time graphs, the effect on the signalling system is more complex. The simulation system trenissimo has been used to show that the effect on a system of longer trains and slower braking curves is [x], with the system responding in a non-linear way to very small changes in train operations. It is posited that this is key reason for the increase in delay per incident currently being seen in the UK.

17 Jun 2019

Punctuality and Capacity in Railway Investment: A Socio-Economic Assessment for Finland

This paper presents two methods designed to provide quantitative data for analysing the socio-economic impacts of rail network improvements developed for the Finnish Transport Agency. The first is a capacity estimation method; it adapts the UIC 406 method to the characteristics of the Finnish rail network. The second method estimates delay propagation based on the key characteristics of lines; in this case distinct formulas were developed using regression for single- and double-track lines. The proposed methods were evaluated based on actual and simulated data from Finland and the UK. They provide network saturation and delay data for evaluation of capital improvements by network managers. The study results were approved and adopted by the Finnish Transport Agency.

Read more
1 Mar 2018

Simulation of Rail Operations

From the long-term design of new infrastructure to the validation of timetables planners need accurate and reliable support tools that allow understand- ing the effect of their decisions. Microscopic simulation has gradually become widespread, since it allows considering not only the characteristics of infrastructure, signalling and rolling stock, but also human factors. In spite of this success and of the increasing quality of commercial simulation software, the setting up of a simulation requires time and accuracy to ensure that all elements are represented correctly.

6 Apr 2017

Stability of saturated timetables: the influence of buffer times

In railway, the saturation problem consists in scheduling extra train paths within an existing timetable, intended to be a fixed reference. Inserting extra train paths reduces the global timetable stability, if compared to that of the not-saturated timetable.

A compromise should therefore be sought, introducing constraints on the number and characteristics of the saturating paths in order to keep the stability of saturated timetables within a desired range. In this study, this task is performed by imposing that saturating paths are separated by a given buffer time. The study aims to provide some figures about the way in which buffer time affects the number of saturating paths and the stability of the resulting timetable. We saturate a real timetable (concerning a 70 km long French railway) using a Mixed Integer Linear Programming algorithm, imposing seven increasing values of buffer time.

The stability of the saturated timetables is evaluated through OpenTrack™ simulations with perturbed traffic conditions. The simulations are carried out with two perturbation scenarios. In this way the influence on stability of the parameters combination used in saturation is assessed. Results are presented and discussed, highlighting the role of the buffer time and of the type of saturating paths in providing stable saturated timetables.

12 Sep 2014

Railway Timetabling & Operations: Statistical Analysis of Train Delays and Movements

In Chapter 11, statistical analysis of train delays and movements is focussed on enabling a deep insight into their variability. Based on this, suitable strategies can be applied to reduce delays, improve punctuality and save energy. Moreover, the statistical analysis will result in appropriate distribution models of train delays and a detailed representation of stochastic running times for precisely identifying potential track conflicts and estimating the propagation of train delays with either analytical models or simulation tools. This precise identification and estimation is always required in the evaluation of timetable robustness and rescheduling optimality.

12 Sep 2014

Railway Timetabling & Operations: Simulation

From the long-term design of new infrastructure to the validation of timetables planners need accurate and reliable support tools that allow understanding the effect of their decisions. Microscopic simulation has gradually become widespread, since it allows considering not only the characteristics of infrastructure, signalling and rolling stock, but also human factors. In spite of this success and of the increasing quality of commercial simulation software, the setting up of a simulation requires time and accuracy to ensure that all elements are represented correctly.

1 Aug 2014

Automatic generation of railway timetables based on a mesoscopic infrastructure model

This paper presents a large-scale application of a heuristic timetabling algorithm on a mesoscopic description of the railway network infrastructures.

We consider a mesoscopic model as it allows a significantly higher accuracy compared to the macroscopic models used in many scientific works. Specifically our mesoscopic model allows an estimation of the headway times and of the conflicts on lines and stations as well as a calculation of running times and time-losses performed with the same detail enabled by simulation models. In addition, in order to maximize the accuracy in the definition of the timetable, various parameters can be defined for each train, including the buffer times, the priority and the allowances.

The model is applied to the rail network of the North-East of Italy. It is tested under different demand conditions, for example considering an increase of the demand for freight slots or a different structure of regional services. Moreover, it is used to obtain a rough estimate of the maximum capacity for freight trains combined to fixed passenger services and the effects of infrastructure improvements.

7 Nov 2011

A method for using stochastic blocking times to improve timetable planning

This paper presents a method for introducing stochastic blocking times to support timetable planning. The approach redefines timetable conflicts by associating a probability with each conflict estimated as a function of process-time variability. The method consists of calibrating a motion equation using data collected on board the train. The calibration set can then be used to compute the stochastic behaviour of individual trains or in micro-simulation models. In this research the behaviour of individual trains was investigated and tested. The method consists of repeatedly simulating an individual train run on a microscopic infrastructure model using the estimated performance parameter distributions obtained in the calibration. The resulting blocking times are stored and depicted in a time–distance diagram using transparencies to represent each run. The diagram presents a wider occupation staircase, in which colour intensity is proportional to the occupation probability. When a second train is inserted into the diagram the probabilistic occupation steps of the two trains can overlap, showing the conflict probability. The software also computes and displays a series of data including the probability of conflicts. The method has been tested on the mixed-traffic, double-track line between Trieste and Venice. The results were a good representation of train blocking times over several operational days.