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

[Guillaume Barreau]

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  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 
> 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  wrote:
>
>> Thanks Patrick, yes, that was what I meant to point at :-)
>>
>> > On Oct 21, 2015, at 12:44 PM, Patrick Niklaus <
>> patrick.nikl...@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 
>> 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 
>> 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 
>> >>> 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

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

[Daniel Patterson]

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  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  > wrote:
> Thanks Patrick, yes, that was what I meant to point at :-)
> 
> > On Oct 21, 2015, at 12:44 PM, Patrick Niklaus 
> > mailto:patrick.nikl...@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  > > 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  >> > 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  >>> >
> >>> wrote:
> >>>
> >>> H

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

[Guillaume Barreau]

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  wrote:

> Thanks Patrick, yes, that was what I meant to point at :-)
>
> > On Oct 21, 2015, at 12:44 PM, Patrick Niklaus <
> patrick.nikl...@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 
> 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 
> 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 
> >>> 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@openstreetmap.org
> >>> https://lists.openstreetmap.org/listinfo/osrm-talk
> >>>
> >>>
> >>>
> >>> ___
> >>> OSRM-talk mailing list
> >>> OSRM-talk@openstreetmap.org
> >>> https://lists.openstreetmap.org/listinfo/osrm-talk
> >>>
> >>
> >>
> >> ___
> >> OSRM-talk mailing list
> >> OSRM-talk@openstreetmap.org
> >> https://lists.openstreetmap.org/listinfo/osrm-talk
> >>
> >
> > ___
> > OSRM-talk mailing list
> > OSRM-talk@openstreetmap.org
> > https://lists.openstreetmap.org/listinfo/osrm-talk
>
>
> ___
> OSRM-talk mailing list
> OSRM-talk@openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>
___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

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

[Daniel Patterson]

Thanks Patrick, yes, that was what I meant to point at :-)

> On Oct 21, 2015, at 12:44 PM, Patrick Niklaus 
>  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  
> 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  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 
>>> 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@openstreetmap.org
>>> https://lists.openstreetmap.org/listinfo/osrm-talk
>>> 
>>> 
>>> 
>>> ___
>>> OSRM-talk mailing list
>>> OSRM-talk@openstreetmap.org
>>> https://lists.openstreetmap.org/listinfo/osrm-talk
>>> 
>> 
>> 
>> ___
>> OSRM-talk mailing list
>> OSRM-talk@openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/osrm-talk
>> 
> 
> ___
> OSRM-talk mailing list
> OSRM-talk@openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk


___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

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

[Patrick Niklaus]

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  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  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 
>> 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@openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/osrm-talk
>>
>>
>>
>> ___
>> OSRM-talk mailing list
>> OSRM-talk@openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/osrm-talk
>>
>
>
> ___
> OSRM-talk mailing list
> OSRM-talk@openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>

___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

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

[Guillaume Barreau]

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  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 
> 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@openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>
>
>
> ___
> OSRM-talk mailing list
> OSRM-talk@openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>
>
___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

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

[Daniel Patterson]

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  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@openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk

___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

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

[Guillaume Barreau]

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@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk