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
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
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.
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.
Dijkstra: relaxation
Keep dist[u] + weight if smaller
- To Widest path: relaxation
Group: The planner's three changed rules
Widest path: relaxation
Keep min(cap[u], weight) if larger
Dijkstra: next node
Take the unvisited node with the smallest distance
- To Widest path: next node
Group: The planner's three changed rules
Widest path: next node
Take the unvisited node with the greatest bottleneck
Dijkstra: start
Start at zero, every other node at infinity
- To Widest path: start
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.
neighbors.forEach((edge) => { const nextCap = Math.min(cap[u], edge.weight); if (nextCap > cap[edge.to]) { cap[edge.to] = nextCap; parent[edge.to] = u; }});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.
- Phone
- (214) 723-2510
- 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.
$199/month
Billed monthly
$182.42/month
Billed yearly
$499/month
Billed monthly
$457.42/month
Billed yearly
- Scammers stopped from sending email as you
- Your website and systems scanned every week
- Your email settings checked every week
- Everything in the 1 to 10 plan
- Covers up to 50 people
$199/month
after a one-time setup fee
- A site planned, designed and built for you
- Hosting and updates every month
$499/month
Billed monthly
$457.42/month
Billed yearly
$999/month
Billed monthly
$915.75/month
Billed yearly
- Your Google profile, fully set up
- A Google post every week
- 2 social posts a week
- Everything in Get found
- 4 social posts a week
- Your top 10 Google searches tracked
from$500/month
after a one-time setup fee
- Your data gathered from the tools you use
- A first analysis that answers your questions
- New findings every month
Related reading
Engineering4 min readWhat building a compiler teaches about data modeling
How choosing an intermediate representation in a compiler maps onto choosing the data model of a business system.
Engineering3 min readOffline-first apps: the product decision to make in week one
A field app that treats offline as an error state fails where the work happens. Three questions settled in week one decide whether yours will.
