Shortest Paths with Resource Constraints Technische Universität München

Introduction
Create a graph
Run the algorithm
Description of the algorithm
More

SPP

SPPTW

Shortest paths

Shortest path problem (SPP)

In many applications one wants to obtain the shortest path from a to b. This path is optimal with respect to a one-dimensional resource, e.g. the distance. These shortes path problems (SPP) can be solved efficiently, depending on the underlying network structure, with the Dijkstra, Bellman-Ford or Floyd-Warshall algorithm.

Shortest path problem with resource constraints (SPPRC)

The SPPRC seeks a shortest (cheapest, fastest) path in a directed graph with arbitrary arc lengths (travel times, costs) from an origin node to a destination node subject to one or more resource constraints.

Shortest path problem with time windows (SPPTW)

A practical problem in which we need to consider two-dimensional resources is the bus driver scheduling problem. The resource cost is unconstrained while the resource time is restricted by corresponding time windows. We now seek the optimal path with respect to cost, which simultanesouly fulfills all the time window restrictions at the nodes it passes through, e.g. latest arrival time of the bus and earliest departure time. This problem is known as the Shortest Path Problem with Time Windows (SPPTW), an illustrative special case of the even more general SPPRC.

This applet presents a simple label-setting algorithm, which solves the two dimensional SPPTW with resources time and cost. No negative cycles are allowed

What do you want to do first?

spp-rc-graph-editor.svg

Legende

	node with time window [arrival,departure]
	edge with 2d resource vector (time,cost)

Which graph do you want to execute the algorithm on?

Start with an example graphs:

Select

Modify it to your desire:

To create a node, make a double-click in the drawing area.
To create an edge, first click on the start node and then click on its node. To create an edge, first click on its start node and then on its end node. Alternatively, you may (single-)click on the drawing field to create a new node as end node.
Right-clicking deletes edges and nodes.

SPPTW specific

The resource consumptions (time,cost) along an edge can be changed by double clicking on the edge.
The time window [arrival,departure] of a node can be changed by double clicking on it.

Download the modified graph:

Download

Upload an existing graph:

occured when reading from file:

the contents:

What next?

Highlight path for label: spp-rc-graph-algorithm-graph.svg

Legende

Labels ending in resident node: spp-rc-graph-algorithm-labels.svg

Legende

Algorithm status

fast forward

Explanation
Pseudocode
Log

First choose a source node

Click on a node to select it as the source/starting node s

Label-Setting SPPTW algorithm

The source node has been selected and is filled with green. Per default, this is the node with lowest id. If you want to change the source node, go back with prev.

The target node is selected at the end of the algorithm.

Edges are annotated with resources (time,cost) and nodes with time windows [arrival,departure] for the resource time.

Now the algorithm can begin. Click on next to start it

Initialize

The queue U of unprocessed labels (yellow) is initialized with the trivial path, ending in start node s. The queue of processed labels P (dark green) is inititially empty.

Main loop

As long as the queue U of unprocessed labels isn’t empty pop a label l (red) from the front of the queue.

The label l ends in its resident node v, which is also highlighted (in red) in the graph.

Path extension step 1/2: extend the label

Extend the path with label l=(~,v) along the edge e=(v,w) to get the new extended path with label l'=(l,w). Both e and l' are highlighted in orange.

The accumulated resource consumption of l' is the sum of its parent label l consumption and the one along the edge e. Furthermore, the resource time is bounded from below by the earliest arrival time of the time window [arrival, departure] (blue rectangle) of resident node w (thick blue border) of l':
time(l') = max(arrival(w),time(l)+time(e))

Path extension step 2/2: l' feasible in w

The extended path with label l'=(l,w) is feasible in w, meaning that the accumulated time consumption time(l') along the path of l' is not larger than the upper resource constraint departure(w) at its resident node w.

l' ∈ FEASIBLE(w) ⇔ time(l') ≤ departure(w)

l' is feasible, thus add it to the set U of unprocessed labels.

Path extension step 2/2: l' infeasible in w

The extended path with label l'=(l,w) is NOT feasible in w, meaning that the accumulated time consumption time(l') along the path of l' is larger than the upper resource constraint departure(w) at its resident node w.

l' ∉ FEASIBLE(w) ⇔ time(l') > departure(w)

l' is infeasible, thus ignore it.

Label processed

All outgoing edges of the resident node v of the label l have been checked for possible label extensions. In the absence of cycles of negative length, a label which has once been fully extended will never again be extended, which is why we speak of a Label Setting algorithm.

Thus, the current label l is now moved to the set of processed labels P (dark green), which we will search for minimum-cost solutions at the very and of the algorithm.

Dominance step 1/2: iterate nodes

If there are two or more labels resident - or equally paths ending - in some node v, prune the ones which are striclty dominated in both sets U and P.

The dominance algorithm thus checks for each node v with at least two labels resident in it if some labels can be discarded.

Dominance step 2/2: check a node for dominaned labels

For the node v (thick blue border), all its labels are checked for dominance and some may be discarded.

A label dominates another one if it has strictly lower time and cost consumptions: l=(~,v) dominates l*=(~,v) ⇔
time(l) < time(l) AND cost(l) < cost(l*).

The remaining paths are incomparable and their labels pareto-optimal with each other, meaning that we cannot say that one is better than another.

Finished

The algorithm terminated since there are no more unprocessed labels to extend.

Filtering step

Per default, the node with the highest id was selected as target node t. The solution of the SPPTW, a feasible minimum-cost s-t path is shown in pink. To select another node as target t, just click on it.

Last operation:

Variable status

l'	U	l	P
-	∅	-	∅

s ← pick(v)

BEGIN

(* Initialize *)

U ← {(ε,s)} and P ← ∅

(* Main Loop *)

WHILE ∃ l=(~,v) ∈ U

U ← U \ {l}

(* Path extension step *)

FORALL e=(v,w) ∈ E

l'=(l,w) ← EXTEND(l,e)

IF l' ∈ FEASIBLE(w)

U ← U ∪ {l'}

ELSE

throw away l'

P ← P ∪ {l}

(* Dominance step *)

FORALL v ∈ V\{s}

U,P ← REMOVE-DOMINATED(U,P)

END

(* Filtering step *)

t ← pick(v)

l* ∈ P | cost(l*) == min({cost(l=(~,t)∈P)})

path for label c

path for label d

pareto frontier of node 2: paths c and d are incomparable

Shortest path problem with resource constraints (SPPRC)

The shortest path problem with resource constraints (SPPRC) seeks a shortest (cheapest, fastest) path in a directed graph with arbitrary arc lengths (travel times, costs) from an origin node to a destination node subject to one or more resource constraints. For example, one might seek a path of minimum length from s to t subject to the constraints that

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.

The SPPRC was introduced in the Ph.D. dissertation of Desrochers (1986) as a sub- problem of a bus driver scheduling problem. It consists of finding a shortest path among all paths that start from a source node, end at a sink node, and satisfy a set of constraints defined over a set of resources. A resource corresponds to a quantity, such as the time, the load picked-up by a vehicle, or the duration of a break in a work shift, that varies along a path according to functions, called resource extension functions (REFs)

The two-resource SPPRC, better known as the shortest path problem with time windows (SPPTW), was first studied in Desrosiers et al. (1983) and Desrosiers et al. (1984). The resource cost is unconstrained while the resource time is restricted by corresponding time windows. [ID05]

Idea of the algorithm

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

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.

Incomparable paths

The main difficulty of the SPPRC/SPPTW compared to the SPP is that (partial) paths ending in the same node may be incomparable, meaning we cannot say that a path is better than another. In the SPPTW, this is the case if path a is better with respect to time, but path b is better with respect to cost. Thus, one has to keep both paths, since there might be extensions of b might be unfeasible in nodes further down the path, but feasible if we extend a.

Dominance and the pareto frontier

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.

Negative cycles: Label-setting vs. Label-correcting

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). If one wants to allow negative cycles, a label which has once been fully extended cannot be laid aside and never be touched again. Instead, it might be picked up and extended later again. This is analogous to the Bellman-Ford Label-Correcting algorithm for the SPP problem.

source: Boost C++ library documentation

What is the pseudocode of the algorithm?


Input:  directed graph G=(V,E) with 
        start node s and end node t
        resource windows for all nodes
        resource vectors for all edges
Output: feasible, pareto-optimal s-t path l* with minimal cost

How fast is the algorithm?

Complexity

Whereas the (unconstrained) shortest path problem can be efficiently solved in polynomial time, the introduction of a single additional resource constraint makes the problem NP-complete. [ZIE01] 3.2 This can be shown by transformation into the well-known knapsack problem (KP).

Dynamic Programming Approaches

Since the knapsack problem can be solved by a dynamic programming recursion and SPPRC can be reduced to a knapsack, we can also find a dynamic programming recursion for SPPRC. \( O(|E|\lambda) \)

Labeling Approaches

improve the dynamic programming bound by using domination rules

Label Setting vs Label Correcting

[ZIE01] p. 60

References

Literature

[ID05]

Stefan Irnich und Guy Desaulniers. „Shortest Path Problems with Resource Constraints“. English. In: Column Generation. Hrsg. von Guy Desaulniers, Jacques Desrosiers und MariusM. Solomon. Springer US, 2005, S. 33–65. isbn: 978-0-387-25485-2. doi: 10.1007/ 0-387-25486-2_2. url: http://dx.doi.org/10.1007/0-387-25486-2_2.

available online: v1 server 1 v1 server 2 v2

[AMO93]

Ravindra K. Ahuja, Thomas L. Magnanti und James B. Orlin. Network flows. Theory, algorithms, and applications. Prentice Hall, Inc., Englewood Cliffs, NJ, 1993, S. xvi+846. isbn: 0-13-617549-X.

4: SHORTEST PATHS: LABEL-SETTING ALGORITHMS
5: SHORTEST PATHS: LABEL-CORRECTING ALGORITHMS

[SCH04]

Schlechte T. Das Resource Constrained Shortest Path Problem und seine Anwendung in der ÖPNV-Dienstplanung, Master's thesis (german diploma), Technische Universät Berlin, 2004.
available online

[ZIE01]

Ziegelmann M. Constrained Shortest Paths and Related Problems. PhD thesis, Universität des Saarlandes, 2001.
available online

[GAR09]

Garcia R. Resource constrained shortest paths and extensions. PhD thesis, Georgia Institute of Technology, 2009. available online

[FEI04]

Feillet, Dominique, et al. "An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems." Networks 44.3 (2004): 216-229. available online

Shortest paths

Shortest path problem (SPP)

Shortest path problem with resource constraints (SPPRC)

Shortest path problem with time windows (SPPTW)

This applet presents a simple label-setting algorithm, which solves the two dimensional SPPTW with resources time and cost. No negative cycles are allowed

What do you want to do first?

Legende

Which graph do you want to execute the algorithm on?

Start with an example graphs:

Modify it to your desire:

Download the modified graph:

Upload an existing graph:

What next?

Legende

Legende

Algorithm status

First choose a source node

Label-Setting SPPTW algorithm

Initialize

Main loop

Path extension step 1/2: extend the label

Path extension step 2/2: l' feasible in w

Path extension step 2/2: l' infeasible in w

Label processed

Dominance step 1/2: iterate nodes

Dominance step 2/2: check a node for dominaned labels

Finished

Filtering step

Last operation:

Variable status

Shortest path problem with resource constraints (SPPRC)

Idea of the algorithm

Labels

Incomparable paths

Dominance and the pareto frontier

Negative cycles: Label-setting vs. Label-correcting

What is the pseudocode of the algorithm?

How fast is the algorithm?

Complexity

Dynamic Programming Approaches

Labeling Approaches

Label Setting vs Label Correcting

References

Literature

Web resources