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