Résumé technique : Planification à long terme des réseaux électriques par Programmation par Réponses d'Ensemble

Définition du problème

L'article aborde le problème de la Planification à long terme des réseaux électriques (LPP), une tâche critique pour les Gestionnaires de Réseau de Distribution (GRD). Ce processus consiste à définir une séquence d'interventions physiques (ajouts de lignes, suppressions et opérations de commutation) pour faire évoluer une configuration actuelle du réseau électrique vers une configuration cible souhaitée sur un horizon étendu (généralement jusqu'à 30 ans).

Le défi principal réside dans le fait de garantir que chaque configuration intermédiaire générée au cours de cette évolution reste opérationnellement valide. Contrairement à la planification statique ou à la reconfiguration à court horizon, la LPP doit satisfaire un ensemble complexe d'invariants topologiques et combinatoires à chaque étape de la transition. Ces contraintes incluent :

• Radialité : Le réseau fermé doit être acyclique, chaque sous-station secondaire étant alimentée par exactement une sous-station primaire.
• Reconfigurabilité (Tolérance aux pannes) : Le réseau doit permettre la restauration de la radialité via des opérations de commutation en cas de défaillance d'un nœud primaire quelconque.
• Conformité du degré : Les sous-stations secondaires doivent maintenir un nombre spécifique de connexions (généralement 2 ou 3).
• Irréversibilité et faisabilité : Seules les lignes présentes dans le réseau cible peuvent être ajoutées, et seules les lignes absentes du réseau cible peuvent être supprimées. Ces opérations sont irréversibles.

Les pratiques actuelles reposent fortement sur le savoir-faire manuel des experts et des ajustements itératifs, ce qui limite la reproductibilité, l'évolutivité et l'exploration systématique des trajectoires d'investissement alternatives. Les méthodes existantes comme la Programmation Linéaire en Nombres Entiers Mixtes (MILP) peinent à gérer des propriétés purement combinatoires comme la radialité, tandis que les langages de planification standards trouvent les invariants de graphe difficiles à exprimer.

Méthodologie

Les auteurs proposent la première approche automatisée pour résoudre la LPP en utilisant la Programmation par Réponses d'Ensemble (ASP), un paradigme de programmation logique déclaratif bien adapté aux problèmes combinatoires riches en connaissances.

Formalisation

Le réseau électrique est modélisé comme un graphe non orienté étiqueté par les arêtes $G(V, E, \lambda)$, où les nœuds représentent les stations primaires et secondaires, et les arêtes représentent les lignes étiquetées comme « ouvertes » ou « fermées ». Le problème est défini comme le calcul d'une séquence d'ensembles d'actions $(A_0, \dots, A_n)$ qui transforment un graphe initial $G$ en un graphe cible $G_T$, de telle sorte que chaque état intermédiaire $G_i$ satisfasse les règles des GRD.

Les auteurs définissent trois types d'actions :

1. Ajout d'arête : Ajouter une nouvelle arête au réseau ouvert.
2. Suppression d'arête : Supprimer une arête ouverte existante.
3. Commutation d'arête : Échanger l'état de deux arêtes adjacentes à la même sous-station secondaire (fermer une ligne ouverte et ouvrir une ligne fermée).

Crucialement, le cadre prend en charge la planification parallèle, permettant l'exécution simultanée d'actions non interférentes (celles affectant des ensembles disjoints d'arêtes) au sein d'un seul pas de temps.

Encodage ASP

La solution utilise le solveur CLINGO. L'encodage modélise l'évolution du réseau sur des pas de temps discrets $t$. Les composants clés incluent :

• Représentation de l'état : Des prédicats suivent le statut des arêtes (ouvertes/fermées) à chaque pas de temps.
• Génération d'actions : Des règles de choix génèrent des séquences valides d'ajouts, de suppressions et de commutations, contraintes par les ensembles d'arêtes constructibles et supprimables.
• Application des contraintes :
  • Radialité : Imposée en garantissant que le réseau fermé est une forêt enracinée aux nœuds primaires (pas de cycles entre primaires, toutes les secondaires connectées à exactement une primaire).
  • Reconfigurabilité : Imposée en vérifiant que chaque nœud secondaire possède un chemin redondant vers un nœud primaire différent via le réseau ouvert.
  • Conformité du degré : Des agrégats comptent le degré des nœuds secondaires, imposant des bornes $[2, 3]$.
• Optimisation : Des contraintes faibles sont utilisées pour minimiser le nombre total d'actions et la longueur du plan (de manière lexicographique).

L'approche prend en charge les modes d'exécution séquentiel ($|A_i|=1$) et parallèle ($|A_i| \ge 1$).

Contributions clés

1. Première automatisation basée sur ASP : Ce travail présente la première approche pour automatiser la planification à long terme des réseaux électriques capable de gérer toutes les contraintes topologiques nécessaires du réseau.
2. Modélisation expressive : Les auteurs démontrent que l'ASP peut encoder élégamment des invariants de théorie des graphes complexes (radialité, reconfigurabilité) qui sont difficiles à exprimer dans les langages de planification ou la MILP.
3. Cadre d'exécution parallèle : L'encodage prend en charge l'exécution d'actions parallèles, ce que les auteurs montrent réduire significativement l'espace de recherche effectif et la longueur du plan par rapport aux approches séquentielles.
4. Validation sur des données réelles : L'approche est validée sur des instances synthétiques et des données réelles dérivées du réseau de distribution français, à une échelle comparable aux opérations quotidiennes des experts.

Résultats expérimentaux

Les auteurs ont mené des expériences en utilisant le solveur CLINGO sur une machine Linux 64 bits avec un délai d'attente de 30 minutes par instance.

• Instances synthétiques : L'étude a évalué 175 instances synthétiques allant de 8 à 50 nœuds.

  • Parallèle vs Séquentiel : La planification parallèle a résolu systématiquement plus d'instances que la planification séquentielle. La « compression » de la longueur de la solution via des actions non interférentes a entraîné des programmes logiques plus petits et des temps de résolution plus rapides.
  • Stratégie de recherche : Pour les plans parallèles, une stratégie de recherche exponentielle (élargissant progressivement l'horizon temporel) a surpassé la recherche bornée, résolvant significativement plus d'instances. À l'inverse, pour les plans séquentiels, la recherche bornée était plus efficace.
  • Évolutivité : L'approche a résolu avec succès des instances jusqu'à 50 nœuds, les plus grandes instances réelles (environ 40 nœuds) étant comparables à celles gérées par des experts humains.

• Instances réelles : En utilisant des données anonymisées d'un réseau urbain français (2 nœuds primaires, nœuds secondaires variables), le système a résolu des instances jusqu'à 42 nœuds.

  • Temps d'exécution : Les temps d'exécution étaient comparables à ceux des instances synthétiques de taille similaire.
  • Optimalité : Pour plusieurs instances résolues, le système a prouvé l'optimalité des plans parallèles.
  • Validation : Les solutions ont été validées par un outil automatisé et examinées visuellement par des experts du domaine, qui ont confirmé la cohérence avec les règles de planification des GRD et la comparabilité topologique avec les solutions générées par des experts.

Importance et affirmations

L'article affirme que l'approche basée sur l'ASP proposée offre une alternative viable et automatisée au processus actuellement manuel et piloté par des experts de la planification à long terme des réseaux électriques. En résolvant avec succès des instances d'une taille comparable à celles gérées par des experts humains, la méthode démontre la puissance expressive de l'ASP pour modéliser des contraintes d'infrastructure complexes.

Les auteurs soulignent que leur solution aborde le « goulot d'étranglement majeur » de l'identification de stratégies d'évolution faisables dans un vaste espace combinatoire. Ils positionnent ce travail comme une étape fondamentale vers des outils d'aide à la décision intelligents capables de compléter l'expertise humaine, d'améliorer la reproductibilité et d'explorer systématiquement les trajectoires d'investissement. L'article reste modeste concernant le déploiement industriel immédiat, notant que des travaux futurs sont nécessaires pour améliorer davantage l'évolutivité via des heuristiques spécifiques au domaine et pour s'adapter à des exigences supplémentaires spécifiques à l'infrastructure (par exemple, limites budgétaires, immuabilité des composants).