A simple coding improvement developed by a UNSW PhD candidate is being integrated into one of the world's most widely used open-source public transport journey planners.
When you’re searching for the fastest way across town, most people expect an answer within seconds.
Behind that simple search, journey planning software evaluates thousands of possible routes, transfers and connections before recommending the fastest trip.
Now, Andrii Rohovyi, a PhD candidate from UNSW Computer Science and Engineering, has developed a way to make that search even more efficient.
His research introduces an optimisation that enables journey planning software to stop considering routes that cannot improve a passenger’s journey, making route searches faster.
The work, presented at the World Conference on Transport Research in France this month, has recently been integrated into OpenTripPlanner – one of the world’s leading open-source public transport routing platforms.
OpenTripPlanner is widely adopted by public transit agencies, national governments and private mobility tech companies across Europe and North America because its ability to combine public transit schedules with walking, cycling, and ridesharing.
“The algorithm behind OpenTripPlanner, RAPTOR, was inspired by how people plan their daily travel. Each time we go somewhere, we try to avoid switching between modes of transport, and the fastest route is usually a direct trip to the destination,” says Rohovyi.
“If we already know we can't find a better journey than the one we've found, there's no reason to keep searching. We simply stop looking earlier.”
Early pruning
Rohovyi builds on RAPTOR, which is extensively used to calculate public transport routes.
Traditionally, planning software explores every possible transfer within a predefined distance or travel time limit, whether or not those options are likely to lead to a quicker journey.
However, Rohovyi’s 'early pruning' method organises transfer options by travel time and stops searching as soon as it determines that no remaining route can get passengers to their destination faster.
It's like looking for the fastest way to get somewhere,” he says.
“If you've already found a route that arrives earlier than every remaining possibility, the algorithm stops checking the rest.
“The result is software that spends less time searching while producing exactly the same route recommendations.”
Just for fun
After publishing his research this year, Rohovyi decided to contribute to OpenTripPlanner – and to his surprise, it was accepted.
The optimisation is now integrated in the latest update of OpenTripPlanner.
“I did it mostly for fun,” he says.
“I knew OpenTripPlanner was one of the biggest open-source journey planning systems, so I thought it would be interesting to see whether the research could work in a real production system.”
Small tweaks – big impact
Public benchmark dashboards used by participating transport agencies have since shown faster routing performance after the optimisation was introduced.
In testing on public transport networks in Switzerland and Germany, the optimisation has reduced routing times by as much as 57% and some have seen the performance of their app double.
For passengers, those improvements could mean even faster trip planning, particularly for cities with complex transport networks.
“The great thing about this method is that it can be integrated with minimal changes to the existing code bases,” says Rohovyi.
“Today, many journey planners limit how far you're allowed to walk or cycle between services because checking every possibility takes too long.
“If routing becomes faster, agencies can choose to consider more transfer options that includes additional mobility modes and potentially find better journeys for passengers.”
Rohovyi’s focus now is completing his PhD and exploring how the technique could be incorporated into additional journey planning platforms.
“Sometimes small algorithmic improvements can have a surprisingly large impact,” he says.
“They don't change the journey itself – they just help us find it much faster.”
Contact details:
Cecilia Duong