Construction d’un graphe dynamique

Afin de tenir compte des multiples contraintes des lignes électriques, nous allons transformer les données renvoyées par les capteurs en différents graphes. Chaque graphe est construit selon des critères précis, que ce soit pour les sommets ou les arêtes. En général, les sommets sont communs, ou du moins nommé par le même identifiant pour une entité réelle donnée. La jointure de ces graphes selon des règles logiques construit un schéma final. Notons que ces graphes peuvent être construits par la topologie ou la prétopologie.

Dans le but de définir les coûts de passage de l’énergie dans les lignes ainsi que les restrictions de capacités de ces dernières, nous construisons trois graphes a1, a2 et a3  en tenant compte de différents critères. Les sommets 1 et 9 sont virtuels, et représentent les productions (ou les consommations) des successeurs (ou prédécesseurs). Nous définissons par la suite trois états de charge de la ligne, avec un cout croissant en fonction du flot passant.

 

family

Figure 13 : Famille de graphes déduit des capteurs et des congestions.

Une ligne peut supporter un flot total de [f] énergie,  de coût c1 si elle transporte une quantité d’énergie entre [0, f1], de coût c2 si elle transporte une quantité d’énergie entre [f1,  f2], et de coût c3 si elle transporte une quantité d’énergie entre [f2,  f], avec c1 < c2 < c3. Nous avons donc trois arêtes, trois états de charge, de capacité [f1], [f2 – f1] et [f – f2] et de coût respectif c1, c2 et c3.

La validité d’un état de charge est définie de la façon suivante : l’état 1 est possible si l’arête existe dans le graphe (a1 inter a2 inter a3); l’état 2 est possible si la ligne existe, c’est-à-dire si l’arête existe dans le graphe (a1 union a2 union a3); l’état 3 est possible si l’arête existe dans le graphe (a1 union a2 inter a3). Nous obtenons à partir des trois graphes de la figure 13 le graphe de la figure 14. L’algorithme de routage devra tenir compte de l’ordre de passage dans les arêtes (1 si elle existe, puis 2, puis 3 si elle existe).

 

Sans titre7

Figure 14 : Graphe final représentant les capacités et coûts des lignes du réseau T&D.

Les algorithmes les mieux adaptés à ce type de problème sont les algorithmes de flot à coût minimal, comme par exemple l’algorithme de Busacker et Gowen. Le principe est simple : tant qu’il existe un chemin entre la source et le puit, nous saturons le chemin avec le coût minimum (calculé par l’algorithme de Dijkstra par exemple). Les différentes entités génératrices d’énergie sont reliées à une source fictive ; les différentes entités consommatrices sont reliées à un puits fictif.

Pour des questions de simplicité, l’exemple suivant ne possèdera que des arcs. Pour tenir compte du côté bidirectionnel, il suffit de ne pas déclarer de sens de parcours à l’arête (i.e. ne pas en faire un arc). Lors du passage d’un flot f dans cette arête de capacité g, deux arcs sont créés de coûts égaux et de capacité f dans le sens contraire du flot, et g+f (somme du flot et de la capacité de l’arête prise dans l’autre sens) dans le sens contraire du flot. Ces deux arcs sont remis à jour à chaque itération de l’algorithme de flot à cout minimal comme pour le cas d’un graphe.

 

Publicités