Th
Forum 'Emplois' - Sujet créé le 2012-04-24
Proposition de thèse à l'Ifsttar Lille - Villeneuve d'Ascq.
Optimisation robuste de tables horaires ferroviaires à l'aide de métaheuristiques hybrides et d'apprentissage.
Dans le transport ferroviaire, la construction des horaires est une tâche délicate, qui consiste à définir pour chaque train, ses horaires de départ, voire de passage, en chaque gare [1]. Cette construction repose sur un ensemble de données et contraintes, parmi lesquelles on peut citer les temps de parcours, les correspondances et les priorités des trains les uns par rapport aux autres.
Les temps de parcours ainsi que les temps d'arrêt sont utilisés de manière déterministe pour construire les horaires, or il s'avère que, dans un cadre concret d'exploitation, des perturbations peuvent survenir dans le réseau et augmenter ces temps, et provoquer ainsi des retards par rapport à la table horaire. En général, pour amortir les effets de ces perturbations, une marge horaire est ajoutée à ces temps de parcours (elle correspond à quelques pour cents du temps de parcours). Cependant, l'ajout de marges horaires distend les temps de voyage et peut, de fait, réduire la fréquence de circulation des trains. L'élaboration d'une table horaire intègre également la recherche de ces marges horaires, compromis entre l'effet amortisseur des perturbations et l'amélioration du cadencement des trains.
D'une manière générale, cette construction introduit énormément de variables (plusieurs centaines de milliers pour un réseau national !) et nécessite le développement de méthodes d'optimisation spécifiques, exactes (voir PESP [2]) ou des métaheuristiques (éventuellement hybrides) [3].
L'objectif de cette thèse est de proposer une méthode évolutionnaire d'optimisation de table horaire robuste aux perturbations stochastiques.
Pour développer une telle méthode intégrant l'incertitude inhérente à la circulation ferroviaire, il s'agira en premier lieu, d'identifier les perturbations stochastiques pouvant survenir dans ce type de système, pour ensuite en fournir une modélisation statistique. À partir de là, des jeux de données stochastiques pourront être développés en vue des expérimentations pour étudier l'influence des perturbations.
Suite à cette étude, l'influence des perturbations stochastiques pourra être modélisée dans la planification horaire ferroviaire. Cette modélisation se basera soit sur des lignes virtuelles construites sur simulateur, soit sur des données réelles comme la ligne Utrecht-Den Bosch (Pays-Bas). À terme, cette modélisation doit permettre une meilleure prise en compte des phénomènes stochastiques dans la construction de la table horaire afin d'en améliorer sa robustesse, c'est-à-dire sa tolérance vis-à-vis des perturbations.
La construction de la table horaire se fera dans un premier temps avec une métaheuristique classique telle qu'un algorithme génétique. De plus, afin d'orienter l'optimisation, un apprentissage pourra être introduit dans l'évaluation ou dans la reconnaissance d'une « bonne » solution [4,5]. À ce niveau, une méthode hybride d'optimisation pourra être proposée et développée. À la lumière des résultats obtenus sur un ensemble de simulations, une réflexion sur les ensembles d'apprentissage sera menée.
Bibliographie
[1] Pachl, J., Timetable Design Principles, chap. in Railway Timetable & trafic, eds Ingo A. Hansen et Jörn Pachl, Eurail Press, pp. 9–42, 2008.
[2] Kroon, L., Huisman, D. et Maróti, G., Optimisation Models for Railway Timetabling, chap. in Railway Timetable & trafic, eds Ingo A. Hansen et Jörn Pachl, Eurail Press, pp. 135–154, 2008.
[3] Semet, Yann et Schoenauer, Marc , An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling, in The 2005 IEEE Congress on Evolutionary Computation, 2005, pp. 2752- 2759, 2005.
[4] Corne, D, Dhaenens C. et Jourdan L., Synergies between Operations Research and Data Mining: the emerging use of multi-objective approaches, Rapport de recherche, accepté pour publication dans European Journal of Operational Research.
[5] Jourdan, L, Dhaenens C. et Jourdan L. Using Datamining Techniques to Help Metaheuristics: A Short Survey. Hybrid Metaheuristics 2006, pp 57-69
Mots-clefs : Transport ferroviaire, planification horaire, optimisation, métaheuristique, algorithme évolutionnaire, hybridation
Financement : Ifsttar (environ 1700€ brut, puis 2000€ brut en 3ème année)
Encadrement : Joaquin Rodriguez, DR Ifsttar ; Laetitia Jourdan, Professeur Université de Lille 1 ; Rémy Chevrier, CR Ifsttar
Lieu de travail : Ifsttar Lille - Villeneuve d'Ascq
Date limite : 4 mai 2012
Merci à tout candidat de faire parvenir un CV, les notes de M1 et M2, ainsi qu'une lettre de motivation.
Contact : Rémy Chevrier, remy.chevrier _at_ ifsttar.fr
Optimisation robuste de tables horaires ferroviaires à l'aide de métaheuristiques hybrides et d'apprentissage.
Dans le transport ferroviaire, la construction des horaires est une tâche délicate, qui consiste à définir pour chaque train, ses horaires de départ, voire de passage, en chaque gare [1]. Cette construction repose sur un ensemble de données et contraintes, parmi lesquelles on peut citer les temps de parcours, les correspondances et les priorités des trains les uns par rapport aux autres.
Les temps de parcours ainsi que les temps d'arrêt sont utilisés de manière déterministe pour construire les horaires, or il s'avère que, dans un cadre concret d'exploitation, des perturbations peuvent survenir dans le réseau et augmenter ces temps, et provoquer ainsi des retards par rapport à la table horaire. En général, pour amortir les effets de ces perturbations, une marge horaire est ajoutée à ces temps de parcours (elle correspond à quelques pour cents du temps de parcours). Cependant, l'ajout de marges horaires distend les temps de voyage et peut, de fait, réduire la fréquence de circulation des trains. L'élaboration d'une table horaire intègre également la recherche de ces marges horaires, compromis entre l'effet amortisseur des perturbations et l'amélioration du cadencement des trains.
D'une manière générale, cette construction introduit énormément de variables (plusieurs centaines de milliers pour un réseau national !) et nécessite le développement de méthodes d'optimisation spécifiques, exactes (voir PESP [2]) ou des métaheuristiques (éventuellement hybrides) [3].
L'objectif de cette thèse est de proposer une méthode évolutionnaire d'optimisation de table horaire robuste aux perturbations stochastiques.
Pour développer une telle méthode intégrant l'incertitude inhérente à la circulation ferroviaire, il s'agira en premier lieu, d'identifier les perturbations stochastiques pouvant survenir dans ce type de système, pour ensuite en fournir une modélisation statistique. À partir de là, des jeux de données stochastiques pourront être développés en vue des expérimentations pour étudier l'influence des perturbations.
Suite à cette étude, l'influence des perturbations stochastiques pourra être modélisée dans la planification horaire ferroviaire. Cette modélisation se basera soit sur des lignes virtuelles construites sur simulateur, soit sur des données réelles comme la ligne Utrecht-Den Bosch (Pays-Bas). À terme, cette modélisation doit permettre une meilleure prise en compte des phénomènes stochastiques dans la construction de la table horaire afin d'en améliorer sa robustesse, c'est-à-dire sa tolérance vis-à-vis des perturbations.
La construction de la table horaire se fera dans un premier temps avec une métaheuristique classique telle qu'un algorithme génétique. De plus, afin d'orienter l'optimisation, un apprentissage pourra être introduit dans l'évaluation ou dans la reconnaissance d'une « bonne » solution [4,5]. À ce niveau, une méthode hybride d'optimisation pourra être proposée et développée. À la lumière des résultats obtenus sur un ensemble de simulations, une réflexion sur les ensembles d'apprentissage sera menée.
Bibliographie
[1] Pachl, J., Timetable Design Principles, chap. in Railway Timetable & trafic, eds Ingo A. Hansen et Jörn Pachl, Eurail Press, pp. 9–42, 2008.
[2] Kroon, L., Huisman, D. et Maróti, G., Optimisation Models for Railway Timetabling, chap. in Railway Timetable & trafic, eds Ingo A. Hansen et Jörn Pachl, Eurail Press, pp. 135–154, 2008.
[3] Semet, Yann et Schoenauer, Marc , An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling, in The 2005 IEEE Congress on Evolutionary Computation, 2005, pp. 2752- 2759, 2005.
[4] Corne, D, Dhaenens C. et Jourdan L., Synergies between Operations Research and Data Mining: the emerging use of multi-objective approaches, Rapport de recherche, accepté pour publication dans European Journal of Operational Research.
[5] Jourdan, L, Dhaenens C. et Jourdan L. Using Datamining Techniques to Help Metaheuristics: A Short Survey. Hybrid Metaheuristics 2006, pp 57-69
Mots-clefs : Transport ferroviaire, planification horaire, optimisation, métaheuristique, algorithme évolutionnaire, hybridation
Financement : Ifsttar (environ 1700€ brut, puis 2000€ brut en 3ème année)
Encadrement : Joaquin Rodriguez, DR Ifsttar ; Laetitia Jourdan, Professeur Université de Lille 1 ; Rémy Chevrier, CR Ifsttar
Lieu de travail : Ifsttar Lille - Villeneuve d'Ascq
Date limite : 4 mai 2012
Merci à tout candidat de faire parvenir un CV, les notes de M1 et M2, ainsi qu'une lettre de motivation.
Contact : Rémy Chevrier, remy.chevrier _at_ ifsttar.fr