Resource-Constrained Shortest Path

Solving the shortest path problem with an additional side constraint on cumulative resource consumption. Introduces the resource-constrained formulation, label extension along edges, dominance of labels, Pareto-optimal label sets, and a full labeling algorithm for RCSP.

Step 1 of 157%

Tutorial

The Resource-Constrained Shortest Path Problem

The resource-constrained shortest path problem (RCSP) augments the standard shortest path problem with a side constraint. Every edge $e$ carries two numbers: a cost $c_e$ and a resource consumption $r_e \ge 0.$ We are given a resource budget $R,$ and we seek the cheapest $s$ -to- $t$ path whose total resource consumption stays within budget.

For a path $P = (e_1, e_2, \dots, e_k),$ define

c(P) = \sum\limits_{e \in P} c_e, \qquad r(P) = \sum\limits_{e \in P} r_e.

The path is feasible when $r(P) \le R.$ The RCSP asks for

\min_{P \text{ feasible}} c(P).

For example, an edge labeled $(c_e, r_e) = (3, 2)$ contributes cost $3$ and resource $2$ to whichever path uses it. With a budget $R = 5,$ a single-edge path using this edge has $r(P) = 2 \le 5,$ so it is feasible.

Unlike the unconstrained problem, the globally cheapest path may be ruled out by the constraint, so neither Dijkstra nor Bellman-Ford applied to costs alone is enough — the resource dimension must be tracked alongside cost.