Hi Fay,<br><br>I had a simmilar problem and what I did was to actualy narrow down the closest 5 vehicles from a particular point using PostGIS's distance() algorithm. With this 5 vehicles, I perform the Dijkstra's algorithm to get the actual distance of this 5 vehicles. I know there are flaws with this method but it would cut down the search time rather than looping through all your vehicles. You can increase the number of vehicles to be shortlisted to increase accuracy but I would assume that one of the 5 closest vehicles to the point would be the closest. However, this method would definately not give you a 1 second calculation and would take some time...
<br><br>Jason<br><br><div><span class="gmail_quote">On 5/12/06, <b class="gmail_sendername">Fay Du</b> <<a href="mailto:fay.du@versaterm.com">fay.du@versaterm.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div>
<div link="blue" vlink="purple" lang="EN-US">
<div>
<p><font face="Courier New" size="2"><span style="font-size: 10pt;">Thank Steve and Franck for the help.</span></font></p>
<p><font face="Courier New" size="2"><span style="font-size: 10pt;">As Franck said, my network is directed, the path from client site to a
car site could be different with the path from car site to the client site. For
example, in a one way street, you can easily to go form one point to another by
following the traffic direction. But if you want go back to you start point,
you have to go to other streets to make a loop back. The 2 paths are different.</span></font></p>
<p><font color="navy" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: navy;"> </span></font></p>
<p><font color="navy" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: navy;">Fay</span></font></p></div><div><span class="q">
<p><font color="navy" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: navy;"> </span></font></p>
<p><font color="navy" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: navy;"> </span></font></p>
<p style="margin-left: 0.5in;"><font face="Tahoma" size="2"><span style="font-size: 10pt; font-family: Tahoma;">-----Original Message-----<br>
<b><span style="font-weight: bold;">From:</span></b> zze-SIGALE PORTANERI F ext
RD-BIZZ-SOP [mailto:<a href="mailto:fportaneri.ext@rd.francetelecom.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">fportaneri.ext@rd.francetelecom.com</a>] <br>
<b><span style="font-weight: bold;">Sent:</span></b> </span></font><font face="Tahoma" size="2"><span style="font-size: 10pt; font-family: Tahoma;">Friday, May 12, 2006</span></font><font face="Tahoma" size="2"><span style="font-size: 10pt; font-family: Tahoma;">
</span></font><font face="Tahoma" size="2"><span style="font-size: 10pt; font-family: Tahoma;">3:13 AM</span></font><font face="Tahoma" size="2"><span style="font-size: 10pt; font-family: Tahoma;"><br>
<b><span style="font-weight: bold;">To:</span></b> Fay Du;
<a href="mailto:cartoweb-users@lists.maptools.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">cartoweb-users@lists.maptools.org</a>; <a href="mailto:postgis-users@postgis.refractions.net" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
postgis-users@postgis.refractions.net</a><br>
<b><span style="font-weight: bold;">Subject:</span></b> RE: [Cartoweb-users]
Looking for single-destination (shortest path)program</span></font></p>
<p style="margin-left: 0.5in;"><font face="Times New Roman" size="3"><span style="font-size: 12pt;"> </span></font></p>
<p style="margin-left: 0.5in;"><font color="blue" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: blue;">Hi Fay,</span></font></p>
<p style="margin-left: 0.5in;"><font face="Times New Roman" size="3"><span style="font-size: 12pt;"> </span></font></p>
<p style="margin-left: 0.5in;"><font color="blue" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: blue;">In fact, dijkstra is
already calculating a graph from one point of the network (the source) to all
other points. See <a href="http://www.nist.gov/dads/HTML/singleSourceShortestPath.html" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://www.nist.gov/dads/HTML/singleSourceShortestPath.html</a>
</span></font></p>
<p style="margin-left: 0.5in;"><font color="blue" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: blue;">An animation can be also
found at <a href="http://www.cs.auckland.ac.nz/software/AlgAnim/dijkstra.html" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://www.cs.auckland.ac.nz/software/AlgAnim/dijkstra.html</a></span>
</font></p>
<p style="margin-left: 0.5in;"><font face="Times New Roman" size="3"><span style="font-size: 12pt;"> </span></font></p>
<p style="margin-left: 0.5in;"><font color="blue" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: blue;">The current pgdijkstra shortest_path()
fonction launches the full graph calculation and then retrieve the stack of
path only for the given target id.</span></font></p>
<p style="margin-left: 0.5in;"><font color="blue" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: blue;">It can be very simple
(i.e. with one call to dijksta) to get the nearest car from the client by using
the client as the source point. It needs some extension to the current dijkstra
contrib code to pass one source id (client) and an array of target (cars) to
the current shortest_path function: When the graph is complete, you just need
to choose the target from the list which gives the smaller cost.</span></font></p>
<p style="margin-left: 0.5in;"><font face="Times New Roman" size="3"><span style="font-size: 12pt;"> </span></font></p>
<p style="margin-left: 0.5in;"><font color="blue" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: blue;">However, one problem
could be that you have a directed network, and the shortest path from</span></font> <font color="blue" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: blue;">the client to the car could be different than the shortest path
from</span></font><font color="black"><span style="color: black;"> </span></font><font color="blue" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: blue;">the car to the client.... but may be it can help.
</span></font></p>
<div>
<p style="margin-left: 0.5in;"><font face="Times New Roman" size="3"><span style="font-size: 12pt;"> </span></font></p>
</div>
<div>
<p style="margin-left: 0.5in;"><font color="blue" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: blue;">Regards</span></font></p>
</div>
<div>
<p style="margin-left: 0.5in;"><font color="blue" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: blue;">Franck</span></font></p>
</div>
<p style="margin-left: 0.5in;"><font face="Times New Roman" size="3"><span style="font-size: 12pt;"> </span></font></p>
<div style="margin-left: 0.5in; text-align: center;" align="center"><font face="Times New Roman" size="3"><span style="font-size: 12pt;" lang="FR">
<hr align="center" size="2" width="100%">
</span></font></div>
</span></div><div><p style="margin-right: 0in; margin-bottom: 12pt; margin-left: 0.5in;"><b><font face="Tahoma" size="2"><span style="font-size: 10pt; font-family: Tahoma; font-weight: bold;" lang="FR">De :</span></font>
</b><font face="Tahoma" size="2"><span style="font-size: 10pt; font-family: Tahoma;" lang="FR"> <a href="mailto:cartoweb-users-bounces@lists.maptools.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
cartoweb-users-bounces@lists.maptools.org</a>
[mailto:<a href="mailto:cartoweb-users-bounces@lists.maptools.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">cartoweb-users-bounces@lists.maptools.org</a>] <b><span style="font-weight: bold;">
De la part de</span></b> Fay Du<br>
<b><span style="font-weight: bold;">Envoy� :</span></b> jeudi 11 mai 2006
21:58</span></font></p></div><font face="Tahoma" size="2"></font><div><span class="q"><font face="Tahoma" size="2"><br>
<b><span style="font-weight: bold;">� :</span></b>
<a href="mailto:cartoweb-users@lists.maptools.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">cartoweb-users@lists.maptools.org</a>; <a href="mailto:postgis-users@postgis.refractions.net" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
postgis-users@postgis.refractions.net</a><br>
<b><span style="font-weight: bold;">Objet :</span></b> [Cartoweb-users]
Looking for single-destination (shortest path)program</font></span></div><div><span lang="FR"></span><p></p></div><div><span class="q">
<p style="margin-left: 0.5in;"><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;">Hi everyone:</span></font></p>
<p style="margin-left: 0.5in;"><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;"> </span></font></p>
<p style="margin-left: 0.5in;"><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;"><span>��
</span>I am trying to use pgDijkstra in my project. pgDijkstra calls boost
library which provides single-source shortest function. My network is a street
network. The graph is directed. My typical scenario is, there is one client
calls dispatch center and there are many cars (for example, 100 cars) are
available all over the network. I want to find the closet car and dispatch it
to the client. It is a single-destination problem. Does anyone know if there is
an existing single-destination program exists available for my project? Or the
explanation of the single-destination algorithm?</span></font></p>
<p style="margin-left: 0.5in;"><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;"><span>��
</span>I know I can call pgDijkstra multiple times to get the answer. The
performance of the solution is not good. Our goal is to calculate shortest
paths of 100 cars to the same destination in less than a second. Calling
pgDijkstra 100 times takes much, much more time than our goal.</span></font></p>
<p style="margin-left: 0.5in;"><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;"> </span></font></p>
<p style="margin-left: 0.5in;"><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;">Many, many thanks.</span></font></p>
<p style="margin-left: 0.5in;"><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;">Fay</span></font></p>
</span></div><div></div>
</div>
</div><br>_______________________________________________<br>Cartoweb-users mailing list<br><a onclick="return top.js.OpenExtLink(window,event,this)" href="mailto:Cartoweb-users@lists.maptools.org">Cartoweb-users@lists.maptools.org
</a><br><a onclick="return top.js.OpenExtLink(window,event,this)" href="http://lists.maptools.org/mailman/listinfo/cartoweb-users" target="_blank">http://lists.maptools.org/mailman/listinfo/cartoweb-users</a><br><br><br></blockquote>
</div><br>