onsdag 26 januari 2011

PG Routing Shooting Star issue

screenshot43In a recent project I’m using PG Routing for routing with Navteq data. To route start to stop PGRouting comes with three different algorithms.

  • Djikstra – classic shortest path.
  • Shortest Path A* – using heuristics to find the shortest path.
  • Shortest Path Shooting Star – using heuristics with traffic rules to find the shortest path.

The Djikstra and Shortest Path A* works fine and are pretty fast after working with the network and bounding box. When trying the algorithm Shortest Path Shooting Star there are some problems. One major problem is when starting reverse direction of the first link.

Navteq’s segments starts from south. So when calculating a route on that starts off south there is a phenomena, see image. It should a straight line from the top point to the bottom point, very badly visualized.