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?

Solutions for snow removal problem

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).

Publications of snow removal

In search of good relaxations for the urban snow removal problemLinköping University Electronic Press, 2023. , p. 46

Lagrangian relaxation for the urban snow removal problemLinköping University Electronic Press, 2023. , p. 37

Optimization of Snow Removal in Cities Linköping University Electronic Press, 2023. , p. 36

The Non Zealous Snow Remover ProblemLinköping University Electronic Press, 2022. , p. 7

Urban snow removal: Tree eliminationLinköping University Electronic Press, 2022. , p. 24

Coordination of vehicles in urban snow removal, Linköping University Electronic Press, 2021. , p. 64

A branch-and-dive heuristic for single vehicle snow removal, WILEY , 2020. Vol. 76, p. 509-521

Heuristics for the Rural Postman ProblemComputers & Operations Research 37, (2010) pp 981-990

The (Over)zealous Snow Remover ProblemTransportation Science 53:3 (2019) pp 867-881

Heuristics for the weighted k-rural postman problem with applications to urban snow removalJournal on Vehicle Routing Algorithms,  (2018) 1:105–119

Prepared Test Instances Extracted from OpenStreetMapData Using Different Network Reductions

Urban Snow Removal:: Modeling and Relaxations

Map Matching by Optimization

On Using OpenStreetMap and GPS for Optimization


Research area