[pgrouting-dev] Boost Turn Restrictions
Stephen Woodbridge
woodbri at swoodbridge.com
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
More information about the pgrouting-dev
mailing list