Cadrons un peu le problème. Il semble raisonnable de former ces régions par agrégation d'unités existantes, de population connue (départements, communes, agglomérations etc.). Dans le numéro 294, d'avril 2002, de Pour la Science, Mourad Baïou et Michel Balinski étudiaient la possibilité de découper algorithmiquement des circonscriptions électorales par assemblage de cantons, et leurs résultats étaient encourageants.

Première remarque : on ne peut pas se contenter d'exiger que les régions soient de population à peu près égale, voire la plus égale possible ; il faut également imposer qu'elles soient connexes (d'un seul morceau, sans enclaves), sans quoi la carte des régions pourrait ressembler à une peinture pointilliste.

Ceci ne suffit pas, car il est possible de concevoir des circonscriptions connexes mais de forme « peu naturelle ». Aux États-Unis, on appelle gerrymandering l'action du pouvoir politique de tracer volontairement de telles circonscriptions, afin de faciliter la réélection du parti au pouvoir ou de limiter la représentation de certaines minorités, en l'honneur d'un gouverneur nommé Gerry qui avait conçu une circonscription en forme de salamandre (la pratique se porte bien dans ce pays, comme on pourra le constater en observant le curieux tracé de la 4e circonscription de l'Illinois pour le Congrès). Rien n'empêcherait, a priori, un algorithme de tracer des circonscriptions aussi biscornues, si celles-ci s'avéraient avantageuses pour l'égalité des populations.

Il faut donc intégrer une sorte de critère de « compacité » (au sens usuel et non au sens de la topologie mathématique), par exemple la distance maximale entre deux points dans la même région, ou la distance au « centre de la région », voire le temps de trajet par la route ; ceci ne ferait après tout que reprendre le critère historique de formation des départements selon lequel il devait être possible de se rendre au chef lieu depuis tout point du département en moins d'une journée de cheval (critère que j'aimerais voir confirmer par un historien ; j'ai également entendu parler d'un critère supplémentaire que l'on devait pouvoir s'y rendre en au plus trois jours à pied).

Comme à chaque fois que l'on a plusieurs critères (ici, l'égalité des populations, et la compacité des régions), il faut s'attendre à devoir les combiner en un seul afin de faciliter la formulation comme un problème d'optimisation, en leur donnant des « poids ».

On peut donc imaginer un algorithme qui, étant donné n communes allouées d'office à n régions, tenterait d'abord d'allouer gloutonnement toutes les communes (ou départements) de la carte en fonction des critères ci-dessus, en conservant à chaque étape la connexité.

Un tel algorithme souffrirait probablement des défauts suivants : dès qu'une zone frontalière serait bloquée ou quasi bloquée par une région, elle finirait forcément par lui appartenir, même si cela devrait déséquilibrer les populations ; de même, une commune enclavée dans une région (par exemple, une grande ville à forte population) devrait finir par lui appartenir. Il faut donc prévoir une deuxième phase de rééquilibrage, où l'on transférerait des communes d'une région à l'autre tant que l'équilibre ne serait pas rétabli.

Bien entendu, un tel algorithme glouton ne convergerait pas forcément vers une solution optimale ; mais qu'importe, en l'espèce, d'atteindre l'optimum ? Il suffirait d'obtenir quelque chose de raisonnablement bon, et de meilleur que ce que l'on obtient par les méthodes manuelles.

On peut envisager des méthodes plus avancées. Mon correspondant mentionnait comme difficulté le nombre astronomique de combinaisons possibles. Rappelons qu'il existe des laboratoires scientifiques (p.ex. le G-SCOP à Grenoble) et des entreprises spécialisées dans la conception d'algorithmes de résolution de problèmes combinatoires, dont l'art consiste justement à éviter d'explorer inutilement un trop grand nombre de combinaisons, et dont la science consiste à prouver que l'on peut s'abstenir de les explorer, ou que telle formulation plus économique en calcul donnera une solution qui ne différera pas plus d'une certaine proportion de l'optimum. De telles approches sont employées quotidiennement dans des industries aussi différentes que la production électrique (planification du fonctionnement des centrales), le découpage des tissus (minimisation des « chutes » par positionnement optimal des pièces à découper), les flottes de véhicules de livraison (minimisation des trajets, de la consommation de carburant, etc.). Je ne suis hélas guère compétent sur ce sujet (je ne vois notamment pas d'expression facile de la propriété de connexité dans le cas d'une formulation par programmation linéaire en nombres entiers) et laisse donc les spécialistes réfléchir.

Bien entendu, on peut compliquer le problème en ajoutant par exemple des critères de stabilité (éviter de trop changer par rapport à l'existant), d'homogénéité par rapport à certains critères socio-économiques, etc. Pour assurer la « compacité » des formes des circonscriptions, certains proposent ainsi le ratio entre l'aire de la circonscription et celle du plus petit polyèdre convexe englobant, ou le quotient isopérimétrique. D'autres proposent un algorithme géométrique simple (donc compréhensible par une bonne proportion des électeurs).

Je serais donc curieux de voir des recherches sur ces méthodes tant pour le découpage des régions que pour celui des circonscriptions électorales en France.

Je ne m'attends cependant pas à ce qu'on envisage sérieusement de les utiliser effectivement, et ce pour plusieurs raisons.

  1. Pouvoir découper les circonscriptions et ajuster les règles électorales est une facilité dont les politiciens n'aimeraient pas se défaire, qu'ils soient dans la majorité (et comptent l'exercer) ou dans l'opposition (et comptent l'exercer une fois qu'ils seront dans la majorité).

  2. Une faible proportion de la population sait ou pense possible l'utilisation de moyens algorithmiques pour résoudre ce type de problèmes. J'ignorais moi-même ce qu'était la recherche opérationnelle jusqu'à ce que je sois au niveau bac+3. Ceci dit, peut-être que pareilles suggestions sembleraient moins surprenantes de nos jours, vu que tout à chacun utilise des services en ligne ou des GPS qui calculent des chemins optimaux selon divers critères (distance, temps...).

  3. Sauf à prendre des méthodes géométriques très simples, il serait cependant très difficile d'expliquer le fonctionnement des algorithmes au français moyen, ainsi que la nécessité de certains « bricolages » (par exemple, les poids pour combiner plusieurs critères en un seul). Le Canard Enchaîné brocarde parfois comme « incompréhensibles » ou réservées aux « crânes d'œufs » des lois ou règlements mentionnant des formules mathématiques de niveau lycée. Un réflexe déjà courant est disqualifier les experts au motif que ceux-ci auraient été à privilégier tel ou tel intérêt (les climatologues serviraient des idéologies collectivistes, les biologistes et médecins seraient forcément inféodés aux laboratoires pharmaceutiques, etc.).

  4. Il y a, notamment en France, une certaine réticence à ce qu'on utilise des méthodes algorithmiques (et, plus généralement, « scientifiques » ou « techniques ») pour résoudre des problèmes réputés « humains ». Ainsi, Google s'est attiré de fortes critiques parce que cette société classe les documents selon des procédés statistiques, sans requérir l'avis d'experts, notamment d'experts des sciences humaines (alors que personne ne s'émeut que l'on planifie algorithmiquement le fonctionnement des centrales électriques, problème pourtant d'importance capitale pour la vie des français).

  5. Les régions ainsi produites ne respecteraient pas les identités historiques et les affinités. On peut cependant relever que les découpages actuels ne les respectent pas non plus (pour prendre deux exemples proches, le nord-Isère est dans l'orbite de Lyon, qui est dans le Rhône, tandis que le sud-Isère gravite autour de Grenoble ; le Vercors est divisé entre Isère et Drôme). Je veux bien que la Bretagne soit une région avec  une identité, mais Rhône-Alpes ?

L'exercice serait cependant intéressant à mener.