[pgrouting-dev] GSoC 2013
Stephen Woodbridge
woodbri at swoodbridge.com
Tue Apr 16 11:34:41 PDT 2013
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 at swoodbridge.com <mailto: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 <mailto:pgrouting-dev at 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 at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
More information about the pgrouting-dev
mailing list