Routeing winter gritting vehicles

When roads may become dangerously slippery due to forst, ice or snow, local authorities treat the roads by spreading a de-icing agent (usually salt) on them. In order to treat a road, a winter gritting vehicle must travel down the road once, spreading salt on to both sides of the carriageway. An application is described where routes were constructed for gritters in a local authority area. The formulation of the model is presented which involves dealing with multiple depot locations, limited vehicle capacities, and roads with different priorities (for example, some must be treated within two hours and others within four hours of the start of gritting). The objective function to be optimised depends on both the total distance travelled, and the number and capacity of the gritters. The solution method is a heuristic algorithm, which involves, as a first stage, the optimal solution of an unconstrained Chinese Postman Problem for the network, and followed by the use of Simulated Annealing for the constrained problem.