  This paper studies large scale instances of a fairly general arc-routing
problem as well as incorporate practical constraints in particular coming from
the scheduling problem of the winter road maintenance (e.g. different
priorities for and methods of road maintenance). We develop a new algorithm
based on a bin-packing heuristic which is well-scalable and able to solve road
networks on thousands of crossroads and road segments in few minutes. Since it
is impossible to find an optimal solution for such a large instances to compare
it with a result of our algorithm, we also develop techniques to compute lower
bounds which are based on Integer Linear Programming and Lazy Constraints.
