[pgrouting-users] pgr_apspjohnson algorithm

Helder_Alves · January 5, 2014, 1:58am

Hi List,

I’ve search the Internet for an example of a practical appliance of pgr_apspjohnson function using OSM data.

If this algorithm is supposed to feed VRP using a VRP distance table, from the found documentation I suppose it must generate the equivalent to TSP distance matrix but in a record format pair by pair of all the vertices instead of the multi-dimensional array used by pgr_TSP, please correct me if I’m wrong.

Problem is, what data is supposed to feed pgr_apspjohnson? source/target/cost ways (table) data for the vids I want to order using pgr_pointtovids function, for example? If not, I would like someone to elaborate a bit on this…

What about pgr_apspwarshall? Is it the same or not?

Thanks in advance for your help!

–
Helder Alves

Stephen_Woodbridge1 · January 5, 2014, 2:52am

On 1/4/2014 8:58 PM, Helder Alves wrote:

Hi List,

I've search the Internet for an example of a practical appliance of
pgr_apspjohnson function using OSM data.

If this algorithm is supposed to feed VRP using a VRP distance table,
from the found documentation I suppose it must generate the equivalent
to TSP distance matrix but in a record format pair by pair of all the
vertices instead of the multi-dimensional array used by pgr_TSP, please
correct me if I'm wrong.

Problem is, what data is supposed to feed pgr_apspjohnson?
source/target/cost ways (table) data for the vids I want to order using
pgr_pointtovids function, for example? If not, I would like someone to
elaborate a bit on this...

What about pgr_apspwarshall? Is it the same or not?

Thanks in advance for your help!

Helder,

I'm not sure that either of these are very useful as they in theory generate ALL pairs for all nodes in the graph and VRP and TSP want a matrix of some defined locations in the graph and not ALL locations in the graph.

I had the same problem and my solution to this was to create

https://github.com/woodbri/osrm-tools

which provides some postgresql wrapper functions that call to a local instance of OSRM and creates the distances or tables needed to feed into VRP or TSP. This is much faster than pgrouting path generation, but does not allow for all the flexibility of pgRouting. Also you have the added headache of setting up ORSM.

The other option that I created was to create a function pgr_vidsToDMatrix()

This creates and array vetrex ids into a distance matrix.

https://github.com/pgRouting/pgrouting/tree/develop/src/common/doc/convenience

-Steve

Helder_Alves · January 5, 2014, 4:28am

Hi Steve,

I’m following those experiments you are working on…

Regarding APSP I think currently it’s not clear on what circumstances these functions can be used. I found some explicit reference on develop-vrp or gsoc-vrp branch and after that I realized no one seems to be using those algorithms, apart from the fact that Johnson’s implementation seems to not handle at all negative costs which I think that may defeat it theoretical purpose (but this is not the reason of this e-mail as I’m still studying that subject).

Maybe this help to understand my doubts…

Thanks!

Helder Alves

On Jan 5, 2014 2:54 AM, “Stephen Woodbridge” <woodbri@swoodbridge.com> wrote:

On 1/4/2014 8:58 PM, Helder Alves wrote:

Hi List,

I’ve search the Internet for an example of a practical appliance of
pgr_apspjohnson function using OSM data.

If this algorithm is supposed to feed VRP using a VRP distance table,
from the found documentation I suppose it must generate the equivalent
to TSP distance matrix but in a record format pair by pair of all the
vertices instead of the multi-dimensional array used by pgr_TSP, please
correct me if I’m wrong.

Problem is, what data is supposed to feed pgr_apspjohnson?
source/target/cost ways (table) data for the vids I want to order using
pgr_pointtovids function, for example? If not, I would like someone to
elaborate a bit on this…

What about pgr_apspwarshall? Is it the same or not?

Thanks in advance for your help!

Helder,

I’m not sure that either of these are very useful as they in theory generate ALL pairs for all nodes in the graph and VRP and TSP want a matrix of some defined locations in the graph and not ALL locations in the graph.

I had the same problem and my solution to this was to create

https://github.com/woodbri/osrm-tools

which provides some postgresql wrapper functions that call to a local instance of OSRM and creates the distances or tables needed to feed into VRP or TSP. This is much faster than pgrouting path generation, but does not allow for all the flexibility of pgRouting. Also you have the added headache of setting up ORSM.

The other option that I created was to create a function pgr_vidsToDMatrix()

This creates and array vetrex ids into a distance matrix.

https://github.com/pgRouting/pgrouting/tree/develop/src/common/doc/convenience

-Steve

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

Stephen_Woodbridge1 · January 5, 2014, 1:18pm

On 1/4/2014 11:28 PM, Helder Alves wrote:

Hi Steve,

I'm following those experiments you are working on...

Regarding APSP I think currently it's not clear on what circumstances
these functions can be used. I found some explicit reference on
develop-vrp or gsoc-vrp branch and after that I realized no one seems to
be using those algorithms, apart from the fact that Johnson's
implementation seems to not handle at all negative costs which I think
that may defeat it theoretical purpose (but this is not the reason of
this e-mail as I'm still studying that subject).

The two APSP algorithms were random additions from two of our GSoC students. I'm not sure what they are useful for, I'll need to go back to my graph theory and look that up again. I think that they have value where you construct a specific graph of important nodes and edges around a specific problem set and then you can solve that specific class of problems. I do not think it is useful to load a huge street network and solve it with APSP.

Graph theory supports an abstract model for solving a lot more problems than vehicle routing. While MOST of our user base is focused on vehicle routing not everyone is so some of the tools we offer are more to support general graph solutions than just vehicle routing solutions.

Maybe this help to understand my doubts...

Understood. We are always looking and hoping to get support from the community. My skills are more generally focused on C development and process management rather than on the specifics of implementing any given graph solution. So pull requests are welcome. These could be for code, tests, and/or docs. I also enjoy a good discussion (like this) with our users. It is hard to know what is important to add to the product with such a discussion around limits and short comings and concerns that users have.

Best regards,
-Steve

Thanks!

----
Helder Alves

On Jan 5, 2014 2:54 AM, "Stephen Woodbridge" <woodbri@swoodbridge.com
<mailto:woodbri@swoodbridge.com>> wrote:

    On 1/4/2014 8:58 PM, Helder Alves wrote:

        Hi List,

        I've search the Internet for an example of a practical appliance of
        pgr_apspjohnson function using OSM data.

        If this algorithm is supposed to feed VRP using a VRP distance
        table,
        from the found documentation I suppose it must generate the
        equivalent
        to TSP distance matrix but in a record format pair by pair of
        all the
        vertices instead of the multi-dimensional array used by pgr_TSP,
        please
        correct me if I'm wrong.

        Problem is, what data is supposed to feed pgr_apspjohnson?
        source/target/cost ways (table) data for the vids I want to
        order using
        pgr_pointtovids function, for example? If not, I would like
        someone to
        elaborate a bit on this...

        What about pgr_apspwarshall? Is it the same or not?

        Thanks in advance for your help!

    Helder,

    I'm not sure that either of these are very useful as they in theory
    generate ALL pairs for all nodes in the graph and VRP and TSP want a
    matrix of some defined locations in the graph and not ALL locations
    in the graph.

    I had the same problem and my solution to this was to create

    https://github.com/woodbri/__osrm-tools
    <https://github.com/woodbri/osrm-tools>

    which provides some postgresql wrapper functions that call to a
    local instance of OSRM and creates the distances or tables needed to
    feed into VRP or TSP. This is much faster than pgrouting path
    generation, but does not allow for all the flexibility of pgRouting.
    Also you have the added headache of setting up ORSM.

    The other option that I created was to create a function
    pgr_vidsToDMatrix()

    This creates and array vetrex ids into a distance matrix.

    https://github.com/pgRouting/__pgrouting/tree/develop/src/__common/doc/convenience
    <https://github.com/pgRouting/pgrouting/tree/develop/src/common/doc/convenience>

    -Steve
    _________________________________________________
    Pgrouting-users mailing list
    Pgrouting-users@lists.osgeo.__org
    <mailto:Pgrouting-users@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>

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

Helder_Alves · January 5, 2014, 6:18pm

Hi Steve,

I think I get it!
As soon I settle the reasoning in my head I’ll contribute for the project…

···

–
Helder Alves

On Sun, Jan 5, 2014 at 1:18 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 1/4/2014 11:28 PM, Helder Alves wrote:

Hi Steve,

I’m following those experiments you are working on…

Regarding APSP I think currently it’s not clear on what circumstances
these functions can be used. I found some explicit reference on
develop-vrp or gsoc-vrp branch and after that I realized no one seems to
be using those algorithms, apart from the fact that Johnson’s
implementation seems to not handle at all negative costs which I think
that may defeat it theoretical purpose (but this is not the reason of
this e-mail as I’m still studying that subject).

The two APSP algorithms were random additions from two of our GSoC students. I’m not sure what they are useful for, I’ll need to go back to my graph theory and look that up again. I think that they have value where you construct a specific graph of important nodes and edges around a specific problem set and then you can solve that specific class of problems. I do not think it is useful to load a huge street network and solve it with APSP.

Graph theory supports an abstract model for solving a lot more problems than vehicle routing. While MOST of our user base is focused on vehicle routing not everyone is so some of the tools we offer are more to support general graph solutions than just vehicle routing solutions.

Maybe this help to understand my doubts…

Understood. We are always looking and hoping to get support from the community. My skills are more generally focused on C development and process management rather than on the specifics of implementing any given graph solution. So pull requests are welcome. These could be for code, tests, and/or docs. I also enjoy a good discussion (like this) with our users. It is hard to know what is important to add to the product with such a discussion around limits and short comings and concerns that users have.

Best regards,
-Steve

Thanks!

Helder Alves

On Jan 5, 2014 2:54 AM, “Stephen Woodbridge” <woodbri@swoodbridge.com

mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

On 1/4/2014 8:58 PM, Helder Alves wrote:

Hi List,

I’ve search the Internet for an example of a practical appliance of
pgr_apspjohnson function using OSM data.

If this algorithm is supposed to feed VRP using a VRP distance
table,
from the found documentation I suppose it must generate the
equivalent
to TSP distance matrix but in a record format pair by pair of
all the
vertices instead of the multi-dimensional array used by pgr_TSP,
please
correct me if I’m wrong.

Problem is, what data is supposed to feed pgr_apspjohnson?
source/target/cost ways (table) data for the vids I want to
order using
pgr_pointtovids function, for example? If not, I would like
someone to
elaborate a bit on this…

What about pgr_apspwarshall? Is it the same or not?

Thanks in advance for your help!

Helder,

I’m not sure that either of these are very useful as they in theory
generate ALL pairs for all nodes in the graph and VRP and TSP want a
matrix of some defined locations in the graph and not ALL locations
in the graph.

I had the same problem and my solution to this was to create

https://github.com/woodbri/__osrm-tools

<https://github.com/woodbri/osrm-tools>

which provides some postgresql wrapper functions that call to a
local instance of OSRM and creates the distances or tables needed to
feed into VRP or TSP. This is much faster than pgrouting path
generation, but does not allow for all the flexibility of pgRouting.
Also you have the added headache of setting up ORSM.

The other option that I created was to create a function
pgr_vidsToDMatrix()

This creates and array vetrex ids into a distance matrix.

https://github.com/pgRouting/__pgrouting/tree/develop/src/__common/doc/convenience
<https://github.com/pgRouting/pgrouting/tree/develop/src/common/doc/convenience>

-Steve

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.__org
mailto:[Pgrouting-users@lists.osgeo.org](mailto:Pgrouting-users@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
<http://lists.osgeo.org/mailman/listinfo/pgrouting-users>

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

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

dkastl · January 5, 2014, 6:27pm

Hi Helder,

As far as I remember the 2 APSP functions were implemented:

pgr_apspwarshall: by Jay Mahadeokar to get familiar with pgRouting before his GSoC term started
pgr_apspjohnson: by Kishore Kumar during his GSoC project, where he needed it for multi-modal routing

Daniel

···

On Mon, Jan 6, 2014 at 3:18 AM, Helder Alves <helderalvespt@gmail.com> wrote:

Hi Steve,

I think I get it!
As soon I settle the reasoning in my head I’ll contribute for the project…

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

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

–
Helder Alves

On Sun, Jan 5, 2014 at 1:18 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 1/4/2014 11:28 PM, Helder Alves wrote:

Hi Steve,

I’m following those experiments you are working on…

Regarding APSP I think currently it’s not clear on what circumstances
these functions can be used. I found some explicit reference on
develop-vrp or gsoc-vrp branch and after that I realized no one seems to
be using those algorithms, apart from the fact that Johnson’s
implementation seems to not handle at all negative costs which I think
that may defeat it theoretical purpose (but this is not the reason of
this e-mail as I’m still studying that subject).

The two APSP algorithms were random additions from two of our GSoC students. I’m not sure what they are useful for, I’ll need to go back to my graph theory and look that up again. I think that they have value where you construct a specific graph of important nodes and edges around a specific problem set and then you can solve that specific class of problems. I do not think it is useful to load a huge street network and solve it with APSP.

Graph theory supports an abstract model for solving a lot more problems than vehicle routing. While MOST of our user base is focused on vehicle routing not everyone is so some of the tools we offer are more to support general graph solutions than just vehicle routing solutions.

Maybe this help to understand my doubts…

Understood. We are always looking and hoping to get support from the community. My skills are more generally focused on C development and process management rather than on the specifics of implementing any given graph solution. So pull requests are welcome. These could be for code, tests, and/or docs. I also enjoy a good discussion (like this) with our users. It is hard to know what is important to add to the product with such a discussion around limits and short comings and concerns that users have.

Best regards,
-Steve

Thanks!

Helder Alves

On Jan 5, 2014 2:54 AM, “Stephen Woodbridge” <woodbri@swoodbridge.com

mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

On 1/4/2014 8:58 PM, Helder Alves wrote:

Hi List,

I’ve search the Internet for an example of a practical appliance of
pgr_apspjohnson function using OSM data.

If this algorithm is supposed to feed VRP using a VRP distance
table,
from the found documentation I suppose it must generate the
equivalent
to TSP distance matrix but in a record format pair by pair of
all the
vertices instead of the multi-dimensional array used by pgr_TSP,
please
correct me if I’m wrong.

Problem is, what data is supposed to feed pgr_apspjohnson?
source/target/cost ways (table) data for the vids I want to
order using
pgr_pointtovids function, for example? If not, I would like
someone to
elaborate a bit on this…

What about pgr_apspwarshall? Is it the same or not?

Thanks in advance for your help!

Helder,

I’m not sure that either of these are very useful as they in theory
generate ALL pairs for all nodes in the graph and VRP and TSP want a
matrix of some defined locations in the graph and not ALL locations
in the graph.

I had the same problem and my solution to this was to create

https://github.com/woodbri/__osrm-tools

<https://github.com/woodbri/osrm-tools>

which provides some postgresql wrapper functions that call to a
local instance of OSRM and creates the distances or tables needed to
feed into VRP or TSP. This is much faster than pgrouting path
generation, but does not allow for all the flexibility of pgRouting.
Also you have the added headache of setting up ORSM.

The other option that I created was to create a function
pgr_vidsToDMatrix()

This creates and array vetrex ids into a distance matrix.

https://github.com/pgRouting/__pgrouting/tree/develop/src/__common/doc/convenience
<https://github.com/pgRouting/pgrouting/tree/develop/src/common/doc/convenience>

-Steve

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.__org
mailto:[Pgrouting-users@lists.osgeo.org](mailto:Pgrouting-users@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
<http://lists.osgeo.org/mailman/listinfo/pgrouting-users>

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

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

Helder_Alves · January 5, 2014, 7:16pm

Hi Daniel,

Regarding pgr_apspjohnson, I came to the conclusion that SQL query passed into pgr_apspjohnson must already return a shortest path distance matrix including all the stop points we want to optimize. Am I getting it right?

What I’m about to try now is to unnest the distance matrix generated for pgr_TSP to feed pgr_apspjohnson…

Problem was that from all my previous reading I thought that at some point APSP Johnson would itself generate the routing graphs, what seems not to be the case, if my understanding from the source code is right… Meaning APSP Johnson only takes care of the total route minimum cost (permutations) avoiding the problem of TSP with negative costs.

Please let me know if I made foolish assumptions!

···

–
Helder Alves

Stephen_Woodbridge1 · January 5, 2014, 7:52pm

On 1/5/2014 2:16 PM, Helder Alves wrote:

Hi Daniel,

Regarding pgr_apspjohnson, I came to the conclusion that SQL query
passed into pgr_apspjohnson must already return a shortest path distance
matrix including all the stop points we want to optimize. Am I getting
it right?

What I'm about to try now is to unnest the distance matrix generated for
pgr_TSP to feed pgr_apspjohnson...

You might be able to use something like this to convert the distance matrix into a table:

with dm as (
   select '{{1,2,3,4,5},
            {6,7,8,9,10},
            {11,12,13,14,15},
            {16,17,18,19,20},
            {21,22,23,24,25}}'::int as dm
)
select i, j, dm.dm[j][i]
   from generate_series(1, 5) i,
        generate_series(1, 5) j,
        dm;

-Steve

Problem was that from all my previous reading I thought that at some
point APSP Johnson would itself generate the routing graphs, what seems
not to be the case, if my understanding from the source code is right...
Meaning APSP Johnson only takes care of the total route minimum cost
(permutations) avoiding the problem of TSP with negative costs.

Please let me know if I made foolish assumptions!

--
Helder Alves

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

Helder_Alves · January 5, 2014, 8:28pm

Hi Steve,

I’m already beyond that stage but thanks anyway!

Steve/Daniel,

Regarding my assumptions regarding pgr_apspjohnson, they seem to be wrong. Can you please elaborate a little bit on exactly which data must be fed into pgr_apspjohnson?

From the pgRouting examples I read, it seems to return the equivalent to the distance matrix used by pgr_TSP however I don’t understand exactly which part of a routable table must be queried in a viable way for an algorithm to be able to infer which nodes have to be routed. Can you help me with this one?

Thanks!

···

–
Helder Alves

On Sun, Jan 5, 2014 at 7:52 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 1/5/2014 2:16 PM, Helder Alves wrote:

Hi Daniel,

Regarding pgr_apspjohnson, I came to the conclusion that SQL query
passed into pgr_apspjohnson must already return a shortest path distance
matrix including all the stop points we want to optimize. Am I getting
it right?

What I’m about to try now is to unnest the distance matrix generated for
pgr_TSP to feed pgr_apspjohnson…

You might be able to use something like this to convert the distance matrix into a table:

with dm as (
select ‘{{1,2,3,4,5},
{6,7,8,9,10},
{11,12,13,14,15},
{16,17,18,19,20},
{21,22,23,24,25}}’::int as dm
)
select i, j, dm.dm[j][i]
from generate_series(1, 5) i,
generate_series(1, 5) j,
dm;

-Steve

Problem was that from all my previous reading I thought that at some
point APSP Johnson would itself generate the routing graphs, what seems
not to be the case, if my understanding from the source code is right…
Meaning APSP Johnson only takes care of the total route minimum cost
(permutations) avoiding the problem of TSP with negative costs.

Please let me know if I made foolish assumptions!

–
Helder Alves

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

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

Helder_Alves · January 6, 2014, 5:11am

Hi,

I was able to make pgr_apspjohnson work but came to the conclusion that when we have available a valid distance matrix suitable for TSP/VRP it makes no sense to feed anything else to pgr_tsp or pgr_vpronedepot as the results will be suboptimal.

Regarding pgr_vrponedepot I was able to also make it work however I guess I stumbled on several issues:

Depot open/close time seems to not be obeyed;
Traveltime also seems to not being considered between departure and arrival time every time;
After each query I have to restart PostgreSQL as last query result seems to be stuck “somewhere” (memory?) and all subsequent queries return the very same result;
When I have to cancel some running query, cancelling procedure takes forever and the only way I found to stop it is by killing postgresql process.
As some of these issues are too serious, I’m not sure if my merging & build may have some problem…

If someone want to get a look, I’ve merged several Steve’s develop tree with Daniel’s develop-vrp, and also merged by hand some other small fixes and contributions I found interesting like Dave Potts and others, that I’m testing as I have free time. You can find everything here: https://github.com/ZupoLlask/pgrouting/tree/develop.

···

–
Helder Alves

On Sun, Jan 5, 2014 at 8:28 PM, Helder Alves <helderalvespt@gmail.com> wrote:

Hi Steve,

I’m already beyond that stage but thanks anyway!

Steve/Daniel,

Regarding my assumptions regarding pgr_apspjohnson, they seem to be wrong. Can you please elaborate a little bit on exactly which data must be fed into pgr_apspjohnson?

From the pgRouting examples I read, it seems to return the equivalent to the distance matrix used by pgr_TSP however I don’t understand exactly which part of a routable table must be queried in a viable way for an algorithm to be able to infer which nodes have to be routed. Can you help me with this one?

Thanks!

–
Helder Alves

On Sun, Jan 5, 2014 at 7:52 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 1/5/2014 2:16 PM, Helder Alves wrote:

Hi Daniel,

Regarding pgr_apspjohnson, I came to the conclusion that SQL query
passed into pgr_apspjohnson must already return a shortest path distance
matrix including all the stop points we want to optimize. Am I getting
it right?

What I’m about to try now is to unnest the distance matrix generated for
pgr_TSP to feed pgr_apspjohnson…

You might be able to use something like this to convert the distance matrix into a table:

with dm as (
select ‘{{1,2,3,4,5},
{6,7,8,9,10},
{11,12,13,14,15},
{16,17,18,19,20},
{21,22,23,24,25}}’::int as dm
)
select i, j, dm.dm[j][i]
from generate_series(1, 5) i,
generate_series(1, 5) j,
dm;

-Steve

Problem was that from all my previous reading I thought that at some
point APSP Johnson would itself generate the routing graphs, what seems
not to be the case, if my understanding from the source code is right…
Meaning APSP Johnson only takes care of the total route minimum cost
(permutations) avoiding the problem of TSP with negative costs.

Please let me know if I made foolish assumptions!

–
Helder Alves

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

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

dkastl · January 6, 2014, 5:55am

Hi Helder,

Thank you for testing and telling us about the problems.
I have not tested the VRP function much, but what I tried has worked so far.
What has several bugs is the demo application I made.

A few weeks ago I wrote a blog post, which hopefully explains a few points of the VRP function: http://blog.georepublic.info/2013/pgrouting-preview-the-new-vrp-solver/
And the blog article also contains a link to the demo and a short presentation. Same as Steve I use OSRM to compute the distance matrix. But I just use the HTTP API and pass the result as a huge SQL statement to PostgreSQL without writing anything to the database. And I think that the NodeJS psql module has some limitation with very long SQL statements, and therefor it will fail for too many stop points.
But so far I have not found any other problems and the routes looked usually OK.

If you are able to create (reproducible) bug reports in the Github issue tracker, that would be helpful.

Daniel

PS: be careful with the demo. It’s just an experiment and multiple users accessing at the same time will experience a single-user (wrong) Websocket implementation

···

On Mon, Jan 6, 2014 at 2:11 PM, Helder Alves <helderalvespt@gmail.com> wrote:

Hi,

I was able to make pgr_apspjohnson work but came to the conclusion that when we have available a valid distance matrix suitable for TSP/VRP it makes no sense to feed anything else to pgr_tsp or pgr_vpronedepot as the results will be suboptimal.

Regarding pgr_vrponedepot I was able to also make it work however I guess I stumbled on several issues:

Depot open/close time seems to not be obeyed;

Traveltime also seems to not being considered between departure and arrival time every time;

After each query I have to restart PostgreSQL as last query result seems to be stuck “somewhere” (memory?) and all subsequent queries return the very same result;

When I have to cancel some running query, cancelling procedure takes forever and the only way I found to stop it is by killing postgresql process.
As some of these issues are too serious, I’m not sure if my merging & build may have some problem…

If someone want to get a look, I’ve merged several Steve’s develop tree with Daniel’s develop-vrp, and also merged by hand some other small fixes and contributions I found interesting like Dave Potts and others, that I’m testing as I have free time. You can find everything here: https://github.com/ZupoLlask/pgrouting/tree/develop.

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

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

–
Helder Alves

On Sun, Jan 5, 2014 at 8:28 PM, Helder Alves <helderalvespt@gmail.com> wrote:

Hi Steve,

I’m already beyond that stage but thanks anyway!

Steve/Daniel,

Regarding my assumptions regarding pgr_apspjohnson, they seem to be wrong. Can you please elaborate a little bit on exactly which data must be fed into pgr_apspjohnson?

From the pgRouting examples I read, it seems to return the equivalent to the distance matrix used by pgr_TSP however I don’t understand exactly which part of a routable table must be queried in a viable way for an algorithm to be able to infer which nodes have to be routed. Can you help me with this one?

Thanks!

–
Helder Alves

On Sun, Jan 5, 2014 at 7:52 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 1/5/2014 2:16 PM, Helder Alves wrote:

Hi Daniel,

Regarding pgr_apspjohnson, I came to the conclusion that SQL query
passed into pgr_apspjohnson must already return a shortest path distance
matrix including all the stop points we want to optimize. Am I getting
it right?

What I’m about to try now is to unnest the distance matrix generated for
pgr_TSP to feed pgr_apspjohnson…

You might be able to use something like this to convert the distance matrix into a table:

with dm as (
select ‘{{1,2,3,4,5},
{6,7,8,9,10},
{11,12,13,14,15},
{16,17,18,19,20},
{21,22,23,24,25}}’::int as dm
)
select i, j, dm.dm[j][i]
from generate_series(1, 5) i,
generate_series(1, 5) j,
dm;

-Steve

Problem was that from all my previous reading I thought that at some
point APSP Johnson would itself generate the routing graphs, what seems
not to be the case, if my understanding from the source code is right…
Meaning APSP Johnson only takes care of the total route minimum cost
(permutations) avoiding the problem of TSP with negative costs.

Please let me know if I made foolish assumptions!

–
Helder Alves

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

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

Stephen_Woodbridge1 · January 6, 2014, 2:14pm

Helder,

On 1/6/2014 12:11 AM, Helder Alves wrote:

Hi,

I was able to make pgr_apspjohnson work but came to the conclusion that
when we have available a valid distance matrix suitable for TSP/VRP it
makes no sense to feed anything else to pgr_tsp or pgr_vpronedepot as
the results will be suboptimal.

Regarding pgr_vrponedepot I was able to also make it work however I
guess I stumbled on several issues:

  * Depot open/close time seems to not be obeyed;
  * Traveltime also seems to not being considered between departure and
    arrival time every time;

One thing that may not be obvious is that times in pgr_vrponedepot are all zero based on the depot open time. So depot open time should always be zero and then are other time should be time units in the future from the open time.

  * After each query I have to restart PostgreSQL as last query result
    seems to be stuck "somewhere" (memory?) and all subsequent queries
    return the very same result;

you might need to change the pgr_vrponedepot sql wrapper to volatile if it is not.

pgrouting/src/vrp_basic/sql/routing_vrp.sql

should say:

LANGUAGE c VOLATILE STRICT;

  * When I have to cancel some running query, cancelling procedure takes
    forever and the only way I found to stop it is by killing postgresql
    process.

Once it get into the C/C++ code we do not get the cancel request. I'll have to do some research and see if there is a function call we can check for a pending CancelRequest.

-Steve

As some of these issues are too serious, I'm not sure if my merging &
build may have some problem...
If someone want to get a look, I've merged several Steve's develop tree
with Daniel's develop-vrp, and also merged by hand some other small
fixes and contributions I found interesting like Dave Potts and others,
that I'm testing as I have free time. You can find everything here:
https://github.com/ZupoLlask/pgrouting/tree/develop.

--
Helder Alves

On Sun, Jan 5, 2014 at 8:28 PM, Helder Alves <helderalvespt@gmail.com
<mailto:helderalvespt@gmail.com>> wrote:

    Hi Steve,

    I'm already beyond that stage but thanks anyway!

    Steve/Daniel,

    Regarding my assumptions regarding pgr_apspjohnson, they seem to be
    wrong. Can you please elaborate a little bit on exactly which data
    must be fed into pgr_apspjohnson?

     From the pgRouting examples I read, it seems to return the
    equivalent to the distance matrix used by pgr_TSP however I don't
    understand exactly which part of a routable table must be queried in
    a viable way for an algorithm to be able to infer which nodes have
    to be routed. Can you help me with this one?

    Thanks!

    --
    Helder Alves

    On Sun, Jan 5, 2014 at 7:52 PM, Stephen Woodbridge
    <woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

        On 1/5/2014 2:16 PM, Helder Alves wrote:

            Hi Daniel,

            Regarding pgr_apspjohnson, I came to the conclusion that SQL
            query
            passed into pgr_apspjohnson must already return a shortest
            path distance
            matrix including all the stop points we want to optimize. Am
            I getting
            it right?

            What I'm about to try now is to unnest the distance matrix
            generated for
            pgr_TSP to feed pgr_apspjohnson...

        You might be able to use something like this to convert the
        distance matrix into a table:

        with dm as (
           select '{{1,2,3,4,5},
                    {6,7,8,9,10},
                    {11,12,13,14,15},
                    {16,17,18,19,20},
                    {21,22,23,24,25}}'::int as dm
        )
        select i, j, dm.dm <http://dm.dm>[j][i]
           from generate_series(1, 5) i,
                generate_series(1, 5) j,
                dm;

        -Steve

            Problem was that from all my previous reading I thought that
            at some
            point APSP Johnson would itself generate the routing graphs,
            what seems
            not to be the case, if my understanding from the source code
            is right...
            Meaning APSP Johnson only takes care of the total route
            minimum cost
            (permutations) avoiding the problem of TSP with negative costs.

            Please let me know if I made foolish assumptions!

            --
            Helder Alves

            _________________________________________________
            Pgrouting-users mailing list
            Pgrouting-users@lists.osgeo.__org
            <mailto:Pgrouting-users@lists.osgeo.org>
            http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
            <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>

        _________________________________________________
        Pgrouting-users mailing list
        Pgrouting-users@lists.osgeo.__org
        <mailto:Pgrouting-users@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>

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

Stephen_Woodbridge1 · January 6, 2014, 5:08pm

I opened this ticket up for the cancel request issue:
https://github.com/pgRouting/pgrouting/issues/232

On 1/6/2014 9:14 AM, Stephen Woodbridge wrote:

Helder,

On 1/6/2014 12:11 AM, Helder Alves wrote:

Hi,

I was able to make pgr_apspjohnson work but came to the conclusion that
when we have available a valid distance matrix suitable for TSP/VRP it
makes no sense to feed anything else to pgr_tsp or pgr_vpronedepot as
the results will be suboptimal.

Regarding pgr_vrponedepot I was able to also make it work however I
guess I stumbled on several issues:

  * Depot open/close time seems to not be obeyed;
  * Traveltime also seems to not being considered between departure and
    arrival time every time;

One thing that may not be obvious is that times in pgr_vrponedepot are
all zero based on the depot open time. So depot open time should always
be zero and then are other time should be time units in the future from
the open time.

  * After each query I have to restart PostgreSQL as last query result
    seems to be stuck "somewhere" (memory?) and all subsequent queries
    return the very same result;

you might need to change the pgr_vrponedepot sql wrapper to volatile if
it is not.

pgrouting/src/vrp_basic/sql/routing_vrp.sql

should say:

LANGUAGE c VOLATILE STRICT;

  * When I have to cancel some running query, cancelling procedure takes
    forever and the only way I found to stop it is by killing postgresql
    process.

Once it get into the C/C++ code we do not get the cancel request. I'll
have to do some research and see if there is a function call we can
check for a pending CancelRequest.

-Steve

As some of these issues are too serious, I'm not sure if my merging &
build may have some problem...
If someone want to get a look, I've merged several Steve's develop tree
with Daniel's develop-vrp, and also merged by hand some other small
fixes and contributions I found interesting like Dave Potts and others,
that I'm testing as I have free time. You can find everything here:
https://github.com/ZupoLlask/pgrouting/tree/develop.

--
Helder Alves

On Sun, Jan 5, 2014 at 8:28 PM, Helder Alves <helderalvespt@gmail.com
<mailto:helderalvespt@gmail.com>> wrote:

    Hi Steve,

    I'm already beyond that stage but thanks anyway!

    Steve/Daniel,

    Regarding my assumptions regarding pgr_apspjohnson, they seem to be
    wrong. Can you please elaborate a little bit on exactly which data
    must be fed into pgr_apspjohnson?

     From the pgRouting examples I read, it seems to return the
    equivalent to the distance matrix used by pgr_TSP however I don't
    understand exactly which part of a routable table must be queried in
    a viable way for an algorithm to be able to infer which nodes have
    to be routed. Can you help me with this one?

    Thanks!

    --
    Helder Alves

    On Sun, Jan 5, 2014 at 7:52 PM, Stephen Woodbridge
    <woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

        On 1/5/2014 2:16 PM, Helder Alves wrote:

            Hi Daniel,

            Regarding pgr_apspjohnson, I came to the conclusion that SQL
            query
            passed into pgr_apspjohnson must already return a shortest
            path distance
            matrix including all the stop points we want to optimize. Am
            I getting
            it right?

            What I'm about to try now is to unnest the distance matrix
            generated for
            pgr_TSP to feed pgr_apspjohnson...

        You might be able to use something like this to convert the
        distance matrix into a table:

        with dm as (
           select '{{1,2,3,4,5},
                    {6,7,8,9,10},
                    {11,12,13,14,15},
                    {16,17,18,19,20},
                    {21,22,23,24,25}}'::int as dm
        )
        select i, j, dm.dm <http://dm.dm>[j][i]
           from generate_series(1, 5) i,
                generate_series(1, 5) j,
                dm;

        -Steve

            Problem was that from all my previous reading I thought that
            at some
            point APSP Johnson would itself generate the routing graphs,
            what seems
            not to be the case, if my understanding from the source code
            is right...
            Meaning APSP Johnson only takes care of the total route
            minimum cost
            (permutations) avoiding the problem of TSP with negative
costs.

            Please let me know if I made foolish assumptions!

            --
            Helder Alves

            _________________________________________________
            Pgrouting-users mailing list
            Pgrouting-users@lists.osgeo.__org
            <mailto:Pgrouting-users@lists.osgeo.org>
            http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
            <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>

        _________________________________________________
        Pgrouting-users mailing list
        Pgrouting-users@lists.osgeo.__org
        <mailto:Pgrouting-users@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>

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

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

Helder_Alves · January 7, 2014, 1:44am

Hi Steve,

Thanks for your feedback… I’m applying the suggested fix and I’ll let you know if it doesn’t work.

Regarding pgr_vrponedepot I was able to also make it work however I

guess I stumbled on several issues:

Depot open/close time seems to not be obeyed;

Traveltime also seems to not being considered between departure and

arrival time every time;

One thing that may not be obvious is that times in pgr_vrponedepot are all zero based on the depot open time. So depot open time should always be zero and then are other time should be time units in the future from the open time

I’ve checked these issues against Daniel’s implementation on his blog post @ http://blog.georepublic.info/2013/pgrouting-preview-the-new-vrp-solver/ and I got to the same conclusions, please check my notes below.

Open a browser window on http://blog.georepublic.info/2013/pgrouting-preview-the-new-vrp-solver/ URL
Hit the “Sample Data” buttons for Vehicles, Depot and Orders, click “Start Scheduler” and when results are generated click “schedule view”
Open a second browser window on http://blog.georepublic.info/2013/pgrouting-preview-the-new-vrp-solver/ URL
Hit the “Sample Data” buttons for Vehicles, Depot and Orders and change Depot to “0,0,300,465,0,139.7107020020485,37.671709126526395”
Click “Start Scheduler” and when results are generated click “schedule view”
Compare both schedule views and please note that both a) traveltime from/to depot as well as b) depot’s open time is not being taken in consideration for arrival/departure time and optimization
Does my reasoning makes sense or I’m missing some detail here?

···

–
Helder Alves

Helder_Alves · January 7, 2014, 2:06am

Hi guys,

Just to let you know that Steve’s fix proposal for persistent pgr_onedepot() results didn’t work out and after building pgrouting from develop-vrp tree (btw, I had to make this change) I got precisely the same problem I got with building from my tree.

Thanks for the help, though!

···

–
Helder Alves

On Tue, Jan 7, 2014 at 1:44 AM, Helder Alves <helderalvespt@gmail.com> wrote:

Hi Steve,

Thanks for your feedback… I’m applying the suggested fix and I’ll let you know if it doesn’t work.

Regarding pgr_vrponedepot I was able to also make it work however I

guess I stumbled on several issues:

Depot open/close time seems to not be obeyed;

Traveltime also seems to not being considered between departure and

arrival time every time;

One thing that may not be obvious is that times in pgr_vrponedepot are all zero based on the depot open time. So depot open time should always be zero and then are other time should be time units in the future from the open time

I’ve checked these issues against Daniel’s implementation on his blog post @ http://blog.georepublic.info/2013/pgrouting-preview-the-new-vrp-solver/ and I got to the same conclusions, please check my notes below.

Open a browser window on http://blog.georepublic.info/2013/pgrouting-preview-the-new-vrp-solver/ URL

Hit the “Sample Data” buttons for Vehicles, Depot and Orders, click “Start Scheduler” and when results are generated click “schedule view”

Open a second browser window on http://blog.georepublic.info/2013/pgrouting-preview-the-new-vrp-solver/ URL

Hit the “Sample Data” buttons for Vehicles, Depot and Orders and change Depot to “0,0,300,465,0,139.7107020020485,37.671709126526395”

Click “Start Scheduler” and when results are generated click “schedule view”

Compare both schedule views and please note that both a) traveltime from/to depot as well as b) depot’s open time is not being taken in consideration for arrival/departure time and optimization
Does my reasoning makes sense or I’m missing some detail here?

–
Helder Alves

Helder_Alves · January 7, 2014, 2:07am

“I had to make this change” >> https://github.com/ZupoLlask/pgrouting/commit/5d0a2037cf6d224be18eb6d3cf48f54dbc8b8d24

···

–
Helder Alves

On Tue, Jan 7, 2014 at 2:06 AM, Helder Alves <helderalvespt@gmail.com> wrote:

Hi guys,

Just to let you know that Steve’s fix proposal for persistent pgr_onedepot() results didn’t work out and after building pgrouting from develop-vrp tree (btw, I had to make this change) I got precisely the same problem I got with building from my tree.

Thanks for the help, though!

–
Helder Alves

On Tue, Jan 7, 2014 at 1:44 AM, Helder Alves <helderalvespt@gmail.com> wrote:

Hi Steve,

Thanks for your feedback… I’m applying the suggested fix and I’ll let you know if it doesn’t work.

Regarding pgr_vrponedepot I was able to also make it work however I

guess I stumbled on several issues:

Depot open/close time seems to not be obeyed;

Traveltime also seems to not being considered between departure and

arrival time every time;

One thing that may not be obvious is that times in pgr_vrponedepot are all zero based on the depot open time. So depot open time should always be zero and then are other time should be time units in the future from the open time

I’ve checked these issues against Daniel’s implementation on his blog post @ http://blog.georepublic.info/2013/pgrouting-preview-the-new-vrp-solver/ and I got to the same conclusions, please check my notes below.

Open a browser window on http://blog.georepublic.info/2013/pgrouting-preview-the-new-vrp-solver/ URL

Hit the “Sample Data” buttons for Vehicles, Depot and Orders, click “Start Scheduler” and when results are generated click “schedule view”

Open a second browser window on http://blog.georepublic.info/2013/pgrouting-preview-the-new-vrp-solver/ URL

Hit the “Sample Data” buttons for Vehicles, Depot and Orders and change Depot to “0,0,300,465,0,139.7107020020485,37.671709126526395”

Click “Start Scheduler” and when results are generated click “schedule view”

Compare both schedule views and please note that both a) traveltime from/to depot as well as b) depot’s open time is not being taken in consideration for arrival/departure time and optimization
Does my reasoning makes sense or I’m missing some detail here?

–
Helder Alves