pgRouting algorithm for shortest path problem with resource constraints

Question

do you know how to get pgRouting to approximate solutions to the shortest path problem with resource constraints (SPPRC), an NP-hard problem?

SPPRC seeks a shortest (cheapest, fastest) path in a directed graph with > arbitrary arc lengths (travel times, costs) from an origin node to a destination node subject to one or more resource constraints. For example, one might seek a path of minimum length from s to t subject to the constraints that

• the total travel time must not exceed some upper bound and/or
• the total amount of some good that has to be picked up at the vertices along the path be less than or equal to some capacity limit and/or
• if two vertices i and j are visited on a path, then i must be visited before j

Quoted from the Boost Graph Library at http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/r_c_shortest_paths.html.

I need such an algorithm to compute low-stress bicycle routes through an Open Street Map network from one origin to many destinations. The 'low-stress' criterion introduces the constraints.

If no algorithm exists, then is there one that can at least compute all paths of a bounded length/cost from one origin to many destinations? Then i can inspect each resulting path to find the ones that satisfy the constraints. Probably not efficient, but it might be good enough for my purposes.

Answer 1

I am no bike rider, but I am a pgRouting developer, I can tell you that we are doing efforts to incorporate all of BGL algorithms to pgRouting, unfortunately the one you ask is not there yet.

• We have pgr_dijkstra one to one, one to many, many to one and many to many based on the cost value you give.
• We also have pgr_KSP (k shortest paths) that give you the K shortest paths from one point to another.
• We also have pgr_drivingDistance that given a "distance" cost, gives all the points that are reachable with in that "distance", (if your cost is in time units, the distance must also be in time units)

There is going to be a pgr_dijkstraVia, where you give the order of vertices and gives you the shortest path, the documentation shows how you can inspect if you "passed" in front of a particular vertex.

But, from what is already there and from what we are documenting for what is going to be version 2.2 I would do something like:

Data preparation:

Have a column that indicates which roads are forbidden to bicycles so that when you make a query, those roads are not included. Calculate what is going to be your cost of each edge,

• can be length,
• or can be time, t=x/s where x is length and s is speed. (I would use this)

The speed of an edge can be in terms of the angle of the edge, you might need to know the slope of the edge to penalize the speed if you are going up, and that improves the speed if you are going down based on a speed of a flat surface.

You can also penalize the speed in terms of type of road, etc. Once you have your time set, you would have a graph that is from the point of view of a cyclist.

(source, target, length(m), speed(m/s), r_speed time(s), r_time(s))

• (1, 2, 120, 10, 30, 12, 4)
• (2, 3, 120, 20, 20, 6, 6)
• (3, 4, 120, 5, 5, 24, 24)

In the above example:

• going from 1 to 2 is slower because its going "up hill" and takes 12 seconds,
• 2 to 3 & 3 to 4 are in a flat surface, but 3 to 4 is slower because it is a road made of sand.

After you prepared your data, play around with the functions, and see whats best, Start with pgr_drivingDistance to rule out "unreachable vertices" withing a time bound.

Hope it helps. P.D. we are working on the documentation of 2.2, the code is done, so visit us in Github.