[pgrouting-users] Shortest Route Search Not Working

pgRouting pgrouting-users
1

Hi Daniel,

To follow on Yasir's comments in terms of routing results, I've been working with a simple example data set where the distance and travel time results are likely to be different (really there are several equally good routes based on distance, but a unique route based on travel time, but with the "length" field in the database reflecting travel time along an edge). When doing the routing based on travel time I get the correct solution using the Dijkstra algorithm, but an incorrect result using the A* and Shooting Star algorithms. The nature of the errors I'm getting would be consistent with what Yasir is finding. I'd be glad to send you both the network data and my test queries. I'm running on 64bit Ubuntu 10.04 using the Ubuntu repository version of PostgreSQL (8.4.4), PostGIS 1.5.1, and built pgRouting from the subversion repository on Tuesday.

Dan

--- On Fri, 7/16/10, Daniel Kastl <daniel.kastl@georepublic.de> wrote:

From: Daniel Kastl <daniel.kastl@georepublic.de>
Subject: Re: [pgrouting-users] Shortest Route Search Not Working
To: pgrouting-users@lists.osgeo.org
Received: Friday, July 16, 2010, 9:58 PM

I hope you don't mind helping me with another couple short questions:
1. Projection 4326 with latlng is lot easier for me to work with. Although there are ways to convert the latlng to
900913 projection, I was wondering how would I be able to directly use 4326 and run search on it (HTML changes), assuming that the tiles were generated with 900913 projection and the routing database is set to 4326?

You can use Postgis "transform()" function to do this: http://postgis.refractions.net/docs/ST_Transform.html

2. Just out of curiosity.
The routing results usually take residential route ways, instead of taking instead of taking highway streets (which is more like what results from Google Maps show). Any ideas why the difference?

pgRouting gives you the "shortest" path and it's up to you to define what is "shortest". Easiest is to take length as cost, but if you take time as cost, then shortest will be the fastest. You could for example define some speed for your road classes, and if the speed is higher on highways it will prefer the highway like Google Maps does.

Daniel

Thanks

_______________________________________________

Pgrouting-users mailing list

Pgrouting-users@lists.osgeo.org

http://lists.osgeo.org/mailman/listinfo/pgrouting-users

-----Inline Attachment Follows-----

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

2

Hi Dan,

A* and Shooting* have a heuristic component and prefer to move towards the goal. It’s an assumption to make shortest path search faster, though usually data loading time takes a lot longer than path calculation. You usually don’t see a (big) difference.
You can send me some data and I can take a look.

Daniel

2010/7/18 Dan Putler <putler@yahoo.com>

Hi Daniel,

To follow on Yasir’s comments in terms of routing results, I’ve been working with a simple example data set where the distance and travel time results are likely to be different (really there are several equally good routes based on distance, but a unique route based on travel time, but with the “length” field in the database reflecting travel time along an edge). When doing the routing based on travel time I get the correct solution using the Dijkstra algorithm, but an incorrect result using the A* and Shooting Star algorithms. The nature of the errors I’m getting would be consistent with what Yasir is finding. I’d be glad to send you both the network data and my test queries. I’m running on 64bit Ubuntu 10.04 using the Ubuntu repository version of PostgreSQL (8.4.4), PostGIS 1.5.1, and built pgRouting from the subversion repository on Tuesday.

Dan

— On Fri, 7/16/10, Daniel Kastl <daniel.kastl@georepublic.de> wrote:

From: Daniel Kastl <daniel.kastl@georepublic.de>
Subject: Re: [pgrouting-users] Shortest Route Search Not Working
To: pgrouting-users@lists.osgeo.org
Received: Friday, July 16, 2010, 9:58 PM

I hope you don’t mind helping me with another couple short questions:

  1. Projection 4326 with latlng is lot easier for me to work with. Although there are ways to convert the latlng to
    900913 projection, I was wondering how would I be able to directly use 4326 and run search on it (HTML changes), assuming that the tiles were generated with 900913 projection and the routing database is set to 4326?

You can use Postgis “transform()” function to do this: http://postgis.refractions.net/docs/ST_Transform.html

  1. Just out of curiosity.
    The routing results usually take residential route ways, instead of taking instead of taking highway streets (which is more like what results from Google Maps show). Any ideas why the difference?

pgRouting gives you the “shortest” path and it’s up to you to define what is “shortest”. Easiest is to take length as cost, but if you take time as cost, then shortest will be the fastest. You could for example define some speed for your road classes, and if the speed is higher on highways it will prefer the highway like Google Maps does.

Daniel

Thanks

Pgrouting-users mailing list

Pgrouting-users@lists.osgeo.org

http://lists.osgeo.org/mailman/listinfo/pgrouting-users

-----Inline Attachment Follows-----

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

3

Hello Dan,

I took a look at the data you sent and the solution appears to be the use
weighted costs (pp. 19-20):
http://www.osgeo.jp/wordpress/wp-content/uploads/2009/11/workshop_manual.pdf
Daniel, himself was the presenter.

Furthermore, reply from Daniel to my post does mention the same point
regarding the difference in results from Google Maps:

...You could for example define some speed for your road classes, and if

the speed is higher on highways it will prefer the highway like Google Maps

does.

Will look into this further if you think otherwise.

Thanks,
Yasir

-----Original Message-----
From: Dan Putler [mailto:putler@yahoo.com]
Sent: July-17-10 1:40 PM
To: pgrouting-users@lists.osgeo.org; Daniel Kastl
Subject: Re: [pgrouting-users] Shortest Route Search Not Working

Hi Daniel,

To follow on Yasir's comments in terms of routing results, I've been working
with a simple example data set where the distance and travel time results
are likely to be different (really there are several equally good routes
based on distance, but a unique route based on travel time, but with the
"length" field in the database reflecting travel time along an edge). When
doing the routing based on travel time I get the correct solution using the
Dijkstra algorithm, but an incorrect result using the A* and Shooting Star
algorithms. The nature of the errors I'm getting would be consistent with
what Yasir is finding. I'd be glad to send you both the network data and my
test queries. I'm running on 64bit Ubuntu 10.04 using the Ubuntu repository
version of PostgreSQL (8.4.4), PostGIS 1.5.1, and built pgRouting from the
subversion repository on Tuesday.

Dan

--- On Fri, 7/16/10, Daniel Kastl <daniel.kastl@georepublic.de> wrote:

From: Daniel Kastl <daniel.kastl@georepublic.de>
Subject: Re: [pgrouting-users] Shortest Route Search Not Working
To: pgrouting-users@lists.osgeo.org
Received: Friday, July 16, 2010, 9:58 PM

I hope you don't mind helping me with another couple short questions:
1. Projection 4326 with latlng is lot easier for me to work with. Although
there are ways to convert the latlng to
900913 projection, I was wondering how would I be able to directly use 4326
and run search on it (HTML changes), assuming that the tiles were generated
with 900913 projection and the routing database is set to 4326?

You can use Postgis "transform()" function to do
this: http://postgis.refractions.net/docs/ST_Transform.html

2. Just out of curiosity.
The routing results usually take residential route ways, instead of taking
instead of taking highway streets (which is more like what results from
Google Maps show). Any ideas why the difference?

pgRouting gives you the "shortest" path and it's up to you to define what is
"shortest". Easiest is to take length as cost, but if you take time as cost,
then shortest will be the fastest. You could for example define some speed
for your road classes, and if the speed is higher on highways it will prefer
the highway like Google Maps does.

Daniel

Thanks

_______________________________________________

Pgrouting-users mailing list

Pgrouting-users@lists.osgeo.org

http://lists.osgeo.org/mailman/listinfo/pgrouting-users

-----Inline Attachment Follows-----

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

4

Yasir, to be clear, you can use any information you have available to you to use as the weight/cost for each segment, and things like posted speed and road length, number of lanes, traffic conditions, etc are typically used to affect the cost.

But if for example you had geo data on Dunkin Donuts stores and you used this to give segments with Dunkin Donuts stores a lower “cost”, you’d find your trips across the US taking you through the New England states :slight_smile:

hth
charles

On Jul 20, 2010, at 11:37 PM, Yasir Shoaib wrote:

Hello Dan,

I took a look at the data you sent and the solution appears to be the use
weighted costs (pp. 19-20):
http://www.osgeo.jp/wordpress/wp-content/uploads/2009/11/workshop_manual.pdf
Daniel, himself was the presenter.

Furthermore, reply from Daniel to my post does mention the same point
regarding the difference in results from Google Maps:

…You could for example define some speed for your road classes, and if

the speed is higher on highways it will prefer the highway like Google Maps

does.

Will look into this further if you think otherwise.

Thanks,
Yasir