Modélisation et Optimisation de la Gestion Opérationnelle du Trafic Ferroviaire en cas dAléas. Thèse présentée par Laurent GÉLY

Modélisation et Optimisationde la Gestion Opérationnelle du Trafic Ferroviaire

en cas d’Aléas.

Thèse présentée par Laurent GÉLY.

2

Présentation générale

Développer les solutions pour un outil d’aide à la décision dédié

à la gestion du trafic ferroviaire en cas d’aléas.

Collaboration (thèse CIFRE)Université Bordeaux I:

Pierre PESNEAU, François VANDERBECK,SNCF DI&R: Gilles DESSAGNE.

3

Plan

1. Problématique, enjeux.

2. Evolutions du système LIPARI.

3. Conception du système EIFEL.

4. Conclusion et Perspectives.

4

I. Problématique, enjeux

• Problématique, enjeux:– Définitions du problème et des enjeux.

– État de l’art,

– Présentation générale des travaux.

• Evolutions du système LIPARI.

• Conception du système EIFEL.

• Conclusion & Perspectives.

5

Périmètre et définition du problème.

Aujourd’hui la production ferroviaire est divisée en plusieurs catégories de problèmes.

La gestion temps réel des (mouvements des) circulations:(replanification + reroutage).

– Suite à un incident, les horaires (itinéraires) prévus ne sont plus réalisables.

– Solution: de nouveaux horaires (vitesses), itinéraires, et ordonnancements afin de limiter les conséquences.

– Respect des contraintes métiers (sécurité, organisation, …)

6

Enjeux industriels.

Constat industriel: accroissement

– de la taille des zones de régulation,

– de la densité des trafics.

Besoin d’une régulation plus globale pour optimiser l’utilisation de l’infrastructure (quantité & qualité).

=> Intérêt d’outils d’aide à la décision.

Opportunité liée à la réorganisation de la régulation (C.C.R.):

– nouveau système d’information + nouveau formalisme,

– mise en place d’un nouveau système (intégration).

7

Missions de recherche.

Trois phases «cœur de métier» :

1. Modélisation (formalisation, représentations)

2. Formulation (modèles math., algorithmes)

3. Implémentation (écriture logicielle optimisée, intégration)

+ un ensemble de problématiques industrielles connexes à considérer.

8

I. Problématique, enjeux:état de l’art.


– État de l’art.





9

Etat de l’art (planification + replanification).

• Des modèles métiers incomplets.• Etudes manquants de réalisme industriel.• De nombreuses méthodes de résolution.• Pas de base de comparaison.

Tornquist (PhD 2006) .

• Cas trop spécifiques (adaptés à d’autres contextes étrangers).• Pas de modèle présentant un schéma d’intégration industriel.

10

Etat de l’art (autres travaux particulièrement intéressants).

(TU Delft): Pachl, Hansen (« bluebook » 2008):

Démarche de formalisation, en particulier espacements « blocking time theory ».

(TU Delft, Roma 3): D’Ariano (PhD 2008), Corman (PhD 2010),

Réalisme des études (Roma): modélisation gare d’Utrecht.

(ETH Zurich): Caimi (PhD 2009), Fuchsberger

Problématiques des niveaux de description.

11

I. Problématiques, enjeux:les ambitions du projet.


– État de l’art.





12

Architecture cible en étude/opérationnel.

Opérationnel

évolution des circulations sur le réseau

Contrôle:

(Localisation, horaires )

Commandes

Outil de prévision des durées d'incidents

Gestion Opérationnelle du Trafic Ferroviaire

Régulation:Re-planification optimisée des circulations

•traitement statistique des catégories d'incidents, lieux, dates, etc ... alimenté par le Rex

Nouvelle planification :• horaires• ordonnancements• itinéraires des trains

Système d'information (temps réel)

• état et positions des circulations,

• état de l'infrastructure

Planification

• Grille horaire théorique

Contrôle

(Rex)

13

Historique des réalisations:

Planification (DEMIURGE), puis deux projets de régulation: 1. Evolution du système LIPARI:

Réécriture, amélioration, formulation et réglages solver.Extension espacements fonction des vitesses.Nombreuses expérimentations métiers (variantes).

Système collaboratif optim./simu .Deux niveaux de description.Des conditions expérimentales simplifiées.

2. Conception du système EIFEL:Nouvelle représentation: modèle gérant différents niveaux.Formalisation complète du problème de régulation: modèles.

Redévelopper la formulation complète déjà expérimentée.Autres formulations pour étendre les capacités de l’outil.Possibilités de couplage avec le modèle multiniveau.

Spécification d’un schéma d’intégration (nouvel usage simu.).

14

II. Un premier projet, le système LIPARI.

• Problématique, Enjeux.

• Evolutions du système LIPARI– Architecture système LIPARI,

– Etudes réalisées,

– Conclusions, définition de nouveaux besoins.



15

Architecture système LIPARI.

Simulateur SiSyFe

Simulation de l’évolution des trains sur le réseau

en fonction :

• des caractéristiques de l'infrastructure et du matériel,

• du système de signalisation,

• du type de conduite modélisé, (conduite manuelle ou automatique)

• des incidents,

• des ordres de régulation en provenance du système LIPARI.

Grille de circulation théorique

Contrôle:

(Localisation, horaires )

Commande:

(Programmations,Consignes)

Détection Automatique des incidents

Système LIPARI

RégulationRe-planification des circulations

• écarts horaires théoriques / réels• nouvelles conditions d’exploitation

Nouvelle planification :• horaires• ordonnancements• itinéraires des trains

Traduction en commandes• consignes de vitesse• programmation d'itinéraires• changement d'ordonnancements

Mise En Oeuvre

Sardaigne

• génération du plan d'expérience,

• traitement statistique des résultats résultats

incidents

16

II. Un premier projet, le Système LIPARI.


• Evolutions du système LIPARI– Architecture système LIPARI,

– Etudes réalisées,




17

1ère catégorie d’études:gestion du trafic en situation perturbée.

Un terrain d’étude pour améliorer la formulation:

Objectif: aider les experts dans leur prise de décision en leur proposant des solutions, suite à une perturbation.

Cadre: gestion d’incidents mineurs à moyens.(ex.: plusieurs minutes au sein d’une zone à fort

trafic)

Protocole:– Objectif: limiter les perturbations– Leviers d’actions: horaires (vitesses), réordonnancement,

routages.– Temps de résolution: limite fixée à 5mn.

18

Campagnes d’études de problèmes métiers:Tours-Bordeaux, Éole, LN1 …

Etudes représentatives

de problèmes métiers:

Tours-Bordeaux

– IPCS (choix de voies)

– réordonnancements

ÉOLE (projet de connexion entre les réseaux est et ouest de Paris)

– Jusqu’à 542 trains.

19

Tailles des problèmes mathématiques.

Variantes influençant la complexité:

– avec ou sans routage (IPCS),

– quantité de réordonnancements possibles,

– taille de l’étude (espace / temps),

– …

20

2eme catégorie d’études:problème de fluidification du trafic.

Objectif: gérer une zone afin de prévenir les conflits, et ainsi optimiser la fluidité du trafic (maximiser le débit).

Principe: « onde verte »

Décisions: vitesses.

Défi: la précision

(des espacements, des consignes de vitesse).

Sp

ac

e

time

First speed limitation(incident)

With fluidification Withoutfluidification

gain

SignalingsystemSecond speed limitation

(consequence)

21

Le nœud ferroviaire de Rémilly – Baudrecourt.

<1 B>

<2 B>

<2

<2

<

1

<

1

Poste 2 de Metz-Sablon

SEI de Lamorville

Benestroff

St-Avold

Rayon = 50 km

Trafic hétérogène, (fret international, trafic

régional, TGV) Vitesses très différentes.

=> Modification du modèle math.

22

II. Un premier projet, le Système LIPARI.


• Evolutions du système LIPARI– Architecture LIPARI,

– Etudes réalises,



• Perspectives & Conclusion.

23

Retour d’expérience (formulation « temps continu », base LIPARI).

Ces études ont montré:+ des problèmes métiers de taille réelle sont traités,+ avec précision: espacements fonction des vitesses,- sensibilité aux données: de faibles variations peuvent causer

problèmes (cf. fluidification),- disponibilité des données,- communication problématique

entre niveaux de représentation.

De plus, en « situation idéale » :– niveaux de représentation (pertinents) fixés (1 macro. / 1 micro.),– durée d’incident, taille de l’étude prédéfinis.

24

Conclusions et identification de nouveaux besoins(suite aux expériences sur base LIPARI)

• Problème de représentation (passage entre différents niveaux).

• Étendre le domaine de validité des outils: fluidification, situation perturbée, coordination d’axe.

• Besoin d’unification et formalisation.

• Intégration complètement réaliste dans un système de contrôle commande et un système logiciel.

25

III. Le Projet EIFEL: formalisme.



• Conception du système EIFEL:– Un formalisme pour l’exploitation ferroviaire.

– Formulations mathématiques.

– Intégration système.


26

1. Modélisation.

Consiste à formaliser la réalité du système ferroviaire en un modèle abstrait afin de le traduire ensuite en une formulation mathématique.

Ce travail a permis:

– une formalisation complète du problème de régulation permettant de décrire tous les fonctionnements possibles du système ferroviaire, (cf. manuscrit)

– une nouvelle représentation de l’infrastructure.

27

La représentation classique: du métier à l’abstrait, du micro. au macro.

Station (simple)

Junction, switches, …

Complex station

Track

arcs = voies ou axes principaux.nœuds = bifurcations, jonctions ou gares.

28

Les limites de la représentation classique,des agrégation incohérentes.

• graphe A: nœuds de natures différentes. • graphe B:

le nœud est un point virtuel,pas une ressource d’infra.

• graphe C: l’arc représentant la LGV agrège des nœuds et des arcs.

29

Nouvelle représentation:exemple d’agrégation.

arcs = ressourcesnœuds=interconnexions

nœuds = ressourcesarcs = relation de connexité

un nœud représenteraitune agrégation de ressources.=> incohérence

30

Agrégation en parallèle: évolutions des propriétés des objets.

Évolution des propriétés:Capacité, débit,espacements de type succession, changement d’ordre possible…

31

Agrégation en série: évolutions des propriétés des objets.

Évolution des propriétés:Capacité, débit, espacements de type conflit,changement d’ordre impossible, …

32

Apports de la représentation multiniveau.

Fonctions d’agrégation et désagrégation automatisables.(propriétés des objets)

Permet de s’adapter à n’importe quel niveau de description:

– coopération entre éléments logiciels,

– description détaillée ou simplifiée selon le besoin,

– adapter la complexité du problème mathématique attenant (cf. couplage avec le choix de formulations).

n.b.: principe peut s’appliquer à d’autres domaines.

33

III. EIFEL: formulations mathématiques



• Conception du système EIFEL:– Un formalisme pour l’exploitation ferroviaire.

– Formulations mathématiques.



34

2. Formulations.

Nous avons développé:

– formulation mathématique en temps continu exhaustifprenant en compte le problème des espacements liés aux vitesses,

– formulations en temps discret et mixte dont les propriétés peuvent être mises à profit,

– couplage avec le modèle multiniveau.

35

Formulation « en temps continu ».

36

Formulation « en temps continu » (1).

Evènement considérés: départs/arrivées des circulations qui se déplacent sur des ressources d’infrastructure.

Contraintes: imposent des durées minimales entre différents évènements (ex. espacements de sécurité, occupation unitaire d’une ressource, etc.).

Programmation linéaire mixte :

– Variables horaires réelles (secondes).

– ex.: contrainte de durée de parcours minimale

37

Formulation en temps continu (2).

– Variables d’ordonnancement, routage, (suppression) binaires.

– Exemple de contrainte disjonctive (espacement de type conflit):

38

Synthèse formulation en temps continu.

39

Espacements en fonction des vitesses.

La valeur des espacements était calculée pour la vitesse théorique des circulations.

Or, cette valeur dépend des vitesses effectives (dans la solution).

Afin de prendre en compte cet aspect, on peut considérer les durées de parcours.

De plus, l’accroissement de la durée d’espacement est linéairement proportionnel à l’allongement de la durée de parcours des circulations.

40

Avantages et inconvénients de la formulation à temps continu.

+ contraintes intuitives à formuler,

+ gère très efficacement les horaires (vitesses),

+ précision des solutions,

- performance avec les contraintes disjonctives (décisions de ré-ordonnancement, routage, …).

41

Formulation « en temps discret ».

Principe: le temps est discrétisé en périodes.

42

Formulation « en temps discret ».

Programmation linéaire entière (variables binaires):

– Variables binaires indiquent si l’évènement s’est déroulé pour chaque (fin de) période considérée.

– Variables binaires d’ordonnancement mais pas de routage.

43

Formulation en temps discret (2).

44

Synthèse modèle en temps discret

45

Avantages et inconvénientsdu modèle en temps discret.

Modèle à temps discret:

+ les contraintes disjonctives (routage) sont gérées efficacement,

- contraintes difficiles à formuler et implémenter,

- nécessite beaucoup de variables,

- précision (période de temps).

46

Problématique liée au choix des modèles.

Complémentarité des deux formulations:

• propriétés,

• usage différent:

– micro. VS macro. ,

– précision horaire VS quantité reroutage « coordination d’axe »,

– …

Modèle mixte:

– pour chaque catégorie de contraintes métiers, la formulation de la contrainte mathématique la plus avantageuse.

– contraintes liantes entre les deux catégories de variables.

47

Formulation « temps mixte ».

48

Problématique liée au choix des modèles.

Couplage avec le modèle multiniveau:

– utiliser la formulation et la description les mieux adaptées pour chaque zone,

– utiliser deux formulations avec deux descriptions différentes sur une même zone,

– utiliser les combinaisons qui réduisent la complexité.

49

Tailles des formulations

• données d’étude extrapolées du modèle Lipari.• un même niveau de description• domaine pour chaque variable:1 heure, périodes de 30s,• plage d’étude: 48h.• correction partielle des données et des propriétés (ressources)• espacements de type conflits 2 à 2 .Comparaison des tailles des problèmes mathématiques:

50

Comparaisons des bornes primales et duales.

(Attention: fonctions objectifs pas directement comparables.)Bornes primales (300s):

De plus, pour 1h de calcul, la borne primale (discret): 645570 .

Bornes duales:

51

III. Le projet EIFEL: intégration système.



• Conception du système EIFEL:– Un formalisme pour l’exploitation ferroviaire,

– Modèles mathématiques,



52

3. Implémentation

Mathématiques appliquées

= transcrire nos travaux en outil informatique performant.

Conception logicielle optimisée (algorithmique, réglages, structures de données , ...).

Intégration de l’outil dans une réalité industrielle.

Nous avons conçu:

– un modèle de données (EIFEL) commun à tous les outils,

– un schéma d’intégration du système logiciel.

53

Un système logiciel, basé sur un même référentiel de données et composé de plusieurs modules.

Référentiel de données: une norme métier pour la description du système ferroviaire (l’abstraction): EIFEL.

Une fois un modèle de données mis en place, on peut envisager de faire coopérer plusieurs modules logiciels.

Le système logiciel ainsi mis en œuvre permet de prendre en compte les réalités industrielles du problème.

Nous allons définir l’architecture et les interactions de ce système logiciel qui constituera in fine l’outil d’aide à la décision.

54

Du couplage entre simulation et optimisation.

Qu’apporte la simulation en temps réel?

Une projection dans le futur de l’état du système:

– permet de détecter un conflit avant sa survenue,

– donne l’état initial du problème d’optimisation i.e. celui déjà prévu pour la fin du calcul (+

5min),

– fournit sur la durée de la plage d’étude la solution initiale (sans intervention) du problème d’optimisation,

– assure la vérification précise des conséquences de nouvelles décisions (macro./micro.).

55

Déroulement chronologique.

1. Contrôle permanent des informations provenant du terrain,

2. Projection en temps réel de l’état du système ferroviaire par simulation,

3. Détection Automatique d’Incident,

4. Analyse et prévision: définition d’une zone et une plage horaire pertinentes via des outils statistiques,

5. Définition du niveau (macro.) de description du problème (multiniveau),

6. Traduction en problème mathématique (service EIFEL),

7. Résolution (moteur d’optimisation),

8. Interprétation de la solution au niveau microscopique (multiniveau),

9. Vérification de la validité par simulation,

10. Validation par l’opérateur,

11. Diffusion automatique des commandes.

56

IV. Conclusion et Perspectives.

• Problématique, enjeux.




57

Principales Contributions de cette thèse:

1. Formalisation complète du problème de régulation,Nouvelle représentation: modèle multiniveau (multiscale).

2. Formulation complète en temps continu,Extension espacements fonction des vitesses,Élaboration des formulations en temps discret et mixte,Possibilités de couplage avec le modèle multiniveau.

3. Spécification du modèle de données EIFEL,Développement du schéma de coopération avec la simulation,Spécification d’un schéma d’intégration.

58

Perspectives:

• Développer des algorithmes/méthodes de résolution spécifiques.

• Critère et fonction objectif: que doit on optimiser?

• Etudier la coordination entre zones.

• Intégrer les problèmes de la production ferroviaire.

59

Développer les algorithmes et méthodes de résolutions.

Sur les bases du travail que nous avons effectué:

1. Développer des heuristiques et paramétrage spécifiques au modèle à temps discret (et mixte).

2. Intégrer encore davantage le savoir faire métier (heuristiques ou méthodes générales de résolution, simulation, règles d’agrégation/désagrégation).

60

Critère, fonction objectif.

Que doit on optimiser ?

« Limiter l’impact des incidents. »

Multitude de variantes possibles.

Nous avons développé un savoir faire traduit dans les valeurs de la fonction objectif

et qui satisfait les utilisateurs (planification).

Dans le cadre de la replanification: Réflexion lancée en interne,

mais travail à continuer en liaison avec tous les acteurs.

61

Coordination entres différentes zones de régulation.

Ce projet se limite à la gestion d’une zone indépendante.

Pourtant, les conséquences de l’incident (ou des décisions de régulation) peuvent se propager au delà.

La coordination entre différentes zones impactées doit être étudiée.

n.b.: un critère peut consister à « contenir » les perturbations… mais ceci peut s’avérer impossible.

62

Intégration des problématiques de la production ferroviaire.

Nous avons vu qu’il existe différentes catégories de problèmes:

– gestion des ressources matérielles,

– gestion des ressources humaines,

– (…)

– gestion temps réel des circulations.

Ces problèmes ne sont pas indépendants!

=> L’intégration de ces problèmes est un axe à développer.

63

Conclusion.

Du point de vue universitaire: un défi industriel passionnant à modéliser, la possibilité d’apporter des solutions réalistes au problème métier.

Du point de vue industriel: un besoin évident, une opportunité pour la mise en œuvre d’outils d’aide à la décision et des gains d’efficacité.

« L’avenir, tu n’as point à le prévoir mais à le permettre. »Citadelle, Antoine de Saint-Exupéry.

Merci de votre attention.

Et merci à toutes celles et ceux

qui ont rendu ce travail possible:sur le plan de universitaire, industriel, administratif et humain !

annexes

66

Intégration S.I. statique/dynamique, C.K.

Système d’Information

•Infrastructure•Plan de transport

Système de contrôle-commande•Consignes de vitesses•Ordonnancements•Ré-affectation des voies

Système d’Informationtemps réel

•État du réseau•État des circulations

*validation, modificationRégulation

Simulation, t réel

Coordination d’axe

…

Replanification

Fluidification

67

Translation Macro -> micro

Now the rescheduling process expects a precise solution:

Macro -> micro

This translation is not unique

Here could take place a second optimization (without backtracking)

E.g. of a 2nd objective: robustness, energy efficiency, …

68

3- Problème de reroutage ou de « coordination d’axe ».

Cadre: incident majeur

(ex.: un axe important est rendu inutilisable)

Principe: les trains doivent être insérés dans un planing existant, selon des routes prédéfinies.

Description simplifiée du réseau (macroscopique).

Original Schedule

Trainsto be inserted

Original Schedule

Inserted Trains

Cancelled Trains

Before optimization After optimization

69

3- Exemple d’étude: Lyon – Paris (LGV 1)

Incident:

– 230 km de “LGV ” rendus inutilisables

– Détournement par Dijon.

Exemple:

– Fenêtre d’étude: 16h-

24h

– 80 trains

– 30 nœuds

– 1380 nœuds=trains

70

Retour d’expérience (coordination d’axe).

Remarques:

– Approche semblable “outil de gestion de capacité” (i.e. outil basique de

planification)

– La description macroscopique rend nécessaire une deuxième passe (pour raffiner la solution macro.).

Problèmes:

– La suppression de trains dans un trafic hétérogène est un problème délicat (enjeux concernant plusieurs opérateurs).

– Les développements pratiques pour l’optimisation concernent plutôt le trafic (homogène) urbain ou régional (un seul opérateur).

71

Outils statistiques de prévision: de la durée d’incident et de la taille de l’étude.Actuellement, on constate l’apparition d’un incident … puis sa fin.

Mais on ne sait pas à priori combien de temps il va durer.

Comment faire pour commencer l’étude dès la détection (identification) de l’incident?

De même, on ignore la taille d’étude réellement nécessaire à priori.« Taille » = dimension espace * plage temps ( = #ressources * #circulations )

Comment définir une bonne taille d’étude à considérer pour un « retour à la normale »?

Intérêt d’outils de traitement statistiques des données sur les incidents passés (et de la simulation).

72

Robustesse, optimalité et incertain.

Comment définir une solution « optimale », si le déroulement de celle-ci est fortement incertain?

Le concept de robustesse est une notion intéressante à étudier:

la solution proposée doit être « peu » impactée par l’aléa subsistant (bruit de fond, système contrôle-commande,…)

L’étude de l’optimisation stochastique pourrait se révéler intéressante, pour la construction d’horaires en premier lieu.

Documents

Modélisation et Optimisation de la Gestion Opérationnelle du Trafic Ferroviaire en cas dAléas. Thèse présentée par Laurent GÉLY