[pgrouting-dev] GSoC 2013

[Raffaello Bertini]

another value for CH, it's is ability to manage huge graph.

ok, go on my ideas:
based on an overlay graph (the distance matrix), generated from multiple
dijkstra results, used for tsp/vrp problem, instead of using euclidean
distances ("distance as the crow flies") and achieve better results:

-*strategy for caching data*:
 need a table/indexed file to store results (this step can be precomputed
or in "real-time request generated")
 when building the graph for ex. tsp computation, check&fetch data directly
on that table, instead of fetch the data from the "roads graph" table and
then compute the arc connect "2 city", if the data it's not present ca be
computed and inserted in the overlay graph. Trading speed for datasize and
reduce fetching data. This operation can be partialy, some are to compute
others are fetched because precompute from previsius dijkstra calling.
The table simply store the node source,target and optional geometry for
visualization. To manage multiple road tables as data input, algorithm
create tables using *special*name  (the name of original table plus
"something") and use it respectively.
if some user wants "detailed" results, the dijkstra results (ex:  the path
connecting 2 city) , it can be used another table (maybe temporary for the
problem istances) to fetch data directly instead of recompute a single
arc/dikstra solution.

One more point is to use  "WaypointResults Table", that can be used to
store solution of some TSP/VRP problem and than fetch solution directly
instead of (re)compute it. etc......

-*vrp (with capacity)*: The first VRP algorithm can be based on the tsp, so
it's somenthing like solving multiple TSP problem. Do it on single and/or
multidepot. Needs one more parameter input as sql query for depots....
So if the vrp depends on tsp, it's a good thing to have a good tsp solver
too..
It also can benefit from the above strategy proposed.

-*CH*: I never worked on it and i will really happy to do it, I think i can
do it in the contest of GSoc. But and i don't have detailed insights at all
on it, I found an online thesys that seems a good point to start. So the
main idea is to develop around the dijkstra and use it to speed up the
results of shortest_path, etc....
The technique of contraction remind me of a tsp historical problem (pr76)
and the way it was resolved.
Some strategies for manage the preprocessing phase can be achieved as you
said or maybe even better.
Finally saying, the first step i think is integrating/developing CH for
pgrouting;
the 2nd find a way to improve performance on preprocessing, etc...


On Tue, Apr 16, 2013 at 5:16 PM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:

> 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
> ______________________________**_________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130416/45225685/attachment.html>