What features should be included?

Mar 26, 2009 at 2:37 AM
Edited Mar 26, 2009 at 2:40 AM
From an admittedly cursory examination of the pgRouting, it seems to implement 6 main functions:
  1. Topology Creation - creation of routing data
  2. Shortest path Dijkstra - simple routing with any heuristics (weighting)
  3. Shortest path A* - routing for large data sets with heuristics
  4. Shortest Path Shooting Star - routing with turn restrictions
  5. Traveling Sales Person problem
  6. Driving distance calculation
It order to have a usable library we would need to implement at least the topology creation function and one of the shortest path functions.  I would propose that we implement the topology creation and A* function first, as Dijkstra can be implemented using the A* function.  On the pgRouting page description for topology creation, they indicate that there are several third party products that can accomplish this task.  However, as it is a fundamental piece of the library (perhaps the most fundamental), it would probably be worth implementing this ourselves.  

The driving distance calculation would be next in importance.  However, I think that we would get this for free if we implement the shortest path functions correctly.

I think that these three functions should be the target of our first release of ssRouting.

The Traveling Sales Person function (or at best an approximation) should be implemented next as it would be useful to specify several waypoints and have the system determine a circular path from a start point to all waypoints and return to the start point.  However, for our immediate usage, this would be a future feature, possible the second release of ssRouting.

The Shooting Star function will not really be necessary for our immediate use, as most bike paths are two way.  However, it should be implemented at some future point for completeness.  Possibly the third release of ssRouting.