A New Arc-Routing Algorithm Applied to Winter Road Maintenance
This addresses the scheduling problem for winter road maintenance, offering a scalable solution for practical constraints, but it is incremental as it builds on existing heuristics and methods.
The paper tackles the large-scale arc-routing problem for winter road maintenance by developing a new algorithm based on a bin-packing heuristic, which solves networks with thousands of crossroads and segments in minutes, and includes techniques to compute lower bounds using Integer Linear Programming and Lazy Constraints for comparison.
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.