Two ways to cross a city, and what happens when the road closes
I wanted to settle a question I had carried for a while: when you route a vehicle across a city, is a graph formulation really more robust than a linear program? Both find shortest paths. The LP gives you an optimality guarantee. The graph does not. On paper the LP wins. But I suspected the graph would hold up better the moment the world changed mid-trip, and I wanted to prove it with running code, not hand-waving.
So I built both, pointed them at the same problem — Transamerica Pyramid to the San Francisco Zoo, surface streets only — and closed a road while a vehicle was driving. This is the story of what I found, including the parts where I was wrong.
The setup
I hand-built a network of San Francisco intersections: real corners, real coordinates, no freeways. The first version had 60 nodes. That number matters later, so hold onto it.
Each road segment carries a distance, a speed limit, and a live traffic label. Travel time falls out of the three: distance over speed, scaled by traffic. Free-flowing traffic costs nothing extra; congestion multiplies the time; a closure sets it to infinity. Distance and speed never change. Only the traffic label moves. That single design choice — keep the road fixed, patch the label — turned out to be the whole argument.
Two solvers consume this network differently.
The graph treats the road network as the model. Nodes are intersections, edges are streets, edge weight is travel time. Ask it for the shortest path and it walks the edges. When traffic changes, you patch one edge's weight and ask again.
The linear program never sees intersections as a route. It sees a flow problem: send one unit of flow from the source, absorb it at the destination, conserve flow at every other node, and minimize total cost. The path emerges from which arcs carry flow. It runs on the full network and re-solves the whole thing every time anything changes.
I chose flow conservation because it is compact: one variable per street, one constraint per intersection. You could model the same route as an integer program instead — closer to an assignment problem, with binary decisions about which arc follows which. It would solve just as fast on a problem this size; these are easy problems for a modern solver. But the variable and constraint counts would balloon, and every one of them is something you must build, track, and edit correctly when the world changes. The flow formulation keeps the model small, which makes the later argument about the cost of editing it as favorable to the LP as it can be.
Same problem. Same answer, as it turned out. The difference is everything around the answer.
The first wall: the solver wanted a DAG
I reached for an existing graph solver and hit a wall on the first run: "no path exists." The network was fine — every node reachable, the destination reachable — but the solver rejected it.
The solver is built for directed acyclic graphs. A road network is the opposite of acyclic. Every two-way street is a little loop: you can go from A to B and from B back to A. Sixty-nine of those loops, in fact. The solver choked on every one.
This is a real constraint, not a bug, and it forced a choice. To use this solver, I had to turn a cyclic map into an acyclic one.
The fix: orient every edge toward the goal. Compute each intersection's straight-line distance to the Zoo, then keep a street only if it moves you closer. Downhill toward the destination, never uphill. A graph that only ever flows downhill cannot loop, so it is acyclic by construction. And it costs nothing to compute — just distance arithmetic per intersection, no search.
It worked. Same shortest path, 17.2 minutes, and now the solver accepted it. The linear program needed none of this. It eats cycles for breakfast; flow conservation handles them natively. Score one quiet point for the LP, and a note for later: the graph made me do extra work just to fit the tool.
The second wall: a road closed and the graph got stuck
Here is where I expected to win, and where I first lost.
Send the vehicle down the route. Partway along the Sunset Boulevard stretch, close the road ahead. The graph re-plans from the vehicle's current position — and finds nothing. No path. The vehicle is stuck.
The cause traces straight back to the downhill rule. Sunset Boulevard, in my sparse 60-node map, was a single thread south. Every cross-street that could carry the vehicle over to the parallel arterial pointed slightly away from the Zoo, so the downhill rule had pruned them all. Close the one street ahead and there is no detour, because I had deleted every detour to make the graph acyclic.
I had traded away the robustness I was trying to prove.
The linear program, meanwhile, shrugged. It re-solved on the full network, cycles and all, and found a way around. At this point the scoreboard read: LP two, graph zero. Not what I came for.
The fix was data, not cleverness
The instinct is to make the routing smarter. The right move was to make the map denser.
My 60-node network was too sparse to reroute. Real San Francisco has a street every couple of blocks; my model had skipped most of them. So I added them — more parallel avenues, more cross-streets, more genuine alternatives — bringing the network to 80 nodes and 130 segments.
Run the closure again. Now the graph reroutes. The vehicle backs up a few blocks to a corner where a real alternative exists, cuts over to 19th Avenue, and continues to the Zoo. The detour exists because the denser map provides it.
This is the first honest tradeoff, and it is worth stating plainly: the graph reroute only works when the network offers a real alternative. Too sparse, and backing out of a closure finds nothing. This is not a flaw in the method. It is a requirement on the data. And it improves with scale — the denser the map, the more alternatives near any point, the cheaper and more local the reroute. Real road networks are far denser than my test corridor, so in practice the requirement is met easily. But you have to meet it.
How the graph backs up
When the road ahead closes and the current corner offers no way forward, the vehicle does what you would do: it reverses to the last corner that has another option, and tries again from there.
In code, this is a short loop. Ask for a path from the current position. If there is one, drive it. If there is not, step back one block — recording the U-turn as real distance driven — and ask again. Repeat until a forward path appears. Each question is cheap, because each asks about a small slice of the map near the vehicle, and that slice shrinks as the vehicle nears the goal.
I keep a running log of every leg the vehicle drives, U-turns included. That log is the honest record of the trip: not the plan, but what happened. When the vehicle backs out of a blocked corridor, the duplicates in the log — the same corners visited going forward, then backward — are the visible cost of the closure.
The results
Before the closure, both solvers agree. Free-flowing traffic, same route, same time:
SOLUTION A — graph (Armada ShortestPath)
Solve time: 4 ms
Weight: 17.20 min
Path: N01 > N76 > N74 > N07 > N09 > N10 > ... > N54 > N56 > N57 > N58 > N60
SOLUTION B — LP (flow conservation, GoogleLinear)
Optimal: true
Objective: 17.17 min
Solve time: 139 ms
Path: N01 > N76 > N74 > N07 > N09 > N10 > ... > N54 > N56 > N57 > N58 > N60
Identical path, found two ways. The 0.03-minute gap is the LP's floating-point tolerance, nothing more. Worth noting already: 4 milliseconds against 139. Even on this tiny network, the graph query is far cheaper than building and solving the model — and that is before anything changes.
Now the closure. The vehicle drives 14 minutes to reach the blocked segment, then the road shuts.
The graph: five small re-plans from successive positions as it backs out, then a clean run down 19th Avenue. Total driven: 22.98 minutes. Of that, 2.87 minutes is the U-turn — the cost of backing out of the dead end. The vehicle physically reverses four blocks, then reroutes. Each re-plan is a tiny query, below millisecond resolution on this network.
The linear program: one re-solve from the vehicle's position. It reports 19.11 minutes total and calls it optimal. It rebuilds and solves all 246 variables and 80 constraints in a few milliseconds.
REROUTE — road N52->N53 closed, vehicle at N52
SOLUTION A (graph)
reroute queries 5
forward 14.03 | u-turn 2.87 | reroute 6.08 min
traveled total 22.98 min (reached goal: true)
SOLUTION B (LP)
full re-solve 246 vars x 80 constraints, 3 ms
forward(driven) 14.03 | replan 5.07 min
reported total 19.11 min (optimal: true)
replan path: N52 > N71 > N68 > N53 > N54 > ... > N60
Read those two totals and the LP looks better: 19.11 against 22.98. But look at the route the LP chose — N52 > N71 > N68 > N53. From the blocked corner it threads sideways through the Sunset grid, slips past the closure on a parallel street, and doubles back. It is a mathematically optimal path for a vehicle that can pivot in any direction from a standstill. No real car, having driven head-on into a closed street, can take it. The LP's 19.11 minutes is unrealizable.
This is the second tradeoff, and the more important one. The LP solved the wrong problem — cheaply and optimally. It treated the vehicle's current corner as a free starting point, ignoring that the vehicle arrived there with momentum and a direction and now faces a wall. To make the LP honest, you would have to rebuild its cost structure to encode the vehicle's physical state: forbid the sideways escapes a real car cannot make; force the backtrack; and move the source. That is not one constraint. It is a careful edit to the whole matrix, and it is easy to get wrong.
The graph never had this problem. The vehicle's position and history live in the structure. Backing out is a step in a loop, not a reformulation.
What scales
At this size both solvers finish in milliseconds, so raw speed settles nothing. The structural difference is what matters as the map grows.
The graph re-examines a small neighborhood around the vehicle, once per backtrack step, and that neighborhood shrinks as the trip proceeds. The linear program re-examines the entire model on every change, regardless of where the vehicle is or how small the change was. Close one street, and the graph patches one weight and asks about one neighborhood; the LP rebuilds every coefficient and solves the whole system again.
Scale the city up and the gap widens. The graph's work stays tied to the local change. The LP's work stays tied to the size of the world. A closure on one corner should not require re-reasoning about the entire city — but for the LP, it does.
The honest scorecard
So is the graph more robust? Yes — with two caveats I did not have when I started.
The graph needs a dense enough map to offer detours. Give it a sparse network and it strands the vehicle; give it a realistic one and it reroutes locally and cheaply.
The graph carries the vehicle's physical state for free, in its structure. The LP can match the graph's correctness, but only if you do the work to encode that state into the matrix by hand — and that work is fiddly, global, and error-prone. The LP's optimality guarantee is real, but it guarantees the optimum of whatever problem you encoded, which may not be the problem you have.
The graph is slower per query and offers no optimality guarantee. On a static problem, solved once, the LP is the cleaner choice. But routing is not static. The road closes while you are driving. And when it does, the cheap local patch beats the expensive global re-solve — not because it is faster today, but because it scales with the change instead of the world, and because it never quietly solves the wrong problem.
The full comparison
The report script reads both runs and lays them side by side. Here it is in full:
===============================================================
REROUTE COST COMPARISON
Event: T3-block-N52-N53 (vehicle at N52)
===============================================================
SOLUTION A - graph (monotone DAG + Armada ShortestPath)
--------------------------------------------------------
N01 -> N76 0.58 min forward
N76 -> N74 0.22 min forward
N74 -> N07 0.19 min forward
N07 -> N09 0.42 min forward
N09 -> N10 0.42 min forward
N10 -> N11 0.34 min forward
N11 -> N12 0.40 min forward
N12 -> N13 0.55 min forward
N13 -> N14 0.32 min forward
N14 -> N15 0.35 min forward
N15 -> N16 0.54 min forward
N16 -> N20 0.12 min forward
N20 -> N24 0.48 min forward
N24 -> N26 0.23 min forward
N26 -> N27 0.22 min forward
N27 -> N29 0.51 min forward
N29 -> N31 0.26 min forward
N31 -> N32 0.29 min forward
N32 -> N34 0.20 min forward
N34 -> N35 0.30 min forward
N35 -> N36 0.28 min forward
N36 -> N38 0.74 min forward
N38 -> N39 0.43 min forward
N39 -> N40 0.42 min forward
N40 -> N41 0.13 min forward
N41 -> N42 1.00 min forward
N42 -> N43 1.22 min forward
N43 -> N44 1.64 min forward
N44 -> N50 0.05 min forward
N50 -> N51 0.25 min forward
N51 -> N52 0.93 min forward
N52 -> N51 0.93 min uturn
N51 -> N50 0.25 min uturn
N50 -> N44 0.05 min uturn
N44 -> N43 1.64 min uturn
N43 -> N45 0.08 min reroute
N45 -> N46 0.25 min reroute
N46 -> N47 0.93 min reroute
N47 -> N48 1.33 min reroute
N48 -> N49 0.97 min reroute
N49 -> N55 1.06 min reroute
N55 -> N54 0.59 min reroute
N54 -> N56 0.18 min reroute
N56 -> N57 0.42 min reroute
N57 -> N58 0.16 min reroute
N58 -> N60 0.11 min reroute
TOTAL 22.98 min
forward 14.03 | u-turn 2.87 | reroute 6.08 min
reroute queries: 5 reached goal: true
SOLUTION B - LP (flow conservation + Armada GoogleLinear)
--------------------------------------------------------
N01 -> N76 0.58 min forward
N76 -> N74 0.22 min forward
N74 -> N07 0.19 min forward
N07 -> N09 0.42 min forward
N09 -> N10 0.42 min forward
N10 -> N11 0.34 min forward
N11 -> N12 0.40 min forward
N12 -> N13 0.55 min forward
N13 -> N14 0.32 min forward
N14 -> N15 0.35 min forward
N15 -> N16 0.54 min forward
N16 -> N20 0.12 min forward
N20 -> N24 0.48 min forward
N24 -> N26 0.23 min forward
N26 -> N27 0.22 min forward
N27 -> N29 0.51 min forward
N29 -> N31 0.26 min forward
N31 -> N32 0.29 min forward
N32 -> N34 0.20 min forward
N34 -> N35 0.30 min forward
N35 -> N36 0.28 min forward
N36 -> N38 0.74 min forward
N38 -> N39 0.43 min forward
N39 -> N40 0.42 min forward
N40 -> N41 0.13 min forward
N41 -> N42 1.00 min forward
N42 -> N43 1.22 min forward
N43 -> N44 1.64 min forward
N44 -> N50 0.05 min forward
N50 -> N51 0.25 min forward
N51 -> N52 0.93 min forward
N52 -> N71 0.97 min replan
N71 -> N68 1.58 min replan
N68 -> N53 0.68 min replan
N53 -> N54 0.97 min replan
N54 -> N56 0.18 min replan
N56 -> N57 0.42 min replan
N57 -> N58 0.16 min replan
N58 -> N60 0.11 min replan
TOTAL 19.11 min
forward(driven) 14.03 | replan 5.07 min
full re-solve: 246 vars x 80 constraints, 3 ms, optimal true
===============================================================
The data
The road network is a single JSON file: 80 San Francisco intersections, 130 street segments, real coordinates, no freeways.