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.