Every analysis runs the same sixteen stages. Here they run on one real town, Oberlin, Ohio, and every figure is drawn from that town's exported files.
The town's drivable road network comes from OpenStreetMap: every intersection, every street, every one-way. A two-way street becomes two directed segments, one per direction, because each side is its own pass of the plow. The download is cached and snapshotted, so a run can be rebuilt from exactly the map it was solved on.
Each segment takes a tier from its OpenStreetMap road class. Arterials and their ramps are Tier 1, tertiary and named unclassified roads Tier 2, residential streets Tier 3. Anything else drivable stays in the graph to drive through, but nobody is asked to plow it. Greedy plows the tiers in order, all of Tier 1 first; CARP plans for the least empty driving, then for each tier's clearance window: a late plan is repaired, or plowed band by band with Tier 1 first, and the least late plan wins.
On request, every intersection gets an elevation from SRTM satellite data and every segment a grade. A loaded truck climbing a steep street burns more fuel and needs more salt, and the cost model adjusts both. An intersection with no data is left blank, not set to zero, so a gap never passes for a flat road.
The map becomes what every solver searches: intersections are nodes, segments directed edges weighted by length. OpenStreetMap's simplified network is used as it comes, so a straight run between two intersections is already a single edge. Routes minimize distance; time follows from each truck's own speeds.
Each truck is modelled on its own: its depot, its salt load, its plowing speed and its driving speed. A fleet can be identical or mixed, and can work from one depot or several.
The rules for the night: Tier 1 cleared within 3 hours, Tier 2 within 6, Tier 3 within 12; salt laid at 50 kg per lane-km, residential streets at half; a reload at the depot costs a quarter of an hour. A client run uses its own windows and rates instead.
Before any routing, a search out from the depot confirms every required segment can be reached, and that the truck can get home from it. A street cut off by one-way rules or a gap in the map is set aside and reported in the run, never silently dropped, so a run cannot claim coverage it does not have.
Routing asks one question thousands of times: how far, by road, from here to there? Each answer comes from Dijkstra's shortest-path search, run the first time a corner is asked about and remembered after, so every later question from the same corner is a lookup.
Why routing still runs on a 1959 algorithm, and what may replace it: an interactive essay
The solver first threads one continuous tour through every required segment, one-ways respected. Where the streets don't join end to end, one min-cost flow finds the cheapest blade-up detours that balance them, and the result is walked as an Euler trail. Pieces that only roads needing no plowing connect are then linked nearest first, a heuristic step. When the streets and detours form one piece, the tour is the least empty driving possible for one truck with unlimited salt. The tour ignores trucks, salt and priority. It is raw material.
How a 1736 puzzle took most of the blade-up out of the routes: an essay
The tour is cut into one stretch per truck, sized by projected hours, each truck's own speeds, salt and reload time included, so that by that projection the last truck finishes as early as possible. A truck that needs several loads can finish a little later than projected, and the refinement after this weighs empty driving, not hours. Inside a stretch that needs more than one load of salt, the reload trips go where they leave the least empty driving: an exact optimization over every possible set of cuts, not a rule of thumb. Between trips a truck goes back to the depot to reload. A fleet with several depots instead cuts the whole tour into salt trips and gives each to a truck whose depot can reach it.
Local search then works the routes over: reverse a run of streets within a route, move a short run into another truck's route where it fits best, nudge a reload earlier or later. A move is kept only if it still saves empty driving once the route is rebuilt end to end, and the search runs until a full pass finds no saving. Inside its cap (120 s, or 1,800 s for seven 5–6-truck runs on the largest towns), which every gallery run finishes within, the same town and fleet give the same plan on any machine.
To show the gain is real, every town is also solved the way a crew might without a plan: whichever truck is free soonest drives to the nearest unplowed street, all of Tier 1 first, then 2, then 3. No look-ahead, no coordination. It is the bar the optimized plan has to clear, on the same network with the same trucks.
For scale, the classic Chinese Postman tour: one truck, no salt limit, no deadlines, directions ignored. Wherever an odd number of required passes meet, the tour must drive something twice; it pairs those corners up as cheaply as possible. Nobody can drive the result, and it is not a strict bound, but it shows how much empty driving the street layout itself forces.
The least empty driving and the most even shifts pull against each other. NSGA-II, a genetic algorithm, seeds a population from the optimized plan and the baseline, then crosses and mutates routes for generations, keeping the plans no other beats on both counts. You get the whole frontier, with the knee — the best compromise — marked.
Every plan is scored the same way: the deadhead ratio (empty driving over all driving), the hour the last truck finishes, fuel, salt, and when each tier is cleared against its window. Per-truck and per-tier breakdowns show where the time goes. A shift ends at the last street plowed; the drive home is not in the totals.
Everything leaves the engine as plain files: the network and routes as GeoJSON, metrics and diagnostics as JSON, a timeline for the replay. Runs carry the engine commit that made them. The gallery, the client dashboard and the printed route sheets all read these same files, which is how every figure on this page was drawn.
The solver's tuning: how hard priority bends the tour, which moves the search tries and in what order, how long it searches and when it stops. The methods are the published algorithms it is built on; the numbers are its output, in files you can open in the gallery.