[pgrouting-dev] GSoC 2013
Raffaello Bertini
raffaellobertini at gmail.com
Wed Apr 17 06:53:25 PDT 2013
On Tue, Apr 16, 2013 at 8:34 PM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:
> 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?
>
yes i'm actually proposing/using N Dijkstra. I try to explain better:
pgroute needs fetch data to build the graph ("roads graph"), for tsp/vrp
computation, this graph can be a "meta-graph" (overlay graph) which each
arc weight connecting 2 city is a solution of one dijkstra, everytime needs
N Dijkstra to build up the overlaygraph and fetch many rows from DB.
if partially have stored some results (X) of this dijkstra computation, can
reduce the ammount of fetch data and increase the speed of computation
because we have only compute N-X dijkstra to build the overlaygraph for
this istance. the price is needing more DB space to store results.
ok, maybe for a completely general way it's not usefull at all, but the
main use case of pgroute i suppose is primarly to sector-based routing
application.
>
> 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<https://github.com/pgRouting/pgrouting/tree/sew-devel-2_0/src/tsp/src>
>
saw it: tsp compute euclidean distance and it's symmetric, it can be
upgraded using the dijkstra results connecting the cities (with an
approximation on the exact point (x,y)) but costs are no more symmteric.
one more:
looking into the code using meta-heuristic, needs to make a choice about
better quality or faster solution because i think the local search used can
be upgrade with a 3opt.
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
>
i like all this stuff to work on, but I prefer contraction hierarchy so i
can improve my skills, learn somenthing new and it' have a major value
respect the others algorithm, because every algorithm can depends on CH.
it's the main purpose and it's related of one of my personal challenge too.
So, yes I need to discuss more about CH, in meanwhile i'm reading/studying
a thesys on this subject.
> On Tue, Apr 16, 2013 at 5:16 PM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.**com<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<pgrouting-dev at lists.osgeo.org>
>> >
>> http://lists.osgeo.org/__**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>> <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<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<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130417/412193e0/attachment.html>
More information about the pgrouting-dev
mailing list