Skip to content

Engineering

Route optimization: when the shortest path is the wrong objective

How an interactive route planner went from the shortest path to the safest one, and what we learned building it.

Computing America. Applications, integrations, data analysis and AI/ML engineering.

State the objective
3 min readComputing America
Painted floor lines guiding a curved forklift route around pallets that block the straight path.

In short

  • A routing question posed as shortest path may need a different objective, such as the route that stays farthest from obstacles.
  • Changing the objective changed three rules of a Dijkstra search, not the algorithm.
  • The right data structure can make an objective nearly free. Every point on a Voronoi edge is equidistant from its two nearest obstacle points, so the diagram already holds the candidate corridors. Our search scores each edge by the clearance at its endpoints, measured to sampled obstacle points.
  • When no route has positive clearance, our planner returns a path whose clearance is zero, not an error, so callers handle failure with the code they already have for paths.
  • Before you ask for an optimizer, write down what it should minimize and what your dispatchers do when they overrule it.

Minimize distance and the route grazes every corner it turns around. An operator who wants margin has to minimize something else, and in our planner that took three changed rules in a Dijkstra search.

The planner is an interactive tool in two dimensions, with static obstacles and no vehicle dynamics. It triangulates hand-drawn obstacles, dualizes the triangulation into a Voronoi diagram and searches the diagram for the route that stays farthest from them. Draw obstacles below and see where it runs.

Interactive · Route planning

Draw obstacles, get a maximum-clearance route

Drag on the canvas to draw obstacles. Then drop a start and goal.
N0tri0vor0Δ0.0msV0.0msfilt0.0mspath0.0ms
8 sizes · 3-iter mean · random points

Note: this in-browser run uses a 3-iteration mean for responsiveness; the pre-baked voronoi_benchmark.json behind the static chart and table uses 10 iterations, so per-cell numbers here will run lower. Its scene holds scattered point obstacles and no drawn walls. That makes its path column the floor for that stage, not a reading of the clearance planner. There, every stroke you draw adds segments the blocking check has to test. The shape (Delaunay dominating, Voronoi nearly free, path growing fast) is the same.

What this isThe planner itself, front to back, in the browser: your strokes become sites, the sites become a Delaunay triangulation, the triangulation’s dual becomes a clearance-weighted graph, and the search returns the route that stays as far from your obstacles as the geometry allows. Two dimensions, static obstacles, no vehicle dynamics: the same limits the write-up states.

The question people ask, and the one they mean

A vehicle must get from a start to a goal through obstacles. The reflexive framing is shortest path. It has a well-known algorithm, so the problem looks solved. The operator's objective is different, and it produces a visibly different path.

Sometimes the structure hands you the answer

Every point on a Voronoi edge is equidistant from the edge's two nearest obstacle points, so the diagram already holds the candidate corridors between obstacles. You don't search for them. Edges that cross an obstacle are dropped before the search sees them. One caveat: ours is the Voronoi diagram of points sampled from your strokes, so clearance means distance to the nearest sampled point, an approximation of distance to a wall. A Voronoi diagram of the segments themselves measures to the wall, and we did not build that.

Three rules change the objective

The graph's nodes are the Voronoi vertices plus the start and the goal. A node's clearance is its distance to the nearest sampled obstacle point, and an edge's weight is the smaller of its two endpoints' clearances. That can overstate a corridor whose narrowest point lies mid-edge, because we did not add that point as a node.

Here “safest route” means the path that maximizes its minimum edge weight, while Dijkstra's algorithm minimizes a sum of weights. Three rules change to get the widest path.

Fig. 1
  1. Dijkstra: relaxation

    Keep dist[u] + weight if smaller

    • To Widest path: relaxation
  2. Group: The planner's three changed rules

    Widest path: relaxation

    Keep min(cap[u], weight) if larger

  3. Dijkstra: next node

    Take the unvisited node with the smallest distance

    • To Widest path: next node
  4. Group: The planner's three changed rules

    Widest path: next node

    Take the unvisited node with the greatest bottleneck

  5. Dijkstra: start

    Start at zero, every other node at infinity

    • To Widest path: start
  6. Group: The planner's three changed rules

    Widest path: start

    Start at infinity, every other node at zero

Three rules turn Dijkstra's shortest sum into a widest path: the relaxation, the choice of next node and the starting values.

SourceThe planner's search described in this article, set against textbook Dijkstra.

planner/geometry.ts: the relaxationTypeScript
neighbors.forEach((edge) => {  const nextCap = Math.min(cap[u], edge.weight);  if (nextCap > cap[edge.to]) {    cap[edge.to] = nextCap;    parent[edge.to] = u;  }});
The textbook line is dist[u] + weight, kept if smaller. The other two changes, greatest-cap selection and the start at Infinity, sit outside this listing.

Make failure the same type as success

When no route has positive clearance, the search returns the direct line if nothing blocks it, and otherwise the start alone, both with zero clearance. A clear direct line is already an edge of the graph, so it comes back this way only when its weight is zero, which happens when the start or goal sits on a sampled obstacle point. The result keeps the type of a success, a path and a clearance, so the drawing code has no null branch. The trade is that the type no longer separates failure from success: zero clearance is a convention the caller has to know. Our interface shows "No safe path between start and goal" only for the single-point result, and reports a direct line as a path found with clearance 0.0.

Then test any optimizer you are offered on your own worst inputs before you accept it: your real stop count, two stops at one address, and a stop that sits on a restricted area.

Next step

Tell us what the optimizer is supposed to minimize.

And what your dispatchers do when they overrule it. The gap between those two answers is often the real specification, and we will write it back to you as one.

Reply
A person replies, not a sequence: within one business day, from someone who would be on the engagement.

Packages

Start with a package

Four packages, each with its price on the page. Pick one and buy it online.

Billing