The art of routing algorithms

Sarah Durante
Berlin 52° 30' 57.852" N, 13° 22' 37.128" E

Driving routes can be highly subjective and personal. The best route for a taxi driver could be very different to the best route that the HERE routing algorithm calculates, which could be entirely different than the route you or I would take.

That’s why researchers and developers from the HERE routing team are digging into the routes our algorithm calculates to analyze their quality as well as to evolve routing to make it more personal and contextual.

We are currently performing route quality research in 40 cities worldwide, from Bangkok and Seoul to London and Rio de Janeiro, and are planning to expand the program to many more.

We recently ran a special trial in London using the famous “London Taxi Blue Book” that showed just how well routing algorithms from HERE stacked up against the routes that drivers must memorize before they can be granted a taxi license. We digitized all 320 of the routes so we could run them through a computer model in comparison to the HERE routes.

 

LondonTaxiOverview Comparison of the HERE shortest route against London Blue Book. Lots of yellow and green lines mean good matches between HERE algorithm and the Blue Book.

ScoreColorLegend Key: Green means a match to the route local drivers would take.

“Taxi drivers are educated to take the shortest route in terms of distance according to the Blue Book. When we ran the comparison models, we were happy to find that the HERE shortest route mode gave the best match consistently,” explains Pedro Campos, one of our routing gurus from the HERE route quality research team.

LondonHEREShortest The light blue line is the HERE shortest route which had a perfect score versus the Blue Book. This means the HERE route went through all the Blue Book defined “must-pass-through” points as shown in green. Compare that to the dark blue line, which is the HERE fastest route, which had a score of 0 compared to the Blue Book.

For other cities, where we don’t have the help of something like London’s Blue Book, we’ve defined 200 origin and destination pairs. Then we have a local driving expert, usually someone from our regional map and content team (they literally drive the roads that make the map), to supply their preferred route for the 200 pairs and we compare these to the routes that the algorithms from HERE create.

When we see a negative correlation, we investigate further to find out why the routes differed so significantly. In Rio de Janeiro for example, we learned that the routes that HERE calculated favored taking the highway while the local expert’s routes used secondary roads.

“We discovered that drivers in Rio avoid taking highways due to the belief that they are always congested, whether that may be the case or not. Now, we are investigating to see why our system may not have picked up on this and if we should tweak our algorithm accordingly to generate routes in Rio that use the highway less frequently,” says Pedro.

RioDeJaneiroOverview Overview of route analysis in Rio. More orange and red lines than in London.

RioHEREtakeshighway HERE route in blue takes the highway in Rio, while the local expert’s route in green takes the secondary roads for a more direct route.

 

Another learning the team came across is from South Korea, where drivers are accustomed to making U-turns in dedicated U-turn lanes before junctions. In general, the HERE algorithm discourages U-turns, which works well in most other geographies, but led to a lower route quality score in South Korea. Yet another example of how route quality research helps us understand such local expectations and driving habits.

While the London Blue Book clearly favors the shortest route in distance, you can also evaluate and select routes on other costs, or resource considerations, like time or fuel consumption or route attractiveness.

There are always trade-offs though. “We can’t always simultaneously produce the fastest, shortest, most aesthetic and easy to navigate route, so we make a compromise between factors, “ Pedro explains, “For example, in fastest route mode, we only consider the travel time and try to get the absolute fastest route, regardless of the other factors.”

Humanizing the route

Right now, the HERE route quality research team uses models that compare our algorithm to a reference route, but we’re already planning for the future where we’ll be able to compare HERE generated routes to the ones taken most frequently by drivers in real time using information coming from probe data or sensors on the car itself. “Then, it’s just a short step to humanize the route based on your personal preferences and the types of routes you take most often, all in the context of what other drivers on the road are doing,” says Pedro.

This type of algorithm would have the flexibility to take into account the subjectivity that comes into play when we humans evaluate whether a route is good or bad. In fact, Pedro and the route quality research team at HERE have already identified nine criteria that drivers commonly use to rate a route like ease of navigation, driving time, driving comfort or scenic attractiveness.

So, if for example, you don’t like to take left turns or your car senses that you make more navigation mistakes when taking them, your personal routing algorithm will calculate routes that minimize left turns. For other drivers that have prioritized the fastest route over ease of navigation, their routing algorithm may include more complex driving maneuvers if it means that they will reach the destination faster.

En-route to the future

“We’re really excited to be able to show everyday drivers how we are testing our route quality and demonstrating that HERE calculates some of the best routes on the road today,” concludes Pedro, “And we’ll look to collaborate with the automotive industry to develop the future of routing as highly automated and fully autonomous cars make their way on the road to make sure that routing has a personal, human touch.”

Topics: Automotive, Features

Comments