SPP

SPPTW

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.

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.

spp-rc-graph-editor.svg
## Legende

node with time window [arrival,departure] | |

edge with 2d resource vector (time,cost) |

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

Highlight path for label:
spp-rc-graph-algorithm-graph.svg
## Legende |
Labels ending in resident node:
spp-rc-graph-algorithm-labels.svg
## Legende |

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

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

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.

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.

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

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.

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.

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.

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.

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.

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

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.

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