[pgrouting-dev] pgrouting extensions

[sumit singh]

Hi all,

I am master's student from IIT Kanpur, India and have been looking at
the source code of pgrouting. I have some points to make

1) One of the things i noticed is that the TSP code is genetic
algorithm based and to my understanding the code tries to provide some
feasible answer, which is possibly good due to the involved heuristic.
For large datasets this is a good approach but a lot more might be
possible. One direction could be implementation of approximation
algorithms that are fast and provide some guarantee of solution in
certain scenarios.

2) The other kind of problem that you cover is shortest path problem
which is sufficient for medium-large data. As an extension, however
the work can be stretched by implementing algorithms based on
hierarchal models.

3) There are still lot more algorithms which should be included in
this library. Examples:

   a) If the input data is complete graph or points from euclidean
plane then problems like euclidean TSP would be interesting and has
fast algorithms for almost optimal solutions.
   b) Variants of TSP: example - Instead of all cities in one tour as
in TSP, one might want to visit selective cities.
   c) Spanning Trees - Instead of tour, one might be ready to visit
selective cities again given the fact that cost should be minimum.
   d) Coloring Maps i.e. graph coloring.
   e) Maximum flow problem.
   f) Graph-Clustering. (i like this one specially if you are looking
beyond graphs that are maps)

I am interested to contribute to pgrouting as it closely fits my
interest. I will be applying for Google summer of Code , and want to
do some of the above or related work. I would appreciate any feedback
from the team.

with regards,
sumit singh.