 Shortest Paths with Resource Constraints  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.

## 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?

### 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.

A 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

## Algorithm status

### 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.

### 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)})