[Cartoweb-users] Looking for single-destination (shortest path)program

[Jase]

Hi Fay,

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...

Jason

On 5/12/06, Fay Du <fay.du at versaterm.com> wrote:
>
>  Thank Steve and Franck for the help.
>
> 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.
>
>
>
> Fay
>
>
>
>
>
> -----Original Message-----
> *From:* zze-SIGALE PORTANERI F ext RD-BIZZ-SOP [mailto:
> fportaneri.ext at rd.francetelecom.com]
> *Sent:* Friday, May 12, 2006 3:13 AM
> *To:* Fay Du; cartoweb-users at lists.maptools.org;
> postgis-users at postgis.refractions.net
> *Subject:* RE: [Cartoweb-users] Looking for single-destination (shortest
> path)program
>
>
>
> Hi Fay,
>
>
>
> In fact, dijkstra is already calculating a graph from one point of the
> network (the source) to all other points. See
> http://www.nist.gov/dads/HTML/singleSourceShortestPath.html
>
> An animation can be also found at
> http://www.cs.auckland.ac.nz/software/AlgAnim/dijkstra.html
>
>
>
> The current pgdijkstra shortest_path() fonction launches the full graph
> calculation and then retrieve the stack of path only for the given target
> id.
>
> 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.
>
>
>
> However, one problem could be that you have a directed network, and the
> shortest path from the client to the car could be different than the
> shortest path from the car to the client.... but may be it can help.
>
>
>
> Regards
>
> Franck
>
>
>  ------------------------------
>
> *De :* cartoweb-users-bounces at lists.maptools.org [mailto:
> cartoweb-users-bounces at lists.maptools.org] *De la part de* Fay Du
> *Envoy� :* jeudi 11 mai 2006 21:58
>
> *� :* cartoweb-users at lists.maptools.org;
> postgis-users at postgis.refractions.net
> *Objet :* [Cartoweb-users] Looking for single-destination (shortest
> path)program
>
> Hi everyone:
>
>
>
> �� 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?
>
> �� 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.
>
>
>
> Many, many thanks.
>
> Fay
>
> _______________________________________________
> Cartoweb-users mailing list
> Cartoweb-users at lists.maptools.org
> http://lists.maptools.org/mailman/listinfo/cartoweb-users
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.maptools.org/pipermail/cartoweb-users/attachments/20060513/284c0149/attachment-0001.html