Algorithms provide a model of railway efficiency

May 03, 2010
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.

Explore further: Computer software accurately predicts student test performance

More information: ARRIVAL project - arrival.cti.gr/

add to favorites email to friend print save as pdf

Related Stories

Russian railways enter modern age with new express

Dec 20, 2009

Famed for the legendary trains that clank across seven time zones on its Trans-Siberian railroad, Russia this week entered the modern railway age with its first high-tech express train.

France's SNCF hopes to run high speed rail in US

Mar 20, 2009

The United States is ready for a truly high-speed rail system and France's national railway SNCF would be "very interested" in operating a network, a senior executive said Thursday.

Recommended for you

'Chief Yahoo' David Filo returns to board

1 minute ago

Yahoo announced the nomination of three new board members, including company co-founder David Filo, who earned the nickname and formal job title of "Chief Yahoo."

Fired Yahoo exec gets $58M for 15 months of work

11 minutes ago

Yahoo's recently fired chief operating officer, Henrique de Castro, left the Internet company with a severance package of $58 million even though he lasted just 15 months on the job.

Simplicity is key to co-operative robots

8 hours ago

A way of making hundreds—or even thousands—of tiny robots cluster to carry out tasks without using any memory or processing power has been developed by engineers at the University of Sheffield, UK.

Freight train industry to miss safety deadline

8 hours ago

The U.S. freight railroad industry says only one-fifth of its track will be equipped with mandatory safety technology to prevent most collisions and derailments by the deadline set by Congress.

User comments : 3

Adjust slider to filter visible comments by rank

Display comments: newest first

ChazzMann
5 / 5 (2) May 04, 2010
We need this for street traffic signals. Cars and trucks sitting at a red light all get the same mileage -- zero MPG. Taking off from a stop isn't much better.
finitesolutions
not rated yet May 04, 2010
Nice one. I am also waiting for a money flow optimization.
Skeptic_Heretic
not rated yet May 04, 2010
Nice one. I am also waiting for a money flow optimization.

With more efficient systems, monetary flow increase is assured. Less waste always equates to greater savings.

More news stories

Simplicity is key to co-operative robots

A way of making hundreds—or even thousands—of tiny robots cluster to carry out tasks without using any memory or processing power has been developed by engineers at the University of Sheffield, UK.

Microsoft CEO is driving data-culture mindset

(Phys.org) —Microsoft's future strategy: is all about leveraging data, from different sources, coming together using one cohesive Microsoft architecture. Microsoft CEO Satya Nadella on Tuesday, both in ...

Floating nuclear plants could ride out tsunamis

When an earthquake and tsunami struck the Fukushima Daiichi nuclear plant complex in 2011, neither the quake nor the inundation caused the ensuing contamination. Rather, it was the aftereffects—specifically, ...

New clinical trial launched for advance lung cancer

Cancer Research UK is partnering with pharmaceutical companies AstraZeneca and Pfizer to create a pioneering clinical trial for patients with advanced lung cancer – marking a new era of research into personalised medicines ...

More vets turn to prosthetics to help legless pets

A 9-month-old boxer pup named Duncan barreled down a beach in Oregon, running full tilt on soft sand into YouTube history and showing more than 4 million viewers that he can revel in a good romp despite lacking ...