r_c_shortest_paths

template<class Graph,
         class VertexIndexMap,
         class EdgeIndexMap,
         class Resource_Container,
         class Resource_Extension_Function,
         class Dominance_Function,
         class Label_Allocator,
         class Visitor>
void r_c_shortest_paths( const Graph& g,
                         const VertexIndexMap& vertex_index_map,
                         const EdgeIndexMap& edge_index_map,
                         typename graph_traits<Graph>::vertex_descriptor s,
                         typename graph_traits<Graph>::vertex_descriptor t,
                         std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >& pareto_optimal_solutions,
                         std::vector<Resource_Container>& pareto_optimal_resource_containers,
                         const Resource_Container& rc,
                         const Resource_Extension_Function& ref,
                         const Dominance_Function& dominance,
                         Label_Allocator la,
                         Visitor vis )

template<class Graph,
         class VertexIndexMap,
         class EdgeIndexMap,
         class Resource_Container,
         class Resource_Extension_Function,
         class Dominance_Function,
         class Label_Allocator,
         class Visitor>
void r_c_shortest_paths( const Graph& g,
                         const VertexIndexMap& vertex_index_map,
                         const EdgeIndexMap& edge_index_map,
                         typename graph_traits<Graph>::vertex_descriptor s,
                         typename graph_traits<Graph>::vertex_descriptor t,
                         std::vector<typename graph_traits<Graph>::edge_descriptor>& pareto_optimal_solution,
                         Resource_Container>& pareto_optimal_resource_container,
                         const Resource_Container& rc,
                         const Resource_Extension_Function& ref,
                         const Dominance_Function& dominance,
                         Label_Allocator la,
                         Visitor vis )

template<class Graph,
         class VertexIndexMap,
         class EdgeIndexMap,
         class Resource_Container,
         class Resource_Extension_Function,
         class Dominance_Function>
void r_c_shortest_paths( const Graph& g,
                         const VertexIndexMap& vertex_index_map,
                         const EdgeIndexMap& edge_index_map,
                         typename graph_traits<Graph>::vertex_descriptor s,
                         typename graph_traits<Graph>::vertex_descriptor t,
                         std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >& pareto_optimal_solutions,
                         std::vector<Resource_Container>& pareto_optimal_resource_containers,
                         const Resource_Container& rc,
                         const Resource_Extension_Function& ref,
                         const Dominance_Function& dominance )

template<class Graph,
         class VertexIndexMap,
         class EdgeIndexMap,
         class Resource_Container,
         class Resource_Extension_Function,
         class Dominance_Function>
void r_c_shortest_paths( const Graph& g,
                         const VertexIndexMap& vertex_index_map,
                         const EdgeIndexMap& edge_index_map,
                         typename graph_traits<Graph>::vertex_descriptor s,
                         typename graph_traits<Graph>::vertex_descriptor t,
                         std::vector<typename graph_traits<Graph>::edge_descriptor>& pareto_optimal_solution,
                         Resource_Container>& pareto_optimal_resource_container,
                         const Resource_Container& rc,
                         const Resource_Extension_Function& ref,
                         const Dominance_Function& dominance )

Introduction and Problem Description

• 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
• etc.

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).

Concepts

ResourceContainer

A type modelling the ResourceContainer concept is used to store the current resource consumptions of a label.

Refinement of
DefaultConstructible, CopyConstructible, Assignable, LessThanComparable, EqualityComparable

Valid Expressions
See ResourceExtensionFunction concept.

This concept defines the interface for a label in the r_c_shortest_paths functions. It is a design decision not to parameterize the functions on the type of label. The type template<class Graph, class Resource_Container> struct r_c_shortest_paths_label is used to model this concept.

Valid Expressions
If label is an object of type r_c_shortest_paths_label, the following expressions are valid:

label.num	Returns an unsigned integer value specifying the number of the label. Labels are numbered consecutively in order of their creation.
label.cumulated_resource_consumption	Returns the object associated with label modelling the ResourceContainer concept.
label.p_pred_label	Returns a const pointer to the predecessor label, i.e., to the label whose extension along label.pred_edge yielded the label} object.
label.pred_edge	Returns an edge descriptor for the arc along which label.p_pred_label was extended to yield the label object.
label.resident_vertex	Returns a vertex descriptor for the vertex at which the label object resides.
label.b_is_dominated	Returns a boolean value indicating whether the label object is dominated by some other label residing at the vertex label.resident_vertex. Is useful only after dominance checking has been performed, i.e. only in the visitor functions on_label_dominated and on_label_not_dominated (see below).

Invariants
Every r_c_shortest_paths_label object, except for the first label, has a valid (not null) p_pred_label pointer and a valid pred_edge member. The p_pred_label pointer of the label with num member equal to zero is a null pointer, and the pred_edge member of this label is a default-constructed edge descriptor.

A model of the ResourceExtensionFunction concept is used to specify how a label is to be extended along an arc.

Valid Expressions
If ref models the ResourceExtensionFunction concept, and if the type Resource_Container models the ResourceContainer concept, the following expression is valid:

bool b = ref( const Graph& g, Resource_Container& new_cont, const Resource_Container& old_cont, graph_traits<Graph>::edge_descriptor ed )

ref must return true if and only if the extension is feasible, i.e., if new_cont fulfills all resource constraints at the target vertex of ed.

Moreover, a reference to a type modelling the ResourceExtensionFunction concept can be passed as a parameter to r_c_shortest_paths, see above.

Hence, a type modelling the ResourceExtensionFunction concept is likely to be a function or a function object.

Invariants
If ref models the ResourceExtensionFunction concept, and if the type Resource_Container models the ResourceContainer concept, after the call

ref( const Graph& g,
     Resource_Container& new_cont,
     const Resource_Container& old_cont,
     graph_traits<Graph>::edge_descriptor )

DominanceFunction

A model of DominanceFunction is used to specify a dominance relation between two labels.

Refinement of
BinaryPredicate

Valid Expressions
If dominance models the DominanceFunction concept, and if the type Resource_Container models the ResourceContainer concept, the following expression is valid:

bool b = dominance(const Resource_Container& rc1, const Resource_Container& rc2)

dominance must return true if and only if rc1 dominates rc2.

Moreover, a reference to a type modelling the DominanceFunction concept can be passed as a parameter to r_c_shortest_paths, see above.

Invariants
A type modelling the DominanceFunction concept must return true if and only if rc1<=rc2. It must not return false if rc1==rc2. Then, it is guaranteed that no two labels with identical resource consumption dominate each other and are both considered as dominated by the r_c_shortest_paths functions.

This concept defines the visitor interface for r_c_shortest_paths. A user can define a type with this interface and pass an object of this type to r_c_shortest_paths to perform user-defined actions at the event points of the algorithm. Note that the object is passed by value.

Refinement of
DefaultConstructible, CopyConstructible

Valid Expressions
If vis is an object of a type modelling the ResourceConstrainedShortestPathsVisitor concept, and if g is an object of a type Graph modelling the IncidenceGraph and the PropertyGraph concepts, and if it is a directed graph, and if l is an object of a type Label modelling the Label concept, the following expressions are valid:

vis.on_label_popped( const Label& l, const Graph& g )

vis.on_label_feasible( const Label& l, const Graph& g )

vis.on_label_not_feasible( const Label& l, const Graph& g )

vis.on_label_dominated( const Label& l, const Graph& g )

vis.on_label_not_dominated( const Label& l, const Graph& g )

See the description of the Label concept for the interface of a Label. See the algorithm description for information on when these functions are called.

Functions Description

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.

r_c_shortest_paths( g,
                    vertex_index_map,
                    edge_index_map,
                    s,
                    t,
                    pareto_optimal_solutions,
                    pareto_optimal_resource_containers,
                    rc,
                    ref,
                    dominance,
                    la,
                    vis )
{
  Label first_label, cur_label, new_label
  Set of Labels unprocessed_labels, labels_cur_vertex
  initialize first_label with rc
  INSERT(unprocessed_labels, first_label)
  while(unprocessed_labels != Ø)
    cur_label := EXTRACTMIN(unprocessed_labels)                      ◁ vis.on_label_popped(cur_label)
    if(cur_label is not dominated)
      vertex i = ResidentVertex(cur_label)
      perform pairwise dominance check over labels resident at i
      mark all dominated labels as dominated
      DELETE all labels which are dominated AND processed
    if(cur_label is not dominated)                                   ◁ vis.on_label_not_dominated(cur_label)
      mark cur_label as processed
      for each arc (i, j) in the forward star of i
        new_label := ref(cur_label)
        if(new_label is not feasible)                                ◁ vis.on_label_not_feasible(new_label)
          DELETE(new_label)
        else                                                         ◁ vis.on_label_feasible(new_label)
          INSERT(unprocessed_labels, new_label)
          INSERT(set of labels resident at j,new_label)
    else                                                             ◁ vis.on_label_dominated(cur_label)
      DELETE(cur_label)
  if(t could be reached from s)
    for each label resident at t
      INSERT(pareto_optimal_resource_containers, label.resource_container)
      recursively construct pareto_optimal_path
      INSERT(pareto_optimal_solutions, pareto_optimal_path)
      if(only one Pareto-optimal solution is sought)
        BREAK
}

Where Defined

Parameters

The graph object on which the algorithm is applied. The type Graph must be directed and must be a model of Incidence Graph and PropertyGraph.

A ReadablePropertyMap mapping vertex descriptors to integers in [0, num_vertices(g)).

A ReadablePropertyMap mapping edge descriptors to integers in [0, num_edges(g)).

A vertex descriptor describing the start vertex of the path.

A vertex descriptor describing the end vertex of the path.

A container for storing the Pareto-optimal (undominated) solutions (s-t-paths) in the overloads where all Pareto-optimal solutions are returned. The paths are returned as sequences of edge descriptors in reverse order (from t to s).

A container for storing the Pareto-optimal resource containers in the overloads where all Pareto-optimal solutions are returned.

A container for storing the first Pareto-optimal (undominated) solution (s-t-path) in the overloads where only one Pareto-optimal solution is returned. The path is returned as a sequence of edge descriptors in reverse order (from t to s). This argument is not modified if there are no solutions.

A Resource_Container object for storing the Pareto-optimal resource container corresponding to the first Pareto-optimal path in the overloads where only one Pareto-optimal solution is returned. This argument is not modified if there are no solutions.

An object specifying the initial resource consumptions at vertex s. The type Resource_Container must be a model of the ResourceContainer concept.

A function object or function pointer or function specifying how a label is to be extended along an arc. The type Resource_Extension_Function must be a model of the ResourceExtensionFunction concept.

A function object or function pointer or function specifying a dominance relation between two labels. The type Dominance_Function must be a model of the DominanceFunction concept.

An object of type Label_Allocator specifying a strategy for the memory management of the labels. It must offer the same interface as std::allocator. There is a default type default_r_c_shortest_paths_allocator for this parameter using the STL standard allocator. If the third or the fourth overload of the function is used, an object of this type is used as Label_Allocator parameter. 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 a specialized allocator, one can specify an arbitrary type as template parameter for the value type to the allocator; it is rebound to the correct type.

template<class Graph,
         class Resource_Container,
         class Resource_Extension_Function>
void check_r_c_path( const Graph& g,
                     const std::vector<typename graph_traits<Graph>::edge_descriptor>& ed_vec_path,
                     const Resource_Container& initial_resource_levels,
                     bool b_result_must_be_equal_to_desired_final_resource_levels,
                     const Resource_Container& desired_final_resource_levels,
                     Resource_Container& actual_final_resource_levels,
                     const Resource_Extension_Function& ref,
                     bool& b_is_a_path_at_all,
                     bool& b_feasible,
                     bool& b_correctly_extended,
                     typename graph_traits<Graph>::edge_descriptor&
                     ed_last_extended_arc )

The file example/r_c_shortest_paths_example.cpp provides 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.