Resource-Constrained Shortest Paths and Label-Setting with Dominance

Every algorithm built on relaxation optimises a single additive quantity, and all of them rely on the same structural fact: the best route to a vertex is a prefix of the best route through it. Add a second quantity that also accumulates along the path and that fact stops being true. The cheapest route to a vertex may be the one that spends too much of the second quantity, and the route that is best overall may pass through a vertex by a route that is not the cheapest to that vertex. This is the resource-constrained shortest path problem, and the machinery that handles it replaces “the distance to a vertex” with “the set of undominated ways to reach a vertex”.

Why the single-label invariant fails

Take a graph with $s \to a$ costing 1 in time and 10 in fuel, $s \to b$ costing 5 in time and 1 in fuel, and both $a$ and $b$ connecting to $t$ with identical edges. Minimising time alone picks the route through $a$. Add a fuel budget of 5 and the route through $a$ is infeasible, while the route through $b$ is feasible and optimal. A search that kept only the time-optimal label at $a$ and $b$ would have discarded nothing useful here, but a slightly different instance shows the general problem: the time-optimal route to an intermediate vertex may exhaust the budget, while a slower route to the same vertex leaves enough budget to complete the path more cheaply overall.

Formally, the constrained problem is

$$\min \sum_{(u,v) \in p} c(u,v) \quad \text{subject to} \quad \sum_{(u,v) \in p} r_i(u,v) \le R_i ;; \text{for each resource } i,$$

over paths $p$ from $s$ to $t$. With one resource and integer values the problem is weakly NP-hard: it contains the knapsack problem as a special case when the graph is a chain of parallel choices. With two or more resources the problem is strongly NP-hard, so no pseudo-polynomial algorithm exists unless P = NP. So the methods below are exact but exponential in the worst case, and their practical value comes from the fact that the worst case is rare on the instances where they are used.

The failure of optimal substructure is precise. If $p$ is an optimal feasible path through vertex $v$, its prefix to $v$ is not necessarily optimal for any single criterion: it is optimal only in the sense that no other feasible prefix dominates it. That weaker statement is the one the algorithms exploit.

Labels, and what dominance means

A label at vertex $v$ is a tuple $(c, r_1, \dots, r_k, \text{predecessor})$ recording the cost and the resource consumption of a specific partial path from $s$ to $v$. The set of labels at $v$ is pruned by dominance: label $A$ dominates label $B$ if

$$c_A \le c_B \quad \text{and} \quad r_{i,A} \le r_{i,B} ;; \text{for every } i,$$

with at least one inequality strict. A dominated label can be discarded, because any feasible completion of $B$ is also a feasible completion of $A$ and yields a path of no greater cost: the completion consumes the same resources and adds the same cost to both.

Two refinements of the rule matter in practice. Weak dominance allows equality in all components but requires that $A$‘s predecessor path be preferable on a tie-breaking criterion; without it, equal labels duplicate and the label count grows for no benefit. And dominance is only valid when the resources are monotone: every edge consumes a nonnegative amount, so extending a path never reduces its resource vector. With a resource that can decrease along an edge, such as a battery charged by a regenerative braking edge, the dominance rule is unsound, because a label that consumes more now may end up with more later. Monotonicity is a modelling requirement, not an implementation detail.

The set of undominated labels at a vertex is its Pareto front in $k+1$ dimensions. Its size is bounded by the number of distinct resource vectors, which is exponential in $k$ in the worst case and, on real instances, is usually small at most vertices and large at a few.

Label-setting versus label-correcting

The single-criterion algorithms split into a label-setting method that settles labels permanently and a label-correcting method that revises them, and the same split exists here.

A label-setting algorithm for the constrained problem maintains a queue of labels ordered by cost, extracts the cheapest, and extends it along outgoing edges. Because cost is the objective and every edge cost is nonnegative, the extracted label is the cheapest way to reach its vertex with its resource vector: no cheaper label with the same or a dominating resource vector can appear later. The correctness argument is the one from Dijkstra and the Settled-Set Invariant, applied per label rather than per vertex.

The catch is the queue’s contents. Labels are generated dynamically as extensions of extracted labels, so the queue is not a fixed set of $|V|$ entries; it can hold a number of entries proportional to the total label count, which is the exponential quantity. A binary heap over labels works and is what most implementations use; a bucket structure indexed by cost works when costs are small integers, for the reasons discussed in Priority Queues for Dijkstra.

A label-correcting variant relaxes labels repeatedly and prunes by dominance after each improvement. It has no settling guarantee, so a label may be extended, pruned, and regenerated; the work is bounded by the label count times the average out-degree rather than by a clean invariant. It is used when costs can be negative, which is legitimate here, since the objective is no longer required to satisfy the nonnegativity that Dijkstra’s argument needs, provided the resource consumptions stay nonnegative.

Elementary paths and the cycle problem

A path that revisits a vertex is not a path in the usual sense, and the constrained problem is normally posed over elementary paths. Enforcing elementarity is expensive: the state must record which vertices have been visited, which turns the label into a bit vector of $|V|$ bits and inflates the label space by a factor of $2^{|V|}$ in the worst case.

The usual engineering compromise is to relax elementarity: allow walks, prune cycles by dominance, and accept that the returned solution may revisit a vertex. On many instances the relaxation changes nothing, because a cycle that consumes resources without reducing cost is dominated by the label without it. When resources can be consumed by a cycle that is required for feasibility elsewhere, the relaxation can return a walk whose cost is below the true elementary optimum, which is a real correctness gap and not a cosmetic one.

A middle ground keeps a counter of the vertices visited and rejects extensions beyond a bound, or stores a short history per label, the last few vertices, and rejects immediate revisits. Both are heuristics with no guarantee, and both are common.

Where the method is used

The problem’s practical importance comes from column generation, where it is the pricing subproblem. In a vehicle-routing or crew-scheduling model, the master problem selects a set of routes and the pricing step asks for a route with negative reduced cost, a shortest path in a graph whose edge costs are reduced costs, subject to resources such as time windows, shift length, and capacity. The label count on those instances is what determines whether the overall method is usable, and the dominance rules are usually strengthened with instance-specific reasoning: arrival time at a vertex dominates, because an earlier arrival leaves more of the time window available; a partial load that is a subset of another’s is dominated when the capacity constraint is the only consumer.

The second use is in routing with a hard constraint that the shortest-path model cannot express: a vehicle with a limited range, a network path with a maximum number of hops, a route that must avoid congestion above a threshold. These are single-resource problems, and a single resource makes the label sets small enough that the method behaves like an ordinary shortest-path search with a filter.

The two dials that control cost

Two parameters dominate the cost of an implementation, and their interaction is the whole performance story.

The first is the dominance check’s cost. Comparing a new label against the existing set at a vertex is a linear scan in the naive version, so the work per generated label grows with the front size, and the total is quadratic in the number of labels at a vertex. Keeping the front sorted by cost allows a scan that stops early, because a label with higher cost than the new one cannot dominate it. With two resources, a sorted structure keyed on one resource and filtered on the other is the usual implementation; with three or more, the check becomes the dominant cost and implementations switch to an approximate or bucketed dominance test.

The second is the resource discretisation. Rounding resource values to a grid reduces the number of distinct vectors and therefore the front sizes, at the price of an answer that may violate a budget by up to the grid step, with a cost excess that grows with the step. That trade between exactness and tractability is the standard escape hatch when the exact method does not finish.

Neither dial has a setting that works everywhere. The instances that defeat the method are the ones where the Pareto fronts are genuinely large: many mutually incomparable trade-offs between cost and resource, at many vertices. Constructing such an instance is easy, since a chain of independent two-way choices produces $2^n$ distinct resource vectors, which is why the exponential worst case is not a theoretical curiosity but a description of a family of small graphs.

What carries over from the unconstrained case

The relaxation primitive survives unchanged: extending a label along an edge adds the edge’s cost and resource vector, and the update is a comparison against the current front. The optimality condition survives in weakened form: a front is complete when no extension of any label in it can produce an undominated label outside it, and the search terminates when every front is complete. What does not survive is the polynomial bound, and with it the assumption that a shortest-path routine is cheap.

That is the honest summary of the constrained case. It is the same search, with the state widened from a scalar to a set, and the widening is what turns a near-linear routine into one whose cost is a property of the instance rather than of the graph’s size.