A View from Emerging Technology from the arXiv
Railway Timetables: A Tantalizing Connection with Gene Regulatory Networks
Future railway timetables could have more in common with gene regulatory networks than their steam-age antecedents.
If you’ve never spent quality time wondering about train timetabling, here’s your chance.
Working out how best to schedule trains across vast, complex networks is a hugely demanding computational task. The problem is to use to resources available (the number of trains, staff, tracks etc) in a way that maximises the utility of the system to the passengers.
Most timetables are generated by experienced humans, whose approach is first to cater for international and intercity services and then to stick as closely as possible to last year’s timetable, which is usually the result of years or decades of evolution.
Starting from scratch is simply too difficult and too risky. But it raises the possibility that the conventional evolutionary process has become stuck in a local minima while other more efficient solutions abound.
Now the steam-age problem of train timetabling is undergoing a 21st century revolution. In the last few years, however, computer scientists have begun to study other approaches such as how to build delay-resistant timetables. The problem for many networks is that connecting services have to wait for intercity trains to arrive before they can leave. So any delay to the intercity service can ripple through the network causing problems elsewhere.
To prevent these knock on effects, it is possible to build in to the timetable a certain amount of waiting time that can absorb small delays. This buffer increases the robustness of the timetable to delay propagation but increases passenger waiting time, thereby reducing the efficiency of the network.
How to balance robustness against efficiency is the fundamental problem for delay resistant timetabling.
Today, Christoph Fretter at Martin Luther University in Germany and a few buddies introduce an entirely new way to think about timetabling. Their idea is that if they think of the arrival of trains at a specific station as a periodic event, they can ignore the actual arrival times and think instead in terms of phases. So if the trains arrive at the same time they are in phase and if not, the differences in arrival times can be expressed as a proportion of the period until the next train.
Next, Fretter and co take the arrival times of all trains at a particular station over a 24 hour period and look for patterns in the phases. And they do this for every station in the network, first in the German long distance train network and then in equivalent networks in Austria, Norway, France and the Czech Republic.
It’s easy to imagine that the phases will be randomly distributed in these networks. And indeed they are at many stations. However, at intermediate-sized stations, the phases are highly synchronised.
Fretter and co then simulate how delays propagate through the network. They introduce a delay at each station and then see how it affects other stations.
The correlation they find is that delays have the biggest effect when introduced at the intermediate-sized stations that are highly synchronised.
That’s not so surprising, given that it’s at these stations that connecting trains usually have to wait for the intercity lines.
What’s interesting is that phase synchronisation gives timetablers an entirely new way to look at their task, one that maps neatly onto many problems being studied elsewhere.
For example, one big challenge is to understand how gene networks regulate the processes that go on in cells. Phase synchronisation plays a big role here as does the balance between efficiency and robustness.
One interesting finding is that in gene regulatory networks certain small patterns of connections between nodes seem to crop up far more often than chance can explain. These structures, called motifs, seem to help the networks by creating feed forward and feedback loops that make the network both more efficient and more robust.
Clearly, gene regulatory networks have been evolving for longer than railway timetables. Perhaps the absence of motifs in railway networks is a sign that they really are stuck in a local minima.
An interesting question that Fretter and co touch on is whether motif-like connections could one day play a role in railway networks. In practice this might mean trains that regularly shuttle a short distance between a few key stations. The implication is that such a service might stabilise the entire timetable.
Either way, the new science of train timetabling indicates that it’s possible that train timetables and even the structure of railway networks themselves will need to look quite different in future. Here comes the gene regulatory network express.
Ref: arxiv.org/abs/1003.4012 : Phase Synchronization in Railway Timetables
Become an Insider to get the story behind the story — and before anyone else.