Partitionnement d'une zone géographique en territoires homogènes et contigus

Le problème de régionalisation ou de "districting" consiste à diviser une zone géographique en un nombre prédéfini de sous-zones contigües tout en minimisant un critère de partitionnement fonction de données non géographiques. Le problème de régionalisation peut être vu comme un processus de regroupement d'unités élémentaires, les unités géographiques (UG), en groupes appelés territoires qui, une fois assemblés, reconstituent la carte ou la configuration donnée. Ce problème a surtout été étudié dans le cadre du découpage électoral. Le problème qui nous intéresse consiste à grouper les UG selon une valeur associée à chacune d'elle en des territoires homogènes respectant un poids minimum. Pour cela nous utilisons comme critère d'agrégation la variance intra-territoire qui est la somme pondérée de la variance de chaque territoire en solution. La variance d'un territoire est la variance de la valeur associée à chaque UG lui appartenant, et la pondération d'un territoire dans l'objectif est la somme des poids de chaque UG qui lui est associé. Ce problème est difficile à résoudre et une technique d'énumération de tous les territoires n'est donc pas envisageable pour de grandes instances. La difficulté par rapport à quelques travaux déjà réalisés est la présence simultanée d'une fonction objectif quadratique et d'une contrainte de contiguïté, ainsi que la taille des instances (500 UG). Ce travail présente une méthode heuristique de génération de colonnes couplée avec une méthode de branchement pour résoudre un tel problème de partitionnement avec contrainte de contiguïté. Dans la méthode de génération de colonnes, le sous-problème génère de nouveaux territoires et il est résolu par un algorithme heuristique de type glouton avec plusieurs points de départ. La méthode de branchement est aussi heuristique car les décisions prises sont fixées de façon permanente, i.e., aucun retour en arrière n'est permis dans l'arbre de branchement. A notre connaissance une telle méthode de résolution avec des instances de l'ordre de 500 UG n'a pas encore été appliquée. Cette méthode a été développée dans un contexte industriel et permet d'obtenir des solutions réalisables de bonne qualité sur les instances testées dans des temps relativement courts (15 min. à 40 min.). Abstract: The regionalization or districting problem consists of dividing a geographical area into a predefined number of contiguous territories, while optimizing a clustering criterion. The regionalization problem can be seen as a process of aggregating elementary geographical units (GU) into clusters called territories, that combined, cover the entire map or given configuration. The most studied variant of this problem is the electoral districting problem. The variant of the regionalization problem studied here, referred to as the PPHCT, consists of aggregating the GU according to their value into homogeneous and contiguous territories, satisfying a minimum weight constraint. For this matter, an aggregation criterion, namely the within-territory variance, is used, which is the weighted sum of the variance of each territory in the solution. The variance of a territory is the variance of the value assigned to each GU in that territory, and the weight of a territory is the sum of the weights of each GU in that territory.

Abstract

The PPHCT is difficult to solve optimally and an enumeration of all the feasible territories cannot be applied for large instances. The main difficulty of this variant, in comparison to other variants previously studied, is the simultaneous presence of a contiguity constraint and a quadratic objective function, together with large instances (500 GU). The purpose of this paper is to present a heuristic column-generation model and branch-and-bound algorithm designed to solve the PPHCT. In the column-generation method, the sub-problem generates new feasible territories and is solved by a greedy multi-start algorithm. The branching method is also heuristic, as branching decisions are taken permanently, that is, no back -tracking is possible in the branching tree. This solution method was developed in an industrial context and is able to produce good quality feasible solutions on the tested data, in relatively short computing times (15 min. to 40 min.).