Routing — Making Travel Time and Edge Weights Independent

Posted by happygo on 27 February 2017 in English (English)

We've just released version 5.6 of our beloved Open Source Routing Machine (OSRM). The release comes with documentation, NodeJs bindings and a osrm/osrm-backend:v5.6.0 Docker image for an easy setup. More details here. See the Release Notes and the Full Changelog for more details.

What I want to highlight in this post is the 5.6 release's main feature: Making Travel Time and Edge Weights Independent

Up until the 5.6 release users were able to adjust way speeds based on tags and their preferences via user-provided Lua scripts. The routing engine then did fastest path routing minimizing for duration.

Now there are use-cases for which you want to penalize certain ways: think alleys or small roads which you don't want the routing engine to prefer. Before the 5.6 release all you could do was to either discard those ways completely or adjust their speeds and make them artificially slower. Adjusting speeds sounds like the way to go, but if the routing engine then really needs to route you over such a way your ETAs will be off by the adjusted amount.

What we instead need is a split between travel time the routing engine aggregates along the way and edge weights the routing engine minimizes. With 5.6 we finally made that major architectural switch.

In your profiles you can do both now:

  • Fine-tune way speeds based on tags to make for great and realistic ETAs and
  • Penalize ways by setting edge weights independently of speeds.

In addition we can handle restricted ways now, too. By restricted ways I mean access=destination and similar which you are only allowed to travel on if you are going to this area. A typical example are gated communities which you don't want to get routed through except you explicitly want to go there.

We do this by penalizing the turns onto such restricted ways setting a very high turn weight but keeping the turn penalty duration untouched. The routing engine will now only ever route you e.g. into gated communities if there is no other option and the user explicitly wants to go there. The ETAs won't be affected at all!

Here is an example of destination routing for when we really want to go there: Destination Routing

We can make use of this technique for certain other tags: think of delivery, private or customer access restrictions. Or even for HOV-ways if you normally want to avoid HOV ways but want the routing engine to still give you routes when you drive your car on a HOV way and re-routing triggers.

If you know of other tags we should penalize this way, feel free to jump into the discussion.

This feature is included in the latest OSRM v5.6 Release. We're always glad for user feedback; in case you stumble over issues like this please talk to us! You can find us in the OSRM Repository on IRC and on the osrm-talk mailinglist.

We will also be at this year's FOSSGIS conference - stop by and say Hi!

Location: Spandauer Vorstadt, Mitte, Berlin, 10115, Germany

Comment from bufferclip on 28 February 2017 at 08:00

What does ETA and HOV mean?

Comment from Marex on 28 February 2017 at 11:30

ETA = Estimated Time of Arrival HOV = High-occupancy Vehicle (mostly relevant in the US, cars with 2+ people in them)

Login to leave a comment