[pgrouting-dev] GSoC projects and next steps

pgRouting pgrouting-dev
1

Mukul and Razequl,

Congratulations on your successful completion of GSoC!
I'm sorry that Daniel and I have been very busy with our own projects of the recent past and have not been engaging more with you guys. Please make sure you complete the final code submission and requirements for Google so you will get paid for all your hard work.

For next steps, I see Daniel has merged the the develop branch into the vrp branch. This will make it easier to eventually merge your code back into the develop branch for our 2.1 release in the future. I think we need to add some methods to generate the distance matrix based on a list of locations. We can write a simple Euclidean distance generator for fast demos and write a separate function that uses one-to-many Dijkstra function to generate the distance matrix.

Daniel, any thoughts on this? Did you have any specific plans with this?

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.

For both these projects, I want to review at the APIs and see if I can make them consistent with our new module of reusable generic types or extent the types as needed. I also want to review them for usability changes like removing fixed table or column names, etc.

From my point of view, these tasks will have to wait for some free time which will be at least 2-3 weeks out if then.

I'm glad you both had a good summer with GSoC and that you will have time and interest in continuing to expand you projects and support pgRouting even if it is at a lower effort level because of class work again.

Thanks again for your efforts and significant contributions.

-Steve

2

On 30/09/13 15:23, Stephen Woodbridge wrote:
Hi

Is it possible to have summary of the features that Mukul and Razequl work adds to pgrouting?
regards
Dave.

Mukul and Razequl,

Congratulations on your successful completion of GSoC!
I'm sorry that Daniel and I have been very busy with our own projects of the recent past and have not been engaging more with you guys. Please make sure you complete the final code submission and requirements for Google so you will get paid for all your hard work.

For next steps, I see Daniel has merged the the develop branch into the vrp branch. This will make it easier to eventually merge your code back into the develop branch for our 2.1 release in the future. I think we need to add some methods to generate the distance matrix based on a list of locations. We can write a simple Euclidean distance generator for fast demos and write a separate function that uses one-to-many Dijkstra function to generate the distance matrix.

Daniel, any thoughts on this? Did you have any specific plans with this?

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.

For both these projects, I want to review at the APIs and see if I can make them consistent with our new module of reusable generic types or extent the types as needed. I also want to review them for usability changes like removing fixed table or column names, etc.

From my point of view, these tasks will have to wait for some free time which will be at least 2-3 weeks out if then.

I'm glad you both had a good summer with GSoC and that you will have time and interest in continuing to expand you projects and support pgRouting even if it is at a lower effort level because of class work again.

Thanks again for your efforts and significant contributions.

-Steve
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

3

Hi all,

I have had a couple of requests for more information on what our Google Summer of Code students developed this summer. The following pages give a pretty good overview of their projects and how to use them.

Mukul added this:

https://github.com/pgRouting/pgrouting/wiki/Details-and-how-to-use-guide-.

it is located in git on branch "gsoc-partition" in src/partition/ directory. Look at the test directory for examples.

Razequl added this:

https://github.com/pgRouting/pgrouting/wiki/GSoc-2013-Project-Information

it is located in git on branch "gsoc-vrp" in src/vrp_basic/ directory. Look in the test directory for examples.

If you have questions, feel free to ask, Mukul and Razequl will probably be on the lists for a while before they have to start tackling their next years course work. And Daniel and I can also field questions on these.

-Steve

On 10/1/2013 9:13 AM, Dave Potts wrote:

On 30/09/13 15:23, Stephen Woodbridge wrote:
Hi

Is it possible to have summary of the features that Mukul and Razequl
work adds to pgrouting?
regards
Dave.

Mukul and Razequl,

Congratulations on your successful completion of GSoC!
I'm sorry that Daniel and I have been very busy with our own projects
of the recent past and have not been engaging more with you guys.
Please make sure you complete the final code submission and
requirements for Google so you will get paid for all your hard work.

For next steps, I see Daniel has merged the the develop branch into
the vrp branch. This will make it easier to eventually merge your code
back into the develop branch for our 2.1 release in the future. I
think we need to add some methods to generate the distance matrix
based on a list of locations. We can write a simple Euclidean distance
generator for fast demos and write a separate function that uses
one-to-many Dijkstra function to generate the distance matrix.

Daniel, any thoughts on this? Did you have any specific plans with this?

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.

For both these projects, I want to review at the APIs and see if I can
make them consistent with our new module of reusable generic types or
extent the types as needed. I also want to review them for usability
changes like removing fixed table or column names, etc.

From my point of view, these tasks will have to wait for some free
time which will be at least 2-3 weeks out if then.

I'm glad you both had a good summer with GSoC and that you will have
time and interest in continuing to expand you projects and support
pgRouting even if it is at a lower effort level because of class work
again.

Thanks again for your efforts and significant contributions.

-Steve
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
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

4

Hi Steve,
Thanks for providing the links. I was about to provide that.

I wish to continue work when I get time. For next step, I would like to check the integrity of the current implementation. So I need your guideline to check the memory status and find possible memory leak. I also need to improve the error and exception handling to pass any negative testing.

As for distance matrix calculation, I think pgRouting already has single source shortest path implementation. I was wondering if we can make use of those. May be it is possible to create another API on the core solution to get result in the desired format.

I appreciate your review on the VRP API itself. Specially in the result format. If you have any suggestion regarding the current API, please let me know. I will be happy to implement those.

There are still some space for improving the core algorithm itself. I already have some idea of improving the Tabu Search. I will gradually implement those also. Any suggestion regarding this is also welcome.

Thanks for all your support and inspiration. I really enjoy to work in the community.

  • Razequl
···

On Tue, Oct 1, 2013 at 7:43 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Hi all,

I have had a couple of requests for more information on what our Google Summer of Code students developed this summer. The following pages give a pretty good overview of their projects and how to use them.

Mukul added this:

https://github.com/pgRouting/pgrouting/wiki/Details-and-how-to-use-guide-.

it is located in git on branch “gsoc-partition” in src/partition/ directory. Look at the test directory for examples.

Razequl added this:

https://github.com/pgRouting/pgrouting/wiki/GSoc-2013-Project-Information

it is located in git on branch “gsoc-vrp” in src/vrp_basic/ directory. Look in the test directory for examples.

If you have questions, feel free to ask, Mukul and Razequl will probably be on the lists for a while before they have to start tackling their next years course work. And Daniel and I can also field questions on these.

-Steve

On 10/1/2013 9:13 AM, Dave Potts wrote:

On 30/09/13 15:23, Stephen Woodbridge wrote:
Hi

Is it possible to have summary of the features that Mukul and Razequl
work adds to pgrouting?
regards
Dave.

Mukul and Razequl,

Congratulations on your successful completion of GSoC!
I’m sorry that Daniel and I have been very busy with our own projects
of the recent past and have not been engaging more with you guys.
Please make sure you complete the final code submission and
requirements for Google so you will get paid for all your hard work.

For next steps, I see Daniel has merged the the develop branch into
the vrp branch. This will make it easier to eventually merge your code
back into the develop branch for our 2.1 release in the future. I
think we need to add some methods to generate the distance matrix
based on a list of locations. We can write a simple Euclidean distance
generator for fast demos and write a separate function that uses
one-to-many Dijkstra function to generate the distance matrix.

Daniel, any thoughts on this? Did you have any specific plans with this?

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.

For both these projects, I want to review at the APIs and see if I can
make them consistent with our new module of reusable generic types or
extent the types as needed. I also want to review them for usability
changes like removing fixed table or column names, etc.

From my point of view, these tasks will have to wait for some free
time which will be at least 2-3 weeks out if then.

I’m glad you both had a good summer with GSoC and that you will have
time and interest in continuing to expand you projects and support
pgRouting even if it is at a lower effort level because of class work
again.

Thanks again for your efforts and significant contributions.

-Steve

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
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

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

5

On Mon, Sep 30, 2013 at 10:23 PM, Stephen Woodbridge <
woodbri@swoodbridge.com> wrote:

Mukul and Razequl,

Congratulations on your successful completion of GSoC!

Yes, congratulations!

For next steps, I see Daniel has merged the the develop branch into the
vrp branch. This will make it easier to eventually merge your code back
into the develop branch for our 2.1 release in the future. I think we need
to add some methods to generate the distance matrix based on a list of
locations. We can write a simple Euclidean distance generator for fast
demos and write a separate function that uses one-to-many Dijkstra function
to generate the distance matrix.

Daniel, any thoughts on this? Did you have any specific plans with this?

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

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?

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 :wink:

Daniel

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

6

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 :wink:

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@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/&gt;

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev