Employee workload balancing by graph partitioning

We consider the problem of partitioning a region into connected areas assigned to administrative officers. The employee in charge of an area takes care of all the activities which involve the towns of that area. An activity requires the effort of a subset of towns, coordinated by the employee in charge. This implies from the employee a fixed basic workload, plus a variable workload proportional to the number of towns involved. If the subset of towns associated to an activity is divided among several areas, the fixed workload is required from each of the corresponding employees, thus leading to a duplication. The problem requires to minimize duplications while balancing the workload among the employees. The Homogeneous Areas Problem (HAP) models this situation as the search for a suitable balanced partition of a vertex-weighted and subset-weighted undirected graph into connected components. We propose a multi-commodity flow formulation, reduction procedures, a Tabu Search and a Very Large Scale Neighbourhood Search algorithm for the problem. We provide computational results for random instances and for two real-world instances, i. e. the provinces of Milan and Monza.