Sujet de thèse IFSTTAR

English version
Fiche détaillée :

Titre : Modèles et algorithmes pour la gestion optimisée d’une gare de triage

Laboratoire principal - Référent principal COSYS - ESTAS  -  RODRIGUEZ Joaquin      tél. : +33 320438332

Directeur du laboratoire principal RODRIGUEZ Joaquin  -

Laboratoire 2 - Référent COSYS - LEOST  -  PELLEGRINI Paola  -    -  tél. : +33 320438404

Spécialité de la thèse Informatique et Recherche Opérationnelle

Axe 1 - COP2017 - Transporter efficacement et se déplacer en sécurité

Site principal Lille-Villeneuve d'Ascq

Etablissement d'inscription ECOLE CENTRALE LILLE

Ecole doctorale MADIS

Directeur de thèse prévu RODRIGUEZ Joaquin  -  Université Gustave Eiffel  -  COSYS - ESTAS

Co-directeur de thèse prévu PELLEGRINI Paola  -  Université Gustave Eiffel  -  COSYS - ESTAS

Type de financement prévu Contrat doctoral  - Université Gustave Eiffel

Résumé

Contexte :
Le transport de marchandise est un sujet clef dans le cadre du développement durable. La part modale occupée par le ferroviaire a fortement décliné en France, passant d’un volume de 75 milliards de t.km en 1974 à 40 milliards de t.km en 2005. Cependant, les projections de l’AIE prévoient une augmentation de 43 % entre 2017 et 2050 (International Energy Agency (2019)). De nombreuses initiatives ont vu le jour depuis quelques années afin de redynamiser le fret ferroviaire et de favoriser sa compétitivité. Un élément crucial pour cette compétitivité est représenté par la gestion des gares de triage, qui cherche à minimiser les temps de voyage des cargaisons et maximiser la fiabilité du système. Ces gares sont des infrastructures complexes où de nombreuses décisions opérationnelles interdépendantes doivent être prises à intervalles réguliers. Hors, ces gares sont souvent gérées manuellement, à partir de règles d’exploitation empiriques adoptées au fil du temps par les exploitants.
Leur gestion implique des prises de décisions sur plusieurs aspects complémentaires et difficiles. De plus, le mode de fonctionnement des gares, lié à leur topologie et aux opérations qui y sont menées, peut être très différent. On peut identifier deux types principaux de topologie qui ont un fort impact sur le mode de fonctionnement : d’une part les gares avec butte (shunting yard) où les wagons des trains sont découplés puis distribués sur les rails de la gare afin de former de nouveaux trains sortants (Boysen et al (2012)); d’autre part les gares de transbordement (transshipment yards) où des containers standardisés sont transférés d’un moyen de transport à un autre (rail-rail, rail-route, rail-maritime) à l’aide de grues et de voitures de transport sur rail (Boysen et al (2013)).

Objectifs de la thèse :
Le sujet de cette thèse, qui se déroulera au sein du groupe Trafic des laboratoires ESTAS et LEOST du COSYS, est de proposer des modèles mathématiques ainsi que des algorithmes d’optimisation, afin de pouvoir gérer une gare de triage générique et la totalité de ses aspects opérationnels de manière efficace. Il est à noter qu’un telle approche est inexistante à l’heure actuelle, du à deux verrous scientifiques et techniques principaux :
1) La différence, parfois importante, de mode de fonctionnement des gares de triages rend difficile leur modélisation mathématique unifiée qui puissent prendre en compte les spécificités de chacune.
2) La gestion intégrée de toutes les opérations qui interviennent dans la gestion d’une gare présente une grande complexité computationnelle. En effet, le nombre de variables de décision et de contraintes s’avère très important lorsque tous les sous-problèmes sont considérés conjointement. Chacun de ces sous-problèmes a été démontré être NP-difficile (voir, e.g., Fedtke and Boysen (2017)), ce qui rend le problème à l’échelle de la gare particulièrement complexe.

État de l’art :
La thématique de la gestion des gares de triage a été explorée dans la littérature mais avec de claires limitations du point de vue opérationnel.
Premièrement, les approches existantes se contentent d’étudier un ou deux des sous-problèmes de manière indépendante. Par exemple, Cichenski et al. (2017) traitent à la fois les problèmes de partitionnement des trains pour les placer séquentiellement sous les grues dans une gare a transbordement, de positionnement exacte de chaque train ainsi que de localisation des containers à placer sur ces mêmes trains. Néanmoins, la gestion des grues et les mouvements des trains restent exclus du processus d’optimisation.
Deuxièmement, la plupart des approches se concentre sur une topologie spécifique. Des pistes concrètes permettant de formuler des algorithmes de traitement de gares présentant des modes de fonctionnement différents ont été proposées lors du projet européen OPTIYARD (financé dans le cadre du programme H2020 et du Joint Undertaking Shift2Rail) auquel a participé l’équipe encadrante de cette thèse. Ce projet était centré sur la gestion optimisée d’une gare de triage (Licciardello et al (2020)) : une modélisation générique des ressources a permis de considérer à la fois une gare avec butte ainsi qu’un port multi-modal avec transbordement, en appréhendant leurs ressources à travers un problème d’ordonnancement de tâches sous contrainte. Un algorithme glouton stochastique développé sur la base de cette modélisation a été intégré à un simulateur microscopique pour vérifier la faisabilité de toutes les opérations effectuées.

Démarche de travail :
Le travail de thèse se basera sur le résultat du projet OPTIYARD en en reprenant la puissance de modélisation unifiée. Il visera en premier lieu à proposer des approches basées sur la programmation mathématique linéaire en nombres entiers qui est un outil puissant et consolidé. Ces approches devront traiter de manière intégrée plusieurs problèmes difficiles, ce qui a tendance à produire des modèles au nombre de variables et de contraintes prohibitif. Une possibilité encore non explorée dans la littérature consiste à utiliser des méthodes avancées de programmation mathématique qui permettent de décomposer le problème maître en divers sous-problèmes et de profiter de méthodes de résolutions existantes pour ces sous-problèmes. La thèse se propose de tester des méthodes telles que la Génération de colonnes ou la Décomposition de Benders pour lesquelles l’équipe d’encadrement possède une certaine compétence (Keita et al (2020), Hosteins and Scatamacchia (2020)).
Dans un second temps, la thèse s’attaquera au problème de gestion des gares de triage en considérant le fait que les contraintes opérationnelles contraignent souvent les exploitants à revoir le planning des opérations en fonction des nouveaux trains en approche. Cette situation implique une réoptimisation récurrente et se traduit par un problème d’optimisation en temps réel ou dynamique. Les problèmes de ce type nécessitent la production rapide de nouvelles solutions et donc d’algorithmes heuristiques adaptés. Lorsque les ressources de la gare sont en quantité limitée, les algorithmes heuristiques ont parfois des difficultés à produire des solutions faisables et des stratégies adaptées devront être mises au point pour traiter le problème de manière efficace. L’équipe d’encadrement possède des compétences avancées en terme d’optimisation en temps réel pour le trafic ferroviaire, démontrées lors des projets européens ONTIME (Quaglietta et al (2016)) ainsi que OPTIYARD (Licciardello et al (2020)), et ces compétences seront mises à profit pour concevoir et développer des algorithmes heuristiques pertinents.

Déroulement de la thèse :
La thèse débutera par l'étude de l’état de l’art concernant les méthodes d’optimisation pour les gares de triage. Elle s’attaquera ensuite à la consolidation des résultats du projet OPTIYARD en implémentant un modèle linéaire en nombres entiers qui permette de résoudre le problème dérivant de la modélisation unifiée conçue par ce même projet. Ensuite, des méthodes de programmation mathématique avancées seront développées pour gérer ces problèmes difficiles, puis des heuristiques adaptées seront mises au point afin de pouvoir fournir des solutions en temps réel dans un contexte opérationnel, si les approches exactes ne sont pas assez rapides. Des expérimentations sur des cas d’études réels permettront de comprendre le gain potentiel d’une gestion automatisée et optimisée d’une gare de triage dans différentes configurations. Tout le long de la thèse, les résultats seront présentés à des conférences nationales et internationales (par exemple, MT-ITS - International Conference on Models and Technologies for Intelligent Transportation Systems). Lorsque les modèles et algorithmes auront atteint le niveau de maturité approprié ils feront l’objet de publications dans des revues internationales à comité de lecture (par exemple, Transportation Research Part B : Methodological, ou IEEE Transactions on intelligent transportation systems).

Profil du candidat : Le candidat doit être titulaire d’un Master en recherche opérationnelle, informatique, intelligence artificielle, mathématique appliquée ou équivalent. Une bonne connaissance du langage de programmation C++ et de la langue anglaise (à l’écrit et à l’oral) sont des prérequis importants. Une familiarité avec les outils et logiciels de la programmation mathématique ou avec le domaine du transport ferroviaire sera appréciée.

Références bibliographiques

N. Boysen et al (2012), Shunting yard operations: Theoretical aspects and applications, European Journal of Operational Research, 220(1):1–14.
N. Boysen et al (2013), A survey on container processing in railway yards, Transportation Science, 47(3):312–329.
M. Cichenski et al (2017). An integrated model for the transshipment yard scheduling problem. Journal of Scheduling, 20:57–65.
S. Fedtke and N. Boysen (2017), Gantry crane and shuttle car scheduling in modern rail–rail transshipment yards, OR Spectrum, 39:473–503.
P. Hosteins and R. Scatamacchia (2020), The stochastic Critical Node Problem over trees, Networks, 76(3):381–401.
International Energy Agency (2019), The Future of Rail Opportunities for energy and the environment.
K. Keita, P. Pellegrini, J. Rodriguez (2020), A three-step Benders decomposition for the real-time Railway Traffic Management Problem, Journal of Rail Transport Planning and Management, 13:100170.
R. Licciardello, N. Adamko, S. Deleplanque, P. Hosteins, R. Liu, P. Pellegrini, A. Peterson, M. Wahlborg, M. Za’tko (2020), Integrating yards, network and optimisation models towards real-time rail freight yard operations, Ingegneria Ferroviaria, 75(6):417–447.
E. Quaglietta et al (2016), The ON-TIME real-time railway traffic management framework: A proof-of-concept using a scalable standardised data communication architecture, Transportation Research Part C: Emerging Technologies, 63:23-50.

Mots-clefs: Gare de triage, fret ferroviaire, gestion des ressources, optimisation, algorithmes dynamiques

Laboratoire principal - Référent principal	COSYS - ESTAS - RODRIGUEZ Joaquin tél. : +33 320438332
Directeur du laboratoire principal	RODRIGUEZ Joaquin -
Laboratoire 2 - Référent	COSYS - LEOST - PELLEGRINI Paola - - tél. : +33 320438404
Spécialité de la thèse	Informatique et Recherche Opérationnelle
Axe	1 - COP2017 - Transporter efficacement et se déplacer en sécurité
Site principal	Lille-Villeneuve d'Ascq
Etablissement d'inscription	ECOLE CENTRALE LILLE
Ecole doctorale	MADIS
Directeur de thèse prévu	RODRIGUEZ Joaquin - Université Gustave Eiffel - COSYS - ESTAS
Co-directeur de thèse prévu	PELLEGRINI Paola - Université Gustave Eiffel - COSYS - ESTAS
Type de financement prévu	Contrat doctoral - Université Gustave Eiffel
Résumé Contexte : Le transport de marchandise est un sujet clef dans le cadre du développement durable. La part modale occupée par le ferroviaire a fortement décliné en France, passant d’un volume de 75 milliards de t.km en 1974 à 40 milliards de t.km en 2005. Cependant, les projections de l’AIE prévoient une augmentation de 43 % entre 2017 et 2050 (International Energy Agency (2019)). De nombreuses initiatives ont vu le jour depuis quelques années afin de redynamiser le fret ferroviaire et de favoriser sa compétitivité. Un élément crucial pour cette compétitivité est représenté par la gestion des gares de triage, qui cherche à minimiser les temps de voyage des cargaisons et maximiser la fiabilité du système. Ces gares sont des infrastructures complexes où de nombreuses décisions opérationnelles interdépendantes doivent être prises à intervalles réguliers. Hors, ces gares sont souvent gérées manuellement, à partir de règles d’exploitation empiriques adoptées au fil du temps par les exploitants. Leur gestion implique des prises de décisions sur plusieurs aspects complémentaires et difficiles. De plus, le mode de fonctionnement des gares, lié à leur topologie et aux opérations qui y sont menées, peut être très différent. On peut identifier deux types principaux de topologie qui ont un fort impact sur le mode de fonctionnement : d’une part les gares avec butte (shunting yard) où les wagons des trains sont découplés puis distribués sur les rails de la gare afin de former de nouveaux trains sortants (Boysen et al (2012)); d’autre part les gares de transbordement (transshipment yards) où des containers standardisés sont transférés d’un moyen de transport à un autre (rail-rail, rail-route, rail-maritime) à l’aide de grues et de voitures de transport sur rail (Boysen et al (2013)). Objectifs de la thèse : Le sujet de cette thèse, qui se déroulera au sein du groupe Trafic des laboratoires ESTAS et LEOST du COSYS, est de proposer des modèles mathématiques ainsi que des algorithmes d’optimisation, afin de pouvoir gérer une gare de triage générique et la totalité de ses aspects opérationnels de manière efficace. Il est à noter qu’un telle approche est inexistante à l’heure actuelle, du à deux verrous scientifiques et techniques principaux : 1) La différence, parfois importante, de mode de fonctionnement des gares de triages rend difficile leur modélisation mathématique unifiée qui puissent prendre en compte les spécificités de chacune. 2) La gestion intégrée de toutes les opérations qui interviennent dans la gestion d’une gare présente une grande complexité computationnelle. En effet, le nombre de variables de décision et de contraintes s’avère très important lorsque tous les sous-problèmes sont considérés conjointement. Chacun de ces sous-problèmes a été démontré être NP-difficile (voir, e.g., Fedtke and Boysen (2017)), ce qui rend le problème à l’échelle de la gare particulièrement complexe. État de l’art : La thématique de la gestion des gares de triage a été explorée dans la littérature mais avec de claires limitations du point de vue opérationnel. Premièrement, les approches existantes se contentent d’étudier un ou deux des sous-problèmes de manière indépendante. Par exemple, Cichenski et al. (2017) traitent à la fois les problèmes de partitionnement des trains pour les placer séquentiellement sous les grues dans une gare a transbordement, de positionnement exacte de chaque train ainsi que de localisation des containers à placer sur ces mêmes trains. Néanmoins, la gestion des grues et les mouvements des trains restent exclus du processus d’optimisation. Deuxièmement, la plupart des approches se concentre sur une topologie spécifique. Des pistes concrètes permettant de formuler des algorithmes de traitement de gares présentant des modes de fonctionnement différents ont été proposées lors du projet européen OPTIYARD (financé dans le cadre du programme H2020 et du Joint Undertaking Shift2Rail) auquel a participé l’équipe encadrante de cette thèse. Ce projet était centré sur la gestion optimisée d’une gare de triage (Licciardello et al (2020)) : une modélisation générique des ressources a permis de considérer à la fois une gare avec butte ainsi qu’un port multi-modal avec transbordement, en appréhendant leurs ressources à travers un problème d’ordonnancement de tâches sous contrainte. Un algorithme glouton stochastique développé sur la base de cette modélisation a été intégré à un simulateur microscopique pour vérifier la faisabilité de toutes les opérations effectuées. Démarche de travail : Le travail de thèse se basera sur le résultat du projet OPTIYARD en en reprenant la puissance de modélisation unifiée. Il visera en premier lieu à proposer des approches basées sur la programmation mathématique linéaire en nombres entiers qui est un outil puissant et consolidé. Ces approches devront traiter de manière intégrée plusieurs problèmes difficiles, ce qui a tendance à produire des modèles au nombre de variables et de contraintes prohibitif. Une possibilité encore non explorée dans la littérature consiste à utiliser des méthodes avancées de programmation mathématique qui permettent de décomposer le problème maître en divers sous-problèmes et de profiter de méthodes de résolutions existantes pour ces sous-problèmes. La thèse se propose de tester des méthodes telles que la Génération de colonnes ou la Décomposition de Benders pour lesquelles l’équipe d’encadrement possède une certaine compétence (Keita et al (2020), Hosteins and Scatamacchia (2020)). Dans un second temps, la thèse s’attaquera au problème de gestion des gares de triage en considérant le fait que les contraintes opérationnelles contraignent souvent les exploitants à revoir le planning des opérations en fonction des nouveaux trains en approche. Cette situation implique une réoptimisation récurrente et se traduit par un problème d’optimisation en temps réel ou dynamique. Les problèmes de ce type nécessitent la production rapide de nouvelles solutions et donc d’algorithmes heuristiques adaptés. Lorsque les ressources de la gare sont en quantité limitée, les algorithmes heuristiques ont parfois des difficultés à produire des solutions faisables et des stratégies adaptées devront être mises au point pour traiter le problème de manière efficace. L’équipe d’encadrement possède des compétences avancées en terme d’optimisation en temps réel pour le trafic ferroviaire, démontrées lors des projets européens ONTIME (Quaglietta et al (2016)) ainsi que OPTIYARD (Licciardello et al (2020)), et ces compétences seront mises à profit pour concevoir et développer des algorithmes heuristiques pertinents. Déroulement de la thèse : La thèse débutera par l'étude de l’état de l’art concernant les méthodes d’optimisation pour les gares de triage. Elle s’attaquera ensuite à la consolidation des résultats du projet OPTIYARD en implémentant un modèle linéaire en nombres entiers qui permette de résoudre le problème dérivant de la modélisation unifiée conçue par ce même projet. Ensuite, des méthodes de programmation mathématique avancées seront développées pour gérer ces problèmes difficiles, puis des heuristiques adaptées seront mises au point afin de pouvoir fournir des solutions en temps réel dans un contexte opérationnel, si les approches exactes ne sont pas assez rapides. Des expérimentations sur des cas d’études réels permettront de comprendre le gain potentiel d’une gestion automatisée et optimisée d’une gare de triage dans différentes configurations. Tout le long de la thèse, les résultats seront présentés à des conférences nationales et internationales (par exemple, MT-ITS - International Conference on Models and Technologies for Intelligent Transportation Systems). Lorsque les modèles et algorithmes auront atteint le niveau de maturité approprié ils feront l’objet de publications dans des revues internationales à comité de lecture (par exemple, Transportation Research Part B : Methodological, ou IEEE Transactions on intelligent transportation systems). Profil du candidat : Le candidat doit être titulaire d’un Master en recherche opérationnelle, informatique, intelligence artificielle, mathématique appliquée ou équivalent. Une bonne connaissance du langage de programmation C++ et de la langue anglaise (à l’écrit et à l’oral) sont des prérequis importants. Une familiarité avec les outils et logiciels de la programmation mathématique ou avec le domaine du transport ferroviaire sera appréciée. Références bibliographiques N. Boysen et al (2012), Shunting yard operations: Theoretical aspects and applications, European Journal of Operational Research, 220(1):1–14. N. Boysen et al (2013), A survey on container processing in railway yards, Transportation Science, 47(3):312–329. M. Cichenski et al (2017). An integrated model for the transshipment yard scheduling problem. Journal of Scheduling, 20:57–65. S. Fedtke and N. Boysen (2017), Gantry crane and shuttle car scheduling in modern rail–rail transshipment yards, OR Spectrum, 39:473–503. P. Hosteins and R. Scatamacchia (2020), The stochastic Critical Node Problem over trees, Networks, 76(3):381–401. International Energy Agency (2019), The Future of Rail Opportunities for energy and the environment. K. Keita, P. Pellegrini, J. Rodriguez (2020), A three-step Benders decomposition for the real-time Railway Traffic Management Problem, Journal of Rail Transport Planning and Management, 13:100170. R. Licciardello, N. Adamko, S. Deleplanque, P. Hosteins, R. Liu, P. Pellegrini, A. Peterson, M. Wahlborg, M. Za’tko (2020), Integrating yards, network and optimisation models towards real-time rail freight yard operations, Ingegneria Ferroviaria, 75(6):417–447. E. Quaglietta et al (2016), The ON-TIME real-time railway traffic management framework: A proof-of-concept using a scalable standardised data communication architecture, Transportation Research Part C: Emerging Technologies, 63:23-50.
Mots-clefs:	Gare de triage, fret ferroviaire, gestion des ressources, optimisation, algorithmes dynamiques

Liste des sujets

Candidatures fermées