[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