Hybrid Heuristics for the Territory Alignment Problem

Hybrid Heuristics for the Territory Alignment Problem

Jorge Freire de Sousa (Universidade do Porto, Portugal), José A. Barros-Basto (Universidade do Porto, Portugal) and Paulo Lima Júnior (Universidade do Vale do São Francisco, Brazil)
DOI: 10.4018/978-1-61350-086-6.ch012
OnDemand PDF Download:


This chapter also illustrates the potential of the proposed approach as a practical and readily implementable management decision aid in the context of a current case that involved the maintenance team of a Portuguese regional office of a worldwide equipment company.
Chapter Preview

1 Introduction

The territory alignment problem (TAP) is part of a bigger procedure, the territory design, which consists of assigning small geographical regions to larger areas following the most relevant criteria for planning.

The territory design problem, that also has been referred to in the literature as the territory project, the automatic zoning design, the land allocation, the (re)districting, the region partitioning and the geographic deployment, is an important problem that is present in a great number of geographic projects and has potential application in various subjects, for instance, the establishment of political districts, location of schools, trash collection, social services (health centers, hospitals, etc.), emergency services, sales and distribution of products and maintenance teams. A quite interesting evaluation of the several areas of application of the territory design can be found in (Kalcsics, Nickel, & Schroder, 2005).

There are many ways of assigning small geographic regions to larger areas or, in other words, of defining a zoning system. The criteria for defining a meaningful zoning system lie in the purpose of the studies and depend on the experience of the zone designer. The zoning criteria are often guided by the problem specifications or restricted by the available data. Depending on the problem context, a careful partition of a territory may represent an increase of efficiency of an activity, a better workload balance or a shorter distance covered.

In the problem of electoral districting, probably the most well known case of the TAP, aside from its obviously political aspect, the process must be evaluated against specified redistricting criteria. For instance, some of the criteria are constitutionally required while other geographical and political concerns may be advocated. Electoral districting consists of the partitioning of administrative units into a predetermined number of zones (districts) such that the units in each zone are contiguous, each zone is geographically compact and the sum of the populations of the units in any district are as similar as possible or lies within a predetermined range.

According to (Bacao, Lobo, & Painho, 2005a), the constraints of the zone design problem are similar to the ones that characterize the clustering problem. Let the set of initial areal units be X = {x1,x2…,xn}, where xi is the i-th areal unit. Let the number of zones be K. Let Zi be the set of all the areal units that belong to zone Zi. Then:

for i = 1,…,K, for ij,

These constitute the set of constraints that can be applied equally in clustering and in zone design. Nevertheless, in zone design an additional constraint has to be included, which accounts for contiguity and creates a more complex problem. This constraint limits the set of acceptable solutions to the problem and consists in assuring contiguity between all the areal units that build up a zone. Contiguity is defined as a continuous connection of a series of entities, a grouping of parts connected throughout an unbroken sequence and sharing a common border. In other words, it means that each areal unit in a zone is connected to every other areal unit via areal units that are also in the zone (Cloonan, 1972; Niemi et al., 1990; Shirabe, 2005a; Shirabe, 2005b).

Complete Chapter List

Search this Book: