Arc Routing with Precedence Constraints: An Application to Snow Plowing Operations

Abstract

In this paper we present an arc routing problem with precedence constraints, with a focus on its application to snow plowing operations in Norway. The problem studied considers the clearing of snow from a network of roads, where there exists precedence relations between the driving lanes and the sidewalks. The goal is to minimize the total time it takes for a heterogeneous fleet of vehicles to clear all the snow from the road network. We describe a mathematical model of the problem and present symmetry breaking constraints to improve the computational performance. We present a computational study where the performance of the model is tested. Further, we study the effect of forbidding or penalizing U-turns along the route, something the snow plowing vehicles struggle to do. The computational experiments show that it is possible to generate solutions without U-turns with only a marginal increase in the objective value.