[OSRM-talk] Modifying the graph with ad-hoc time penalties at intersections

Wed Oct 21 22:48:58 UTC 2015

Thanks a lot Daniel,

That gives me fuel for some exploration. I will play with the code to see
if I get anywhere.

Guillaume

On 21 October 2015 at 18:02, Daniel Patterson <daniel at mapbox.com> wrote:

> Guillaume,
>
>   Yes, that's basically correct, you've understood the rough structure.
> We typically call the first graph, that looks like OSM, the
> "node-based-graph".  The graph that models all turns is referred to as the
> "edge-based-graph".  Somewhat confusing terminology, I know.
>
>   The edge-based-graph edge weights are measured in deci-seconds.
> Everything is routed based on travel time.
>
>   The "speed * length" calculation happens slightly earlier in the process:
>
>
> https://github.com/Project-OSRM/osrm-backend/blob/develop/extractor/extraction_containers.cpp#L323-L337
>
>   Unfortunately, the terminology used "distance/weight" is not consistent
> across the codebase, so it can be difficult to navigate.  Suffice to say,
> the traffic penalty is adding "deci-seconds" to the edge-based-edge-weight.
>
>   To do per-node penalties, you would need to add a lookup table for each
> node, populate it, probably in the "node_function" in the Lua profile, then
> consult the lookup in the same place the traffic light penalty is currently
> added.
>
> daniel
>
>
> On Oct 21, 2015, at 2:26 PM, Guillaume Barreau <g.barreau at gmail.com>
> wrote:
>
> Thanks Daniel and Patrick for your help,
>
> I will have to pick your brains a little bit more I am afraid.
>
> Having read this page:
> https://github.com/Project-OSRM/osrm-backend/wiki/Graph-representation
>
> I now understand that what OSRM models as a node is actually what I
> initially thought of as an edge (i.e. a piece of road connecting 2
> intersections) and what OSRM calls an edge is a transition from one road
> segment (travelled in a particular direction) to another, so the edge ends
> up being a way of crossing a road intersection. This is kind of confusing
> at first, but I can see the benefits of doing that way in terms of handling
> intersections well. Please correct me if I haven't understood properly.
>
> So in my case, the penalty would be associated with edges and not nodes.
> And all edges associated with the same physical interesection would get the
> same penalty (although this way of modelling has the advantage of allowing
> each turn to have a different penalty easily).
>
> The code you pointed me to is called at the graph preparation phase,
> right? That is fine for my purposes, I am just clarifying.
>
> This distance variable that is incremented it ends up representing the
> total penalties associated with crossing that particular intersection in a
> particular way and I assume it gets stored as the attribute of the
> corresponding edge in the graph. I was curious of when and how this
> distance (a penalty expressed in meters) then gets converted back into a
> time.
>
> Thanks a lot for your time again,
>
> Guillaume
>
>
>
> On 21 October 2015 at 15:56, Daniel Patterson <daniel at mapbox.com> wrote:
>
>> Thanks Patrick, yes, that was what I meant to point at :-)
>>
>> > On Oct 21, 2015, at 12:44 PM, Patrick Niklaus <
>> patrick.niklaus at student.kit.edu> wrote:
>> >
>> > Hey Guillaume,
>> >
>> > I think Daniel wanted to post a link to this line:
>> >
>> >
>> https://github.com/Project-OSRM/osrm-backend/blob/develop/extractor/edge_based_graph_factory.cpp#L417
>> >
>> > All you need to do is to adapt the code to not only add penalties for
>> > traffic signals but also your node.
>> > Actually this code should be made more general as outlined in
>> > https://github.com/Project-OSRM/osrm-backend/issues/1490
>> >
>> > Best,
>> > Patrick
>> >
>> >
>> > On Wed, Oct 21, 2015 at 9:02 PM, Guillaume Barreau <g.barreau at gmail.com>
>> wrote:
>> >> Hi Daniel,
>> >>
>> >> Thanks a lot for this very fast reply. The url you sent appears to be
>> >> broken. Could you please double-check it for me?
>> >>
>> >> Thanks again,
>> >>
>> >> Guillaume
>> >>
>> >> On 21 October 2015 at 14:56, Daniel Patterson <daniel at mapbox.com>
>> wrote:
>> >>>
>> >>> Hi Guillaume,
>> >>>
>> >>>  There is a function called for every node:
>> >>>
>> >>>
>> >>>
>> https://github.com/mapbox/inrix-processing/blob/master/regions.json#L198-L201
>> >>>
>> >>>  however, it doesn't feed back any specific per-node penalties.  It's
>> >>> used to flag barriers and traffic lights right now.
>> >>>
>> >>>  It could be adapted to do per-node penalty values, you would probably
>> >>> need to modify the existing light penalty functionality and add a
>> lookup for
>> >>> your values, rather than using the global light penalty we have
>> currently.
>> >>>
>> >>> daniel
>> >>>
>> >>> On Oct 21, 2015, at 11:46 AM, Guillaume Barreau <g.barreau at gmail.com>
>> >>> wrote:
>> >>>
>> >>> Hello,
>> >>>
>> >>> I would like to OSRM for a research project but I have this unusual
>> >>> requirement. I would want to be able to add time penalties at some
>> sets of
>> >>> vertices (defined by their id) that would be used to compute the
>> fastest
>> >>> routes in a table calculation. My input would therefore be a list of
>> >>> (node_id,delays) to be added to the underlying graph. Is this
>> feasible? I am
>> >>> prepared to modify the code if needs be, I don't expect to be able to
>> do
>> >>> this with a config file. If it is feasible, could someone point me in
>> the
>> >>> right direction?
>> >>>
>> >>> Thank you very much for your help,
>> >>>
>> >>> Guillaume
>> >>> _______________________________________________
>> >>> OSRM-talk mailing list
>> >>> OSRM-talk at openstreetmap.org
>> >>> https://lists.openstreetmap.org/listinfo/osrm-talk
>> >>>
>> >>>
>> >>>
>> >>> _______________________________________________
>> >>> OSRM-talk mailing list
>> >>> OSRM-talk at openstreetmap.org
>> >>> https://lists.openstreetmap.org/listinfo/osrm-talk
>> >>>
>> >>
>> >>
>> >> _______________________________________________
>> >> OSRM-talk mailing list
>> >> OSRM-talk at openstreetmap.org
>> >> https://lists.openstreetmap.org/listinfo/osrm-talk
>> >>
>> >
>> > _______________________________________________
>> > OSRM-talk mailing list
>> > OSRM-talk at openstreetmap.org
>> > https://lists.openstreetmap.org/listinfo/osrm-talk
>>
>>
>> _______________________________________________
>> OSRM-talk mailing list
>> OSRM-talk at openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/osrm-talk
>>
>
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> https://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/20151021/35a7b23d/attachment-0001.html>