[pgrouting-dev] Boost Turn Restrictions

Wed May 17 17:48:31 PDT 2017

All,

Here are some related links that might be of interest:

http://stackoverflow.com/questions/43655284/boost-graph-library-turn-restrictions-or-turn-penalties

http://lekv.de/pub/lv-turns-2008.pdf

My post to the Boost graph list from 2011:
https://lists.boost.org/boost-users/2011/11/71549.php

Some ideas that might be useful if you have not already seen them.

-Steve

On 5/17/2017 3:46 PM, Vicky Vergara wrote:
> Hello Anthony,
> 
> I must tell you that Vidhan's project involves only the TRSP version one 
> to one.
> He researched some algorithms, but we haven't discussed in detail what 
> his final approach will be.
> We are currently on the getting to know the code standard stage.
> 
> Any comments are welcome,
> You can find our conversations in
> https://gitter.im/pgRouting/pgrouting
> 
> Please feel free to read our history of conversations and ask or comment.
> 
> Vicky
> 
> 
> On Wed, May 17, 2017 at 1:59 PM, Stephen Woodbridge 
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
> 
>     Hello Anthony,
> 
>     Thank you for reaching out to me. I have CC'd
> 
>     Vicky Vergara - Lead developer and release manager on pgRouting
>     Vidhan Jain   - GSoC Student working on TRSP rewrite
> 
>     I think that collaborating with them in this effort will be most
>     fruitful.
> 
>     It has been a while since I have really wrapped my head around this
>     problem and you seem to have gotten farther into the design and
>     planning for this than I did. You raise some interesting problems.
> 
>     In addition to the problems you pose, had you thought about how you
>     would what to prevent an illegal turn rather than just add a cost to it?
> 
>     Also for complex intersections/restrictions you need to be able to
>     specify a sequence of multiple edges to define a restriction (if
>     your working with nodes then an ordered list of nodes preceding the
>     current node under evaluation).
> 
>     Vicky, Vidhan, any thoughts on how you might proceed working with
>     Anthony? I'm thinking that sharing ideas and discussing the issues
>     and concerns would be a good starting point, but I'll leave this up
>     to the three of you to sort out what works best with Vicky having
>     the final say as release manager.
> 
>     Best regards,
>        -Steve
> 
>     On 5/17/2017 2:10 PM, A Tasca wrote:
> 
>         Hello Stephen,
> 
>         I am looking at adding turn costs to the one-to-many dijkstra
>         implementation in pgRouting 2.4.1. I found that you created a
>         discussion on this topic
>         (https://github.com/pgRouting/pgrouting/issues/610
>         <https://github.com/pgRouting/pgrouting/issues/610>
>         <https://github.com/pgRouting/pgrouting/issues/610
>         <https://github.com/pgRouting/pgrouting/issues/610>>) and wanted
>         to share my ideas with you, and possibly get some feedback. If I
>         am successful, I plan to commit the code to pgRouting for anyone
>         to use.
> 
>         My original plan was to:
> 
>         1) Create a turn restriction table, similar to pgr_trsp, that
>         contains, a pair of edges, and a cost for going from one of
>         those edges to the other.
> 
>         2) Pass this turn restriction table, a reference to the
>         predecessor map, and a reference to the weight map into a boost
>         dijkstra visitor.
> 
>         3) Every time the visitor examines an edge, it looks at the
>         predecessor map to figure out which edge it got to the current
>         vertex from. It will then look at the turn restriction table and
>         see if there is an added cost for going from the edge it came
>         from to the edge it is examining. If there is, it will update
>         the weight map and add the appropriate weight to the edge that
>         it is examining.
> 
>         I was able to implement this and it did exactly what I planned.
>         The problem is, my plan does not solve the turn restriction
>         shortest path problem. It adds costs to edges based on turns
>         that it makes, given the predecessor of the current vertex, but
>         it does not check to see if a different possible predecessor to
>         the current vertex would have been a better choice, given the
>         turn restrictions.
> 
>         I am now thinking about how to do this (ie. check to see if a
>         different possible predecessor to the current vertex would lead
>         to a lower cost path to the next vertex, given the turn
>         restrictions). In my mind, this would look like:
> 
>         1) For each incoming edge of the current vertex, add the weight
>         of that edge (gotten from the weight map) to the distance of the
>         other vertex that this edge connects to (gotten from the
>         distance map), apply the appropriate turn cost for this edge and
>         the edge that connects the current vertex to the vertex we want
>         to go to.
> 
>         2) Determine the lowest cost possible path
> 
>         3) Update the predecessor map and replace the predecessor of the
>         current vertex with the vertex that we found to be in the lowest
>         cost possible path
> 
>         4) Update the distance map and replace the distance of the
>         current vertex with the new distance, based on the new predecessor
> 
>         The problem is, I still don't think that this approach will
>         solve the turn restriction shortest path for every possible
>         graph. If one of the incoming edges to the current vertex has
>         not yet been examined, then we will not know the distance of the
>         vertex that it is connected to.
> 
>         If you are still reading, please let me know if you have any
>         input on whether or not this approach is completely insane,
>         whether or not you have any input on how to make this work, or
>         any other input you think might be useful for someone who wants
>         to get a one-to-many trsp algorithm that is comparable in
>         run-time to boost dijkstra.
> 
>         In this stackoverflow post:
>         http://stackoverflow.com/questions/32116289/how-turn-restrictions-in-k-shortest-paths-algorithm-in-pgrouting
>         <http://stackoverflow.com/questions/32116289/how-turn-restrictions-in-k-shortest-paths-algorithm-in-pgrouting>
>         , you said that one should just write a wrapper that calls
>         pgr_trsp for each target, but I am working with around 100->500
>         targets, a 200,000 edge map, and run-time is critical.
> 
>         Thanks for reading and thank you for helping make some great
>         open source software,
> 
>         Anthony
> 
> 
> 
>     ---
>     This email has been checked for viruses by Avast antivirus software.
>     https://www.avast.com/antivirus <https://www.avast.com/antivirus>
> 
> 
> 
> 
> -- 
> 
> Georepublic UG (haftungsbeschränkt)
> Salzmannstraße 44,
> 81739 München, Germany
> 
> Vicky Vergara
> Operations Research
> 
> eMail: vicky at georepublic.de <http://georepublic.de>
> Web:https://georepublic.info
> 
> Tel: +49 (089) 4161 7698-1
> Fax: +49 (089) 4161 7698-9
> 
> Commercial register: Amtsgericht München, HRB 181428
> CEO: Daniel Kastl
> 

---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus