Th
Forum 'Emplois' - Sujet créé le 2013-02-27
Optimisation robuste de tables horaires ferroviaires à l'aide de métaheuristiques hybrides et d'apprentissage.
Mots-clefs : Transport ferroviaire, planification horaire, optimisation, métaheuristique, algorithme évolutionnaire, hybridation, apprentissage
Financement : Bourse Ifsttar (environ 1700€ brut, puis 2000€ brut en 3ème année)
Encadrement : Joaquin Rodriguez, DR Ifsttar ; Rémy Chevrier, CR Ifsttar
Lieu de travail : Ifsttar Lille - Villeneuve d'Ascq
Compétences requises : Solides connaissances en Recherche Opérationnelle et en programmation (Java ou C/C++). Une bonne connaissance de l'optimisation sous incertitude et des métaheuristiques serait appréciable.
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
Dans le transport ferroviaire, la construction des tables horaires 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 [1,2].
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 l'offre de transport. L'élaboration d'une table horaire intègre également la recherche de ces marges horaires, compromis entre l'effet amortisseur des perturbations et une bonne utilisation de la capacité.
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 [3] ou approchées comme des métaheuristiques [4], éventuellement hybrides [5].
L'objectif de cette thèse est de proposer une méthode d'optimisation multicritère de table horaire robuste aux perturbations stochastiques. Les critères d'optimisation sont, d'une part, la maximisation de la robustesse de la table horaire (selon des indicateurs à définir) et, d'autre part, la minimisation de la consommation de la capacité ferroviaire (à couverture du réseau constante).
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. À 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 [6,7]. À ce niveau, une méthode hybride d'optimisation pourra être proposée et développée.
Bibliographie
[1] J. Pachl, Timetable Design Principles, chap. in Railway Timetable & trafic, eds Ingo A. Hansen et Jörn Pachl, Eurail Press, pp. 9-42, 2008.
[2] A. Caprara, M. Fischetti et P. Toth, Modeling and solving the train timetabling problem. Operations Research, 50(5), pp. 851-861, 2002.
[3] A. Higgins, E. Kozan et L. Ferreira, Optimal scheduling of trains on a single line track. Transportation Research Part B : Methodological, 30(2), pp. 147-161, 1996.
[4] O. Engelhardt-Funke et M. Kolonko, Analysing stability and investments in railway networks using advanced evolutionary algorithms. International Transactions in Operational Research, 11(4), pp.381-394, 2004.
[5] Y. Semet et M. Schoenauer, An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling, in The 2005 IEEE Congress on Evolutionary Computation, pp. 2752-2759, 2005.
[6] D. Corne, C. Dhaenens et L. Jourdan, Synergies between Operations Research and Data Mining: the emerging use of multi-objective approaches, in European Journal of Operational Research, pp. 469-479, 2012.
[7] L. Jourdan, C. Dhaenens et E.-G. Talbi, Using Datamining Techniques to Help Metaheuristics: A Short Survey, in Hybrid Metaheuristics, pp 57-69, 2006.
Mots-clefs : Transport ferroviaire, planification horaire, optimisation, métaheuristique, algorithme évolutionnaire, hybridation, apprentissage
Financement : Bourse Ifsttar (environ 1700€ brut, puis 2000€ brut en 3ème année)
Encadrement : Joaquin Rodriguez, DR Ifsttar ; Rémy Chevrier, CR Ifsttar
Lieu de travail : Ifsttar Lille - Villeneuve d'Ascq
Compétences requises : Solides connaissances en Recherche Opérationnelle et en programmation (Java ou C/C++). Une bonne connaissance de l'optimisation sous incertitude et des métaheuristiques serait appréciable.
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
Dans le transport ferroviaire, la construction des tables horaires 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 [1,2].
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 l'offre de transport. L'élaboration d'une table horaire intègre également la recherche de ces marges horaires, compromis entre l'effet amortisseur des perturbations et une bonne utilisation de la capacité.
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 [3] ou approchées comme des métaheuristiques [4], éventuellement hybrides [5].
L'objectif de cette thèse est de proposer une méthode d'optimisation multicritère de table horaire robuste aux perturbations stochastiques. Les critères d'optimisation sont, d'une part, la maximisation de la robustesse de la table horaire (selon des indicateurs à définir) et, d'autre part, la minimisation de la consommation de la capacité ferroviaire (à couverture du réseau constante).
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. À 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 [6,7]. À ce niveau, une méthode hybride d'optimisation pourra être proposée et développée.
Bibliographie
[1] J. Pachl, Timetable Design Principles, chap. in Railway Timetable & trafic, eds Ingo A. Hansen et Jörn Pachl, Eurail Press, pp. 9-42, 2008.
[2] A. Caprara, M. Fischetti et P. Toth, Modeling and solving the train timetabling problem. Operations Research, 50(5), pp. 851-861, 2002.
[3] A. Higgins, E. Kozan et L. Ferreira, Optimal scheduling of trains on a single line track. Transportation Research Part B : Methodological, 30(2), pp. 147-161, 1996.
[4] O. Engelhardt-Funke et M. Kolonko, Analysing stability and investments in railway networks using advanced evolutionary algorithms. International Transactions in Operational Research, 11(4), pp.381-394, 2004.
[5] Y. Semet et M. Schoenauer, An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling, in The 2005 IEEE Congress on Evolutionary Computation, pp. 2752-2759, 2005.
[6] D. Corne, C. Dhaenens et L. Jourdan, Synergies between Operations Research and Data Mining: the emerging use of multi-objective approaches, in European Journal of Operational Research, pp. 469-479, 2012.
[7] L. Jourdan, C. Dhaenens et E.-G. Talbi, Using Datamining Techniques to Help Metaheuristics: A Short Survey, in Hybrid Metaheuristics, pp 57-69, 2006.