What path fulfills all time constraints and has the least overall cost?
The problem is NP-hard in the strong sense. If the path need not be elementary, i.e., if it is allowed that vertices are visited more than once, the problem can be solved in pseudopolynomial time. A central aspect is that two (partial) paths in an SPPRC can be incomparable, contrary to the SPP without resource constraints. This makes the SPPRC similar to a multi-criteria decision problem.
A recent survey on the problem is:
Irnich, S.; Desaulniers, G. (2005):
Shortest Path Problems with Resource Constraints
in:
Desaulniers, G.; Desrosiers, J.; Solomon, M. (eds.) (2005):
Column Generation
Springer, New York, pp. 33–65
The present document cannot give a complete introduction to SPPRCs. To get a thorough understanding of the problem, the reader is referred to the above paper. However, to understand the algorithm and its implementation, it is necessary to explain some fundamental ideas and point out the differences to a labelling algorithm for the shortest path problem without resource constraints (SPP).
The standard solution technique for SPPRCs is a labelling algorithm based on dynamic programming. This approach uses the concepts of resources and resource extension functions. A resource is an arbitrarily scaled one-dimensional piece of information that can be determined or measured at the vertices of a directed walk in a graph. Examples are cost, time, load, or the information ‘Is a vertex i visited on the current path?’. A resource is constrained if there is at least one vertex in the graph where the resource must not take all possible values. The resource window of a resource at a vertex is the set of allowed values for the resource at this vertex.
A resource extension function is defined on each arc in a graph for each resource considered. A resource extension function for a resource maps the set of all possible vectors (in a mathematical sense, not to be confused with a std::vector) of resource values at the source of an arc to the set of possible values of the resource at the target of the arc. This means that the value of a resource at a vertex may depend on the values of one or more other resources at the preceding vertex.
Labels are used to store the information on the resource values for partial paths. A label in an SPPRC labelling algorithm is not a mere triple of resident vertex, current cost and predecessor vertex, as it is the case in labelling algorithms for the SPP. A label for an SPPRC labelling algorithm stores its resident vertex, its predecessor arc over which it has been extended, its predecessor label, and its current vector of resource values. The criterion to be minimized (cost, travel time, travel distance, whatsoever) is also treated as a (possibly unconstrained) resource. It is necessary to store the predecessor arc instead of the predecessor vertex, because, due to the resource constraints, one can not assume that the underlying graph is simple. Labels reside at vertices, and they are propagated via resource extension functions when they are extended along an arc. An extension of a label along an arc (i, j) is feasible if the resulting label l at j is feasible, which is the case if and only if all resource values of l are within their resource windows.
To keep the number of labels as small as possible, it is decisive to perform a dominance step for eliminating unnecessary labels. A label l_{1} dominates a label l_{2} if both reside at the same vertex and if, for each feasible extension of l_{2}, there is also a feasible extension of l_{1} where the value of each cardinally scaled resource is less than or equal to the value of the resource in the extension of l_{2}, and where the value of each nominally scaled resource is equal to the value of the resource in the extension of l_{2}. Dominated labels need not be extended. A label which is not dominated by any other label is called undominated or Pareto-optimal. The application of the dominance principle is optional—at least from a theoretical perspective.
The implementation is a label-setting algorithm. This means that there must be one or more resources whose cumulated consumption(s) after extension is/are always at least as high as before. This is similar to the Dijkstra algorithm for the SPP without resource constraints where the distance measure must be non-negative. It is sufficient if there is one resource with a non-negative resource consumption along all arcs (for example, non-negative arc lengths or non-negative arc traversal times).
source: Boost C++ library documentationThe SPPRC was introduced in the Ph.D. dissertation of Desrochers (1986) as a sub- problem of a bus driver scheduling problem. It consists of finding a shortest path among all paths that start from a source node, end at a sink node, and satisfy a set of constraints defined over a set of resources. A resource corresponds to a quantity, such as the time, the load picked-up by a vehicle, or the duration of a break in a work shift, that varies along a path according to functions, called resource extension functions (REFs)
The two-resource SPPRC, better known as the shortest path problem with time windows (SPPTW), was first studied in Desrosiers et al. (1983) and Desrosiers et al. (1984). The resource cost is unconstrained while the resource time is restricted by corresponding time windows.
node with exess flow and height function | |
current node | |
active nodes | |
edge with flow ≤ cap | |
s-t flow |
Click on a node to select it as the source/starting node s
Now the algorithm can begin. Click on next to start it
The algorithm is initialized with U = {trivial label/path} and P = &empty
As long as the queue containing the unprocessed labels isn’t empty pop the first label l from the front of the queue.
Extend the current path with label l=(~,v) along the edge e=(v,w) to get a new extended path with label l'=(l,w)
The accumulated resource consumption of this label is given by r(l') = max(r_lower(w),r(l)+r(e))
Check if the extended path with label l'=(l,w) is feasible in w, meaning that the accumulated resource consumption r(l') along the path is not larger than the upper resource constraint at its end node w.
l' ∈ FEASIBLE(w) ⇔ r(l') ≤ r_upper(w)
If it is feasible, add l' to the set Q of unprocessed labels/paths
In the absence of cycles of negative length, a label which has once been fully extended will never be touched again, which is why we speak of a Label Setting algorithm.
Thus, the current label l is now moved to the set of processed labels P, which we will later search for for our solution
For all the paths which end in some node v, prune the paths/labels which are striclty dominated in both sets U and P
l_1=(~,v) dominates l_2=(~,v) ⇔ time(l1) < time(l2) AND cost(l1) < cost(l2)
The algorithm terminated since there are no more unprocessed labels to extend
Hover over a node to see the set of all feasible paths ending in it
s ← pick(v)
BEGIN
(* Initialize *)
U ← {(ε,s)}, P ← ∅
(* Main Loop *)
WHILE ∃ l=(~,v) ∈ U
(* Path extension step *)
FORALL e=(v,w) ∈ E
l'=(l,w) ← EXTEND(l,e)
IF l' ∈ FEASIBLE(w)
U ← U ∪ {l'}
P ← P ∪ {l}
(* Dominance step *)
U,P ← REMOVE-DOMINATED(U,P)
END
(* Filtering step *)
t ← hover(v)
FORALL l=(~,t) ∈ P
highlight(l)
l' | U | l | P |
---|---|---|---|
- | ∅ | - | ∅ |
Du kannst die Anwendung in einem anderen Browserfenster öffnen, um parallel einen anderen Tab zu lesen.