Utiliser l'intelligence décisionnelle pour accroître la productivité : Le Solveur de Conflits
Détection de conflits dans la planification à moyen terme à l’aide de la MoD
Un important objectif du travail de planification à moyen terme (entre X-5 et X-3) est de créer des horaires sans ou quasiment sans conflit. Bien que les trains ne circuleront pas avant quelques années, à ce stade du processus de planification, la structure de base de l'horaire devient claire et il est important d’acquérir la certitude que les sillons planifiés pourront circuler sans retards structurels par rapport à l'horaire prévu.
Le travail à cet horizon temporel implique typiquement l'utilisation d'un outil de planification avec un modèle d’infrastructure macroscopique. Le principe de base de cet outil est permissif : le planificateur est libre de créer des sillons qui répondent aux demandes des opérateurs ferroviaires et aux règles de planification des gestionnaires d'infrastructure. Mais durant cette phase, les détails de l'infrastructure se précisent progressivement et les volumes de sillons se rapprochent des niveaux définitifs. Ces évolutions rendent fondamental le contrôle de la faisabilité des sillons créés et de leurs interactions à un niveau de détail approprié. Nous avons décrit notre approche à cet égard sous le nom de Microscopie à la demande ("MoD") dans les rapports annuels précédents.
En résumé, les services de la MoD permettent de valider à l'aide d'un outil microscopique externe les horaires planifiés à l'échelle macroscopique dans Viriato. Ces services permettent de rechercher les itinéraires microscopiques empruntés par les trains, de calculer les temps de parcours sur cette infrastructure et de vérifier si les trains sont exempts de conflit à l'échelle microscopique. Ces opérations sont intégrées à Viriato et se font sans que l'utilisateur ne quitte la vue de planification de Viriato.
Gain de productivité grâce à la résolution automatique des conflits simples
Quelle que soit la qualité de la planification des trains au niveau macroscopique, il est inévitable que des conflits microscopiques existent et doivent être gérés avant que le plan de transport puisse être livré. Lorsque les planificateurs sont confrontés à un grand nombre de ces conflits, une question naturelle se pose : ces conflits peuvent-ils être supprimés, ou du moins minimisés, en utilisant la flexibilité inhérente à un horaire venant des différentes réserves de temps qui sont ajoutées à des fins opérationnelles, techniques ou commerciales ? En manipulant la distribution de ces réserves, il est souvent possible d'éliminer bon nombre de ces conflits sans modifier la structure de base de l'horaire prévu. Si ce processus peut être automatisé, la majeure partie de ces conflits peut être supprimée promptement. Les planificateurs ont alors le temps de se concentrer sur les conflits les plus complexes et leur productivité est augmentée. Cette réflexion nous amène à l'objet de cet article, le Solveur de Conflits.
Le Solveur de Conflits est une approche visant à améliorer la productivité des planificateurs en les assistant dans la résolution des conflits. Cette approche s'appuie sur les fondements de la MoD pour tisser le lien entre les modèles macro- et microscopique, sur des travaux de recherche antérieurs concernant les méthodes d'aide à la décision pour l'élimination des conflits et sur des améliorations algorithmiques afin de réduire le nombre d'appels aux services microscopiques souvent chronophages.
Comment ça marche ?
Le Solveur de Conflits fonctionne sur la base d’une sélection d’un corridor le long duquel l'utilisateur souhaite éliminer les conflits des sillons planifiés. L'utilisateur peut travailler sur ce corridor en sachant que les trains ne seront pas adaptés au-delà du périmètre choisi. Pour le planificateur, l'utilisation du Solveur de Conflits se résume à appuyer sur un bouton dans l'outil de planification Viriato.
Cette apparente simplicité couvre un processus mathématique complexe en arrière-plan. L'outil Viriato n'a lui-même aucune connaissance de l'infrastructure microscopique sous-jacente pour l’évaluation des conflits. Pour mener à bien cette évaluation, les temps d'occupation des blocks sont nécessaires. De plus, ceux-ci doivent être transformés en un modèle mathématique pour la minimisation subséquente des conflits. En principe, il serait possible de simuler la progression de chaque train à travers chaque block de manière répétée afin de trouver l'ensemble complet des temps de réservation et de libération des blocks susceptibles d’advenir lorsque des trains sont en conflits, et sur la base de ce modèle, entreprendre la résolution des conflits. Cependant, les nombreux degrés de liberté possibles pour chaque train rendraient la tâche de calcul dans la pratique excessivement longue.
Heureusement, les principes de conception de l'infrastructure ferroviaire et de la dynamique des trains fournissent une méthode alternative permettant d'obtenir une bonne approximation des temps de prise et de libération des blocks sur base de laquelle nous pouvons générer un modèle mathématique adéquat. Dans la pratique, le dimensionnement des blocks de signalisation et les changements relativement faibles des temps de parcours lors de modification des réserves mènent à une dépendance approximativement linéaire entres les temps de prise et libération des blocks et les temps de réserve macroscopiques. En conséquence, un petit nombre d'appels de calcul des temps d’occupation par l'outil microscopique, typiquement quatre par train, chacun utilisant des temps de réserve différents, permet d’obtenir par régression linéaire une relation de bonne qualité statistique entre les temps d’occupation des blocks microscopiques et les temps de réserve macroscopiques.
Avec ce modèle relationnel entre le système de signalisation et les horaires des trains, nous pouvons construire un modèle mathématique dans lequel les trains peuvent être reprogrammés et réacheminés en redistribuant uniquement les temps de réserve disponibles et en changeant les itinéraires locaux à l'intérieur des gares, tout en maintenant la structure de base des horaires.
Techniquement, un jeu de programmes linéaires en nombres entiers mixtes ("MILP") est construit et transmis à un solveur mathématique commercial, en l'occurrence Gurobi. Ce solveur tente de minimiser les conflits entre les trains, représentés par le chevauchement des temps d’occupation de blocks qui ont été approximés à l'aide de la relation linéaire décrite plus haut. Si la capacité disponible est suffisante, le solveur sera en mesure d'éliminer les conflits.
Des contraintes supplémentaires spécifiques à une organisation ou un pays peuvent être prises en compte, comme des règles concernant le temps de réserve minimal devant être conversé entre deux nœuds et donc indisponible pour la résolution des conflits, ou d'autres règles contraignantes d'exploitation.
Une fois que le solveur a trouvé une solution, celle-ci est remontée vers l'utilisateur qui dispose alors d'un ensemble de trains actualisés entre lesquels la plupart des petits conflits devraient avoir été résolus et les conflits plus importants minimisés. Un contrôle peut être effectué simplement en utilisant le service microscopique de détection des conflits (MoD).
Cette approche offre un gain substantiel de productivité, sans que les utilisateurs ne quittent l’environnement de la planification macroscopique dans Viriato, ni pour la résolution automatique des conflits ni pour le contrôle des résultats.
De la recherche à la pratique
Cette méthode est le fruit plusieurs projets de recherche académique et a été documentée dans un article publié en collaboration avec la TU Dresden à l’occasion de la conférence ICROMA RailDresden 2025. Comme pour tous les projets de ce type, il est important de tester la méthode sur des cas réels et des configurations de données différentes. Des premiers tests ont été effectués par des experts en planification d'horaire chez SMA et ils ont confirmé son potentiel. Actuellement, une phase d'industrialisation du prototype est en cours dans laquelle le code de construction du modèle mathématique et la partie algorithmique sont réécrits dans processus d'ingénierie de logiciel standardisé et intégrés à la plateforme algorithmique de Viriato. Cette intégration permettra une utilisation dans une plus vaste gamme de projets internes et externes et facilitera l'incorporation des retours d’expérience et des exigences supplémentaires.