Optimization of Snow Removal in Cities 

Snow removal and similar activities, such as sanding, salting, etcetera, are important for society to function well even in winter, but give challenging optimization problems. In which order should the streets be cleared? Which vehicle should take care of which street How should the vehicles drive? At which time can one expect a certain street to be cleared?

A difficult problem to solve - in an optimal way 

There are many complicating details. For example, there are different types of roads that can be cleared by various types of vehicles. Bicycle and pedestrian paths cannot be cleared by larger vehicles, especially if there are tunnels, but require smaller, specialized vehicles. In addition, there are bus stops, intersections, turning spaces, etcetera, that require additional work.

It is even challenging to formulate the optimization problem as a mathematical model. There are similar models in the literature about vehicle routing, and some of them even include time. However, usually they do not allow a vehicle to return to a place several times, which is necessary when removing snow.

Gatunät i LinköpingStreet network in Linköping. Picture: Kaj Holmberg. Data from OpenStreetMap.

The entire problem is very complicated and cannot be solved by existing state-of-the-art solvers within a reasonable time. One possible approach is to divide the optimization into levels, so that you first decide which area each vehicle will clear, and then determine how the vehicles should drive. These decisions affect each other, so when you know the routes for each vehicle you may need to revise the street allocation.

GPS data can help

The possibility to obtain input to the model has drastically improved. Digital maps (such as OpenStreetMap) are available online. Vehicles are equipped with GPS devices, so afterwards the rides can be analyzed and better estimations can be made of how long each task takes. Previously, much information had to be entered manually, which has prevented the use of optimization in many cases.

Ongoing research

These problems, including applications to other service jobs in urban networks, is subject to ongoing research at the Division of Applied Mathematics (TIMA).



Research area