The Mathematics Behind Getting All That #@%&! Snow Off the Streets

It's been a challenging winter for people who think that technology, urbanized living and the broader benefits of civilization should insulate them from the effect of inconveniences like the weather.

As a practical matter, figuring out how to remove tons of stuff while managing straitened municipal budgets, angry commuters and frantic employers.

Needless to say, lots of companies are claiming there's a data-driven software solution for this.

The problem, as the following article explains, is that the interface of myriad variables - many of which encompass seemingly intractable problems like human emotion, cities apparently designed by wandering cows in the mid - 17th century and balky equipment - make the perfect answer more of an aspirational goal than measurable achievement. As many of you have no-doubt discovered all too frequently over the past couple of months. JL

Marcus Woo reports in Wired:

Some big cities use commercially available software which considers all variables and automatically spits out an optimized route. Years back, it was primarily based on people’s experience and knowledge of the areas
This winter has dumped a lot of snow on the east coast. A lot of snow.
Boston, to offer an example, has seen 99.9 inches of the stuff, just eight inches shy of its all-time record with another storm approaching. In what seems like a losing battle to clear it all, cities deploy fleets of plows and salting trucks. Crews in Boston, to continue the example, have so far spent 185,000 man-hours driving trucks a total of 293,000 miles—far enough to go around the world almost 12 times—and dumping 76,000 tons of salt. It has cost $35 million so far.
Keeping things moving takes more than simply sending out a bunch of trucks. Clearing all that snow as quickly and cheaply as possible requires choosing the most efficient routes, one with no back-tracking or scenic routes. And how do you do that?
With math, of course.
To mathematicians, determining the best snowplow route is an iteration of the “Chinese postman problem.” The premise is simple: A postman must deliver mail to every house on every street. But, he wants to be able to travel with as little backtracking as possible. It’s a problem that applies to all sorts of scenarios, from garbage pickup to, yes, snow removal.
Back in the 18th century, Swiss mathematician Leonhard Euler—messing around with bridges connecting islands in Königsberg (now Kaliningrad in Russia)—proved you could indeed find a route that covered every segment exactly once without doubling back. Great! Problem solved, right? Not quite. The catch is his solution required that every intersection consist of an even number of roads. Two-way and four-way intersections were fine. But T-intersections, which connect three streets, and oddballs like the maze around Copley Square were not. Which means that, in any realistic city, some backtracking would be inevitable.
In 1962, Chinese mathematician Mei-Ko Kwan introduced the problem in the general case with both even and odd intersections. He called it the postman problem, and proposed a solution. (Leave it to classy Americans to rename it the Chinese postman problem.) It was American mathematician Jack Edmonds who, in 1973, made the algorithms efficient enough to solve the problem for good.
So how does it work? Roughly speaking, it’s about finding the most efficient routes between intersections with an odd number of streets. As Euler showed, those are the only places that force you to backtrack. So to find the best overall route, you have to identify all the odd intersections and all the possible ways you can travel between them, and then find the most efficient paths. Combining those with the routes covering all the even intersections gives you the most efficient route.
So the mathematicians have it: The perfect way to plow snow. “Even if you give me a layout of 220,000 lines and 300,000 intersections, it’s really doable,” says Peh Ng, a mathematician at the University of Minnesota in Morris. In the 1990s, she applied the algorithm to optimize snowplowing in her own hometown of Morris, and city planners actually tried it.
But as with so many things involving math, the answer is more complicated. The postman solution applies only to a simple scenario—for example, when you have exactly one plow. Most cities have dozens, even hundreds, each of them responsible for specific areas. “Already, there it becomes a less tractable problem,” says David Shmoys, an applied mathematician at Cornell University. Other variables quickly come into play. Highways and expressways have priority over residential streets. Plows deploy from depots throughout the city. Cities want to minimize overtime, or ensure each driver works a similar number of hours. With so many variables, it’s impossible to calculate the perfect answer. “Those are really hard problems, so they tend not to get solved mathematically,” Shmoys says. “That means giving up any sort of proof that you’re getting the best route.”
But you don’t need the perfect solution—just one that gets the job done. So engineers can break the problem down, for example, by dividing a network of streets into smaller networks that they can tackle individually (using the postman algorithm, for example). Some big cities such as Toronto use commercially available software like ArcGIS, which considers all those variables and automatically spits out an optimized route. Since Toronto implemented this system in 2001, the city has seen marked improvement in snow removal. “Years back, it was primarily based on people’s experience and knowledge of the areas,” says Hector Moreno, Toronto’s manager of road operations. In other words, people often planned routes by hand. But now, without the reliance on individual experience, people can transfer to other groups or retire without any loss of knowledge.
The new plan has also saved money. Most of Toronto’s winter road maintenance consists of salting, which requires the same sort of route optimization as snowplowing. The combination of more efficient routes and better equipment has cut costs by 30 percent since 2001, Moreno says. The city now spends $10 million a year (about $8 million US dollars) on salting, dropping 130,000 tons of salt.
So far this season, Toronto has gotten about 28 inches of snow, which is actually below its average of 51 inches. As for Boston, the Mayor’s Office of New Urban Mechanics is supposed to be using tough math, new algorithms, and software to figure out new and better ways to deploy snowplows after storms. And how’s the project going? Tough to say; they weren’t able get back to us. Which is understandable. They’ve got all that snow to deal with.