PGdijkstra Routing performance

I have gotten a surprising amount of questions since i posted my routing articles using Cartoweb’s pgdijkstra PostGIS pl/sql functions. A lot have focused around the speed of the routing calculations, especially in comparison with commercial offerings.

Disclaimer: This should only aid in you decision making. I definately would not consider using pgdjikstra to replace emergency vehicles routing and travelling salesmen type problems. Considerable work would need to be added to flesh out commonly requested features such as turn by turn navigation

Alright, lets see how we went …

Sample dataset: 57k vertices, 44k nodes

Machine specs: P4 Celeron M 2.6ghz Laptop, 512mb RAM, PostgreSQL 8.1

Sample queries are using the following function,

SELECT astext(the_geom) FROM shortest_path_as_geometry(‘roadstable’, startnode, endnode)

uery

Key

From

To

Path Size

(coord pairs)

Query Time

1

219102

181359

792

984.056 ms

2

216366

179845

738

1289.002 ms

3

229280

188416

586

871.655 ms

4

205276

197586

660

1421.800 ms

5

229280

179038

941

2180.597 ms

6

209203

206037

491

1101.798 ms

7

203982

193450

208

755.187 ms

Routing geometry
Click to enlarge!

Considering my laptop is definately not the best benchmark machine, I can only assume that deployment on a proper server environment would result in a significant performance increase across the board.

Interesting stuff! Head over to cartoweb.org to give Sylvain and his crew any feedback or bugs. I havent checked lately but i’m sure the CVS version have had some improvements.

3 thoughts on “PGdijkstra Routing performance”

  1. Hi,

    Your benchmarks are quite interesting. Regarding CVS there is no improvements since the binaries you are using, but some people have developped some nice enhancements to pgdijkstra, that may be part of the main distribution in the future and which could improve performances quite a bit. Maybe I will put a link to your page in a possible performance section on our wiki.

    By the way, my name is Sylvain Pasche, not Paschain. Nice to see how you merged that ;-)

  2. Sorry Sylvain, i merged your names without even knowing

    You guys should be pleased with the amount of interest this module is getting … lots of queries!

  3. Hi Chris,
    I kow it is been a while since you wrote this tutorial. I was wondering if you any tips to providing turn-by-turn navigation. I have look all over the internet with no luck (even pgrouting website). I will appreciate any input

Comments are closed.