Shortest Paths with Resource Constraints

Question

I have a directed acyclic graph and need to find the shortest paths with resource constraints. My constraint is that the paths selected must have a minimum number of a set resource consumed.

Currently I am using Yen's K Shortest Path algorithm to calculate K shortest paths and then only accept those that satisfy my constraint. The issue here is in guessing K, as if it is incorrectly chosen, it is possible that no feasible paths will be found.

I have found quite a lot of literature on this topic, this provides a good overview I think. However, I am struggling to make sense of it and find a concise algorithm that is able to be implemented (I am using Python, however any clear algorithmic ideas would be great).

I understand that this problem is NP-Complete, and as such I am interested in any good approximation algorithms as well as exact approaches.

Anyone have any good recommendations?

Answer 1

What you can do is to transform your graph (V,E) into (V',E') where

• P(v) is the price of the original node v
• R is the maximum resource use.
• V' = {(v,k) | v in V and k in [0..R]}
• E'((v,k),(w,l)) = E(v,w) and k+P(w)=l

Then you do a dijkstra search from (v0,P(v0)). If it was possible to find a path to v1, given the limit, the shortest distance to it, will be the shortest among the (v1,k) vertices.

You obviously don't create the actual expanded graph. What would be going on in your modified dijkstra is that in addition to the distance so far, you would keep the resource use so far as well. You would only follow a path if it didn't exceed the limit. And instead of keeping a dist[v] you would keep dist[v,k] representing the shortest path to v so far, using exactly k resources.

If your resource bound is very large, this can potentially grow as big. Hence the NP completeness. However if your resource bound is small, or you don't mind rounding of to nearest 10, 100 or 1000, it will run in fast polynomial time. Especially if you implement the optimization of stopping once you've reached a useable (v1,k).

Answer 2

Solving this problem as a k-shortest path suffers from the fact that you don't know how to choose k.

Solving it as the accepted answer proposes, suffers from the fact that you need to maintain dist[v,k] for potentially all values of k from all distinct paths arriving from the source to node v (which results in very inefficient algorithm).

There are pseudo-polynomial time algorithms for solving this problem, which is called, as you'd expect, "Shortest Path Problem with Resource Constraints" (SPPRC). The problem appears often in Vehicle Routing Problems (VRP) and Crew Pairing Problems (both are transportation problems, that are mostly dealt with in Operations Research). For a starting point see the following (review) paper: S. Irnich & G. Desaulniers, "Shortest Path Problems with Resource Constraints", In G. Desaulniers, J. Desrosiers, M. Solomon (eds): Column Generation, Springer, 2005.

You can google for the title of the paper, and you should be able to download it for free. I should mention though that your problem has an unusual constraint structure: namely, you need to "spend" at least a certain amount of a resource instead of making sure you don't spend "too much" of a resource...