<div dir="ltr">Hello Anthony,<div><br></div><div>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.</div><div><br></div><div>1. Convert the graph into its corresponding <a href="https://en.wikipedia.org/wiki/Line_graph">Line Graph</a>.</div><div>2. While converting the graph to its Line graph, the costs can be handled as described <a href="https://github.com/vidhan13j07/Line-Graph#handling-of-costs">here</a>.</div><div>3. Apply dijkstra to calculate the shortest path.</div><div>4. Convert the result back to original graph.</div><div><br></div><div>More detailed information <a href="https://github.com/vidhan13j07/GSOC17-Proposal/blob/master/proposal.pdf">proposal</a>.</div><div><a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP#references">These</a> are the references that I consulted while researching about the problem.<br></div><div><br></div><div>Feel free to share your ideas and suggest changes that I should make into my algorithm.</div><div><br></div><div>Thanks,</div><div>Vidhan Jain</div></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div style="font-size:12.8px">Vidhan Jain,</div><div style="font-size:12.8px">Computer Science and Engineering</div><div style="font-size:12.8px">(Third Year)</div><div style="font-size:12.8px"><font size="2" color="#000000"><font face="monospace, monospace">The LNM Institute of Information Technology,</font></font><span style="color:rgb(0,0,0);font-family:monospace,monospace;font-size:small">Jaipur<br>+91-8890873934</span></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:monospace,monospace;font-size:small"><a href="https://github.com/vidhan13j07" target="_blank"><img src="https://github.com/favicon.ico"></a> <a href="https://www.linkedin.com/in/vidhan13j07/" target="_blank"><img src="http://barroncommunications.com/communities/9/000/001/378/119//images/4129418.jpg"></a><br></span></div></div></div></div></div></div></div></div>
<br><div class="gmail_quote">On Thu, May 18, 2017 at 6:18 AM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">All,<br>
<br>
Here are some related links that might be of interest:<br>
<br>
<a href="http://stackoverflow.com/questions/43655284/boost-graph-library-turn-restrictions-or-turn-penalties" rel="noreferrer" target="_blank">http://stackoverflow.com/quest<wbr>ions/43655284/boost-graph-<wbr>library-turn-restrictions-or-<wbr>turn-penalties</a><br>
<br>
<a href="http://lekv.de/pub/lv-turns-2008.pdf" rel="noreferrer" target="_blank">http://lekv.de/pub/lv-turns-20<wbr>08.pdf</a><br>
<br>
My post to the Boost graph list from 2011:<br>
<a href="https://lists.boost.org/boost-users/2011/11/71549.php" rel="noreferrer" target="_blank">https://lists.boost.org/boost-<wbr>users/2011/11/71549.php</a><br>
<br>
Some ideas that might be useful if you have not already seen them.<span class=""><br>
<br>
-Steve<br>
<br>
On 5/17/2017 3:46 PM, Vicky Vergara wrote:<br>
</span><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
Hello Anthony,<br>
<br>
I must tell you that Vidhan's project involves only the TRSP version one to one.<br>
He researched some algorithms, but we haven't discussed in detail what his final approach will be.<br>
We are currently on the getting to know the code standard stage.<br>
<br>
Any comments are welcome,<br>
You can find our conversations in<br>
<a href="https://gitter.im/pgRouting/pgrouting" rel="noreferrer" target="_blank">https://gitter.im/pgRouting/pg<wbr>routing</a><br>
<br>
Please feel free to read our history of conversations and ask or comment.<br>
<br>
Vicky<br>
<br>
<br></span><div><div class="h5">
On Wed, May 17, 2017 at 1:59 PM, Stephen Woodbridge <<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.co<wbr>m</a>>> wrote:<br>
<br>
Hello Anthony,<br>
<br>
Thank you for reaching out to me. I have CC'd<br>
<br>
Vicky Vergara - Lead developer and release manager on pgRouting<br>
Vidhan Jain - GSoC Student working on TRSP rewrite<br>
<br>
I think that collaborating with them in this effort will be most<br>
fruitful.<br>
<br>
It has been a while since I have really wrapped my head around this<br>
problem and you seem to have gotten farther into the design and<br>
planning for this than I did. You raise some interesting problems.<br>
<br>
In addition to the problems you pose, had you thought about how you<br>
would what to prevent an illegal turn rather than just add a cost to it?<br>
<br>
Also for complex intersections/restrictions you need to be able to<br>
specify a sequence of multiple edges to define a restriction (if<br>
your working with nodes then an ordered list of nodes preceding the<br>
current node under evaluation).<br>
<br>
Vicky, Vidhan, any thoughts on how you might proceed working with<br>
Anthony? I'm thinking that sharing ideas and discussing the issues<br>
and concerns would be a good starting point, but I'll leave this up<br>
to the three of you to sort out what works best with Vicky having<br>
the final say as release manager.<br>
<br>
Best regards,<br>
-Steve<br>
<br>
On 5/17/2017 2:10 PM, A Tasca wrote:<br>
<br>
Hello Stephen,<br>
<br>
I am looking at adding turn costs to the one-to-many dijkstra<br>
implementation in pgRouting 2.4.1. I found that you created a<br>
discussion on this topic<br>
(<a href="https://github.com/pgRouting/pgrouting/issues/610" rel="noreferrer" target="_blank">https://github.com/pgRouting/<wbr>pgrouting/issues/610</a><br>
<<a href="https://github.com/pgRouting/pgrouting/issues/610" rel="noreferrer" target="_blank">https://github.com/pgRouting/<wbr>pgrouting/issues/610</a>><br>
<<a href="https://github.com/pgRouting/pgrouting/issues/610" rel="noreferrer" target="_blank">https://github.com/pgRouting/<wbr>pgrouting/issues/610</a><br>
<<a href="https://github.com/pgRouting/pgrouting/issues/610" rel="noreferrer" target="_blank">https://github.com/pgRouting/<wbr>pgrouting/issues/610</a>>>) and wanted<br>
to share my ideas with you, and possibly get some feedback. If I<br>
am successful, I plan to commit the code to pgRouting for anyone<br>
to use.<br>
<br>
My original plan was to:<br>
<br>
1) Create a turn restriction table, similar to pgr_trsp, that<br>
contains, a pair of edges, and a cost for going from one of<br>
those edges to the other.<br>
<br>
2) Pass this turn restriction table, a reference to the<br>
predecessor map, and a reference to the weight map into a boost<br>
dijkstra visitor.<br>
<br>
3) Every time the visitor examines an edge, it looks at the<br>
predecessor map to figure out which edge it got to the current<br>
vertex from. It will then look at the turn restriction table and<br>
see if there is an added cost for going from the edge it came<br>
from to the edge it is examining. If there is, it will update<br>
the weight map and add the appropriate weight to the edge that<br>
it is examining.<br>
<br>
I was able to implement this and it did exactly what I planned.<br>
The problem is, my plan does not solve the turn restriction<br>
shortest path problem. It adds costs to edges based on turns<br>
that it makes, given the predecessor of the current vertex, but<br>
it does not check to see if a different possible predecessor to<br>
the current vertex would have been a better choice, given the<br>
turn restrictions.<br>
<br>
I am now thinking about how to do this (ie. check to see if a<br>
different possible predecessor to the current vertex would lead<br>
to a lower cost path to the next vertex, given the turn<br>
restrictions). In my mind, this would look like:<br>
<br>
1) For each incoming edge of the current vertex, add the weight<br>
of that edge (gotten from the weight map) to the distance of the<br>
other vertex that this edge connects to (gotten from the<br>
distance map), apply the appropriate turn cost for this edge and<br>
the edge that connects the current vertex to the vertex we want<br>
to go to.<br>
<br>
2) Determine the lowest cost possible path<br>
<br>
3) Update the predecessor map and replace the predecessor of the<br>
current vertex with the vertex that we found to be in the lowest<br>
cost possible path<br>
<br>
4) Update the distance map and replace the distance of the<br>
current vertex with the new distance, based on the new predecessor<br>
<br>
The problem is, I still don't think that this approach will<br>
solve the turn restriction shortest path for every possible<br>
graph. If one of the incoming edges to the current vertex has<br>
not yet been examined, then we will not know the distance of the<br>
vertex that it is connected to.<br>
<br>
If you are still reading, please let me know if you have any<br>
input on whether or not this approach is completely insane,<br>
whether or not you have any input on how to make this work, or<br>
any other input you think might be useful for someone who wants<br>
to get a one-to-many trsp algorithm that is comparable in<br>
run-time to boost dijkstra.<br>
<br>
In this stackoverflow post:<br>
<a href="http://stackoverflow.com/questions/32116289/how-turn-restrictions-in-k-shortest-paths-algorithm-in-pgrouting" rel="noreferrer" target="_blank">http://stackoverflow.com/quest<wbr>ions/32116289/how-turn-restric<wbr>tions-in-k-shortest-paths-<wbr>algorithm-in-pgrouting</a><br>
<<a href="http://stackoverflow.com/questions/32116289/how-turn-restrictions-in-k-shortest-paths-algorithm-in-pgrouting" rel="noreferrer" target="_blank">http://stackoverflow.com/ques<wbr>tions/32116289/how-turn-restri<wbr>ctions-in-k-shortest-paths-<wbr>algorithm-in-pgrouting</a>><br>
, you said that one should just write a wrapper that calls<br>
pgr_trsp for each target, but I am working with around 100->500<br>
targets, a 200,000 edge map, and run-time is critical.<br>
<br>
Thanks for reading and thank you for helping make some great<br>
open source software,<br>
<br>
Anthony<br>
<br>
<br>
<br>
---<br>
This email has been checked for viruses by Avast antivirus software.<br></div></div>
<a href="https://www.avast.com/antivirus" rel="noreferrer" target="_blank">https://www.avast.com/antiviru<wbr>s</a> <<a href="https://www.avast.com/antivirus" rel="noreferrer" target="_blank">https://www.avast.com/antivir<wbr>us</a>><span class=""><br>
<br>
<br>
<br>
<br>
-- <br>
<br>
Georepublic UG (haftungsbeschränkt)<br>
Salzmannstraße 44,<br>
81739 München, Germany<br>
<br>
Vicky Vergara<br>
Operations Research<br>
<br></span>
eMail: <a href="mailto:vicky@georepublic.de" target="_blank">vicky@georepublic.de</a> <<a href="http://georepublic.de" rel="noreferrer" target="_blank">http://georepublic.de</a>><span class=""><br>
Web:<a href="https://georepublic.info" rel="noreferrer" target="_blank">https://georepublic.info</a><br>
<br>
Tel: +49 (089) 4161 7698-1<br>
Fax: +49 (089) 4161 7698-9<br>
<br>
Commercial register: Amtsgericht München, HRB 181428<br>
CEO: Daniel Kastl<br>
<br>
</span></blockquote>
<br><div class="HOEnZb"><div class="h5">
<br>
---<br>
This email has been checked for viruses by Avast antivirus software.<br>
<a href="https://www.avast.com/antivirus" rel="noreferrer" target="_blank">https://www.avast.com/antiviru<wbr>s</a><br>
<br>
</div></div></blockquote></div><br></div>