Des mathématiques pour faire rouler les trains

Guillaume Dalle

Cycle SMAI & Musée des arts et métiers

2025-09-10

Introduction

La recherche, c’est quoi ?

Plein de métiers différents à la fois !

  • 📖 Lire
  • 🤔 Réfléchir
  • ⌨️ Coder
  • 📜 Écrire
  • 🎤 Présenter
  • 🧑‍🏫 Enseigner
  • 🧑‍🎓 Encadrer
  • 📂 Organiser
  • 💵 Financer

La recherche en transports

De multiples disciplines mobilisées :

  • 🏭 Ingénierie
  • 🤑 Économie
  • 🗺️ Géographie
  • 🧑‍🤝‍🧑 Sociologie
  • 💻 Informatique
  • ➕ Mathématiques ?

Mon parcours

  1. Lycée scientifique
  2. Classe préparatoire maths-physique
  3. École d’ingénieurs
  4. Thèse (comment prédire et éviter les retards de trains ?)
  5. Postdoctorat (comment analyser des réseaux complexes ?)
  6. Chercheur (comment mutualiser les livraisons de marchandises ?)

La planification ferroviaire

Étapes du processus (Schlechte 2012)

Étapes du processus (Schlechte 2012)

Acteurs impliqués :

  • 🚄 Entreprises ferroviaires (RU)
  • 🛤️ Gestionnaire d’infrastructure (IM)

Échelles temporelles :

  • 👴 Stratégique : A-5
  • 📆 Tactique : A-1 à M-1
  • ⌚ Opérationnelle : M-1 à J-1

Focus sur l’allocation d’itinéraires

But : amener chaque train de son point de départ à son point d’arrivée.

Le challenge Flatland (https://flatland-association.github.io/)

Le challenge Flatland (https://flatland-association.github.io/)

Problème d’optimisation sur un graphe, de complexité exponentielle.

Notions de théorie des graphes

Définition

Un graphe \(G = (N, A)\) est composé

  • d’un ensemble de noeuds \(i \in N\)
  • d’un ensemble d’arêtes \(a = (i, j) \in A\)

Permet de représenter des connexions entre différentes entités.

Origines : les 7 ponts de Königsberg

Le premier problème de théorie des graphes fut posé par Euler.

Peut-on traverser tous ces ponts une fois chacun sans revenir sur ses pas ?

Peut-on traverser tous ces ponts une fois chacun sans revenir sur ses pas ?

Applications

  • Communications
  • Réseaux sociaux
  • Molécules / protéines

Structure de communauté dans un graphe (Abbe 2018)

Structure de communauté dans un graphe (Abbe 2018)

Le réseau ferroviaire comme graphe

Un noeud ne correspond pas toujours à une localisation physique !

Représentation graphique d’un réseau avec orientation (Laurent et al. 2021)

Représentation graphique d’un réseau avec orientation (Laurent et al. 2021)

Notions d’optimisation

Est-ce de l’IA ?

L’Intelligence Artificielle désigne un ensemble d’algorithmes permettant d’automatiser des tâches typiquement attribuées aux humains.

Prédiction

Anticiper un phénomène inconnu ou futur.

Génération

Produire des médias à partir de consignes et d’exemples.

Décision

Planifier l’usage de ressources limitées.

Vous apprendrez cette année à résoudre des problèmes d’optimisation

Trouver le minimum d’une fonction \(x \in \mathbb{R} \longmapsto f(x)\).

Il suffit de calculer sa dérivée \(f'(x)\) (pente de la courbe) et de résoudre \(f'(x) = 0\).

Problème : comment fait-on si \(x\) doit satisfaire des contraintes ?

Un problème sous contrainte

On me donne une tôle d’aluminium de surface \(1 m^2\) pour fabriquer une casserole. Comment obtenir le plus grand volume ?

  • La casserole a un rayon \(r\) et une hauteur \(h\).
  • Sa surface est donnée par \(S(r, h) = \pi r^2 + 2 \pi r h\).
  • Son volume est donné par \(V(r, h) = \pi r^2 h\).

Problème d’optimisation :

\[\begin{aligned}\max_{r,h} \quad & V(r, h) \\ \text{s.c.} \quad & S(r, h) \leq 1 \\ & r \geq 0 \\ & h \geq 0\end{aligned}\]

Modéliser la réalité

Pour que l’ordinateur aide à la décision, il faut expliciter le problème :

  • Données
  • Variables
  • Contraintes
  • Objectif

Simplification nécessaire

“Tous les modèles sont faux, mais certains sont utiles.” (George Box)

Données du problème

  • Topographie du réseau : un graphe dirigé \(G = (N, A)\)

  • Durée de la journée \(T\)

  • Ensemble \(V\) de voyages, chaque voyage \(v \in V\) possédant :
    • Station de depart \(s_v^d\) et d’arrivée \(s_v^a\)
    • Heure de départ \(h_v^d\) et d’arrivée \(h_v^a\) théoriques

Variables de décision

Itinéraire de chaque voyage : suite de noeuds \((n_v^1, ..., n_v^T)\)

Heures d’arrivée et de départ ? Déterminées par les contraintes.

Décider ce que fait chaque train à chaque intersection (Laurent et al. 2021)

Décider ce que fait chaque train à chaque intersection (Laurent et al. 2021)

Contraintes à respecter

  • Chaque voyage existe sur le réseau : \((n_v^t, n_v^{t+1}) \in A\)
  • Chaque voyage part de sa station de départ : \(n_v^1 = s_v^d\)
  • Chaque voyage arrive à sa station d’arrivée : \(n_v^T = s_v^a\)
  • Chaque voyage attend son heure de départ : \(n_v^1 = n_v^2 = \dots = n_v^{h_v^d}\)
  • Deux voyages n’occupent pas le même noeud en même temps : \(n_v^t \neq n_{v'}^t\)

Fonction objectif

Retard d’un voyage : \[r_v = \max(0, \delta_v) \quad \text{où} \quad \delta_v = \text{ heure d'arrivée réelle } - h_v^a\]

“Coût” à minimiser : plusieurs choix possibles pour agréger les voyages

  • Retard total \(r_1 + r_2 + \dots + r_V\)
  • Plus grand retard \(\max (r_1, r_2, \dots, r_V)\)

Résolution

Les problèmes d’optimisation réalistes sont résolus par des algorithmes, implémentés sous forme de code informatique.

Critères d’évaluation :

  • ✅ Terminaison
  • 👉 Correction
  • 🥇 Optimalité
  • 🏃 Complexité

Notions de complexité

Taille de l’entrée & efficacité

Nos données d’entrée se mesurent par :

  • le nombre de noeuds du graphe \(N\)
  • le nombre d’arêtes du graphe \(A\)
  • le nombre de voyages \(V\)

L’efficacité d’un algorithme se mesure par :

  • le temps de calcul
  • la mémoire utilisée

Plus l’entrée est grande, plus l’algorithme utilise de ressources.

Polynomial vs exponentiel

On mesure la complexité en opérations arithmétiques (\(+\), \(-\), \(\times\), \(\div\)). Supposons que chacune prend \(1\) nanoseconde.

Complexité \(N = 50\) \(N = 100\) \(N = 200\)
“linéaire” (\(N\)) 50 ns 0.1 µs 0.2 µs
“quadratique” (\(N^2\)) 2.5 µs 10 µs 40 ms
“cubique” (\(N^3\)) 0.1 ms 1 ms 8 ms
“exponentielle” (\(2^N\)) 13 jours 10\(^{13}\) ans ?

Exemples

Problème Complexité Algorithme
Trouver le minimum d’une liste de nombres \(N\) Parcours simple
Trier une liste de nombres \(N \log N\) Tri fusion
Calculer un seul itinéraire \(N \log N\) A*
Calculer plusieurs itinéraires compatibles exponentielle ?

Le rôle des benchmarks

Pourquoi se comparer ?

On sait résoudre des problèmes exponentiels, mais pas toujours exactement.

Benchmark = scénario standardisé pour évaluer les différentes approches.

Différentes méthodes de résolution pour Flatland (Laurent et al. 2021)

Différentes méthodes de résolution pour Flatland (Laurent et al. 2021)

Nécessite de trouver des points communs entre différents problèmes.

Simplification 1 : de la réalité à Flatland

Flatland est un problème plus simple que la réalité :

  • Réseau assimilé à une grille
  • Commande centralisée
  • Vitesse constante
  • Pas de stations intermédiaires
  • Pas de mécanisme de sécurité

Un paysage suisse bucolique (https://flatland-association.github.io)

Un paysage suisse bucolique (https://flatland-association.github.io)

Simplification 2 : de Flatland au MAPF

Le Multi-Agent PathFinding est un problème encore plus simple que Flatland :

  • Cellules plus simples (vides ou obstacles)
  • Les agents sont ponctuels
  • Pas d’accidents aléatoires

Très utile pour développer de nouveaux algorithmes !

Une instance de MAPF à deux agents (Gao et al. 2024)

Une instance de MAPF à deux agents (Gao et al. 2024)

Le benchmark MAPF

Instances de tailles et natures variées (Stern et al. 2019).

Villes

Jeux vidéo

Labyrinthes

Pièces

Aléatoires

Comment gagner le challenge Flatland ?

Avec des techniques éprouvées pour un problème plus simple (MAPF) :

  1. Recherche d’itinéraire efficace pour un seul train
  2. Gestion des conflits pour plusieurs trains

Découvrons la stratégie de l’équipe gagnante !

Les deadlocks sont un défi majeur (Li et al. 2021)

Les deadlocks sont un défi majeur (Li et al. 2021)

Itinéraire pour un seul train

Existe-t-il toujours un plus court chemin ?

Pas si le graphe est déconnecté

Pas si le graphe a des cycles de coût négatif

Recherche en largeur : exploration naïve

Explorer le graphe par cercles concentriques autour du point de départ.

Avantage

Très facile à appliquer

Défaut

Exploration à l’aveugle

Lien de visualisation

Algorithme A* : exploration guidée

Prioriser les sommets selon la somme de deux quantités :

  • distance exacte depuis l’origine \(g(n)\)
  • distance approximative jusqu’à la destination \(h(n)\)

Avantage

Évite de se disperser

Défaut

Nécessite une bonne “heuristique”

Lien de visualisation

Est-ce le meilleur algorithme ?

A* est le meilleur algorithme de sa “famille” si l’heuristique utilisée est :

  • admissible : sous-estime toujours le coût du chemin restant
  • consistente : satisfait l’inégalité triangulaire \(h(j) \leq w(i, j) + h(i)\)

Mais on peut faire mieux si on a accès au graphe en avance (Bast et al. 2016).

Itinéraires pour plusieurs trains

Une explosion des possibilités

Idéalement, on voudrait trouver les itinéraires pour chaque agent en parallèle.

Plus les agents sont nombreux, plus on dévie du chemin optimal.

Lien de visualisation

Recherche arborescente : c’est trop long !

Idée (Conflict-Based Search) : dès qu’on rencontre un conflit, explorer les deux possibilités engendrées.

Il faut explorer toutes les feuilles de l’arbre (Wang et al. 2025)

Il faut explorer toutes les feuilles de l’arbre (Wang et al. 2025)

Avantage

Trouve une solution optimale

Défaut

Complexité exponentielle

Planification priorisée

Idée : planifier les agents un par un, et les considérer comme obstacles figés ensuite.

L’ordre de priorité est important (Wang et al. 2025)

L’ordre de priorité est important (Wang et al. 2025)

Avantage

Très rapide à exécuter

Défaut

Ne trouve pas forcément de solution (optimale)

Conclusion

Leçons à retenir

  • 🚦 Les maths peuvent servir à décrire et résoudre des problèmes d’optimisation en transport.
  • 😱 Certains sont faciles (plus court chemin), d’autres difficiles (Flatland).
  • 📊 Simplifier et généraliser le problème permet des approches générales et comparables.
  • 🫠 En pratique, tout est toujours plus compliqué (c’est ça qui est fun).

Des questions ?

Mon site web pour plus d’infos : https://gdalle.github.io/

Références

Abbe, Emmanuel. 2018. “Community Detection and Stochastic Block Models: Recent Developments.” Journal of Machine Learning Research 18 (177): 1–86. http://jmlr.org/papers/v18/16-480.html.
Bast, Hannah, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. 2016. “Route Planning in Transportation Networks.” In Algorithm Engineering: Selected Results and Surveys, edited by Lasse Kliemann and Peter Sanders, 19–80. Lecture Notes in Computer Science. Cham: Springer International Publishing. https://doi.org/10.1007/978-3-319-49487-6_2.
Gao, Jianqi, Yanjie Li, Xinyi Li, Kejian Yan, Ke Lin, and Xinyu Wu. 2024. “A Review of Graph-Based Multi-Agent Pathfinding Solvers: From Classical to Beyond Classical.” Knowledge-Based Systems 283 (January): 111121. https://doi.org/10.1016/j.knosys.2023.111121.
Laurent, Florian, Manuel Schneider, Christian Scheller, Jeremy Watson, Jiaoyang Li, Zhe Chen, Yi Zheng, et al. 2021. “Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World.” March 30, 2021. http://arxiv.org/abs/2103.16511.
Li, Jiaoyang, Zhe Chen, Yi Zheng, Shao-Hung Chan, Daniel Harabor, Peter J. Stuckey, Hang Ma, and Sven Koenig. 2021. “Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge.” Proceedings of the International Conference on Automated Planning and Scheduling 31 (May): 477–85. https://ojs.aaai.org/index.php/ICAPS/article/view/15994.
Schlechte, Thomas. 2012. “Railway Track Allocation: Models and Algorithms.” PhD thesis, Technische Universität Berlin. https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1489.
Stern, Roni, Nathan Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne Walker, Jiaoyang Li, et al. 2019. “Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks.” Proceedings of the International Symposium on Combinatorial Search 10 (1, 1): 151–58. https://doi.org/10.1609/socs.v10i1.18510.
Wang, Shiyue, Haozheng Xu, Yuhan Zhang, Jingran Lin, Changhong Lu, Xiangfeng Wang, and Wenhao Li. 2025. “Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding.” May 25, 2025. https://doi.org/10.48550/arXiv.2505.19219.