A simple coding improvement developed by a UNSW PhD candidate is helping people map their routes all over the world.

Just 457 lines of code written by Andrii Rohovyi, a PhD candidate from UNSW Computer Science and Engineering, is all it has taken to boost the capabilities of OpenTripPlanner, a leading open-source public transport routing platform.

Journey planning software packages typically evaluate up to thousands of possible routes, transfers and connections before recommending the fastest trip.

Rohovyi’s research introduces an optimisation that enables journey planning software to stop considering routes that cannot improve a passenger’s journey, making route searches faster.

OpenTripPlanner is widely used by public transport agencies, national governments and private mobility companies across Europe and North America thanks to 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,” said Rohovyi.

“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,”

“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 method incorporated into OpenTripPlanner

Rohovyi’s work builds on RAPTOR, which is extensively used to calculate public transport routes.

His ‘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.

“If you’ve already found a route that arrives earlier than every remaining possibility, the algorithm stops checking the rest,” he said.

“The result is software that spends less time searching while producing exactly the same route recommendations.”

After publishing his research this year, Rohovyi decided to contribute to OpenTripPlanner.

To his surprise, his work was accepted, and his optimisation is now integrated into OpenTripPlanner’s latest update.

“I did it mostly for fun,” he said.

“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 tweak leads to big performance increase

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.”