La théorie des graphes

Utilisation de la théorie des graphes dans les réseaux électriques

Plusieurs études en réseau électrique utilisent la théorie des graphes comme concept de base. C’est ainsi que bon nombre d’entre elles ramènent les réseaux électriques de leur étude à des graphes (Rozel, Caire et al. 2009), (Salman, Mohammed et al. 2009), (Chindris, Tomoiaga et al. 2006), (Andrei and Chicco 2008), (Padamati, Schulz et al. 2007), (Bouchard, Salama et al. 1996). À cet effet, on constate que les lignes sont considérées comme les arêtes qui relient les sommets du graphe et ces sommets sont des noeuds du réseau. Dans d’autres cas, les générateurs, lignes, jeux de barres et charges constituent les arêtes et les disjoncteurs sont les sommets (Padamati, Schulz et al. 2007). Quelque soient les considérations effectuées, la matrice d’adjacence obtenue permet de faire la représentation mathématique du réseau électrique (Chindris, Tomoiaga et al. 2006), (Padamati, Schulz et al. 2007), (Bouchard, Salama et al. 1996). Ainsi cette utilisation de la théorie des graphes a permis de faire le calcul des facteurs de contribution des générateurs et d’extraction des charges d’un réseau (Wu, Yixin et al. 2000), la reconfiguration des réseaux en cas de pannes (Padamati, Schulz et al. 2007). Elle a aidé à l’élaboration d’algorithme permettant l’identification de tous les réseaux radiaux possibles d’un réseau (Andrei and Chicco 2008), d’algorithme de test de fiabilité d’un réseau électrique (Majeed, Rashed et al. 2006).

On note toutefois que ramener le réseau à un graphe a de multiples avantages : améliorer la topologie existante du réseau, développer les stratégies futures de développement du réseau en ayant détecté ses points faibles (Chindris, Tomoiaga et al. 2006). Cependant, toutes ces recherches ne s’harmonisent pas au niveau de la codification des données. Les modèles de réseaux auxquels les études font allusion sont limités, car soit ces réseaux sont petits en taille ou ne sont pas assez complexes. Ces différentes études démontrent la nécessité d’un générateur de réseau sous forme de graphes. Très peu d’études portent sur la visualisation des réseaux, c’est pourquoi cette partie présentera 3 articles. En dehors de la représentation habituelle des réseaux que nous donne la littérature, nous présenterons ici 3 approches différentes.

Visualisation du comportement dynamique des réseaux

Il s’agit de 4 techniques de représentation du dynamisme du réseau électrique présentées par Kobayashi (Kobayashi, Okamoto et al. 1997) en 1997. Les 3 premières rendent possibles la visualisation des résultats de la stabilité dynamique et la dernière, les résultats de l’analyse des vecteurs propres. Elles sont toutes basées sur des techniques d’animation qui permettent de voir les oscillations des paramètres importants du réseau en fonction d’autres entre l’instabilité et l’état stable. La première technique (P-) permet de voir la puissance active de chaque noeud en fonction de l’angle de déphasage de la tension (P-). La seconde (Q--V) présente la puissance réactive en fonction du déphasage et de la tension tandis que (V-) présente plutôt la tension en fonction de l’angle de déphasage. Ces techniques de représentation sont adéquates pour le milieu académique et s’appliquent sur des réseaux de petite taille. Mais leur handicap reste le fait qu’on perd les informations géographiques sur la répartition du réseau (connectivité des éléments) et le fait que ces techniques demandent de grandes capacités graphiques pour les machines où elles sont mises en place.

Représentation graphique de la connectivité et l’amplitude de la tension dans un réseau électrique En 1999, cette technique est proposée par José Garcia M. et Al (Garcia Moreno, Vigil- Escalera et al. 1999). C’est aussi une technique graphique qui permet de voir comment les éléments du réseau (lignes, jeux de barre, charge et génération) sont interconnectés et l’amplitude des paramètres du réseau en fonction de leur capacité maximale ou limites imposées. La connectivité et l’amplitude sont présentées par le biais de cercles concentriques et de pipelines (représente les lignes). La variation du cercle interne ou diamètre interne du pipeline caractérise la variation du paramètre de l’élément du réseau représenté par ce cercle ou pipeline. Cette représentation du réseau à l’avantage de donner à l’utilisateur une vue globale du réseau moins encombrant et permet de voir simultanément les fluctuations sur le réseau. Une représentation similaire a été faite par Thomas J. Overbye et Jamie D. Weber (Overbye 2008) en 2000. Dans sa proposition, il utilise les diagrammes circulaires comme dans la figure cidessous pour illustrer le niveau d’occupation des lignes, des générateurs et charges du réseau.

Représentation hiérarchique

La représentation hiérarchique est une représentation du réseau basée sur les graphes orientés et le découpage du réseau en classe hiérarchique. En 2003, elle est présentée par Maricar, N.M. et Shahidehpour, S. M.(Maricar and Shahidehpour 2003). Hiérarchisation du réseau est faite par le biais des noeuds qui sont regroupés en 3 groupes : niveau élevé, niveau intermédiaire et niveau bas. Cette hiérarchisation permet à l’utilisateur de décider quels éléments du réseau il désire voir. D’autre part, le concept de hiérarchie est associé à la modulation de couleur pour indiquer le niveau de tension, de courant et les statuts des lignes et générateurs. Mais avant tout, il s’agit d’un programme graphique orienté-objet, ce qui permet à l’utilisateur d’avoir une grande flexibilité et rapidité dans l’exécution du programme. Cependant, la hiérarchisation du réseau fait perdre la vision sur l’impact géographique de la gestion du réseau même s’il a l’avantage de permettre de travailler avec des réseaux de taille variable. D’autre part, cette technique présente l’avantage de structurer assez efficacement l’ensemble des données du réseau et d’avoir un accès facile à celles-ci.

Perspectives Ces 3 modes de représentation ouvrent la voie à d’autres perspectives, à savoir la création d’un outil de visualisation du réseau électrique qui permet de visualiser le dynamisme des paramètres essentiels du réseau en présentant le réseau sous forme de graphe. D’autre part, toutes ces recherches partent de réseaux électriques existants, un autre axe de recherche consistera à créer un générateur de réseau qui présentera la connectivité des éléments du réseau ainsi que leur initialisation (valeurs) à partir de quelques données de base. Le deuxième et le troisième mode de représentation montrent la possibilité d’illustrer le réseau sous forme de graphe. Ainsi on peut donner une matrice d’adjacence comme l’élément fondamental de ces recherches. Du fait qu’il s’agit de réseau imaginaire, plusieurs questions fondamentales se posent : comment générer une matrice d’adjacences, qui est reproductible ? Quels sont les paramètres à prendre en compte pour la génération et comment se caractérise la distribution des connexions dans une matrice d’adjacence ? Voilà autant de questions auxquelles nous désirons apporter des réponses au cours de notre travail de recherche.

Analyse Cette première phase de lecture permet de voir des éléments qui peuvent aider dans le sens de l’implémentation de ce générateur. On constate que le réseau peut être représenté par une matrice d’adjacences, mais il faut trouver une méthode reconnue qu’on puisse adopter. Nous avons constaté que les études précédentes utilisent les réseaux existants, or nous devons en créer. La tâche la plus complexe consistera à définir la matrice d’adjacence qui génère le graphe. Comme éléments que nous pouvons exploiter : il y a le degré d’un noeud ou du graphe pour définir le nombre de connexions et la forme du graphe. La planarité est un aspect des graphes qu’on peut exploiter pour l’aspect visuel des graphes. Ayant ces quelques éléments, nous comptons examiner la structure des réseaux électriques pour trouver d’autres paramètres que nous comptons utiliser pour la génération de la matrice d’adjacences. Ces paramètres nous guideront dans le choix des règles et conventions que doit remplir notre algorithme de représentation de graphes.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

INTRODUCTION
CHAPITRE 1 REVUE DE LA LITTÉRATURE
1.1 Introduction
1.2 La théorie des graphes
1.2.1 Graphes simples
1.3 Graphes orientés et évalués
1.3.1 Matrice d’adjacence
1.3.2 Graphes évalués
1.3.3 Graphe planaire
1.4 Classification des graphes
1.5 Représentation automatique des graphes
1.5.1 L’objet à représenter
1.5.2 Les conventions de représentation
1.5.3 Les règles de représentation
1.5.4 Les priorités entre les règles et les conventions
1.5.5 Les particularités de l’algorithme de représentation
1.6 Utilisation de la théorie des graphes dans les réseaux électriques
1.7 Visualisation du comportement dynamique des réseaux
1.8 Représentation graphique de la connectivité et l’amplitude de la tension dans un réseau électrique
1.9 Représentation hiérarchique
1.10 Perspectives
1.11 Analyse
CHAPITRE 2 MODÉLISATION DES RÉSEAUX ÉLECTRIQUES
2.1 Introduction
2.2 Sources d’énergie électrique
2.3 Réseau de transport et de distribution
2.4 Modélisation des lignes de transport
2.4.1 Modèle équivalent en quadripôle ABCD
2.4.2 Modèle équivalent en ?
2.4.3 Modèle en quadripôle d’admittance
2.5 Modélisation des transformateurs
2.6 Jeux de barres
CHAPITRE 3 ALGORITHME DE GÉNÉRATION DE GRAPHES ET DE RÉSEAUX ÉLECTRIQUES PLANAIRES
3.1 Introduction
3.2 Graphes planaires
3.3 Stratégie de génération de graphe
3.4 Algorithme de création d’un graphe planaire
3.4.1 Initialisation
3.4.2 Matrice d’adjacences initiale
3.4.3 Calcul des positions initiales
3.4.4 Création de la région initiale
3.4.5 Construction de régions
3.4.6 Choix de région
3.4.7 Choix des 3 noeuds
3.4.8 Calcul des 3 angles formés par les sommets
3.4.9 Création de 3 régions
3.4.9.1 Noeud pivot
3.4.9.2 Division de la région en 2 zones
3.4.9.3 Création de 3 régions
3.4.9.4 Construction des sommets
3.4.9.5 Choix de 2 sommets consécutifs dans une région
3.4.9.6 Détermination des 2 régions d’appartenance de l’arête choisie
3.4.9.7 Création du nouveau noeud
3.4.9.8 Ajout du nouveau sommet dans la région choisie
3.5 Agrandissement ou réduction du graphique
CHAPITRE 4 SIMULATION ET ANALYSE DE RÉSULTATS
4.1 Introduction
4.1.1 Analyse
4.1.2 Diversité
4.1.3 Reproductibilité
4.1.4 Impact visuel et fiabilité des réseaux
4.1.5 Performance de l’algorithme
4.2 Simulations
CONCLUSION