Districting for salt spreading operations

The districting problem presented in this paper involves the partitioning of the road network in a region into sub-networks (or districts), to facilitate the organization of the operations to be performed within the region. Typically, each district contains one local center (depot) whose location is given, while the operations involve different types of routing, with routes starting and ending at the depot. For public sector applications like salt spreading and road maintenance, this partitioning is a real distinct stage in the organization and planning of services, and as is the case with location, districting is of a non-operational nature. Relevant characteristics of well-designed districts are: ability to support good routing, balance in workload, compactness of the sub-areas, centrality of the depot, etc. We present a heuristic procedure for our districting problem. First we partition the road network into small cycles, then we aggregate them into districts in two phases. Phase 1 uses an approach based on bin packing principles, while in Phase 2 a multi-criteria approach is used. We illustrate the procedure and discuss its merits for the salt spreading operations in the province of Antwerp.