Réseaux de PETRI Temporels Stochastiques

Avant toute chose, il est nécessaire d’introduire quelques notions qui se rapportent au domaine du ferroviaire ainsi que quelques précisions.

Dans le contexte de ce travail, quand on parle de systèmes ferroviaires, il s’agit princi-palement de réseaux de métro. On considère que ceux-ci comportent un ensemble de trains et de tronçons ferroviaires (que l’on appellera sections) qui constituent les voies des trains. On s’intéresse d’une manière particulière aux événements d’arrivée et de départ des trains, à leurs dates prévues et à leurs dates d’occurrence effective.

On parlera de planning pour désigner l’ensemble de toutes les dates de départ et d’arrivée des trains prévues pour une journée d’exploitation. On utilisera le terme table horaire pour désigner le modèle théorique qui regroupe le planning, l’ordon-nancement des trains, leurs chemins, etc. Cette table horaire est calculée de sorte à satisfaire un ensemble de contraintes qui sont définies en fonction des exigences physiques du système, i.e., les vitesses commerciales maximales des trains, le temps de séjour minimum d’un train en station (temps de chargement et de déchargement des passagers), les distances de sécurité entre les trains, etc.

Il existe deux types d’intervalles de sécurité à respecter impérativement : une distance en terme de sections et une distance temporelle (un intervalle de temps) entre chaque deux trains qui se suivent. La contrainte physique dicte qu’il ne faut jamais qu’un train rentre dans une section si celle-ci n’est pas libre 1 ; la contrainte temporelle dicte, quant à elle, qu’il faut absolument qu’un certain temps minimal s’écoule après l’entrée d’un train dans une section pour qu’un autre train puisse y entrer. Cette contrainte est appelée headway minimal ; le headway étant l’intervalle de temps entre l’entrée de la tête du train dans une section et la sortie de sa queue de la section d’avant, plus une marge additionnelle de sécurité par rapport au train qui le suit. En d’autres mots, c’est la distance entre l’extrémité d’un train et celle du train qui le suit, exprimée en fonction du temps que va prendre le second train à la couvrir.

Au cours de ce travail, une approche modulaire est adoptée dans le choix de modélisa-tion des systèmes ferroviaires. Les composantes du modèle dérivent principalement des modèles théoriques de réseaux de PETRI et de graphes d’alternatives qui sont détaillés dans la section suivante. Les choix de modélisation sont justifiés tout au long de cette partie du document.

Les systèmes ferroviaires peuvent être vus comme de grands systèmes à événements discrets (SED) où les événements sont, entre autres, les départs et les arrivées effectifs des trains, les ordres de départ donnés par le système de régulation automatique ou encore l’occurrence d’incidents.

Les réseaux de PETRI (RdP) ont longtemps été un très bon moyen de modélisation des SED grâce à leur puissance d’expression, leur forme graphique intuitive, leurs bases théoriques, mais aussi parce qu’ils permettent de modéliser les phénomènes de synchronisation et de parallélisme d’une manière aisée et très explicite.

Dans le milieu ferroviaire, plusieurs variantes des RdP on été utilisées comme moyen de modélisation. On cite : les RdP classiques dans [5], les RdP colorés dans [8] ou encore les graphes d’événements temporisés (une sous classe de RdP) dans [7].

La section suivante est consacrée à une présentation brève de la syntaxe et de la sémantique des réseaux de PETRI.

Les réseaux de PETRI ont vu le jour avec la thèse de doctorat de C. A. PETRI en 1962 [13] et se sont développés, au fil du temps, grâce aux travaux de plusieurs chercheurs. Un réseau de PETRI est un 6-uplet hP,T, A¡, A¯,L, M0i où :

– P est un ensemble non vide de places. Chaque place est représentée par un cercle et porte habituellement une étiquette qui décrit la condition qu’elle modélise.

On définit le marquage d’un RdP comme étant la fonction M : P ! N qui as-socie à chaque place un entier positif représentant le nombre de jetons (ou de marques) dans la place. Un jeton est représenté par un point (ou un disque) à l’intérieur d’une place.

– T est un ensemble non vide de transitions tel que P [T ˘ ?. Chaque transition est représentée par une barre horizontale ou verticale et porte une étiquette qui décrit l’événement qu’elle modélise.

– A¡ µ P £T et A¯ µ T £P sont des ensembles d’arcs de flux. Un arc de flux est représenté par une flèche qui part d’une place vers une transition, si l’arc est un élément de A¡. Si c’est un élément de A¯, il est représenté par une flèche qui part d’une transition vers une place.

On désigne par †t (resp. t†) l’ensemble de toutes les places en amont (resp. en aval) d’une transition t. †t (resp. t†) est dit l’ensemble de préconditions (resp. postconditions) de la transition t.

– L : A¡ [ A¯ ! N¨0 est une fonction de flux qui associe à chaque arc un entier naturel non nul fini. Cette valeur représente le nombre de jetons consommés ou produits par le tir d’une transition. Dans la représentation graphique des RdP, ces valeurs sont représentées sur les arcs. D’une manière exceptionnelle, une valeur n’est pas représentée lorsqu’elle est égale à 1.

– M0 est le marquage initial. Il représente le nombre de jetons dans chaque place à l’état initial du RdP.

Un état du RdP est décrit par un marquage M. Le passage d’un état du RdP vers un autre se fait par le biais du tir (ou franchissement) d’une transition. Ceci reflète l’occurrence de l’événement qu’elle modélise. Pour qu’une transition t puisse tirer, il faut que chaque place p 2 †t contienne au moins L(p, t) jetons ; quand c’est le cas, on dit qu’une transition est activée. Lorsqu’une transition t est tirée, des jetons sont consommés et/ou crées suivant A¡, A¯ et L : L(p, t) jetons sont consommés de chaque place dans †t et L(t, p) jetons sont créés dans chaque place dans t†. Le nouvel état est donc décrit par le marquage M0 tel que : 8 p 2 P, M0 (p) ˘ 8 M(p) ¡L(p, t) si p 2 †t.

Au fil du temps, un grand nombre d’extensions des RdP a été proposé pour pallier aux limitations en matière d’expressivité des RdP classiques. Parmi celles-ci, on cite :

– Les RdP à arcs inhibiteurs qui dérivent des RdP contextuels présentés dans [12] : c’est des RdP dotés d’un ensemble d’arcs A– µ P £T , dits inhibiteurs.

On note par –t l’ensemble des places inhibitrices d’une transition t. Il comporte les places liées à la transition t par un arc inhibiteur, i.e., –t ˘ {p 2 P j 9(p, t) 2 A–}.

Une transition ne peut être activée si, au moins, l’une de ses places inhibitrices p 2 –t contient au moins un jeton. (Des définitions plus générales existent mais on se contentera de celle-ci.)

Les arcs inhibiteurs servent à modéliser le fait qu’un événement ne puisse se réaliser que si une condition n’est pas satisfaite. Dans le contexte du ferroviaire, cela pourrait servir pour représenter le fait qu’un train ne puisse rentrer dans un tronçon ferroviaire que si celui-ci n’est pas déjà occupé.

– Les RdP temporisés et temporels : cette branche des RdP introduit explicitement la notion du temps. Le passage d’un état du RdP vers un autre se fait en respect de certaines contraintes temporelles. Ces contraintes peuvent être attachées aux places, aux transitions ou aux arcs comme dans les modèles présentés respectivement dans [9], [2] et [4].

Les modèles temporels les plus utilisés sont ceux des RdP T-temporels (abrégé en RdPT) [11]. Ce sont les modèles où les temporisations sont représentées sur les transitions. Un RdPT est un RdP muni d’une fonction Is : T ! I(Q‚0) qui associe à chaque transition un intervalle de tir. Si l’on note fi(t) et fl(t) les bornes inférieure et supérieure de l’intervalle Is (t) associé à la transition t, celle-ci doit rester activée pendant au moins fi(t) et au plus fl(t) unités de temps avant de pouvoir être tirée.

– Les RdP stochastiques (RdPS) : cette branche des RdP introduit l’indéterminisme. Un RdPS est un RdP classique muni d’une fonction ⁄ : T ! Q‚0 qui associe à chaque transition un taux. Le temps de tir de chaque transition suit une loi exponentielle. Si l’on note ‡i la variable aléatoire définissant le temps de tir de la transition ti , alors ‡i est de fonction de répartition F‡i (x) ˘ 1 ¡e¡⁄(ti ).x .

Dans un RdPS, au moment où une transition ti est activée, son temps de tir est échantillonné aléatoirement à partir de la fonction de répartition F‡i . Il est ensuite décrémenté avec le passage du temps jusqu’à ce qu’il atteigne 0. À  ce moment-là, la transition peut être tirée. Lorsque plusieurs transitions ont un temps de tir nul au même instant, la transition t à être tirée en premier est choisie avec une probabilité égale à ⁄(t) Pti 2act(M) ⁄(ti ) où act(M) est l’ensemble des transitions activées par le marquage M.

Une extension des RdPS sont les réseaux de PETRI stochastiques généralisés (RdPSG) [10]. Dans cette variante, l’ensemble des transitions est composé de transitions à temps de tir aléatoire et de transitions discrètes qui tirent dès qu’elles sont activées. Quand plusieurs transitions discrètes sont tirables en même temps, le choix de la transition à tirer se fait avec une probabilité dépen-dant des poids de ces transitions ; chaque transition ayant un poids prédéfini.

– Les RdP temporels stochastiques (RdPTS) : ce modèle, proposé par A. Horváth et al. [6], est une extension qui nous intéresse particulièrement. Elle introduit les fonctions T : T ! Q‚0 et T : T ! Q‚0 [{¯1} qui, respectivement, associent à chaque transition un temps de tir au plus tôt et un temps de tir au plus tard ; ainsi qu’une fonction F : T ! §F qui associe à chaque transition t une fonction de répartition F(t) notée Ft et définie sur l’intervalle [T (t),T (t)].

Lorsqu’une transition t est activée, un temps de tir est échantillonné à partir de la fonction de répartition Ft y étant attachée. Cette valeur est décrémentée au fil du temps et, quand elle atteint 0, la transition peut être tirée. De la même manière que dans les RdPSG, à chaque transition est associé un poids qui sert à déterminer quelle transition tirer en premier lorsque plusieurs transitions peuvent tirer au même instant.

Cette variante est particulièrement intéressante car elle permet non seulement de modéliser les contraintes minimales et maximales des opérations :

– contrainte sur la vitesse : un train ne peut faire moins de x unités de temps pour parcourir un tronçon ferroviaire ;

– contrainte sur le temps de séjour : un train ne peut rester en station plus de x unités de temps ;

– contrainte sur l’intervalle de passage de deux trains par le même point.

mais aussi de modéliser finement l’imprécision sur l’occurrence des événements de départ et d’arrivée des trains grâce aux fonctions de répartition.

Au cours de ce travail, une version légèrement modifiée de ce modèle de RdP est reprise ; elle est présentée dans une partie ultérieure du document.

D’une manière plus générale, la modélisation par réseaux de PETRI reprend fidèle-ment la topologie du système réel. Intuitivement, il est très facile de faire l’analogie entre le système réel et le RdP. En effet, les places et les arcs forment un graphe qui est quasiment isomorphe au réseau ferroviaire modélisé. C’est un autre point qui a influencé le choix de prendre un modèle à base de RdP. Un inconvénient réside, toutefois, dans le fait qu’il n’est pas possible (ou très compliqué) de prendre en compte des politiques de régulation différentes qui régissent le comportement du système. De plus, dans les modèles de type RdPTS, il n’est pas possible de recalculer un temps de tir d’une transition une fois celui-ci défini. Ceci rend la reprogrammation du RdP, a priori, impossible en cas d’occurrence d’un événement à une date tardive qui impose un recalcul d’un nouveau planning pour les trains. Pour ces raisons, on a décidé de définir une partie distincte du modèle qui modélise la table horaire et sur laquelle il est possible d’appliquer une politique de régulation donnée afin de commander le système. Intuitivement, le système non régulé est modélisé au moyen d’un RdPTS et la table horaire modélise le planning des dates de départ et d’arrivée des trains de/aux stations.

On présente, dans la section suivante, le modèle des graphes d’alternatives pour les systèmes ferroviaires proposé par A. D’Ariano et al. dans [3]. Le modèle des tables horaires dérive directement de ce dernier.

Les graphes d’alternatives sont un moyen utilisé pour résoudre les problèmes d’ordon-nancement d’atelier à acheminements multiples (job shop scheduling). A D’Ariano et al. utilisent les graphes d’alternatives pour modéliser et résoudre les problèmes d’ordonnancement des trains qui pourraient survenir suite à des incidents qui causent des retards sur les arrivées des trains (typiquement deux trains qui arrivent dans un même intervalle de temps à un point d’embranchement).

Un graphe d’alternatives est un 4-uplet G ˘ hN ,F, A,⁄i où

– N est un ensemble de nœuds. Chaque nœud est représenté par un cercle et modélise une opération qui peut être le déplacement d’un train d’un tronçon vers un autre ou son séjour dans une station. Cet ensemble comporte également deux nœuds particuliers ns et n f que l’on représente par des triangles et qui désignent respectivement le début et la fin du planning (ou de la partie du planning considéré) ;

– F est un ensemble d’arcs fixes. Un arc est une paire de nœuds (ni ,n j ) 2 N 2. Il représente l’existence d’une contrainte temporelle entre le début de l’opération ni et celui de l’opération n j . Les arcs fixes représentent des contraintes qui doivent impérativement être prises en compte et qui sont toujours valables (e.g. le temps de course minimal que fait un train pour parcourir un tronçon ferroviaire, le temps de séjour minimal d’un train dans une station, etc.). Dans un graphe d’alternatives, les arcs fixes sont représentés par des flèches d’un trait solide ;

– A est une ensemble de paires d’arcs alternatifs. Un arc alternatif est un arc qui indique une éventuelle priorité d’un événement sur un autre ; les deux événements impliquant deux trains différents. Les arcs alternatifs viennent toujours par paire et les contraintes représentées par ces arcs sont mutuellement exclusives. Les arcs alternatifs sont représentés par des flèches en trait pointillé. Dans la figure 2, soit l’événement représenté par n1e2 précède celui représenté par n2e1, soit l’événement représenté par n2e2 précède celui représenté par n1e1 mais jamais les deux en même temps car cela créerait une boucle qui ne permet pas de trouver un ordonnancement des événements satisfaisant toutes les contraintes imposées par les arcs ;

Dans ce qui suit, on désigne par E, l’ensemble de tous les arcs du graphe d’alter- natives (arcs fixes dans N et arcs alternatifs dans les paires de A) défini par : 8 ei j 2 F > > ei j 2 E () <_ 9(ekl ,ei j ) 2 A > _ 9(ei j ,ekl ) 2 A > :

À des fins de simplification des notations, on écrira ei j pour désigner tout arc (n j ,n j ). n1e1       n1e2 L n2e1       n2e2

– ⁄ : E ! Q¨0 est une fonction qui associe à chaque arc un nombre rationnel strictement positif fini représentant une contrainte temporelle.

Encore une fois, pour simplifier les notations, on écrira ‚i j ˘ ⁄(ei j ) pour dési-gner la contrainte de temps entre les événements représentés par les nœuds ni et n j .

Les contraintes de temps sur les arcs fixes représentent les temps de séjour et les temps de courses minimaux des trains tandis que les contraintes sur les arcs alternatifs représentent les headways entre les trains.

On désigne par conflit, le cas où deux ou plusieurs trains demandent à rentrer dans un même tronçon ferroviaire à un moment donné. La résolution des conflits dans [3] se fait au moyen d’un algorithme par séparation et évaluation (branch and bound). Cet algorithme essaye de retrouver une solution, i.e., un ordonnancement des trains en minimisant le retard maximum possible.

Une solution est un graphe G(S) ˘ hN ,F [S,⁄i où S est une sélection d’arcs alternatifs. Une sélection S est un ensemble d’arcs qui contient au plus un élément de chaque paire dans A. Une sélection est dite complète si elle comporte un et un seul arc de toutes les paires d’arcs dans A. Une sélection est dite consistante si la solution G(S) construite à partir de cette sélection ne contient pas de cycle ; un cycle impliquant l’existence de contraintes contradictoires. La résolution d’un conflit consiste donc à retrouver une sélection complète et consistante.

Dans le contexte du ferroviaire où un graphe représente des trajectoires possibles de trains et les contraintes de temps (durée de déplacement, temps de stationnement) et de sécurité (headway obligatoire), une solution donne un planning faisable au plus tôt.

À partir de ce planning il est possible de déduire une table horaire mais si l’on prend les dates au plus tôt, cette table horaire ne sera jamais robuste, i.e., il faudrait la recalculer dès que le moindre retard a lieu. C’est pourquoi, la table horaire est calculée à partir du planning en prenant des temps tampons (des marges temporelles). Lorsqu’un train arrive en retard a une station, par exemple, il suffit de déduire ce retard de la marge sur son temps de séjour en station pour ne pas avoir a recalculer une nouvelle date de départ qui aura pour conséquence de décaler toutes les dates des trains qui le suivent.

Les référents théoriques étant définis, il faut rappeler que l’objectif derrière la construc-tion de ce modèle c’est d’arriver à évaluer des politiques de régulation afin de voir si celles-ci améliorent l’exploitation des systèmes ferroviaires et de les comparer. Une manière de procéder consiste à faire des jeux de simulation et de voir si les résul-tats satisfont des critères prédéfinis. Nous avons décidé de prendre pour critères un ensemble d’indicateurs clés de performance (KPI, pour Key Performance Indicators) préconisés par L’Union internationale des transports publics (UITP) [1]. La section suivante est consacrée à la présentation de ces KPI.

Les KPI sont, comme souligné précédemment, des mesures qui permettent de juger de la performance d’un système ferroviaire. L’UITP exhorte tout exploitant de système ferroviaire à considérer les KPI suivants :

Il y a deux manières de mesurer la régularité du service : le temps d’attente des passagers et le headway. Le temps d’attente est la mesure recommandée car elle reflète ce que ressentent les passagers. Le headway reflète, quant à lui, les performances réelles du système qui ne collent pas forcément avec le ressenti des passagers.

Temps d’attente

Ce KPI mesure le pourcentage des passagers qui ont dû attendre plus de x minutes dans des stations spécifiques. x peut également être exprimé en pourcentage de headway. La valeur de x varie en fonction de la période de la journée (heure de pointe, soir, etc.) et du type de jour (weekend, jour férié, etc.). Les incidents de « force majeure » ne doivent pas être inclus dans le calcul de ce KPI.

Comme indiqué précédemment, les modèles classiques ne permettent pas de modéli-ser des stratégies de régulation, la reprogrammation de départs de trains, etc. Nous proposons un modèle composé d’une partie réseau de PETRI, d’une table horaire, et d’une politique de régulation. La simulation synchronisée de ces éléments permet de définir un modèle de systèmes ferroviaires équipé d’une politique de régulation.

Dans notre modèle, le comportement réel du système est décrit par un réseau de PETRI temporel stochastique (RdPTS).
À des fins d’abréviations, on reprendra souvent, dans le restant du document, l’ex-pression réseau(x) de PETRI (resp. RdP) pour parler de réseau(x) de PETRI temporel(s) stochastique(s) (resp. RdPTS).

Definition 1. Un RdPTS est un 10-uplet RdPTS ˘ hP,T, A¡, A¯, A–, M0,T ,T ,F,W i où
– P , T , A¡, A¯, A– et M0 sont les composantes d’un RdP à arcs inhibiteurs tels que défini dans la section 4.1.
À des fin de simplification, tous les arcs ont une multiplicité de 1 (pas de fonc-tion de flux, uniquement des ensembles d’arcs de flux). On rajoute également la condition que les arcs inhibiteurs et les arcs de flux soient toujours mutuelle-ment exclusifs, i.e., un arc (p, t) est soit dans A– ou dans A¡ mais jamais dans les deux en même temps ;
– T : T ! Q‚0 est une fonction qui associe à chaque transition un nombre ration-nel positif fini représentant son temps de tir au plus tôt ;
– T : T ! Q‚0 [{¯1} est une fonction qui associe à chaque transition un nombre rationnel positif représentant son temps de tir au plus tard ;
– F : T ! §F est une fonction qui associe à chaque transition une fonction de répartition (fonction de distribution cumulative). Pour chaque transition t 2 T , on note par Ft , F(t) la fonction de répartition y étant associée ;
N.B. §F dénote l’ensemble des fonctions de répartition ;
– W : T ! R‚0 est une fonction qui associe à chaque transition un poids. Ces poids permettent de déterminer quelle transition tirer en premier quand plusieurs transitions sont tirables au même instant.

Avant de préciser les calculs faits par les fonctions de régulation, rappelons les règles sémantiques utilisées pour définir l’exécution d’une table horaire : les ordres de départ sont donnés aux dates dictées par la table horaire ; les départs peuvent avoir lieu plus tard que la date prévue ; les arrivées peuvent avoir lieu plus tôt ou plus tard que la date prévue ; et les retards peuvent imposer un changement dans le planning. Ces changements sont le résultat d’un calcul qui est effectué au moyen d’une fonction notée °. Dans cette section, nous donnons une formulation générale de ce qu’est une fonction de régulation ainsi qu’un exemple de celle-ci.
Definition 16. Soit G l’ensemble des graphes d’alternatives, T l’ensemble des tables horaires et C l’ensemble de leurs configurations possibles. Une fonction de régulation est une fonction ° : G£T£C£N £R‚0 ! T. Elle prend en argument une table horaire et sa configuration, le graphe d’alternatives à partir duquel la table horaire a été construite, l’identité d’un événement (un nœud) et sa date d’occurrence (un réel positif fini) et retourne une nouvelle table horaire.
Le calcul d’une nouvelle table horaire peut consister en un simple décalage des dates des événements à venir en prenant compte des contraintes sur les arcs de la table horaire. Il peut aussi être une fonction plus complexe : il peut, par exemple, consister à faire un nouveau choix d’arcs alternatifs pour la partie non encore exécutée de la table horaire. Ceci rend, par exemple, le dépassement entre deux trains possible, comme il permet de choisir un nouveau chemin pour un train si la situation l’impose.
Definition 17. On définit la fonction de régulation °1 comme étant une fonction qui décale simplement les dates d’un ensemble d’événements à venir. Cet ensemble regroupe tous les successeurs d’un nœud donné, i.e., tous les événements futurs qui en dépendent. Le décalage se fait jusqu’à la date au plus tôt qui satisfait toutes les contraintes liées à ces événements. Une fenêtre temporelle au delà de laquelle le calcul doit s’arrêter est également définie. Elle est souvent de l’ordre de l’heure et est choisie avec la perspective de revenir à la table horaire originale, si possible, dans un temps inférieur à cette fenêtre. L’idée aussi c’est de limiter le temps de recalcul des dates.