Resource-Constrained Shortest Paths

The shortest path problem with resource constraints (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 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
(available online here)

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₁ dominates a label l₂ if both reside at the same vertex and if, for each feasible extension of l₂, there is also a feasible extension of l₁ where the value of each cardinally scaled resource is less than or equal to the value of the resource in the extension of l₂, and where the value of each nominally scaled resource is equal to the value of the resource in the extension of l₂. 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).

The functions are an implementation of a priority-queue-based label-setting algorithm. At each iteration, the algorithm picks a label l from a priority queue (the set of unprocessed labels) and checks it for dominance against the current set of labels at the vertex i where l resides. If l is dominated by some other label residing at i, l is deleted from the set of labels residing at i. If l is undominated, it is extended along all out-edges of i. Each resulting new label is checked for feasibility, and if it is feasible, it is added to the set of unprocessed labels and to the set of labels residing at the respective successor vertex of i. If a new label is not feasible, it is discarded. The algorithm stops when there are no more unprocessed labels. It then checks whether the destination vertex could be reached (which may not be the case even for a strongly connected graph because of the resource constraints), constructs one or all Pareto-optimal (i.e., undominated) s-t-path(s) and returns. A pseudo-code of the algorithm follows.

The function leaves a lot of work to the user. It is almost like a small framework for SPPRCs. This, however, is a property inherent to the problem. It is entirely up to the user to make sure that he stores the 'right' resources in his resource container object, that the resource extension function extends a label in the desired way, and that the dominance function declares the 'right' labels as dominated and not dominated. In particular, the precondition that the initial ResourceContainer object supplied to the function must be feasible is as important as it is unpleasant. The implementation does not check this and, hence, sacrifices comfort for genericity here. It was a design decision not to make any assumptions with respect to the relationship between the type modelling ResourceContainer and the vertex properties of the graph type.

In case the underlying graph does not contain negative cycles (cycles with overall negative resource consumption for the unconstrained resource whose consumption is to be minimized, such as cost or distance), the resulting paths will always be elementary, i.e., without repetitions of vertices. In the presence of negative cycles, the algorithm is finite if there is at least one strictly increasing resource, i.e., one resource with strictly positive resource consumption on all arcs (this is a sufficient condition). Otherwise, one must provide a customized type for the ResourceContainer concept to ensure finiteness. See, for example
Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C. (2004):
An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints: Application to Some Vehicle Routing Problems
Networks, vol. 44, pp. 216-229.

Experience shows that for 'small' resource containers, it may be useful to try a specialized small object allocator, e.g., from the Boost Pool library. For larger resource containers (i.e., for a large number of resources), the default allocator is the right choice.

If the third or the fourth overload of the function is used, objects of type default_r_c_shortest_paths_allocator and default_r_c_shortest_paths_visitor are used as the Label_Allocator and Visitor parameters respectively. If the first or the second overload is used, one must specify both a Label_Allocator and a Visitor parameter. If one wants to develop a user-defined type only for Visitor, one can use default_r_c_shortest_paths_allocator as Label_Allocator parameter. If one wants to use only a specialized allocator, one can use default_r_c_shortest_paths_visitor as Visitor parameter.

There is a utility function called check_r_c_path that can be used for debugging purposes, if r_c_shortest_paths returns a path as feasible and Pareto-optimal and the user is of the opinion that the path is either infeasible or not optimal:

The boolean parameters have the following meaning:

ed_last_extended_arc stores the edge descriptor of the last extended arc. If ed_vec_path is a path of positive length and b_feasible==false, ed_last_extended_arc is the edge descriptor of the arc at whose target vertex the first violation of a resource window occured.

The file example/r_c_shortest_paths_example.cpp provides additional examples for how SPPRCs can be solved with the r_c_shortest_paths functions. There is an example for an SPP without resource constraints and an example for a shortest path problem with time windows.
It is obvious that one would not use the algorithm for SPPs without resource constraints, because there are faster algorithms for this problem, but one would expect a code for the SPP with resource constraints to be able to handle such a case.