10) The Homogeneous Areas Problem (HAP)

posted Jul 1, 2011, 3:25 AM by Ecmi Milano   [ updated Jul 8, 2011, 1:32 AM ]

Instructor: Marco Trubian

In Italy, provinces play a coordination role: they support all local activities involving more than one town. Examples of such common activities are the management of some parks, the maintenance of some roads, the management of incentives to locally relevant economic sectors, the organization of cultural happenings, and so on. Experts on the technical and legislative issues related to these specific fields work for the different departments of the provincial administrations. For each given activity, the employees of town administrations must refer to these experts and interact with the employees of the other towns involved.
To provide a simple and effective structure from the point of view of the towns, the province administration offers a sort of "help desk", or friendly interface, under the form of a team of employees. This team supports the town employees on any matter of interest, addresses them to the experts in the right departments, keeps track of their needs, organizes meetings, and so on. This is also a way to improve cooperation by means of personal relationships between the employees of the towns and those of the province. In small provinces, a single team is sufficient. When the number of towns and activities grows larger, however, it is no longer possible to guarantee that all employees of the team have the necessary expertise on all the activities involving the province. Larger provinces, therefore, are partitioned into areas so that the team supporting each area can specialize on the corresponding activities. A desirable partitioning should group into the same area towns involved in the same activities and should disperse in different areas those involved in different activities. In short, it should yield "homogeneous" areas. Moreover, each area should correspond to a connected subset of towns, both because this makes it simpler to organize meetings for the town employees of the area and because disconnected areas are considered historically and politically "unacceptable".
The size of the teams cannot be too large, because the members of each team should be interchangeable, and it cannot be too small, to avoid that vacations and illnesses might deprive a whole area of all support. Two to four officers are considered a reasonable size. Since the total workload cannot exceed the available number of work hours, the size of the teams and the total workload imply a small range of reasonable values for the number of teams. Moreover, for equity reasons, the workload should also be distributed fairly among the teams.
The workload for each activity derives from two groups of elementary tasks: the former is devoted to the activity itself (keeping up-to-date with the legislation, organizing meetings, sending standard letters, etc\ldots), the latter is repeated for each town singularly (paying visits, answering questions, etc\ldots). An estimate of the workload can be made taking into account both groups of tasks.
Due to the connection and capacity constraints, as well as the heterogeneous nature of the activities, it might be impossible to keep all towns involved in the same activity in a single area, so that two or more teams might be forced to replicate the first group of elementary tasks. This is a source of redundancy and inefficiency, which should be minimized.
Therefore, the optimization problems is the following: we are looking for a partition of the towns into connected areas with a balanced workload, such that the amount of replicated tasks is as little as possible.
The problem can be fromulated as an integer linear programming (ILP) optimization problem. The spreadsheets with the data of two provinces, of about 50 and 130 towns, are available.

Preferred mathematical background: optimization, integer linear programming.