Multi-Period Service Territory Design

In service districting, a given set of customers has to be assigned to the individual members of the service workforce such that each customer has a unique representative, each service provider faces an equitable workload and travel time, and service districts are compact and contiguous. One important, but rarely addressed feature of many service districting applications is that customers require service with different frequencies. As a result, planners not only have to design the service districts, but also schedule visits to customers within the planning horizon such that the workload for each service provider is the same across all periods and the set of all customers visited in the same time period is as compact as possible. We present a mixed-integer linear programming formulation for the problem. As it turns out, only very small data sets can be solved to optimality within a reasonable amount of time. One of the reasons for that appears to be the high level of symmetry between solutions. We first characterize these symmetries and propose ideas to try to eliminate them in the formulation. Afterwards, we focus on the scheduling component of the problem and present a location-allocation based heuristic for determining visiting schedules for the service providers for fixed districts. In addition, we propose a branch-and-price algorithm to solve larger data sets to proven optimality. One of the novel features of the algorithm is a symmetry-reduced branching scheme that results in a significant speed-up.