Resource Constrained Shortest Path program

Okay, this is officially a 'Resource Constrained Shortest Path' problem. I have been given an algorithm in class , but I'm having a really difficult time understanding it. The algorithm is as follows:

Let $\displaystyle R$ be a set of resources.

Let $\displaystyle N$ be the set of nodes.

Let $\displaystyle A_i$ be the set of nodes connected to node $\displaystyle i$.

Let $\displaystyle d_{ij}$ be the length of arc from $\displaystyle i$ to $\displaystyle j$, assumed to be positive for all arcs.

Let $\displaystyle U_{ij}$ be the vector of resource consumption on the arc from $\displaystyle i$ to $\displaystyle j$. It is not necessary that these are positive. Some arcs can replenish resources.

Let $\displaystyle L_i$ be the set of labels for node $\displaystyle i$.

($\displaystyle i, s V, done$) - the data stored with a label: $\displaystyle i$ the node, $\displaystyle s$ the relevant path length, $\displaystyle V$ the vector of resource levels, $\displaystyle done$ a boolean flag. For label $\displaystyle l$ these can be written as $\displaystyle i_l, s_l, V_l, done_l$.

Assume we start at the origin $\displaystyle O$ with an initial vector of resources $\displaystyle V_O$. We can define a resource constrained shortest path algorithm as follows:

(1) Set $\displaystyle L_i = $ ∅, $\displaystyle i \in N$; $\displaystyle L_O = \{(O, 0, V_O, false)\}$.

(2) Choose $\displaystyle l$ the label such that $\displaystyle s_l = min \{s_l | done_l = false\}$

(3) If $\displaystyle i_l = D$ then stop.

(4) Set $\displaystyle done_l = true.$

(5) For all $\displaystyle j \in A_ij$, such that $\displaystyle V_l - U_{ij} \geq 0 $

AddLabel$\displaystyle \{j, s_l +d_{ij}, V_l - U_{ij}, false\}$

(6) Go to step 2

The process AddLabel removes and labels (including the label to be added itself) if the are dominated by some other label. By definition, label $\displaystyle l_1$ dominates label $\displaystyle l_2$ if and only if

$\displaystyle i_{l_1} = i_{l_2}, s_{l_1} \leq s_{l_2}, V_{l_1} \geq V_{l_2}$

One label dominating another implies a separate path to the same node that is shorter (or at least no longer) and consumes less (or at least no more) of every resource. In the case of no resource this algorithm reduces to a shortest path algorithm.

What I have to do is write down a general purpose formulation (recursion or algorithm) for calculating the cheapest way from Townsville to Villageville, using the above algorithm, and find the shortest path from each node to Villageville. How can the this information (shortest path to destination from each node) be used to find a lower bound on the cost of completing any partial journey using the algorithm used to find the cheapest way from Townsville to Villageville.

I am also unsure what is meant by the lower bound.