[pgrouting-users] Shortest Path with varying costs.

pgRouting pgrouting-users
1

Hello,

I need to calculate the shortest path, taking into account that the cost of traveling beetween edges varies according to the time of day. I have a table of edges [my_edges(id, source, target, …)] and other table for cost and reverse_cost with columns especifying the time of day in which that cost is applicable [my_costs(cost, reverse_cost, start_time, end_time,…)], the cost is the number of minutes it takes to traverse from source to target.

Is there a way pgRouting can help me to calculate this special shortest path?

Thanks, Roberto.

2

I think that you need to make a inner joint into my_cost according the time and pass the cost and reverse_cost, where match that time with and edge id.

2012/1/30 Roberto Oropeza Gamarra <oropezaroberto@gmail.com>

Hello,

I need to calculate the shortest path, taking into account that the cost of traveling beetween edges varies according to the time of day. I have a table of edges [my_edges(id, source, target, …)] and other table for cost and reverse_cost with columns especifying the time of day in which that cost is applicable [my_costs(cost, reverse_cost, start_time, end_time,…)], the cost is the number of minutes it takes to traverse from source to target.

Is there a way pgRouting can help me to calculate this special shortest path?

Thanks, Roberto.

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

3

On 1/30/2012 3:48 PM, Roberto Oropeza Gamarra wrote:

Hello,

I need to calculate the shortest path, taking into account that the cost
of traveling beetween edges varies according to the time of day. I have
a table of edges [my_edges(id, source, target, ...)] and other table for
cost and reverse_cost with columns especifying the time of day in which
that cost is applicable [my_costs(cost, reverse_cost, start_time,
end_time,...)], the cost is the number of minutes it takes to traverse
from source to target.

Is there a way pgRouting can help me to calculate this special shortest
path?

I have not tried to setup a problem and use the code for this problem, but we do have gsoc_tdsp branch in git that is supported to solve this time dependent shortest path problem. Jay Mahadeokar implemented this and I believe he monitors this list, so if you have some specific questions, check the wiki first and then post to the list and we will see if we can help.

-Steve

4

On 1/30/2012 4:04 PM, Stephen Woodbridge wrote:

On 1/30/2012 3:48 PM, Roberto Oropeza Gamarra wrote:

Hello,

I need to calculate the shortest path, taking into account that the cost
of traveling beetween edges varies according to the time of day. I have
a table of edges [my_edges(id, source, target, ...)] and other table for
cost and reverse_cost with columns especifying the time of day in which
that cost is applicable [my_costs(cost, reverse_cost, start_time,
end_time,...)], the cost is the number of minutes it takes to traverse
from source to target.

Is there a way pgRouting can help me to calculate this special shortest
path?

I have not tried to setup a problem and use the code for this problem,
but we do have gsoc_tdsp branch in git that is supported to solve this
time dependent shortest path problem. Jay Mahadeokar implemented this
and I believe he monitors this list, so if you have some specific
questions, check the wiki first and then post to the list and we will
see if we can help.

If your routes are shorter and the costs do not vary from the start of the route to the end of the route, then you can just do a join as Jorge mentioned and use the regular solutions.

-Steve

5

Yes, I’m already doing that, but the problem is: let’s go from node A to node C, assume the travel lasts three hours, if I use a join using my_cost and my_edges with the time ‘10:00’ it will travel from A to C as every path is traversed at 10:00, it will ignore the fact that when you get midway A - C it is 11:30 and the traverse costs (i.e. time used to travel the nodes) has changed, so it will not be the shortest path, instead it will be the shortest path assuming we are frozen in time…

Hard, isn’t it? Some idea?

Regards, Roberto.

El 30 de enero de 2012 17:04, Jorge Eliécer Osorio Caro <jorgeliecer.osorio@gmail.com> escribió:

I think that you need to make a inner joint into my_cost according the time and pass the cost and reverse_cost, where match that time with and edge id.

2012/1/30 Roberto Oropeza Gamarra <oropezaroberto@gmail.com>

Hello,

I need to calculate the shortest path, taking into account that the cost of traveling beetween edges varies according to the time of day. I have a table of edges [my_edges(id, source, target, …)] and other table for cost and reverse_cost with columns especifying the time of day in which that cost is applicable [my_costs(cost, reverse_cost, start_time, end_time,…)], the cost is the number of minutes it takes to traverse from source to target.

Is there a way pgRouting can help me to calculate this special shortest path?

Thanks, Roberto.

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