Umeå universitets logga

Winter road maintenance is associated with significant operational costs and requires efficient planning to ensure accessibility and traffic safety during winter conditions. In many municipalities, including Skellefteå municipality, snow plowing routes are primarily planned and executed based on practical experience, which limits the ability to systematically evaluate alternative routing strategies.

The purpose of this thesis is to develop and evaluate mathematical optimization models for municipal snow plowing route planning. The study investigates how graph-theoretical methods and Arc Routing Problems can be applied to model and optimize snow plowing operations in a municipal road network.

The work combines literature review, processing of geographic road network data, and development of optimization models implemented in Python. The road network is represented as a directed multigraph, where mandatory road segments correspond to required arcs in a Rural Postman Problem formulation. To incorporate turn penalties and operational constraints, the problem is transformed into an Asymmetric Traveling Salesman Problem using a line graph representation. The study includes both heuristic and exact solution methods. 

The heuristic solution method is based on Large Neighborhood Search combined with Simulated Annealing, while the exact model is formulated as a Mixed Integer Linear Programming problem and solved using Gurobi. The models are applied to multiple case study areas in Skellefteå municipality and evaluated through computational experiments and route visualizations. The results indicate that optimization-based planning can generate more structured and efficient snow plowing routes compared with experience-based planning. The study also analyzes how model assumptions, parameter settings, and operational constraints affect solution quality and computational performance.

Finally, the thesis discusses implementation challenges, model limitations, and opportunities for further development of decision-support systems for winter road maintenance.