On 4/16/2013 1:41 PM, Raffaello Bertini wrote:
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.
Ok, if I understand this, you are proposing creating a table to cache routes in that you might want for a TSP solution, and if you do not find the route stored, then you will compute it and store. Is this what you are proposing?
If so here are some comments related to do that.
1. this might make sense for a given client, say a bakery that has N clients that they service. This would allow them to cache the various routes, and plug them into a delivery truck route plan if they had say 10 orders for today.
2. This does not make sense in the more generalized case of a web application where the user enter N random points and requests an optimized route. It is unlikely that you will ever have the needed routes cached and more likely that you will need to generate all the routes for the matrix on the fly.
3. creating a cache table requires some additional infrastructure to manage the cache. This adds complexity. If you only have one client, and 50-100 locations you can cache the routes and if you add a new location you can add the required rows.
If you have N cities, have you thought about using Dijkstra to compute N Dijkstra solutions to extract the 1 to N-1 routes in each iteration?
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.
Look at this:
https://github.com/pgRouting/pgrouting/tree/sew-devel-2_0/src/tsp/src
In fact, you should be looking at this sew-develop-2_0 branch as this will be the new structure going forward and what we will expect for GSoC students to work with.
-*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...
With respect to the GSoC program:
1. pick a project that is interesting and challenging to you. It should be something that will hold your interest, let you learn something new and be of value to the pgRouting.
2. Right sizing your effort. Students tend to be very enthusiastic and tend to over commit, we can help you with this. A project needs to define a minimum set of goals to be successful, and then can have additional stretch goals. You need to think about your project in terms of goals and deliverables because this is how you get measured.
3. I think either of these projects would be of value, although I'm not sure I understand what you would be doing related to the VRP problem and just adding a caching table to your existing code does not sound very challenging. So we might need to hear more about what you plan to do if you go that direction.
4. If you are interested in working on the contraction hierarchy we should discuss this more as there are a lot of aspects related to this and it is something that you would probably want to get more familiar with.
Do you have a preference (strong or weak) on which project is most interesting to you? You might not at this point and that is ok.
-Steve
On Tue, Apr 16, 2013 at 5:16 PM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@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@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev