[pgrouting-dev] GSoC 2013

[Stephen Woodbridge]

Hi Raffaello,

Thank you for your interest. It sounds like you are doing some 
interesting work.

On 4/16/2013 10:38 AM, Raffaello Bertini wrote:
> Hi,
> I'm raffaello bertini student of computer science university of Bologna,
> Italy.
> i'm actually doing a thesys project using pgrouting (forked) to solve
> tsp, vrp problem.

You might be interested to look at sew-devel-2_0 branch in github. This 
will be our 2.0 release eventually. I have already integrated a lot of 
changes into it. On major change it the there is a new TSP solver that 
is not dependent on GAUL, and while I have not benchmarked it yet, I 
believe it is faster than GAUL.

> My master course of computer science was on logistic and graph theory
> problem, algorithm and code-optimization
> I'm interested partecipating in Gsoc2013 to:
> -develop vrp problem (heuristic) based on tsp instance.
> -develop a strategy for caching data to speed-up computation for problem
> or large problem.
> -and I'm also interested in contraction Hieracy.
>
> actually I've already developed on my pgrouting forked: project:
>
> tsp 3opt asym (start from nearest neighbour).
> trivial vrp single depot solution
> a overlay graph mapping dijkstra solutions, usefull for computation on
> tsp/vrp or any algorithm that needs it.

This would all be interesting stuff to contribute back to pgRouting.

I think that we would like to get the contraction hierarchy code 
integrated with pgrouting. The big value is the ability to compute many 
routes very quickly, which would be advantageous for compute the 
distance matrix needed to feed the tsp solver. The challenge will be how 
to integrate this with pgRouting. One solution might be to set it up as 
a separate daemon where the plpgsql wrapper connects to it via shared 
memory or a socket and passes the query to it and then formates the 
results back to the SQL caller.

Because of the cost to detoast blobs in the database, I'm not sure there 
is any value in trying to store the preprocessed data in the database. 
We might want to have a data loader than can pull the edge data from the 
database via a configured SQL query and then build the contraction 
hierarchy data file, which then gets used for later route requests.

Anyway, I'm interested in hearing more about your ideas on your three 
areas of interest.

Thanks,
   -Steve