[pgrouting-dev] Boost Turn Restrictions
Stephen Woodbridge
woodbri at swoodbridge.com
Thu May 18 08:21:06 PDT 2017
Te reason for the initial focus on one-to-one is to keep the problem
simple to start with and then expand on that solution. You are correct
the dijkstra does return one to all presuming you don't exit the solver
once you find the target node, but this could be change to exit once you
find all targets.
One of the ways to deal with the complexity issue it to transform the
problem from a node based graph to and edge based graph. In the edge
based graph, edge in the original graph become in the new graph, then
the "edges" in the new graph become the connections between the edges in
the old graph.
1-----A-----2-----B------3
\----C------4
becomes
A-----2-----B
\--2--C--2-/
if you want to restrict movement between B and C then you remove that
edge, like:
A-----2-----B
\--2--C
This greatly simplifies (but does not remove) the data management around
adding and removing restrictions.
-Steve
On 5/18/2017 10:44 AM, A Tasca wrote:
> Hi,
>
> Thank you all for taking the time to share these ideas with me. For
> Stephen's comment about having the visitor do book-keeping to keep track
> of possible paths that have not yet been discovered and update them when
> they are; I think this might work but in the worst case scenario I would
> end up calculating every possible path to every node in the graph, which
> is NP-Hard and will probably take more time (and space) than just
> running pgr_trsp for each destination.
>
> For the related links that Stephen referenced, I am tempted to use the
> approach suggested in both the boost.org <http://boost.org> post and the
> stack overflow post, where one would pre-process the graph and create a
> new graph that has additional edges that represent turns. At this point,
> one could just run a standard pgr_dijkstra(one to many) and then convert
> the results back to the original graph. The problem with this approach
> is that, for a graph with average 4 incoming edges and 4 outgoing edges
> per vertex (like a map of city streets), the new graph will be 16 times
> larger and if i ever want to change the added cost of turning, I will
> have to reprocess the whole graph.
>
> I did not look into this thoroughly but Vidhan's idea may solve this
> space complexity issue, but I am curious as to why you are only looking
> to do the one-to-one implementation and not one-to-many/many-to-one? If
> you are using boost, the path to every vertex in the graph will be
> returned anyway. Is there some restriction on the line-graph approach
> that makes it so that you would have to use a create a different line
> graph for each destination to apply the proper turn penalties?
>
> Thanks again,
> Anthony
>
>
> On Thu, May 18, 2017 at 4:23 AM, vidhan jain <vidhanj1307 at gmail.com
> <mailto:vidhanj1307 at gmail.com>> wrote:
>
> Hello Anthony,
>
> I will be working on the TRSP(one to one). The algorithm that I have
> proposed is a lot similar to yours. Though I have not implemented it
> so a lot more issues may arise while implementing.
>
> 1. Convert the graph into its corresponding Line Graph
> <https://en.wikipedia.org/wiki/Line_graph>.
> 2. While converting the graph to its Line graph, the costs can be
> handled as described here
> <https://github.com/vidhan13j07/Line-Graph#handling-of-costs>.
> 3. Apply dijkstra to calculate the shortest path.
> 4. Convert the result back to original graph.
>
> More detailed information proposal
> <https://github.com/vidhan13j07/GSOC17-Proposal/blob/master/proposal.pdf>.
> These
> <https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP#references> are
> the references that I consulted while researching about the problem.
>
> Feel free to share your ideas and suggest changes that I should make
> into my algorithm.
>
> Thanks,
> Vidhan Jain
>
> Vidhan Jain,
> Computer Science and Engineering
> (Third Year)
> The LNM Institute of Information Technology,Jaipur
> +91-8890873934 <tel:+91%2088908%2073934>
> <https://github.com/vidhan13j07>
> <https://www.linkedin.com/in/vidhan13j07/>
>
> On Thu, May 18, 2017 at 6:18 AM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>
> 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://stackoverflow.com/questions/43655284/boost-graph-library-turn-restrictions-or-turn-penalties>
>
> http://lekv.de/pub/lv-turns-2008.pdf
> <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
> <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
> <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>
> <mailto: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>>
> <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>
>
> <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>
> <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 <mailto: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 <https://www.avast.com/antivirus>
>
>
>
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
More information about the pgrouting-dev
mailing list