AZP : l'algorithme qui découpe les territoires depuis 1977

Dans l'article pilier de cette série, nous avons posé le problème : partitionner un territoire en secteurs équilibrés, compacts et continus, alors que le nombre de découpages possibles dépasse tout ce qu'un calculateur peut énumérer. Nous avions annoncé qu'un algorithme s'attaque à ce problème « depuis 1977 » — le voici. L'Automatic Zoning Procedure, AZP pour les intimes, n'est pas une curiosité historique : c'est l'ancêtre direct des moteurs de zonage d'aujourd'hui, et comprendre sa mécanique, c'est comprendre ce que fait réellement un outil de sectorisation quand on clique sur « générer ».

L'histoire commence par une frustration. Dans les années 1970, Stan Openshaw, géographe britannique de l'école dite quantitative, travaille sur un phénomène troublant : les statistiques calculées sur des zones — taux de chômage par quartier, corrélations entre revenus et santé — changent quand on change le découpage des zones, parfois du tout au tout. Mêmes données, mêmes habitants, mais d'autres frontières : d'autres résultats. Ce phénomène porte aujourd'hui un nom, le Modifiable Areal Unit Problem (MAUP), et il est suffisamment vertigineux pour qu'un article de cette série lui soit entièrement consacré.

La réaction d'Openshaw est celle d'un ingénieur plus que d'un théoricien : si les résultats dépendent du zonage, alors le zonage ne doit plus être subi — il doit être construit explicitement, selon des critères choisis et affichés. Encore faut-il savoir fabriquer un découpage sur mesure : tant de zones, équilibrées selon tel critère, aussi compactes que possible. C'est exactement le programme de l'article qu'il publie en 1977, où il décrit une procédure pour engendrer des zonages « à la demande » : l'Automatic Zoning Procedure. Ce qui était au départ un instrument de laboratoire pour étudier le MAUP se révélera être l'outil dont tous les métiers du découpage territorial avaient besoin.

L'intuition centrale d'AZP tient en une phrase : on ne dessine pas un bon découpage, on l'obtient en corrigeant patiemment un mauvais. L'algorithme n'a aucune vision d'ensemble, aucun plan ; il ne fait que des retouches locales — prendre une unité de base à la frontière entre deux secteurs et la faire changer de camp — et il juge chaque retouche à l'aune d'un critère chiffré. Une retouche qui améliore est conservée, une retouche qui dégrade est annulée. Répétée des milliers de fois, cette myopie assumée produit des découpages remarquablement bons. En optimisation, on appelle cela une recherche locale ; voici, pas à pas, à quoi elle ressemble pour un zonage.

1. Partir d'un découpage initial — n'importe lequel

   On attribue chaque unité de base à l'un des k secteurs voulus, en veillant seulement à ce que chaque secteur soit d'un seul tenant. Ce découpage de départ peut être tiré au hasard, hérité de l'organisation existante, ou produit par une croissance de proche en proche autour de k germes. Il est en général médiocre — c'est sans importance : il sert de matière première.

2. Repérer les unités frontalières

   Seules les unités situées à la frontière entre deux secteurs peuvent changer de camp : déplacer une unité au cœur d'un secteur vers un secteur qu'elle ne touche pas créerait une enclave. Le graphe d'adjacence — la carte devenue réseau de voisinages — fournit cette liste de candidates à chaque instant.

3. Tester un transfert

   On simule le passage d'une unité candidate de son secteur « donneur » vers le secteur « receveur » voisin, et on mesure l'effet sur la fonction objectif : l'équilibre des charges s'améliore-t-il ? La compacité ? Le gain des uns compense-t-il la perte des autres ?

4. Valider — ou annuler

   Le transfert n'est entériné que s'il améliore la fonction objectif et que le secteur donneur reste d'un seul tenant après le départ de l'unité. Si l'une des deux conditions échoue, on remet l'unité à sa place et on passe à la candidate suivante.

5. Répéter jusqu'à convergence

   On recommence — nouvelles frontières, nouvelles candidates — jusqu'à ce que plus aucun transfert n'améliore le découpage. L'algorithme s'arrête alors de lui-même : il a atteint un optimum local, un découpage que nulle retouche élémentaire ne peut plus améliorer.

Deux ingrédients de cette boucle méritent qu'on s'y attarde, car c'est là que tout se joue : le juge — la fonction objectif — et le garde-fou — la contrainte de continuité.

La fonction objectif est le juge de paix de l'algorithme : un nombre unique qui résume la qualité du découpage, et que chaque transfert cherche à faire baisser. Chez Openshaw, c'était typiquement l'écart des secteurs à une valeur cible — la traduction directe de l'exigence d'équilibre. Les implémentations modernes y agrègent plusieurs termes : écart de charge, mesure de compacité, éventuellement pénalités spécifiques, chacun affecté d'un poids. Ce détail d'apparence technique est en réalité le volant que l'utilisateur tient en main : donner plus de poids à l'équilibre produit des secteurs justes mais tourmentés, en donner plus à la compacité produit des secteurs ronds mais inégaux. La fonction objectif est l'endroit précis où l'arbitrage entre équilibre, compacité et continuité cesse d'être un discours pour devenir un réglage.

La continuité, elle, n'est pas un terme de la fonction objectif : c'est une contrainte absolue, vérifiée à chaque transfert. Et cette vérification est moins anodine qu'il n'y paraît. Retirer une unité d'un secteur peut le couper en deux — l'unité était un isthme, un pont de terre entre deux moitiés — et détecter ce cas impose de re-parcourir le voisinage du secteur donneur à chaque mouvement envisagé. Nous avons détaillé cette mécanique dans l'article sur la contiguïté et le graphe d'adjacence ; retenons ici sa conséquence : la vérification de continuité est, de loin, le poste de calcul le plus coûteux d'AZP, et c'est elle qui sépare les implémentations soignées des naïves.

Dernière subtilité : l'ordre des mouvements compte. Chaque transfert validé modifie les frontières, donc la liste des candidates du tour suivant : deux exécutions qui examinent les unités dans un ordre différent empruntent des chemins différents et aboutissent à des découpages différents — tous deux « localement optimaux », pas nécessairement de même qualité. C'est pourquoi l'algorithme mélange volontairement l'ordre d'examen, et pourquoi on le relance plusieurs fois : non par acharnement, mais parce que chaque exécution explore une trajectoire distincte dans l'immense paysage des découpages possibles.

AZP ne cherche pas le meilleur découpage possible : il cherche un découpage que plus aucune retouche locale n'améliore. Toute la question est de ne pas s'arrêter au premier venu.

Il faut le dire nettement : AZP est une heuristique. Le mot n'est pas péjoratif — il désigne une méthode qui cherche une très bonne solution sans garantir la meilleure. Pourquoi renoncer à l'optimum ? Parce que le problème exact est hors de portée : le nombre de façons de partager quelques centaines d'unités en une poignée de secteurs continus dépasse le nombre d'atomes de l'univers observable, et aucun raccourci général n'est connu pour en extraire le meilleur sans tout examiner. Un article à venir de cette série, consacré au face-à-face entre sectorisation manuelle et algorithmique, donnera toute sa mesure à cette explosion combinatoire. La conséquence pratique est immédiate : puisqu'on ne peut pas tout explorer, on explore intelligemment — et on accepte de s'arrêter sur « excellent » faute de pouvoir certifier « optimal ».

La faiblesse structurelle de la recherche locale pure, c'est le piège de l'optimum local. Imaginez un randonneur dans le brouillard qui veut atteindre le point le plus bas de la vallée en ne faisant que des pas qui descendent : il finira au fond d'une cuvette — mais rien ne dit que c'est la bonne, et il refusera obstinément de remonter la pente qui le sépare d'une cuvette plus profonde. AZP première manière s'arrête exactement ainsi : sur le premier découpage que nulle retouche isolée n'améliore, même quand un découpage bien meilleur existe à quelques mouvements « défavorables » de distance. Les quarante années suivantes ont surtout consisté à apprendre au randonneur à remonter des pentes.

Dès les années 1990, Openshaw et ses continuateurs greffent sur AZP les grandes métaheuristiques de l'époque — des stratégies génériques pour échapper aux optima locaux. Toutes reposent sur la même idée contre-intuitive : accepter temporairement de dégrader le découpage pour se donner une chance d'atteindre mieux ensuite.

Ces variantes ne sont pas exclusives : les moteurs contemporains combinent volontiers un cœur AZP, une dose de recuit ou de tabou, et des redémarrages multiples orchestrés en parallèle. Le tout reste fidèle au principe de 1977 — des transferts d'unités frontalières, jugés par une fonction objectif, sous contrainte de continuité. La famille a aussi essaimé : d'autres approches du zonage existent (croissance de régions à partir de germes, méthodes exactes sur de petites instances, algorithmes génétiques), mais pour le problème qui nous occupe — des secteurs équilibrés, compacts et continus sur des centaines ou milliers d'unités — la lignée d'AZP demeure le cheval de trait du domaine.

Un demi-siècle plus tard, AZP est partout où l'on découpe. La bibliothèque open source PySAL, référence de l'analyse spatiale en Python, en propose une implémentation fidèle dans son module d'optimisation spatiale spopt — variantes recuit et tabou comprises —, et les outils métier en descendent en droite ligne. Un logiciel de sectorisation comme Sectora appartient à cette famille : son moteur enchaîne les transferts d'unités frontalières sous contrainte de continuité, y ajoute la prise en compte des barrières géographiques et des pondérations de charge, et expose à l'utilisateur précisément les leviers que cet article a décrits — tolérance d'équilibre, poids de la compacité, nombre de secteurs. La référence technique de Sectora détaille ces paramètres un à un, et l'on y reconnaîtra sans peine la fonction objectif et les contraintes de l'algorithme d'Openshaw.

Reste une élégance qu'il faut souligner pour conclure. AZP est né d'un constat dérangeant — le découpage des zones fabrique en partie les résultats qu'on y calcule — et en a tiré la seule réponse honnête : puisque tout découpage est un choix, autant le construire avec des critères explicites, mesurables et discutables. C'est vrai en statistique, et c'est tout aussi vrai pour des tournées de collecte ou des secteurs commerciaux : un découpage généré par un algorithme dont on connaît la fonction objectif se discute, se mesure et s'améliore — un tracé hérité ne se discute pas, il se subit. Pour resituer cet algorithme parmi les autres ingrédients d'une sectorisation — contraintes, charge, unités de base, barrières —, l'article pilier de la série reste le meilleur point d'entrée.