Hi Iñigo,<div><br></div><div>I needed to do something similar to what you are trying to do some time ago and asked in the list. Unfortunately, it is not possible to retrieve several shortest paths in one run. It is certainly possible to reduce the time needed to perform the shortest path routing between a set of nodes, but for this the code of the shortest_path C function should be modified to fetch the road network data it needs from the DB only once and then perform the routing algorithm several times. </div>
<div><br></div><div>Tao</div>
<div class="gmail_extra"><br><br><div class="gmail_quote">2012/11/21 Iñigo Vázquez <span dir="ltr"><<a href="mailto:ivgwildchild666@hotmail.com" target="_blank">ivgwildchild666@hotmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div><div dir="ltr"><span style="font-size:12pt">Thanks for your reply, but in my case the shortest path doesn`t interest me. I need the shortest paths from one given node to each others beacuse then I want to calculate a path taking into account a given time limit. </span><br>
<div><div dir="ltr"><div><br></div><div>Something like in the "Traveling Salesman Problem" but with Time Window.</div><div><br></div><div>Thanks!<br><div class="hm HOEnZb"><br></div><div><div class="hm HOEnZb"><div>
</div><hr>From: <a href="mailto:gunnar@tradlosetrondheim.no" target="_blank">gunnar@tradlosetrondheim.no</a><br>Date: Wed, 21 Nov 2012 11:08:03 +0100<br>Subject: Re: [pgrouting-users] Multiple queries in a row<br>To: <a href="mailto:pgrouting-users@lists.osgeo.org" target="_blank">pgrouting-users@lists.osgeo.org</a><br>
CC: <a href="mailto:ivgwildchild666@hotmail.com" target="_blank">ivgwildchild666@hotmail.com</a></div><div><div class="h5"><br><br>Hello,<div><br></div><div><br></div><div>I do not know the answer to you question, but I might know an workarround if you are only interrested in the shortest of them.</div>
<div><br></div><div>We use a hack to find the path to the closest node of a set of nodes.</div>
<div><br></div><div>Basically we tweak the query which builds the graph to rename all nodes which are applicable to some id which cannot be found in the graph elsewere (e.g. -1), and the search for the path to this node.</div>
<div><br></div><div>(NB: this could/would give strange beahviour if used with astar)</div><div><br></div><div><br></div><div><br></div><div>Best regards Gunnar</div><div><br><br><div>2012/11/21 Iñigo Vázquez <span dir="ltr"><<a href="mailto:ivgwildchild666@hotmail.com" target="_blank">ivgwildchild666@hotmail.com</a>></span><br>
<blockquote style="border-left:1px #ccc solid;padding-left:1ex">
<div><div dir="ltr">Dear all,<div><br></div><div><p style="margin-bottom:1em;border:0px;font-size:14px;vertical-align:baseline;clear:both;word-wrap:break-word;color:rgb(51,51,51);font-family:'Helvetica Neue',Helvetica,Arial,sans-serif;line-height:18px">
I need to obtain a set of nearest nodes from a given location (maybe 30 or 40). Then I need to calculate the shortest path from the given node from each others. It means to execute shortes_path query multiple times in a row, wich takes about 2 seconds (1 query 2 seconds: 30 queries 60 -> too long).</p>
<pre style="margin-bottom:10px;padding:5px;border:0px;font-size:12px;vertical-align:baseline;overflow:auto;width:auto;max-height:600px;font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif;background-color:rgb(238,238,238);color:rgb(57,51,24);line-height:18px">
<code style="padding:0px;border:0px;vertical-align:baseline;font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif;color:rgb(34,34,34)"><span style="padding:0px;border:0px;vertical-align:baseline;color:rgb(138,74,11)">SELECT</span><span style="padding:0px;border:0px;vertical-align:baseline;color:black"> </span><span style="padding:0px;border:0px;vertical-align:baseline;color:rgb(20,86,128)">*</span><span style="padding:0px;border:0px;vertical-align:baseline;color:black"> </span><span style="padding:0px;border:0px;vertical-align:baseline;color:rgb(138,74,11)">FROM</span><span style="padding:0px;border:0px;vertical-align:baseline;color:black"> shortest_path</span><span style="padding:0px;border:0px;vertical-align:baseline;color:rgb(20,86,128)">(</span><span style="padding:0px;border:0px;vertical-align:baseline;color:maroon">'
SELECT id AS id,
source::int4 AS source,
target::int4 AS target,
cost::float8 AS cost
FROM tt_2po_4pgr'</span><span style="padding:0px;border:0px;vertical-align:baseline;color:rgb(20,86,128)">,</span><span style="padding:0px;border:0px;vertical-align:baseline;color:black">
</span><span style="padding:0px;border:0px;vertical-align:baseline;color:rgb(149,56,56)">275742</span><span style="padding:0px;border:0px;vertical-align:baseline;color:rgb(20,86,128)">,</span><span style="padding:0px;border:0px;vertical-align:baseline;color:black">
</span><span style="padding:0px;border:0px;vertical-align:baseline;color:rgb(149,56,56)">274494</span><span style="padding:0px;border:0px;vertical-align:baseline;color:rgb(20,86,128)">,</span><span style="padding:0px;border:0px;vertical-align:baseline;color:black">
false</span><span style="padding:0px;border:0px;vertical-align:baseline;color:rgb(20,86,128)">,</span><span style="padding:0px;border:0px;vertical-align:baseline;color:black">
false</span><span style="padding:0px;border:0px;vertical-align:baseline;color:rgb(20,86,128)">)</span></code></pre><p style="margin-bottom:1em;border:0px;font-size:14px;vertical-align:baseline;clear:both;word-wrap:break-word;color:rgb(51,51,51);font-family:'Helvetica Neue',Helvetica,Arial,sans-serif;line-height:18px">
What would be the best way to do this in a reasonable time?</p><p style="margin-bottom:1em;border:0px;font-size:14px;vertical-align:baseline;clear:both;word-wrap:break-word;color:rgb(51,51,51);font-family:'Helvetica Neue',Helvetica,Arial,sans-serif;line-height:18px">
<br></p><p style="margin-bottom:1em;border:0px;font-size:14px;vertical-align:baseline;clear:both;word-wrap:break-word;color:rgb(51,51,51);font-family:'Helvetica Neue',Helvetica,Arial,sans-serif;line-height:18px">
Thank in advance!</p><p style="margin-bottom:1em;border:0px;font-size:14px;vertical-align:baseline;clear:both;word-wrap:break-word;color:rgb(51,51,51);font-family:'Helvetica Neue',Helvetica,Arial,sans-serif;line-height:18px">
<br></p><p style="margin-bottom:1em;border:0px;font-size:14px;vertical-align:baseline;clear:both;word-wrap:break-word;color:rgb(51,51,51);font-family:'Helvetica Neue',Helvetica,Arial,sans-serif;line-height:18px">
Pd: excuse my english</p></div> </div></div>
<br>_______________________________________________<br>
Pgrouting-users mailing list<br>
<a href="mailto:Pgrouting-users@lists.osgeo.org" target="_blank">Pgrouting-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-users</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><table style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:normal;text-decoration:none" border="0">
<tbody style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:normal;text-decoration:none">
<tr style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:normal;text-decoration:none">
<td style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:bold;text-decoration:none">Gunnar Rangøy</td>
</tr>
<tr style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:normal;text-decoration:none">
<td style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:normal;text-decoration:none">System developer</td>
</tr>
<tr style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:normal;text-decoration:none">
<td style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:normal;text-decoration:none">Trådløse Trondheim / Wireless Trondheim</td>
</tr>
<tr style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:normal;text-decoration:none">
<td style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:normal;text-decoration:none"><a style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:normal;text-decoration:none" href="http://tradlosetrondheim.no/" target="_blank"><span>tradlosetrondheim.no</span></a></td>
</tr>
<tr style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:normal;text-decoration:none">
<td style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:normal;text-decoration:none"><a style="color:#010101;font-size:12px;font-family:arial,sans-serif;font-weight:normal;text-decoration:none">+47 99 36 06 99</a></td>
</tr>
</tbody>
</table>
<br>
</div></div></div></div></div> </div></div> </div></div>
<br>_______________________________________________<br>
Pgrouting-users mailing list<br>
<a href="mailto:Pgrouting-users@lists.osgeo.org">Pgrouting-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-users</a><br>
<br></blockquote></div><br></div>