Planning a Robot's Route Through a Warehouse

A warehouse robot drives between stations along aisles of different lengths, and some aisles get congested. The fastest route is a shortest path in a weighted graph; change one aisle's cost and the best route can jump to a completely different path.

How it works

Shortest paths in weighted graphs

In one sentence

For nonnegative edge weights, Dijkstra's algorithm computes all shortest-path distances $d(v)$ from a source, which satisfy Bellman's equation $d(v) = \min_u (d(u) + w(u, v))$ , in $O((V + E)\log V)$ time with a priority queue.

General formula

{\htmlData{sym=0}{d(v)}} = \min_{\htmlData{sym=2}{{u}}}\bigl(d({\htmlData{sym=2}{u}}) + {\htmlData{sym=1}{w(u, v)}}\bigr), \qquad {\htmlData{sym=3}{d(S)}} = 0

Distances spread outward from the start like a wave, and a station's distance is final once the wave reaches it.

What the symbols mean

$d(v)$
Shortest distance
The least total travel time from S to station v.
$w(u, v)$
Aisle time
How long the aisle between u and v takes.
$u$
Neighboring station
A station one aisle away from v; the minimum runs over all of them.
$d(S)$
Start
The start station is distance 0 from itself.

Model stations as vertices and aisles as edges weighted by travel time. The robot needs the cheapest path from S to G.
Dijkstra's algorithm settles vertices in order of distance: S, then B (2.5), then A (3), and so on, always extending from the closest vertex not yet settled.
Every distance obeys $d(v) = \min_u (d(u) + w(u, v))$ : the best route to $v$ is the best route to one of its neighbors plus one aisle.
Raise the congestion on an aisle and the distances update; the moment another route becomes cheaper, the whole path switches.

Learn the math

Graphs, Degrees and the Handshake LemmaDiscrete · Lesson 37, Graph Theory Paths, Connectivity and Shortest PathsDiscrete · Lesson 38, Graph Theory