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

Daniel Patterson daniel at mapbox.com
Wed Oct 21 22:02:28 UTC 2015


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 <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 <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 <mailto: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 <mailto: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 <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 <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 <mailto: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 <mailto: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 <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 <mailto: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 <mailto:OSRM-talk at openstreetmap.org>
> >>> https://lists.openstreetmap.org/listinfo/osrm-talk <https://lists.openstreetmap.org/listinfo/osrm-talk>
> >>>
> >>>
> >>>
> >>> _______________________________________________
> >>> OSRM-talk mailing list
> >>> OSRM-talk at openstreetmap.org <mailto:OSRM-talk at openstreetmap.org>
> >>> https://lists.openstreetmap.org/listinfo/osrm-talk <https://lists.openstreetmap.org/listinfo/osrm-talk>
> >>>
> >>
> >>
> >> _______________________________________________
> >> OSRM-talk mailing list
> >> OSRM-talk at openstreetmap.org <mailto:OSRM-talk at openstreetmap.org>
> >> https://lists.openstreetmap.org/listinfo/osrm-talk <https://lists.openstreetmap.org/listinfo/osrm-talk>
> >>
> >
> > _______________________________________________
> > OSRM-talk mailing list
> > OSRM-talk at openstreetmap.org <mailto:OSRM-talk at openstreetmap.org>
> > https://lists.openstreetmap.org/listinfo/osrm-talk <https://lists.openstreetmap.org/listinfo/osrm-talk>
> 
> 
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org <mailto:OSRM-talk at openstreetmap.org>
> https://lists.openstreetmap.org/listinfo/osrm-talk <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/a6c1f386/attachment.html>


More information about the OSRM-talk mailing list