Same Streets, a Fraction of the Blade-Up: How a 1736 Puzzle Rebuilt PlowPath's Routes

Some of a plow's empty driving is forced by the streets. Much more of it was forced by the plan. In October 2026 PlowPath began ordering a town's streets along an Euler trail, an idea from 1736. With the same trucks and settings, blade-up fell by a median 81% across 69 plans in 19 towns, and by 82% on the 31 whose street maps had not changed.

Greg Dogum · 2026-10-15

A plow on its way to the next street it has to clear drives with the blade up. Nothing gets plowed. The truck burns fuel and the driver burns hours. Some of that driving is forced on the truck by the streets themselves. A lot of it, it turns out, was forced by the plan.

In October 2026, engine 0.2.0 changed the step that matters most in how PlowPath builds a plan: the order the streets are taken in. The new order comes from an argument Leonhard Euler published about the bridges of Königsberg in 1736, and a recipe Carl Hierholzer left for it in 1873. The engine then re-solved the optimized (CARP) plans in the gallery. For 69 of them, in 19 towns, the earlier result is kept beside the new one, with the same trucks and the same settings. Blade-up driving fell in every one, by a median of 81%.

This essay explains why the plows were driving empty, what Euler's idea does about it, and what changed on real streets.

Why a plow drives empty

Deadhead, or blade-up driving, has two sources. It is worth keeping them apart.

The first is the network. A truck has to get from the depot to its first street, and back to the depot for salt. A one-way street can only be plowed in its direction, so after plowing it the truck may have to drive around the block to get back. No plan avoids this driving. A good plan keeps it short.

The second is the order. A plan that takes streets in a poor order leaves some behind, finishes the area around them, and then comes back for them over streets it has already plowed. That driving is a choice, and a better plan doesn't make it.

PlowPath builds a plan the way most arc-routing methods do: route first, split second.¹ First it lines up every street that needs plowing in one long order, the giant tour, as if one truck with unlimited salt were going to plow the whole town. Then it cuts that order into stretches, one per truck, with trips back for salt inside each. Last, a local search tries small changes and keeps any that cut blade-up. These are stages 09, 10 and 11 on the pipeline page.

Up to engine 0.1.3, the giant tour was a nearest-neighbour walk. From wherever the walk had got to, it took the closest street not yet plowed. To favour main roads, it counted the distance to a street of a lower priority tier double. Both rules look sensible one step at a time. Neither looks back. A street that is never the closest one gets left behind: the far side of a two-way street, a short dead end, the last block of a loop, a residential street passed over for an arterial. Once everything around it is done, the truck comes back for it, blade up.

The local search could not repair this. It tries small changes to a finished order: reverse a run of streets, move a few to another truck. A search polishes a plan; it does not reorder a town. Measured against the least blade-up any plan could drive on its streets (the floor, below), the plans it polished drove a median of about ten times that much.

Euler's bridges

Königsberg, in Prussia, had seven bridges joining two islands and the two banks of its river. The puzzle was whether anyone could walk across every bridge exactly once. In 1736 Euler showed they could not, and why.²

Every time a walk arrives on a piece of land by one bridge, it must leave by another. So the bridges at each piece of land get used in pairs. Only where the walk starts, and where it ends, can a bridge be left over. In Königsberg every piece of land had an odd number of bridges, so no such walk existed.

Turn that around and it describes a plow route. At every intersection in town, count the streets the plow must plow into it and the streets it must plow out of it. If the two counts match everywhere, and the streets all connect, one truck can plow every street exactly once and never lift the blade. Where they don't match, the truck must drive blade-up into or out of that intersection to make up the difference.

PlowPath plows a two-way street once in each direction, one pass per side. So a two-way street takes the truck into each of its ends once and out once. It never upsets the count. Only one-way streets do. A town of two-way streets is balanced before anyone plans anything.

Euler stated the condition but did not show how to find the walk. Hierholzer did, in a paper published in 1873, two years after his death.³ His recipe is short:

1. Start at the depot. Keep plowing any unplowed street out of where you are.
2. On a balanced network you can only get stuck back where you started.
3. Go back along your own route to the last intersection that still has an unplowed street leaving it. Walk a loop from there until you are stuck again: you will be back at that same intersection.
4. Splice the loop into the route at that point. Repeat until no street is left.

Each loop starts and ends at an intersection the route already passes through, so splicing it in costs no extra driving. As long as the streets connect, nothing is left behind: any unplowed street touches the route somewhere, and a loop from there picks it up.

Paying for the one-way streets

Real towns have one-way streets, so the counts do not match everywhere. The fix is to add blade-up driving first, the cheapest that balances every intersection, and only then walk.

When every street can be driven either way, choosing that extra driving is the Chinese Postman Problem, posed by Guan Meigu in 1960.⁴ When streets have directions, as a town's one-ways do, it becomes a minimum-cost flow. Every intersection with more plowed streets in than out has trucks to send away; every intersection with more out than in needs trucks brought to it. The flow finds the cheapest set of legal drives that does all of it at once, across the whole town. Jack Edmonds and Ellis Johnson showed in 1973 how to solve both versions exactly, and quickly.⁵⁶ Minimum-cost flow is a standard tool of operations research,⁷ and the engine solves it with the network simplex method.

Engine 0.2.0 builds the giant tour in three steps:

1. Balance. One minimum-cost flow over the town's directed road network, one-way signs respected, finds the cheapest blade-up driving that lets a single walk from the depot plow every street once. The walk may end anywhere.
2. Walk. Hierholzer's recipe, from the depot, over the streets plus that driving.
3. Join. Streets the flow leaves unconnected, such as streets reached only over roads that need no plowing, are joined on nearest first.

When the streets and the added driving form one piece, the walk's blade-up is the least that any one-truck plan with unlimited salt can drive. PlowPath calls that the floor. Each run page in the gallery shows its plan's floor, computed for that plan's own fleet. The floor leaves out salt reloads and each truck's drive out to its share of the streets, so real plans sit above it. No plan sits below.

Two towns show what one-way streets cost. In Oberlin, Ohio, 21 of 445 street segments are one-way, and the floor is 0.35 km for 92 km of streets. In Canton, a neighbourhood of Baltimore, 242 of 606 segments are one-way, and the floor is 7.26 km for 48 km of streets. Same arithmetic, very different streets.

Five towns, before and after

Here are five towns, each solved by engine 0.1 and then by 0.2.0, with the same configuration and fleet. Every truck carries 8,000 kg of salt, plows at 40 km/h and drives blade-up at 60 km/h, from one depot. Last street is the hour the last street is plowed.

Interactive figure 1: Every plan, before and after: each CARP plan's deadhead ratio on engine 0.1 against 0.2.0

Oberlin is the cleanest case. One truck carries salt for all 92 km, so it never reloads, and the new plan drives exactly its floor: 0.35 km. The 23.31 km it no longer drives empty are the 23 minutes it finishes sooner. At 60 km/h, a kilometre of blade-up is a minute. Bel Air, Maryland; Galena, Illinois; Leadville, Colorado; and River Edge, New Jersey did the same. Of the nine one-truck plans re-solved, every one that needs no reload now drives exactly its floor, to the ten metres the results record.

Woodstock went from a third of all driving blade-up to under 5%. Its two trucks now drive 15.70 km empty, exactly a tenth of the 157.00 they drove before. Its floor is 0.87 km. What is left above it is driving the floor leaves out: trips to the depot for salt, and the second truck's drive out to its share. Woodstock's 323 km of streets take 16,164 kg of salt, more than its two trucks carry between them.

Saratoga Springs finishes 4.02 hours sooner with three trucks. That is more than all of its old blade-up driving took: 184.55 km at 60 km/h is about 3.1 hours. The rest is the other half of the release, below.

Canton gained least. It drove 14.19 km blade-up before and 8.39 km after, against a floor of 7.26 km. Most of what its plows drive empty is the floor: driving that the one-way streets and the depot's location demand. No ordering removes it. A better plan only stops adding to it.

Sharing the tour among trucks

Engine 0.2.0 changed a second thing: how the tour is shared out. The old split cut it into trips the size of one salt load and handed those out, so a fleet could include a truck with almost nothing to do. On Houghton–Hancock, Michigan, one of the two towns the engine is benchmarked on, the old three-truck plan worked its trucks for 4.58, 2.22 and 0.03 hours. The third truck had two minutes of work.

Now each truck takes one stretch of the tour, sized in hours so that the last truck finishes as early as possible, with salt trips inside it as before. Engine 0.2.0's plan works the same three trucks 1.99 hours each, and its blade-up is 13.4 km against the old plan's 64.5.

Saratoga Springs shows what that means for a fleet decision. Before, a third truck finished the town five minutes sooner than two did: 9.24 hours against 9.16. After, it finishes 2.69 hours sooner: 7.83 against 5.14.

The table above mixes the two changes. One-truck plans separate them, because there is nothing to share out: what changed there is the tour alone. Across the nine one-truck plans, blade-up fell by a median 92% and the last street was plowed a median 17% sooner. On fleets the finish time fell further, a median 34%, as the even shares were added to the shorter driving.

Interactive figure 2: What another truck buys: Bel Air, Maryland, the hour of the last street for 1 to 6 trucks, engine 0.1 against 0.2.0

Across the gallery

The 69 CARP plans with a result on record from both engines cover 19 towns and fleets of 1 to 6 trucks. With the same trucks and settings:

• Blade-up fell in every plan, by a median 80.8%: from 34.4% in Canton with six trucks to 98.5% in Oberlin with one. In all, 8,684 km became 1,988 km.
• The median deadhead ratio went from 26.5% to 6.5%.
• The last street was plowed sooner in every plan, by a median 29.6% (11.1% to 65.5%): from 3.54 hours at the median to 2.31.
• The fuel the model charges fell by 21%, from 25,725 to 20,325 litres.
• No plan changed status. A plan that served every street still did. A plan the map left a few streets out of reach still left out the same number.

Two checks on these figures. Eleven of the 19 towns' street maps changed between the two solves, and their street totals differ by up to 1.7%. On the eight towns whose totals match exactly, 31 plans, the result is the same: a median cut of 81.7%, and a deadhead ratio of 24.8% before and 5.4% after. Measured against their floors, those plans went from a median 10.3 times theirs to 1.85 times. The same re-run also re-solved those eight towns' greedy plans, which 0.2.0 did not change. Of those 24, 22 came out with the same blade-up to the ten metres.

The engine page gives a smaller median change for 0.2.0, because it also counts the greedy plans re-solved alongside.

What it cost

Three costs come with the change.

The tour no longer favours main roads. The old tour reached for arterials first. The new one ignores priority tiers. Tier 1 still finished sooner in 59 of the 69 plans, because everything finishes sooner. In 9 it finished later. The worst was Bel Air with one truck, where tier 1 went from 2.22 to 3.24 hours, past its 3-hour window. Woodstock with three trucks went the other way, from 3.22 to 2.77 hours, now inside it. Planning tier windows into the solve is to be a release of its own.

The floor is not the plan. The floor leaves out salt. Woodstock's one-truck plan drives 10.55 km blade-up against a floor of 0.87 km. It goes back to the depot twice to reload, and the floor does not count those trips. That driving is real; the floor cannot see it.

The gallery has moved on since. Each run page shows a plan as the latest engine solved it, and later releases have moved the numbers again, by much less. Each run page also lists its engine history, so the before and after above can be read off the runs themselves.

Old ideas, measured

None of this needed new trucks, a new depot or a faster computer. The streets are the same. The fleets are the same. What changed is that the engine now asks the question in Euler's order: first, what does this network force; then, how to walk it without adding to that.

The floor made the difference visible. Before 0.2.0, PlowPath could say how much a plan drove blade-up, but not how much it had to. Once it could say both, most of the gap turned out to be the plan's, and the oldest result in graph theory closed most of it.

A run in the gallery that a newer engine re-solves keeps the result it replaced. Open a run in Oberlin or Woodstock to see its engine history and its floor.

Open the gallery · Model your town · How the engine works