# Outils d'aide à la décision pour la planification des réseaux de distribution de l'énergie électrique

Khalid El Yassini — Rabie Zine — Mustapha Raïssouli

Département Mathématiques et Informatique

Faculté des Sciences

Université Moulay Ismaïl

Meknès

Maroc

{Khalid.ElYassini, Rabie.Zine}@gmail.com et Raissouli_10@hotmail.com

**RÉSUMÉ.** La croissance continue de la demande en énergie électrique présente de plus en plus de défis pour la société. Ce phénomène nécessite de grands efforts pour l'optimisation des décisions à prendre surtout pour la gestion de la distribution de l'énergie électrique qui pose de nombreux problèmes à la société, dus principalement à l'extension du réseau, l'augmentation de la consommation d'énergie électrique et à la gestion en temps réel. Comme le renforcement des réseaux électriques est difficile et coûteux en même temps, il est nécessaire d'opter pour une gestion optimale afin de garantir la satisfaction des clients, réduire les dépenses et augmenter la marge bénéficiaire. Dans ce travail, on proposera quelques différentes méthodes d'optimisation afin de résoudre partiellement ou globalement ce problème et permettre à la société de prendre les choix appropriés.

**ABSTRACT.** The continued growth in demand for electricity is a increasingly challenge for the company. This requires great efforts to optimize decisions to be taken especially for managing the distribution of electricity which poses many problems in society, primarily due to the expansion of the network, increased consumption Power and real-time management. As the strengthening of electrical networks is difficult and expensive at the same time, it is necessary to choose an optimal management to ensure customer satisfaction, reduce costs and increase profit margins. In this work, we propose a few different optimization methods to solve partially or globally this problem, allowing to make appropriate choices.

**MOTS-CLÉS** : réseau de distribution, énergie électrique, heuristique, recherche Tabou, recuit simulé, recherche à voisinage variable.

**KEYWORDS** : distribution network, electricity, heuristics, Tabu search, simulated annealing, variable neighborhood search.
# 1. Introduction

Depuis de nombreuses années, le développement de l'énergie électrique dans le monde a conduit à un vaste système de production, transport et distribution d'énergie électrique. Ce système a été, en très grande partie, conditionné par une contrainte très forte : l'énergie électrique étant très difficilement stockable, elle doit être acheminée en temps réel des centres de production vers les consommateurs finaux, industriels ou domestiques.

Le système d'énergie comprend des sites de production (centrales nucléaires, thermiques, hydrauliques, ou production décentralisée : éoliennes, petite hydraulique, cogénération, ... etc.) et des lieux de consommation (communes, entreprises, ... etc.) reliés par le réseau électrique (transport et distribution). Ce dernier a pour rôle d'acheminer l'énergie vers les lieux de consommation, avec des étapes d'élévation et de baisse du niveau de tension dans des postes de transformation. La tension, à la sortie des grandes centrales, est transformée pour limiter les pertes d'énergie sous forme de chaleur dans les câbles. Ensuite, la tension est progressivement réduite au plus près de la consommation, pour arriver aux différents niveaux de tension auxquels sont raccordés les consommateurs.

Le secteur énergétique connaît une évolution sans précédent. Les clients sont de plus en plus exigeants, la conjoncture économique impose de faire le plus avec le moins, et de nouveaux concurrents apparaissent chaque jour. Suivre ce rythme effréné est, selon les distributeurs, un véritable défi et une immense opportunité. Les distributeurs d'énergie électrique s'efforcent de garantir la qualité de la fourniture d'électricité. Les premiers efforts se sont portés sur la continuité de service afin de rendre toujours disponible l'accès à l'énergie chez l'utilisateur.

D'où le besoin de se pencher sur l'étude du problème de transport et de distribution de l'énergie électrique, afin de présenter des méthodes d'aide à la décision permettant à la société de prendre les choix appropriés répondant à des besoins critiques au niveau de la gestion de tels réseaux.

La planification et ainsi que l'exploitation englobent tous les problèmes de gestion d'un réseau électrique. Notre travail s'inscrit dans cette catégorie. En effet, nous nous limiterons à l'étude des problèmes de la gestion des réseaux de distribution d'énergie électrique. Ce phénomène nécessite de grands efforts pour l'optimisation des décisions à prendre.

# 2. Formulation du problème de distribution d'énergie électrique

Nombreuses sont les formulations du problème de distribution d'énergie électrique dans la littérature. Cependant, toutes ces formulations ont été établies pour des situations particulières que des sociétés ont sollicité ou bien pour la planification ou bien pour l'exploitation de leurs réseaux (voir [1], [2], [5] et [6]). On se propose d'établir une formulation générale du problème qui consiste à modéliser le réseau de distribution électrique par un graphe $G = (V, E)$ où seule une partie des différentes caractéristiques du réseau est prise en considération (les demandes des consommateurs, les capacités des arêtes, ...). Ainsi, le problème consiste à déterminer un arbre maximum de $G$ optimisant une certaine fonction objectif et respectant les contraintes de capacité des arêtes.

Rappelons qu'un réseau de distribution électrique ne peut être exploité que si les arêtes utilisées forment un arbre maximum ([1] et [2]). On peut même établir que si le réseau
dispose de plusieurs sources alors on peut réduire l'ensemble des sources à une seule source. Cependant, il existe des modèles [8] qui transforment ce problème particulier en un problème d'affectation des ressources sans se soucier du nombre de sources. Le problème consiste donc à déterminer s'il existe un arbre maximum pour lequel les contraintes de capacité des arêtes sont respectées. La formulation de ce problème est la suivante :

On se donne un graphe $G(V, E)$, un sommet particulier $S \in V$, une capacité $c_e$ positive pour toute arête $e \in E$ et une demande $d_i$ positive pour tout sommet $i \in V - \{S\}$.

Existe-t-il un arbre maximum $T = (V^T, E^T)$ dans le graphe $G$ tel que pour toute arête $e \in E^T$, la relation $\sum_{i \in V^T_e} d_i \le c_e$ est satisfaite ?

Soit

$$x_e = \begin{cases} 1, & \text{si } e \in E^T; \\ 0, & \text{sinon.} \end{cases}$$

Pour répondre à la question, il suffit de résoudre le modèle mathématique suivant :

$$(P) \left\{ \begin{array}{l} \sum_{e \in E} x_e = |V| - 1 \\ \\ \sum_{e \in E^H} x_e \le |V^H| - 1, \forall H = (V^H, E^H) \subset G \\ \\ \sum_{i \in V^{T_e}} d_i \le c_e, \forall e \in E^T. \end{array} \right\} \Rightarrow T \text{ est un arbre maximum}$$

Le nombre de contraintes permettant de garantir que $T$ est un arbre maximum est équivalent au nombre de sous-ensembles possibles de sommets de $V$. Ce nombre a pour valeur $2^{|V|}$ et nous constatons qu'il croît exponentiellement en fonction du nombre de sommets du réseau. Et par conséquent, un tel système d'inéquations ne peut être exploité pour la résolution du problème $(P)$. Cela montre que l'adjonction de la contrainte d'arbre maximum augmente la complexité du problème $(P)$ par rapport à un problème traditionnel de flots. Dans la section suivante, on montrera que le problème $(P)$ est un problème NP-Complet alors que les problèmes usuels de flots sont polynomiaux.

L'objectif à atteindre consiste à déterminer une configuration arborescente admissible $T = (V^T, E^T) \left( \rightarrow I_e^A = \sum_{i \in V^{T_e}} d_i, \forall e \in E^T \right)$ telle qu'une fonction objectif $f$ soit minimale parmi toutes les configurations admissibles.

En pratique, différents critères permettant de définir la fonction objectif sont susceptibles d'intéresser les entreprises. Parmi ces critères d'optimisation, on peut citer :

* Pertes ohmiques :

Elles entraînent un échauffement des branches du réseau limitant leur capacité de transfert.

$$f(A) = \sum_{e \in E^A} R_e (I_e^A)^2$$

où $R_e$ est la résistance de l'arc $e$, alors que $I_e^A$ est l'intensité de courant électrique circulant dans l'arc $e$.

* Nombre d'opérations :

Ce critère intervient dans le cas où suite à une perturbation de la topologie initiale du réseau (défaillance d'une branche, surcharge de branche,...), on souhaite déterminer
une topologie de secours, dont la réalisation nécessitera un nombre d'opérations pour transformer la configuration initiale $C_i$ en une autre configuration $A$. Dans ce cas, la fonction $f$ vaut :

$$ \sum_k |x_e - x_e^0| $$

où $x_e^0$ est l'état de la branche $e$ dans la configuration initiale $C_i$.

→ *Configuration d'exploitation admissible :*

La détermination d'une configuration d'exploitation admissible peut être réalisée de manière heuristique en minimisant la fonction

$$ f(A) = \sum_{e \in E^A} \left( \frac{I_e^A}{c_e} \right)^k $$

où $c_e$ est la capacité maximale de l'arc $e$.

### 3. Méthodes heuristiques de recherche de configuration optimale d'un réseau de distribution d'énergie électrique par les méthodes de type permutation des branches

Le problème de distribution d'énergie électrique appartient à la classe des problèmes NP-complet (voir [5]). Pour le résoudre, on peut envisager des stratégies de recherche heuristiques s'appuyant sur un principe très simple qui s'énonce comme suit : "Partant d'une configuration initiale, parcourir l'espace des configurations possibles en tentant d'améliorer la configuration en cours d'examen en la substituant par une configuration voisine".

Selon ce principe, la résolution du problème revient, tout simplement, à le décomposer en une succession de sous-problèmes de complexité suffisamment simple de sorte que la solution de chaque sous-problème puisse être déterminée à partir de celle du sous problème précédent. Dès lors, les questions que l'on se pose sont les suivantes :

→ Comment choisir le point de départ du parcours c'est-à-dire la configuration initiale ?

→ Comment définir une configuration voisine ?

→ Comment choisir celle qui conviendra pour la substitution ?

→ À quel moment faudra-t-il interrompre le parcours et déclarer la configuration couvrante comme étant la meilleure configuration possible ?

Les éléments de réponse à ces quatre questions seront, au cours des sections prochaines, illustrés à travers trois exemples de stratégies de parcours, à savoir

* la stratégie "constructive",

* la stratégie "destructive",

* la stratégie de type "permutation de branches".
L'intérêt de l'heuristique provient du fait que pour les problèmes NP-complet, les algorithmes exacts connus possèdent une complexité exponentielle et par conséquent ils présentent un moindre intérêt en pratique.

Généralement, une heuristique est conçue pour un problème particulier, en s'appuyant sur sa structure propre. De plus, les approches utilisées dans les heuristiques peuvent contenir des principes plus généraux. On fait référence à des méta-heuristiques (recherche Tabou, recuit simulé, recherche à voisinage variable) pour les méthodes approximatives générales, pouvant s'appliquer à différents problèmes et en particulier au problème de distribution d'énergie électrique.

## 3.1. Détermination d'une solution admissible

L'existence d'une configuration d'exploitation admissible est le premier obstacle qui se pose lorsqu'il s'agit de diriger la recherche d'une configuration optimale de reprise de service suite à un événement modifiant les données du réseau telle qu'une panne subite. Ce problème se pose également lors de la planification. En effet, lorsqu'une entreprise modifie certains éléments de son réseau, ceux-ci sont généralement inutilisables durant un certain laps de temps. Dans un tel cas, il est nécessaire, de prévoir une configuration de rechange lors de l'exécution des travaux et donc, en premier lieu, de déterminer si une configuration d'exploitation admissible existe.

## 3.2. Stratégie constructive

L'idée, à la base de cette approche, est de construire la configuration recherchée de manière progressive en y insérant, à chaque étape, une et une seule branche judicieusement choisie.

Comme son nom l'indique, à chaque itération de l'algorithme, on connecte au noeud source un seul noeud isolé par la fermeture d'une seule branche (c'est-à-dire on construit une topologie arborecente en partant du graphe du réseau dont toutes les branches sont initialement ouvertes et les noeuds sont ainsi isolés).

<figure><img src="image_1.png" /></figure>

Cette approche consiste donc à considérer un ensemble d'arêtes $E^T$ initialement vide puis à y introduire successivement une arête de $E - E^T$ ne formant aucun cycle avec les arêtes de $E^T$. Le processus s'arrête lorsque la cardinalité de $E^T$ est égale à $|V| - 1$ ou lorsqu'il n'existe plus d'arête pouvant être sélectionnée.

## 3.3. Stratégie destructive

Cette approche consiste à procéder selon une démarche inverse à celle de l'approche constructive. Dans ce cas, on débute le parcours d'itérations par une configuration pour laquelle toutes les branches sont hors service, comme on pourra aussi envisager une stratégie duale où cette fois-ci on partira d'une configuration où toutes les branches sont en service.
En effet, nous considérons initialement un ensemble $E^T$ contenant toutes les arêtes du réseau $E^T = E$. Puis une arête $e$ de $E^T$, pour laquelle le sous graphe $(V, E^T - \{e\})$ est connexe, est supprimée de $E^T$ à chaque itération.

Ce processus s'arrête après $|B|-N+1$ itérations où $|B|$ désigne le nombre de branches et $N$ représente le nombre des noeuds du réseau étudié.

<figure><img src="image_2.png" /></figure>

### 3.4. Principe de la stratégie permutation des branches

Les stratégies discutées jusqu'à présent sont à décisions irrévocables. Aucune d'elles ne peut, dans les meilleurs des cas, proposer qu'une seule configuration arborescente réalisable et par conséquent on ne pourra pas suffisamment apprécier la valeur finale de la fonction objectif du problème posé. Pour faire face à cet inconvénient, on propose d'introduire une nouvelle stratégie qui fera l'objet de cette partie.

L'approche consiste à passer (transiter) itérativement d'une configuration $T$ à une configuration voisine jusqu'un critère d'arrêt soit atteint. On applique à $T$ une modification élémentaire sollicitant deux variables de décision du problème :

- une variable associée à une branche hors service, notée $b_h$

- une variable associée à une branche en service, notée $b_e$

La modification élémentaire consiste simplement à permuter les valeurs de ces deux variables de décision en mettant la branche correspondante à $b_h$ en service et la branche correspondante à $b_e$ hors service. Afin de garantir l'arborescence de la configuration résultante, on choisit tout d'abord la branche correspondante à $b_h$. Par la suite, on choisit la branche correspondante à $b_e$ parmi les branches qui constituent le chemin unique dans la configuration $T$ permettant de relier les deux noeuds extrémités de la branche correspondante à $b_h$.

Contrairement aux stratégies constructives et destructives, au cours de la stratégie de type permutation des branches, chaque variable modifiée pour passer à une étape donnée peut, si nécessaire, être reconsidérée à nouveau pour passer à une étape ultérieure.

Enfin, la stratégie de type permutation des branches conduit à des configurations arborescentes globalement optimales lorsque la fonction objectif du problème est linéaire et que les contraintes d'inégalités sont relaxées. Elle porte, dans ce cas, le nom de "Méthode du simplexe pour réseau".

<figure><img src="image_3.png" /></figure>
### 3.5. Choix d'une configuration initiale

La stratégie de type permutation des branches débute à partir d'une configuration quel-
conque pour autant qu'elle soit arborescente, contrairement aux autres stratégies. Cette
caractéristique n'est en fait pas un avantage étant donné que cette méthode a la particula-
rité d'être instable vis-à-vis de la configuration initiale. En effet, elle ne conduit pas, en
général, à une même configuration finale quelque soit la configuration de départ.

Dans notre cas, on se contentera d'établir la configuration initiale sur la base des consi-
dérations suivantes :

a. S'il on connaît la configuration couramment utilisée par les exploitants, on peut s'en servir comme une configuration initiale pour autant que le problème posé soit relatif au régime de planification normal ou critique du réseau.

b. Si la configuration précédente n'est pas connue, il conviendra alors de générer une configuration arborescente initiale soit de manière aléatoire soit selon une stratégie constructive ou destructive. Dans ce cas, la stratégie de type permutation des branches devrait contribuer à améliorer les résultats que chacune de ces deux stratégies à décision pourra proposer.

### 3.6. Définition du voisinage d'une configuration

Le voisinage $N(T)$ d'une configuration arborescente $T = (V, E^T)$, issue d'un graphe $G = (V, E)$, est l'ensemble de toutes les configurations pouvant être obtenues à partir de la configuration $T$ en introduisant dans $E^T$, une arête $e$ de $E - E^T$, puis en supprimant une arête de l'unique cycle obtenu par l'introduction de l'arête $e$.

D'une manière plus formelle, soit l'arête $e = [u, v] \in E - E^T$ alors le sous-graphe $(V, E^T \cup \{e\})$ contient exactement un cycle $C$ contenant l'arête $e$. Soit $h \in C$, alors le sous-graphe $(V, E^T \cup \{e\} - \{h\})$ est un arbre maximum correspondant à une configuration de $N(T)$ où $T \in N(T)$.

Sur le plan pratique, pour déterminer le voisinage d'une configuration courante d'étape $i$, on prend une branche hors service par rapport à $i$, notée $b_h$. Il existe entre les deux noeuds d'extrémités $u$ et $v$ de la branche $b_h$, un chemin unique à l'étape $i$ noté $L_u \cup L_v$ tel que $L_u$ et $L_v$ désignent les chemins reliant $u$ à $S$ et $v$ à $S$ respectivement. L'union de la branche $b_h$ et du chemin $L_u \cup L_v$ définit un cycle par rapport à la structure du réseau. En permutant l'état topologique de $b_h$ et celui de chacune des branches de $L_u \cup L_v$ prise individuellement, on engendrera autant de configurations voisines de $S$ que des branches appartenant à $L_u \cup L_v$.

**Exemple :** On se donne la configuration courante $T$

<figure><img src="image_4.png" /></figure>
Les voisinages de la configuration $T$ peuvent être résumés comme suit

$$
\begin{array}{llll}
T \cup \{b_{14}\} - \{b_{11}\} & T \cup \{b_6\} - \{b_{16}\} & T \cup \{b_4\} - \{b_1\} & T \cup \{b_9\} - \{b_5\} \\
T \cup \{b_{14}\} - \{b_7\} & T \cup \{b_6\} - \{b_5\} & T \cup \{b_4\} - \{b_8\} & T \cup \{b_9\} - \{b_1\} \\
T \cup \{b_{14}\} - \{b_3\} & T \cup \{b_6\} - \{b_1\} & T \cup \{b_4\} - \{b_{12}\} & T \cup \{b_9\} - \{b_{13}\} \\
T \cup \{b_{14}\} - \{b_{10}\} & T \cup \{b_6\} - \{b_2\} & T \cup \{b_4\} - \{b_{15}\} & T \cup \{b_9\} - \{b_{15}\} \\
T \cup \{b_{14}\} - \{b_{16}\} & & T \cup \{b_4\} - \{b_{11}\} & T \cup \{b_9\} - \{b_{11}\} \\
T \cup \{b_{14}\} - \{b_5\} & & T \cup \{b_4\} - \{b_7\} & T \cup \{b_9\} - \{b_7\} \\
T \cup \{b_{14}\} - \{b_1\} & & T \cup \{b_4\} - \{b_3\} & T \cup \{b_9\} - \{b_3\}
\end{array}
$$

### 3.7. Mise à jour des flots

Soit $T = (V, E^T)$ une configuration de planification issue d'un graphe $G = (V, E)$. Les flots circulant dans les arcs d'une configuration $A = (V, E^A)$ appartenant à $V(T)$ peuvent être aisément déterminés à partir des flots circulant dans les arcs de $E^T$ de la manière suivante :

$$1. \text{ Si } A = T \text{ alors } I_e^A = I_e^T, \forall e \in E^A = E^T$$

$$2. \text{ Si } A \neq T \text{ alors } \exists e = [u, v] \in E - E^T \text{ et } h \in E^T \text{ tq } E^A = E^T \cup \{e\} - \{h\}$$

Soit $C$ l'unique cycle de $(V, E^T \cup \{e\})$ et soit $V^C$ l'ensemble des sommets $s$ tels que $s$ est l'extrémité d'une arête de $C$. Soit $E^C$ l'ensemble des arêtes de $C$. Le sous-graphe $(V^C, E^C \cup \{e\})$ est une sous-arborescence de la configuration $T$ de racine $S$ et formée des chemins $C_u$ allant de $S$ à $u$ et des chemins $C_v$ allant de $S$ à $v$. Les nouveaux flots deviennent

$$\bullet I_e^A = I_e^T, \forall g \notin E^C$$

$$\bullet \text{ Si } h \in C_v \text{ alors}$$

$$I_g^A = I_h^T + I_g^T, \forall g \in C_u$$

$$I_g^A = |I_h^T - I_g^T|, \forall g \in C_v$$

Sinon ($h \in C_u$)

$$I_g^A = |I_h^T - I_g^T|, \forall g \in C_u$$

$$I_g^A = I_h^T + I_g^T, \forall g \in C_v$$

<figure><img src="image_5.png" /></figure>

En effet, si $A = T$, rien n'est à changer puisque la configuration voisine correspond à la configuration actuelle.

Par contre, si $A \neq T$ alors on utilise les variables définies dans la figure ci-dessus.
Supposons que $h = (v_j, v_{j+1})$. Par symétrie, la justification est similaire pour $h = (u_j, u_{j+1})$. Par la suite, on obtient

$$C_u = ([S, u_1], [u_1, u_2], \dots, [u_{p-1}, u_p]) \text{ et } C_v = ([S, v_1], [v_1, v_2], \dots, [v_{q-1}, v_q])$$

Il apparaît que, hormis les arêtes $[v_k, v_{k+1}]$ où $k = j+1, \dots, q-1$, les arêtes communes à $T$ et à $A$ ont les mêmes orientations.

Afin de déterminer les flots circulant dans les arcs de $A$, on utilise le fait que pour tout arc $e$ d'une configuration $T = (V, E^T)$ on a

$$I_e = \sum_{i \in V^{T_e}} d_i$$

→ Comme $V^{T_g} = V^{A_g}, \forall g \notin C$, nous avons $I_g^A = I_g^T, \forall g \notin E^C$.

→ Comme $V^{T_h} = V^{A_e}$, nous avons $I_e^A = I_h^T$.

→ Si $g = [u_k, u_{k+1}] \in C_u$ alors $V^{A_g} = V^{T_g} - V^{T_h}$ et $V^{T_g} \cap V^{A_e} = \emptyset$. On obtient

$$I_g^A = \sum_{i \in V^{A_g}} d_i = \sum_{i \in V^{T_g}} d_i + \sum_{i \in V^{A_e}} d_i = I_g^T + I_h^T$$

→ Si $g = [v_k, v_{k+1}] \in C_v$ où $k < j$, alors $V^{A_g} = V^{T_g} \cup V^{A_h}$ et $V^{T_h} \subset V^{T_g}$. On en déduit que

$$f_g^A = \sum_{i \in V^{T_g}} d_i - \sum_{i \in V^{T_h}} d_i = I_g^T - I_h^T = |I_h^T - I_g^T|$$

→ Si $g = [v_k, v_{k+1}] \in C_v$ où $k > j$ alors $V^{A_g} = V^{T_h} \cup V^{A_g}$ et $V^{T_h} \subset V^{T_g}$. Par conséquent, on trouve

$$I_g^A = \sum_{i \in V^{T_h}} d_i - \sum_{i \in V^{T_g}} d_i = I_h^T - I_g^T = |I_h^T - I_g^T|$$

## 3.8. Détermination d'une configuration voisine à coût minimum

Comme nous l'avons mentionné auparavant, les méthodes à permutations d'arêtes engendrent des visites successives des configurations voisines. Le but est de déterminer une configuration d'exploitation en minimisant un certain critère. La configuration voisine de la configuration courante, sélectionnée pour l'itération suivante, est le plus souvent celle engendrant le plus petit coût. La détermination d'une telle configuration à coût minimum est généralement effectuée en évaluant les coûts de toutes les configurations voisines. Dans le cas où le critère à minimiser est une fonction quadratique, sans terme linéaire et sans terme constant, cette détermination peut être grandement améliorée. Cependant, dans cette section, nous ne considérons que des fonctions dont la forme générale est donnée par

$$f(A) = \sum_{e \in E^A} \alpha_e (I_e^A)^2$$

où $\alpha_e$ est un paramètre positif constant pour chaque arc $e$.

Considérons le sous-ensemble $N(T, e)$ de $N(T)$ contenant toutes les configurations voisines de $T$ obtenues par l'introduction de l'arête $e$ et la suppression d'une arête de
l'unique cycle C créé par l'introduction de l'arête e où $T \in N(T, e)$. Pour toute configuration $A = (V, E^A)$ de $N(T, e)$, nous savons que les flots (voir la section 3.7) circulant dans les arcs de $E^A$ n'appartenant pas à C sont égaux à ceux des arcs de $E^T$ :

$$I_e^A = I_e^T, \forall g \notin E^C$$

Le coût induit par ces arcs est donc identique peu importe la configuration de $N(T, e)$. Cela implique que nous pouvons comparer les coûts des configurations de $N(T, e)$ en ne considérant que les arêtes de C. Soit $f_C(A)$ le coût induit par les arêtes de C pour la configuration A de $N(T, e)$ :

$$f_C(A) = \sum_{e \in C \cap E^A} \alpha_e (I_e^A)^2$$

Comme $E^A = E^T \cup \{e\} - \{h\}$, nous pouvons appliquer les formules de mise à jour indiquées à la section 3.7. Rappelons que pour toute arête $e = [u, v]$, $C_u$ désigne le chemin allant de $S$ à $u$ alors que $C_v$ représente le chemin allant de $S$ à $v$.

Si $h \in C_v$, alors on a

$$ 
\begin{align*}
f_C(A) &= \sum_{g \in C_u} \alpha_g (I_g^A)^2 + \sum_{g \in C_v, g \neq h} \alpha_g (I_g^A)^2 + \alpha_e (I_e^A)^2 \\
&= \sum_{g \in C_u} \alpha_g (I_h^T + I_g^T)^2 + \sum_{g \in C_v, g \neq h} \alpha_g (|I_h^T - I_g^T|)^2 + \alpha_e (I_e^A)^2 \\
&= \sum_{g \in C_u} \alpha_g (I_h^T + I_g^T)^2 + \sum_{g \in C_v} \alpha_g (|I_h^T - I_g^T|)^2 + \alpha_e (I_h^A)^2 \\
&= \sum_{g \in C_u} \alpha_g (I_h^T + I_g^T)^2 + \sum_{g \in C_v} \alpha_g (I_h^T - I_g^T)^2 + \alpha_e (I_h^A)^2.
\end{align*}
$$

Par contre si $h \in C_u$, alors on trouve que

$$ 
\begin{align*}
f_C(A) &= \sum_{g \in C_v} \alpha_g (I_g^A)^2 + \sum_{g \in C_u, g \neq h} \alpha_g (I_g^A)^2 + \alpha_e (I_e^A)^2 \\
&= \sum_{g \in C_v} \alpha_g (I_h^T + I_g^T)^2 + \sum_{g \in C_u, g \neq h} \alpha_g (|I_h^T - I_g^T|)^2 + \alpha_e (I_e^A)^2 \\
&= \sum_{g \in C_v} \alpha_g (I_h^T + I_g^T)^2 + \sum_{g \in C_u} \alpha_g (|I_h^T - I_g^T|)^2 + \alpha_e (I_h^A)^2 \\
&= \sum_{g \in C_v} \alpha_g (I_h^T + I_g^T)^2 + \sum_{g \in C_u} \alpha_g (I_h^T - I_g^T)^2 + \alpha_e (I_h^A)^2.
\end{align*}
$$

## 3.9. Méta-heuristiques de recherche de configuration optimale

Plusieurs types de méthodes heuristiques peuvent être utilisés lors de la recherche de configuration optimale d'un réseau de distribution d'énergie électrique en employant l'approche de type permutation des branches.

### 3.9.1. Méthode descendante

Une stratégie est dite descendante si elle correspond à un processus passant successivement d'une configuration arborescente $T' \subset T$ à une configuration voisine à coût inférieur jusqu'à ce que le voisinage de la configuration courante ne contient plus de configuration à coût inférieur. Ainsi, le processus fournit comme solution le premier op- timum local obtenu.
La procédure générale permettant de réaliser un tel parcours consiste à générer à chaque étape de la stratégie un ensemble $N'(T) \subset N(T)$ de configurations voisines à la configuration courante $T$ puis d'identifier, dans cet ensemble, un sous-ensemble $N^*(T)$ de telle sorte que chaque élément $T'$ lui appartenant vérifie l'inégalité $f(T') < f(T)$. Par la suite, on choisit dans $N^*(T)$, une configuration que l'on substitue à $T$ pour transiter à l'étape suivante. À une étape où l'on peut identifier le sous-ensemble non vide $N^*(T)$, le parcours dans l'ensemble $E'$ est interrompu et la configuration courante $T$ est déclarée comme étant une solution optimale locale du problème posé.

**Méthode descendante à voisinage maximal** : elle consiste à sélectionner la configuration d'exploitation, voisine de la configuration courante, pour laquelle la valeur de la fonction objectif est minimale parmi celles de toutes les configurations voisines.

**Méthode descendante à voisinage dynamique** : elle consiste à sélectionner la première configuration d'exploitation, voisine de la configuration courante, pour laquelle la valeur de la fonction objectif est inférieure à celle de la configuration courante.

### 3.9.2. Méthode utilisant les principes de la méthode Tabou

La méthode Tabou est une méthode qui se retrouve actuellement employée dans plusieurs types de problèmes et dont les performances sont très intéressantes. Son principe est identique à celui de la méthode descendante. Cette dernière étant une primitive de la méthode Tabou en question. En effet, dans le cas de la reconfiguration optimale d'un réseau de distribution selon l'approche "permutation des branches", ces deux méthodes suggèrent de générer à chaque étape un ensemble de configurations arborescentes voisines à la configuration courante $T$, puis de substituer cette dernière par l'une de ses configurations voisines afin de transiter à l'étape suivante. Il en existe de nombreuses modifications, ce qui fait qu'un examen de toutes les variantes possibles applicables à notre problème sera fort long.

À partir d'une configuration courante $T$, la méthode Tabou détermine le voisinage $N(T)$ et choisit comme nouvelle configuration courante :

$$T \in N(T) \text{ tel que } f(T) = \min_{y \in N(T)} f(y)$$

La configuration $T$ est donc l'élément du voisinage pour lequel la fonction objectif est minimale. La méthode recommence le processus continuellement. Elle ne s'arrête que lorsqu'un certain nombre d'itérations ont eu lieu sans amélioration de la meilleure solution trouvée.

À chaque fois que la méthode adopte une nouvelle solution courante, elle insère dans la liste Tabou la permutation inverse de celle qu'elle vient d'effectuer. Lorsque la nouvelle solution courante est choisie, la méthode Tabou rejettera une configuration qui entraînera l'une des permutations interdites. La liste ayant une longueur finie, la méthode "oublie" l'ancienne interdiction, après un certain nombre de permutations.

Il y a une dernière subtilité qui se rattache à la méthode Tabou. On imagine facilement que la liste Tabou peut être parfois un frein à l'optimisation en interdisant une permutation vers une solution intéressante. Afin de contourner ce phénomène, une fonction d'aspiration est ajoutée à la méthode Tabou. Si une solution envisageable est interdite par la liste Tabou, la méthode évalue pour cette solution la fonction d'aspiration, et si celle-ci dépasse un certain seuil, elle fait fi du Tabou et elle choisit malgré tout cette configuration (par exemple, choisir une version classique de la fonction d'aspiration qui accepte une solution interdite par la liste Tabou à condition que son coût soit inférieur à celui de la meilleure solution visitée jusqu'à date).
### 3.9.3. Méthode utilisant les principes du Recuit simulé

Les méthodes heuristiques de type permutation de branches présentées auparavant (stratégie descendante et recherche Tabou) peuvent être qualifiées comme étant déterministes. En effet, pour chacune d'elles, à chaque étape, le couple de branches établissant la configuration de substitution est choisie de façon guidée en opérant une sélection systématique parmi un ensemble de couples bien définis. Dans le cadre de cette section, on se propose d'adapter les principes de la méthode d'optimisation dit *recuit simulé* au cas de la stratégie de type permutation de branches. Il s'agit d'une méthode de nature probabiliste dont les fondements sont empruntés au processus de recuit physique qui autorise le choix d'une solution dont la qualité est inférieure par rapport à la solution courante.

Ce processus utilisé en métallurgie pour améliorer la qualité d'un solide cherche un état d'énergie minimale qui correspond à une structure stable du solide. En partant d'une haute température à laquelle le solide est devenu liquide, la phase de refroidissement conduit la matière liquide à retrouver sa forme solide par diminution progressive de la température. Chaque température est maintenue jusqu'à ce que la matière trouve un équilibre thermodynamique. Quand la température tend vers zéro, seules les transitions d'un état à un état d'énergie plus faible sont possibles. Les origines du recuit simulé remontent aux expériences réalisées par Metropolis et al. dans les années 50 pour simuler l'évolution d'un tel processus de recuit physique.

L'algorithme retourne la meilleure solution $T^*$ rencontrée au cours de la recherche. Il se peut toutefois que cet optimum local ne soit pas le meilleur parmi les solutions visitées, c'est pourquoi nous gardons en mémoire la meilleure solution trouvée jusqu'à date. À la fin de la recherche, la méthode du recuit simulé fournit la meilleure solution visitée.

Le recuit simulé est parfois présenté comme une méthode facile à adapter à un problème et qui ne tente pas d'exploiter des connaissances spécifiques. La performance du recuit simulé dépend largement du schéma de refroidissement utilisé, autrement dit ; de la manière de faire diminuer $t$.

### 3.9.4. Méthode de recherche à voisinage variable

Cette méthode est la plus récente des heuristiques de recherche locale. Son adaptation nécessite uniquement une liste de voisinages et une procédure de recherche locale. Contrairement aux autres méthodes, une heuristique de recherche à voisinage variable utilise méthodiquement plusieurs types de voisinages. Soit $L = N^1, ..., N^{t_{max}}$ une liste finie de voisinages. Dans la plupart des méthodes de recherche locale, on a $t_{max} = 1$. Ces voisinages interviennent de la manière suivante dans le processus de recherche : tout d'abord, étant donné une solution initiale $T$, on génère une solution voisine $T'$ dans $N^1(T)$ et on lui applique une procédure de recherche locale afin d'obtenir une solution $T''$. Si $f(T'') < f(T)$ alors on pose $T = T''$ et on génère une nouvelle solution voisine dans $N^1(T)$. Sinon, la solution courante demeure $T$ et on change de voisinage en générant une solution voisine $T'$ dans $N^2(T)$.

Plus généralement, on change de voisinage à chaque fois que l'un d'entre eux n'est pas parvenu, après application de la procédure de recherche locale à améliorer la solution courante $T$. Par contre, dès qu'un voisinage permet d'améliorer la solution $T$, on recommence le processus avec le premier voisinage de la liste $L$.

Notons que le fait de choisir $T'$ au hasard permettra d'éviter de cycler (ce qui pourrait se produire si des règles déterministes étaient introduites). Cependant, on pourrait tout à fait choisir $T'$ comme étant la meilleure d'un échantillon de solutions de $N^t(T)$. La procédure de recherche locale peut, tout simplement, être une descente ou alors une méthode plus élaborée comme l'algorithme Tabou ou le recuit simulé. On remarque également que
cette recherche à voisinage variable peut être considerée comme une méthode de descente
car la solution courante $T$ n'est remplacée par $T''$ que si cette dernière lui est de qualité
supérieure.

Remarque

Le fait d'utiliser plusieurs voisinages devra permettre de diversifier l'exploration de l'es-
pace des solutions afin d'accéder à un plus grand nombre de régions intéressantes. Cela
devra conduire à une méthode plus robuste que le recuit simulé ou encore la méthode
Tabou.

Pour le voisinage $N^1$, on prend le voisinage décrit dans la section 3.6 et pour le
voisinage $N^k$ on prend des voisinage à "$k$ permutations". Dans ce cas, une configu-
ration $A = (V, E^A)$ est voisine de $T$ s'il existe $2k$ arêtes distinctes telles que $E^A =$
$E^T \cup \{e_1, \dots, e_k\} - \{h_1, \dots, h_k\}$ où $k$ est inférieur ou égal au nombre de branches hors ser-
vice à l'étape *i*. Le choix des $\{e_1, \dots, e_k\}$ sera de même que dans le paragraphe précèdent.

4. Conclusion

Dans ce travail, nous avons proposé une méthode heuristique basée sur l'approche
de permutation des branches et s'appuyant sur les méta-heuristiques usuelles (recherche
Tabou, Recuit simulé et recherche à voisinage variable) permettant d'obtenir de bonnes
solutions en un temps polynomial. Ainsi, nous avons répondu aux problèmes exposés à
la troisième section, à travers les stratégies constructives et destructives comme point de
départ et à travers l'ensemble de toutes les configurations pouvant être obtenues à partir
d'une configuration $T$ en introduisant une branche hors service $e$ puis en supprimant
une arête de l'unique cycle obtenu par l'introduction de la branche $e$ comme voisinage
d'une configuration. Le choix de la configuration de substitution s'effectue à travers la
mise à jour des flots après la permutation des branches et finalement il y a le procédé de
la comparaison entre la configuration utilisée et la configuration de substitution après le
calcul de la fonction objectif pour la configuration de substitution. Et pour clore, il y a la
sélection du moment opportun pour interrompre le parcours et déclarer la configuration
courante comme étant la meilleure configuration possible à partir de méta-heuristiques.

Cette méthode est très importante dans les problèmes de détermination d'une confi-
guration optimale lors de la gestion d'un réseau de distribution d'énergie électrique en
temps réel. En général, elle convient d'autant mieux dans le cadre de la planification des
réseaux électriques.

5. Bibliographie

[1] A. BENCHAKROUN, « Un modèle de Planification des Réseaux de Distribution d'Énergie Élec-
trique », Thèse de Ph. D., Université de Montréal, Canada, 1988.

[2] S.R. CHERKAOUI, « Méthodes heuristiques pour la recherche de configuration optimales d'un réseau électrique de distribution », Thèse de Doctorat, Ecole Polytechnique Fédérale de Lausanne, Suisse, 1992.

[3] N. DUBOIS, « Méthodes d'optimisation combinatoire pour des problèmes de graphes », Thèse de Doctorat, Ecole Polytechnique Fédérale de Lausanne, Suisse, 1994.
[4] K. EL YASSINI, R. ZINE, « La planification et l'exploitation des réseaux de distribution d'énergie électrique », *Proceedings de la 1ère Rencontre des Enseignants Chercheurs de la Province de Nador*, Maroc, 2008.

[5] Y. MEYNARD, « Heuristique pour la Planification des réseaux de distribution d'énergie électrique », *Thèse de Ph. D.*, Université de Montréal, Canada, 1995.

[6] E. KALLEL, « Planification des Réseaux de Distribution d'Énergie Électrique avec demande incertaine », *Thèse de Ph. D.*, Université de Sherbrooke, Canada, 2002.

[7] C.H. PAPADIMITRIOU, K. STEIGLITZ, « Combinatorial optimization : algorithms and complexity », *Englewoods Cliffs, Prentice Hall*, 1982.

[8] C.O. PIEUME, P.B. FOTSO, P. SIARRY, « A multicriteria optimization approach for planning distribution of electrical energy », *Optimization Methods and Software*, Novembre 2007.

[9] ROSEAUX, « Exercices et problèmes résolus de recherche opérationnelle. 1. Graphes : leurs usages, leurs algorithmes », *Dunod, Paris*, 1998.

[10] R. ZINE, « Optimisation des Réseaux de Distribution de l'Energie Electrique », *Mémoire Master, Faculté des Sciences, Université Moulay Ismail, Meknès, Maroc*, 2008.

[11] D.L. WALL, G.L. THOMPSON, J.E.D. NORTHCOTEGREEN, « An Optimization Model for Planning Radial Distribution Networks », *IEEE Transactions on Power Apparatus and Systems PAS-98*, pp. 1061-1067, Mai/Juin 1979.