[pgrouting-users] Dynamic costs question

Dear pgRouting users,

I am currently working on my project and would like to learn more about the library. Specifically, I am using it to find the most profitable paths between two tokens.

The graph I am working with represents tokens between which transfers on the Ethereum blockchain are possible.

Could you please help me with the following questions:

  1. Is it possible to use dynamic costs in path finding algorithms, specifically in pgr_bellmanFord? By dynamic costs, I mean modifying the cost of an edge as the algorithm passes through the graph based on previously added edges in the path.

  2. If dynamic costs are not possible, is it correct to say that this is the problem of finding paths in time-dependent graphs? I am unsure because in my case, it is possible for the weight to decrease as the algorithm travels along the edges.

Thank you very much.

Hello,

No, we do not have an implementation where costs can vary while executing the algorithm.

If you can point out a paper of such an algorithm you describe, it would be nice.
Regards
Vicky

On Fri, Sep 1, 2023 at 1:00 AM Alex D. <kmortyk@gmail.com> wrote:

Dear pgRouting users,

I am currently working on my project and would like to learn more about the library. Specifically, I am using it to find the most profitable paths between two tokens.

The graph I am working with represents tokens between which transfers on the Ethereum blockchain are possible.

Could you please help me with the following questions:

  1. Is it possible to use dynamic costs in path finding algorithms, specifically in pgr_bellmanFord? By dynamic costs, I mean modifying the cost of an edge as the algorithm passes through the graph based on previously added edges in the path.

  2. If dynamic costs are not possible, is it correct to say that this is the problem of finding paths in time-dependent graphs? I am unsure because in my case, it is possible for the weight to decrease as the algorithm travels along the edges.

Thank you very much.


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

Thank you for your reply.

Is it possible to find someone here who can develop this feature for a fee, with the intention of releasing the final solution as open source?

I am currently considering two potential approaches for implementation:

  1. Implementing the Bellman-Ford Based Algorithm as described in the following paper: https://www.researchgate.net/publication/221103374_Finding_time-dependent_shortest_paths_over_large_graphs (Finding time-dependent shortest paths over large graphs) and https://essay.utwente.nl/92401/ (Solving time-dependent shortest path problems in a database context).

  2. Implementing callbacks for https://docs.pgrouting.org/latest/en/pgr_bellmanFord.html, as discussed in the issue https://github.com/pgRouting/pgrouting/issues/243.

вс, 3 сент. 2023 г. в 04:50, Vicky Vergara <vicky@erosion.dev>:

Hello,

No, we do not have an implementation where costs can vary while executing the algorithm.

If you can point out a paper of such an algorithm you describe, it would be nice.
Regards
Vicky

On Fri, Sep 1, 2023 at 1:00 AM Alex D. <kmortyk@gmail.com> wrote:

Dear pgRouting users,

I am currently working on my project and would like to learn more about the library. Specifically, I am using it to find the most profitable paths between two tokens.

The graph I am working with represents tokens between which transfers on the Ethereum blockchain are possible.

Could you please help me with the following questions:

  1. Is it possible to use dynamic costs in path finding algorithms, specifically in pgr_bellmanFord? By dynamic costs, I mean modifying the cost of an edge as the algorithm passes through the graph based on previously added edges in the path.

  2. If dynamic costs are not possible, is it correct to say that this is the problem of finding paths in time-dependent graphs? I am unsure because in my case, it is possible for the weight to decrease as the algorithm travels along the edges.

Thank you very much.


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


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

Hi,

Sure, we can start a discussion.

Normally pgRouting meetings are at 13:00 CMT hours, allowing other project members from other parts of the world to join.

What about on Monday?

Regards

Vicky

On Mon, Sep 4, 2023 at 7:06 AM Alex D. <kmortyk@gmail.com> wrote:

Thank you for your reply.

Is it possible to find someone here who can develop this feature for a fee, with the intention of releasing the final solution as open source?

I am currently considering two potential approaches for implementation:

  1. Implementing the Bellman-Ford Based Algorithm as described in the following paper: https://www.researchgate.net/publication/221103374_Finding_time-dependent_shortest_paths_over_large_graphs (Finding time-dependent shortest paths over large graphs) and https://essay.utwente.nl/92401/ (Solving time-dependent shortest path problems in a database context).

  2. Implementing callbacks for https://docs.pgrouting.org/latest/en/pgr_bellmanFord.html, as discussed in the issue https://github.com/pgRouting/pgrouting/issues/243.

вс, 3 сент. 2023 г. в 04:50, Vicky Vergara <vicky@erosion.dev>:

Hello,

No, we do not have an implementation where costs can vary while executing the algorithm.

If you can point out a paper of such an algorithm you describe, it would be nice.
Regards
Vicky

On Fri, Sep 1, 2023 at 1:00 AM Alex D. <kmortyk@gmail.com> wrote:

Dear pgRouting users,

I am currently working on my project and would like to learn more about the library. Specifically, I am using it to find the most profitable paths between two tokens.

The graph I am working with represents tokens between which transfers on the Ethereum blockchain are possible.

Could you please help me with the following questions:

  1. Is it possible to use dynamic costs in path finding algorithms, specifically in pgr_bellmanFord? By dynamic costs, I mean modifying the cost of an edge as the algorithm passes through the graph based on previously added edges in the path.

  2. If dynamic costs are not possible, is it correct to say that this is the problem of finding paths in time-dependent graphs? I am unsure because in my case, it is possible for the weight to decrease as the algorithm travels along the edges.

Thank you very much.


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


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


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

Hello,
I would like to attend the pgRouting meeting on Monday.

Could you tell me the platform where the meetings will take place?

Also, I would like to confirm the timezone. Is it UTC-6? Please let me know if I am mistaken.

пт, 8 сент. 2023 г. в 06:20, Vicky Vergara <vicky@erosion.dev>:

Hi,

Sure, we can start a discussion.

Normally pgRouting meetings are at 13:00 CMT hours, allowing other project members from other parts of the world to join.

What about on Monday?

Regards

Vicky

On Mon, Sep 4, 2023 at 7:06 AM Alex D. <kmortyk@gmail.com> wrote:

Thank you for your reply.

Is it possible to find someone here who can develop this feature for a fee, with the intention of releasing the final solution as open source?

I am currently considering two potential approaches for implementation:

  1. Implementing the Bellman-Ford Based Algorithm as described in the following paper: https://www.researchgate.net/publication/221103374_Finding_time-dependent_shortest_paths_over_large_graphs (Finding time-dependent shortest paths over large graphs) and https://essay.utwente.nl/92401/ (Solving time-dependent shortest path problems in a database context).

  2. Implementing callbacks for https://docs.pgrouting.org/latest/en/pgr_bellmanFord.html, as discussed in the issue https://github.com/pgRouting/pgrouting/issues/243.

вс, 3 сент. 2023 г. в 04:50, Vicky Vergara <vicky@erosion.dev>:

Hello,

No, we do not have an implementation where costs can vary while executing the algorithm.

If you can point out a paper of such an algorithm you describe, it would be nice.
Regards
Vicky

On Fri, Sep 1, 2023 at 1:00 AM Alex D. <kmortyk@gmail.com> wrote:

Dear pgRouting users,

I am currently working on my project and would like to learn more about the library. Specifically, I am using it to find the most profitable paths between two tokens.

The graph I am working with represents tokens between which transfers on the Ethereum blockchain are possible.

Could you please help me with the following questions:

  1. Is it possible to use dynamic costs in path finding algorithms, specifically in pgr_bellmanFord? By dynamic costs, I mean modifying the cost of an edge as the algorithm passes through the graph based on previously added edges in the path.

  2. If dynamic costs are not possible, is it correct to say that this is the problem of finding paths in time-dependent graphs? I am unsure because in my case, it is possible for the weight to decrease as the algorithm travels along the edges.

Thank you very much.


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


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


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


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