[OSRM-talk] Map-matching transit vehicles: giving preference to known routes?

Daniel Hofmann hofmann at mapbox.com
Sun May 28 13:11:18 UTC 2017


You are correct re. edge costs.

Weight is used for route optimization. Speed/duration is used to annotate a
found route with an ETA.
Think of weight as a speed/duration generalization: osm comes with km/h
speeds per way; you take the distance and calculate a duration per way.

Here's an old schematic with weights still missing but already showing the
overall pipeline:

https://github.com/Project-OSRM/osrm-backend/wiki/Graph-representation#graph-edge

And here's a osm diary post why you want to split speed and weight:

https://www.openstreetmap.org/user/happygo/diary/40564

tl;dr: Tune speeds to get more accurate ETAs. Tune weights to get different
routes.

HTH,
Daniel J H

On Wed, May 24, 2017 at 4:15 PM, Nate Wessel <nate.wessel at mail.utoronto.ca>
wrote:

> Hi Daniel,
>
> Thanks for the link to the documentation! I had indeed not seen that - it
> was very helpful.
>
> I'm a little unclear though on what the difference between "weight" and
> speed and length. Is "weight" equivalent to the "cost" of traversing an
> edge, which would presumably be a function of speed and length? Or does a
> higher weight give preference to an edge over others?
>
> And what happens if I have an edge with a high weight and a low speed or
> vice versa? i.e. how do weight and speed (and duration?) interact in the
> selection of a shortest path? Are these all names for the same thing?
>
> Thanks,
> Nate Wessel
> Jack of all trades, Master of Geography
> SAUSy Lab <http://sausy.ca>, Sid Smith Hall
>
> On 05/22/2017 08:28 AM, Daniel Hofmann wrote:
>
> Actually we base map matching on the distance of _the fastest path_ here:
>
> https://github.com/Project-OSRM/osrm-backend/blob/
> a63b43c259d49fc4915810eb4bfdd86bc78bce93/src/engine/routing_
> algorithms/map_matching.cpp#L220-L226
>
> I got confused a bit this morning because `getNetworkDistance` does this
> two levels of indirection approach.
>
> So if you set edge weights in the profiles accordingly (based on if a way
> is a transit-relevant way or not) orsm will find the fastest route and then
> does map matching on it based on its distance.
>
> Hope that helps
>
> On Mon, May 22, 2017 at 10:38 AM, Daniel Hofmann <hofmann at mapbox.com>
> wrote:
>
>> Did you see the profile docs here? Granted they could be more detailed
>> but should get you started. If you have anything to add we're always happy
>> for pull requests :)
>>
>> https://github.com/Project-OSRM/osrm-backend/blob/master/docs/profiles.md
>>
>> What I can suggest is to
>> - always provide timestamps otherwise defaults will be used internally
>> - investigate the map matching's tidy option for blob removal (think:
>> waiting at a traffic signal)
>>
>> Unfortunately map matching is distance based so modifying edge weights or
>> speeds in the profiles won't help.
>> And completely discarding ways won't help you either since you
>> specifically want to capture detours.
>>
>> Maybe have a look at Figure 7 in the map matching paper "Hidden Markov
>> Map Matching Through Noise and Sparseness. And then just give it a try with
>> your data and see how it goes.
>>
>> There are probably other ways to do your analysis, e.g. map match your
>> traces on a regular profile and then compare the results against a osrm
>> route query on a transit-ish profile.
>> For this transit-ish profile you could set low weights (note: modify
>> weights, keep speeds for correct ETAs) except for actual transit routes. I
>> don't know if the transit data is good enough for this, though.
>>
>> Interested in what you find out.
>>
>> On Mon, May 22, 2017 at 2:02 AM, Nate Wessel <
>> nate.wessel at mail.utoronto.ca> wrote:
>>
>>> Hi all,
>>>
>>> I have recently been using OSRM to do map-matching for transit vehicles,
>>> with locations from historical GPS data. The documentation on creating
>>> profiles is pretty minimal from what I can tell, so I've just been able to
>>> make a few modifications to the car.lua profile to allow vehicles to go on
>>> streetcar tracks, agency service roads, etc.
>>>
>>> The data I've been playing with so far has a ~20second sampling
>>> frequency, which has worked well, but I'm about to start working with data
>>> that has a lower sampling rate (30-60secs) and I'm worried that I'll get a
>>> lot of spurious matches. I was wondering if it is possible to modify the
>>> profile such that a strong preference is given to known transit routes
>>> (which are tagged with route relations in OSM). Transit almost always
>>> follows a known route, but sometimes it detours, and it's important to my
>>> research to be able to capture that in matched GPS data.
>>>
>>> What might be a good way to add this to a routing profile? Does
>>> everything in the profile come down to speed, access, and node-related
>>> penalties? Would I want to artificially inflate the "speed" of
>>> transit-served streets? Is there more thorough documentation on profiles
>>> somewhere than what is provided here
>>> <https://github.com/Project-OSRM/osrm-backend/wiki/Profiles>?
>>>
>>> The profile I've been using is:
>>> https://github.com/SAUSy-Lab/retro-gtfs/blob/master/etc/ttc.lua
>>>
>>> Any help would be greatly appreciated!
>>> --
>>> Nate Wessel
>>> Jack of all trades, Master of Geography
>>> SAUSy Lab <http://sausy.ca>, Sid Smith Hall
>>>
>>> _______________________________________________
>>> OSRM-talk mailing list
>>> OSRM-talk at openstreetmap.org
>>> https://lists.openstreetmap.org/listinfo/osrm-talk
>>>
>>>
>>
>
>
> _______________________________________________
> OSRM-talk mailing listOSRM-talk at openstreetmap.orghttps://lists.openstreetmap.org/listinfo/osrm-talk
>
>
>
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20170528/4a99ee07/attachment.html>


More information about the OSRM-talk mailing list