[pgrouting-dev] Boost Turn Restrictions

pgRouting pgrouting-dev
1

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@swoodbridge.com <mailto:woodbri@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&gt;
        <https://github.com/pgRouting/pgrouting/issues/610
        <https://github.com/pgRouting/pgrouting/issues/610&gt;&gt;\) 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&gt;
        , 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

--

Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany

Vicky Vergara
Operations Research

eMail: vicky@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

2

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.
  2. While converting the graph to its Line graph, the costs can be handled as described here.
  3. Apply dijkstra to calculate the shortest path.
  4. Convert the result back to original graph.

More detailed information proposal.
These 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

···

On Thu, May 18, 2017 at 6:18 AM, Stephen Woodbridge <woodbri@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://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@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@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@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

Vidhan Jain,
Computer Science and Engineering
(Third Year)
The LNM Institute of Information Technology,Jaipur
+91-8890873934

3

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@gmail.com <mailto:vidhanj1307@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&gt;\.
    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&gt;\.
    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&gt;\.
    These
    <https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP#references&gt; 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&gt;
    <https://www.linkedin.com/in/vidhan13j07/&gt;

    On Thu, May 18, 2017 at 6:18 AM, Stephen Woodbridge
    <woodbri@swoodbridge.com <mailto:woodbri@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&gt;

        http://lekv.de/pub/lv-turns-2008.pdf
        <http://lekv.de/pub/lv-turns-2008.pdf&gt;

        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&gt;

        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&gt;

            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@swoodbridge.com <mailto:woodbri@swoodbridge.com>
            <mailto:woodbri@swoodbridge.com
            <mailto:woodbri@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&gt;
                     <https://github.com/pgRouting/pgrouting/issues/610
            <https://github.com/pgRouting/pgrouting/issues/610&gt;&gt;
                     <https://github.com/pgRouting/pgrouting/issues/610
            <https://github.com/pgRouting/pgrouting/issues/610&gt;
                     <https://github.com/pgRouting/pgrouting/issues/610
            <https://github.com/pgRouting/pgrouting/issues/610&gt;&gt;&gt;\) 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&gt;
                                <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&gt;&gt;
                     , 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&gt;
            <https://www.avast.com/antivirus
            <https://www.avast.com/antivirus&gt;&gt;

            --

            Georepublic UG (haftungsbeschränkt)
            Salzmannstraße 44,
            81739 München, Germany

            Vicky Vergara
            Operations Research

            eMail: vicky@georepublic.de <mailto:vicky@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

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