The recent winter storm left a lot of snow on my driveway. A lot. My driveway is the perfectly place for huge snowdrifts to form. A tweet of my shoveling resulted in the discovery of The Snowblower Problem by Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Valentin Polishchuk (HT @fbahr)
https://twitter.com/lauramclay/status/561990866945179648
The Snowblower Problem (SBP) answers the following question:
How does one optimally use a snowblower to clear a given polygonal region?
The snowblower problem is like the Traveling Salesman Problem (TSP): the objective to find the shortest snow removing tour to remove all the snow from a domain (the polygonal region). The difference between TSP and SBP is that the snow is displaced into a nearby region in the SBP and that if the snow is piled too high, then the snowblower cannot clear the snow. SBP is NP-complete.
There are three model variants considered in the paper differ in how and where you can throw the snow: (1) the default model where snow can be thrown in any direction, (2) the adjustable throw direction (left, right, or center) and (3) left throw only. Changing the snow throw direction is cumbersome, so the fixed direction model variant (the left throw only) has more practical value.
Theorem: The SBP is NP-complete, both in the default model and in the adjustable throw model, for inputs that are polygonal domains with holes.
From The Snowblower Problem by Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Valentin Polishchuk.
The SBP is similar in spirit to various zombie research models: it’s a silly problem context that has real applications. The applications for SBP are in milling and lawn-mowing. And you guessed it: lawn mowing is also NP-complete.
The paper goes on to present various approximation algorithms for SBP. The algorithms used decompose the snowy region into Voronoi cells and then clear the domain cell-by-cell. It is difficult to succinctly summarize the results here without introducing a bunch of mathematical notation so I’ll refer you directly to the paper for mathematical details. The conclusion notes that the approximation ratios are likely not the best possible, so there are opportunities for follow on work.
What is your snow removing algorithm and how close to optimality is it?
Update: this is my favorite comment about this post on twitter. I also shovel my snow the old fashioned way and agree!
Punk Rock Operations Research 
February 9th, 2015 at 5:53 pm
[…] Research shows snowblowing is NP-complete. While that may be true, snow shoveling is aptly described as HP-hard. punkrockor.wordpress.com/2015/02/09/sno… […]
February 9th, 2015 at 8:43 pm
Shoveling is linear (albeit with a pretty big constant)
December 11th, 2016 at 6:50 pm
Problem formulation and framing is (almost) everything. You’re solving the wrong problem. “How does one optimally use a snowblower to clear a given polygonal region?” If the polygonal region doesn’t have any snow, the optimal use of a snowblower to clear the given polygonal region is to not use a snowblower at all. I.e., get a faculty position head in a non-snowy clime. And if you don’t want to do that, just hire a plow to clear it for you. If co-author Joseph S. B. Mitchell had stayed in coastal California, where he went to graduate school, rather than moving to New York, he would never have even needed to solve this problem.
December 4th, 2019 at 11:09 pm
[…] someone to mow our lawn here instead of doing it ourselves. For my friends and family in the north: https://punkrockor.com/2015/02/09/snowblowing-is-np-complete/ Side note: Prof. Radz forgot about me on Monday because he was shoveling snow and caring for his […]