[pgrouting-dev] GSoC projects and next steps

[Stephen Woodbridge]

On 10/2/2013 1:58 AM, Daniel Kastl wrote:

> It would be nice to have some "Distance Matrix Generator", but I don't
> think all distances need to be newly calculated with every request, so
> it would be probably more useful to have a function that can transform a
> "row based" list of distances (stored in a table) into a matrix as
> needed by TSP or VRP.
>
> I think users might calculate distances like this:
>
>   * Use Euclidean distance
>   * When adding a new "stop point" k-Dijkstra can be run and the result
>     can be stored in a table
>   * Use a different route generator like OSRM and store the distances in
>     PostgreSQL
>
> ... or something else.
> This would be faster than re-creating the distance matrix with every VRP
> query.

I think that we should think about this in terms of an application where 
you have orders and these change every day so you would need a table like:

id, lat, lon, size, time_start, time_end, description
1, y, x, 0, 0, 480, depot
... <orders>

Then the function can that this table and compute the distance table 
using Euclidean distance or kdijkstra or whatever

And interesting variant on this is parcel pickup and delivery. Here you 
have a parcel at a location and you have to pick it up and drop it off, 
or return it to the depot for delivery the next day.

A simpler variant is a package pickup service, where the truck collects 
parcels and returns them to the depot. In this case, we could pickup in 
the morning and deliver in the afternoon, but clearly doing both at the 
same time is more efficient.

>     I want to do some testing on the partition projects, and look at
>     performance and memory usage on large graphs. Mukul is going to look
>     at creating a trsp-partition branch to see if he can integrate the
>     partition model into TRSP.

TSP and VRP take their matrices in different formats and have some 
different requirments, like TSP expects a symmetric matric and I don't 
think VRP has the requirement. But having a functions that can convert 
from matrix to table and table to matrix would be handing to have.


> Do you think it makes sense to have a "develop-2.0" branch to collect
> bug fixes and a "develop-2.1" branch to merge new functions such as the
> partitioning and VRP function?

Yes, but I don't like those names but I have not thought about names yet 
and I think we should look at the branching model again. At the moment 
the only changes in develop are 2.0.1 changes.

> I think for Razequl and Mukul it's also neice to have their work merged
> into a branch that is going to become a release in a few months. It's
> better to do this now when both of you remember what you actually wrote
> and not one year later ;)

I agree with this but, I need some time to review and test the code and 
decide if we need to change the interface. I don't want to rush a bunch 
of changes into a branch without thinking what it means to the release. 
This is how things got to be such a mess before. Anyone can create their 
own local fork and branch and pull in these changes to plan with which 
was the whole point of using git. It will be able a month before I can 
focus on this so in the mean time tag you branches with a 
gsoc-vrp-submission or gsoc-partition-submission tags and then continue 
making changes in the current branches.

Thanks,
   -Steve

> Daniel
>
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl at georepublic.de>
> Web: http://georepublic.de <http://georepublic.de/>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>