Algorithms provide a model of railway efficiency

(PhysOrg.com) -- If you've noticed that Dutch trains experience less delays or that waiting times are shorter on the Berlin underground you can thank a team of European researchers whose advanced algorithms are optimising rail services.

In what has been described as a breakthrough in the field of operational research (OR) and has garnered a prestigious award, the researchers succeeded in developing advanced algorithms able to optimise planning and scheduling in vast, complex rail networks.

In practice, their work means that railways can be more confident that their routing choices will allow more trains, more passengers and more goods to safely traverse the same infrastructure while increasing punctuality, passenger satisfaction and operator profit. It’s a win-win for everyone.

It is not surprising then that many railway and transport network operators across Europe, from Netherlands Railways and the Berlin U-Bahn to Swiss Federal Railways and others, have implemented the technology or are planning to do so.

“We set out doing foundational algorithmic research, to develop universal algorithms and methods, we did not expect to see them being used in real-world applications so soon. But by now 95 percent of our algorithms and methods have been verified with real-world data and many are being used commercially,” explains Christos Zaroliagis, a professor at the University of Patras and a senior researcher at the Computer Technology Institute in Patras, Greece.

Zaroliagis coordinated the team behind the EU-funded ARRIVAL project, which brought together researchers from seven European countries. Among them was a team from Erasmus University in Holland that had been working closely with Netherlands Railways on a new railway timetable. Together with collaborators from the University of Padua, Italy, the Dutch researchers were awarded the 2008 Edelman Award, described as the Nobel Prize of applied operations research.

Thanks to their work, much of it carried out in the ARRIVAL project, the Dutch railway network is today one of Europe’s most efficient.

“The Netherlands is a small country, but it has a very dense railway system that has to handle 5,500 trains per day. Trains literally travel one behind the other, so any disruption anywhere has knock-on effects that can lead to long delays and major scheduling problems,” says Zaroliagis. “The new timetable, drawn up using the ARRIVAL algorithms, has meant that trains can be scheduled more efficiently and disruptions handled more effectively, while maintaining the usual security measures.”

As a result, trains suffer fewer delays, passenger surveys show higher levels of satisfaction, and Netherlands Railways’ profits have risen by 40 million euros per year - a figure that is expected to rise to 70 million euros in the near future.

Robust and online planning

The key to such significant gains in efficiency lies in two approaches to optimised planning that had previously not been applied to the rail transport sector: Robust planning and online planning.

The first approach involves deploying algorithms to ensure all aspects of the railway network, from train scheduling and platform allocation to staff distribution and freight loads, are organised as efficiently as possible, while still being able to absorb disruptions without impacting services too dramatically.

“It’s a proactive approach. You don’t have an optimal offline plan that can’t handle disruptions. You have a near-optimal plan that can handle as much disruption as possible,” Zaroliagis explains.

Online planning, on the other hand, takes a reactive approach, dealing with disruptions as they happen in real time.

“No system, no matter how optimised, can deal with all disruptions. Online planning ensures trains can be rerouted, rescheduled, or other action taken on the fly while minimising disruption across the rail network,” the ARRIVAL coordinator says.

Although robust and online optimisation methods have previously been developed for other sectors, such as the aviation industry, they turned out to be inadequate when applied to railways due to the complexity and sheer size of rail networks. Whereas changing the take-off order of planes at an airport may cause notable disruption elsewhere, in a railway system, because trains have to use the same tracks, delaying the departure of one train can cause chaos across the network.

Dealing with such disruptions has traditionally been left to the experience of human planners, who have until now received little computer assistance.

“The only software used by most railway operators is graphics software that makes it easier for human planners to visualise what is going on and make their decisions. Our algorithms will not diminish the importance of human planners but they will help them find much more optimised solutions to problems,” Zaroliagis says. “ARRIVAL’s success is based on the development of new concepts and methods that considerably advance the theory necessary to tackle such large and complex problems efficiently.”

In Berlin’s U-Bahn underground network, where the ARRIVAL algorithms are being used commercially, they have resulted in the average waiting time between trains being reduced from four minutes to two minutes, while trials at Padua and Genoa train stations in Italy showed that the technology resulted in an average 25 percent reduction in delays.

Hafas, the German company that provides itinerary information services for German rail operator Deutsche Bahn, has shown interest in the algorithms for use in its systems, while France’s MediaMobile and Germany’s PTV have bought them for use in mobile navigation services.

Zaroliagis says the project’s algorithms can find itineraries, not in seconds, but microseconds. In general, methods that could not be applied on the large scale required for railway applications have been so improved that they now not only work on the required scale but they do so efficiently, respecting of course the safety regulations set by rail companies.

This can mean the difference between chaos and potential accidents and a smooth contingency plan. It is no surprise, then, that the industry is paying attention.

“We have had a lot of interest from railway operators and firms in the transport industry, and some are implementing or planning to implement our algorithms,” he notes.

The technology also has applications in other sectors.

“Our algorithms could benefit industrial work-flow systems, e-commerce, P2P and grid computing networks and even healthcare,” he explains. “They could be used, for example, to optimise decisions about what type, dose and with what frequency to administer medications depending on how a patient’s health is evolving.”

The project partners plan to explore those and other applications in subsequent projects, and Zaroliagis says that they are open to ideas from outside investors and partners to take their work further.