  Resource constrained shortest path problems are usually solved thanks to a
smart enumeration of all the non-dominated paths. Recent improvements of these
enumeration algorithms rely on the use of bounds on path resources to discard
partial solutions. The quality of the bounds determines the performance of the
algorithm. The main contribution of this paper is to introduce a standard
procedure to generate bounds on paths resources in a general setting which
covers most resource constrained shortest path problems, among which stochastic
versions.
  In that purpose, we introduce a generalization of the resource constrained
shortest path problem where the resources are taken in a monoid. The resource
of a path is the monoid sum of the resources of its arcs. The problem consists
in finding a path whose resource minimizes a non-decreasing cost function of
the path resource among the paths that respect a given constraint. Enumeration
algorithms are generalized to this framework. We use lattice theory to provide
polynomial procedures to find good quality bounds. These procedures solve a
generalization of the algebraic path problem, where arc resources belong to a
lattice ordered monoid. The practical efficiency of the approach is proved
through an extensive numerical study on some deterministic and stochastic
resource constrained shortest path problems.
