[pgrouting-dev] Boost Turn Restrictions

vidhan jain vidhanj1307 at gmail.com
Thu May 18 01:23:05 PDT 2017


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
<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
> 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 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-restric
>> tions-in-k-shortest-paths-algorithm-in-pgrouting
>>         <http://stackoverflow.com/questions/32116289/how-turn-restri
>> ctions-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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20170518/807ed799/attachment-0001.html>


More information about the pgrouting-dev mailing list