The Snow Grooming Routing Problem

Abstract

There are more than 30,000 km of cross-country skiing tracks in Norway, and to maintain these track networks municipalities and local ski clubs spend more than 250 million NOK every year. The primary cost driver is the daily grooming operations which are manually planned based on the experience of the snowcat operators. Large networks with many vehicles starting at different depots complicate the problem of finding effective routes. The result is unnecessary high costs due to suboptimal route choices, yielding a benefit of solving the route planning problem.

Employees of the municipal enterprise responsible for the cross-country facilities in Trondheim, Trondheim Bydrift, explain that today’s planning of grooming activities is based on experience and old habits. As Trondheim is an area known for unstable weather conditions, long-term planning lacks robustness. Meetings are therefore conducted every morning to handle the variations. The multifaceted Snow Grooming Routing Problem (SGRP) is an arc routing problem with profits that involves multiple depots, time windows, a heterogeneous fleet of vehicles and track segments having numerous attributes.

We formally define the SGRP and present a mathematical formulation of the problem. The formulation is then tested on a number of different networks taken from Bymarka, the largest cross-country area around Trondheim, Norway.