<div dir="ltr">another value for CH, it's is ability to manage huge graph.<br><br>ok, go on my ideas:<br>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:<br>

<br>-<b>strategy for caching data</b>: <br> need a table/indexed file to store results (this step can be precomputed or in "real-time request generated")<br> 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.<br>

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. <br>

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.<br>

<br>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......<br><br>-<b>vrp (with capacity)</b>: 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.... <br>

So if the vrp depends on tsp, it's a good thing to have a good tsp solver too.. <br>It also can benefit from the above strategy proposed.<br><div><div style><br></div></div><div style>-<b>CH</b>: 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....</div>

<div style>The technique of contraction remind me of a tsp historical problem (pr76) and the way it was resolved. <br>Some strategies for manage the preprocessing phase can be achieved as you said or maybe even better. <br>

Finally saying, the first step i think is integrating/developing CH for pgrouting;<br>the 2nd find a way to improve performance on preprocessing, etc...</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">

On Tue, Apr 16, 2013 at 5:16 PM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

Hi Raffaello,<br>
<br>
Thank you for your interest. It sounds like you are doing some interesting work.<div class="im"><br>
<br>
On 4/16/2013 10:38 AM, Raffaello Bertini wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi,<br>
I'm raffaello bertini student of computer science university of Bologna,<br>
Italy.<br>
i'm actually doing a thesys project using pgrouting (forked) to solve<br>
tsp, vrp problem.<br>
</blockquote>
<br></div>
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.<div class="im">

<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
My master course of computer science was on logistic and graph theory<br>
problem, algorithm and code-optimization<br>
I'm interested partecipating in Gsoc2013 to:<br>
-develop vrp problem (heuristic) based on tsp instance.<br>
-develop a strategy for caching data to speed-up computation for problem<br>
or large problem.<br>
-and I'm also interested in contraction Hieracy.<br>
<br>
actually I've already developed on my pgrouting forked: project:<br>
<br>
tsp 3opt asym (start from nearest neighbour).<br>
trivial vrp single depot solution<br>
a overlay graph mapping dijkstra solutions, usefull for computation on<br>
tsp/vrp or any algorithm that needs it.<br>
</blockquote>
<br></div>
This would all be interesting stuff to contribute back to pgRouting.<br>
<br>
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.<br>


<br>
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.<br>


<br>
Anyway, I'm interested in hearing more about your ideas on your three areas of interest.<br>
<br>
Thanks,<br>
  -Steve<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</blockquote></div><br></div>