Optimal Routing of Snowplows-A Column Generation Approach

In countries with heavy winters, winter road maintenance, i.e. snow removal, salting etc, is an important problem. In Sweden the government and municipalities together spend close to 0.3 GEUR every year for winter road maintenance. Approximately half of this is snow removal cost, which mainly is the cost for snowplows, which in turn mainly depends on the routing of the snowplows. In this paper we study optimal routing of snowplows after snowfall. One has then to design a set of routes starting and ending at given depots, such that each road segment gets plowed within a prescribed time window, depending on the class of road segment. Our solution approach is based on Dantzig-Wolfe decomposition with column generation. In order to obtain an integer solution to the master problem we have applied two heuristic procedures, one using branch-and-bound on a subset of the columns and the other one a greedy procedure.