Le 30/11/2018 par hosteins :

Stage de développement algorithmique et logiciel en Recherche Opérationnelle :
Génération de colonnes pour la gestion du trafic ferroviaire

Contexte:
Ce stage sera effectué dans l’équipe Trafic du laboratoire ESTAS (Évaluation
des Systèmes Automatisés et de leur Sécurité) de l’institut IFSTTAR. Il a pour
objectif l’implémentation de techniques de Programmation Mathématique avan-
cées pour un problème de gestion du trafic ferroviaire. Le modèle d’optimisation
utilisé par l’équipe Trafic se nomme RECIFE et résout un problème de gestion
opérationnelle de trafic ferroviaire basé sur le reroutage et l’ordonnancement
des différents trains afin de minimiser la propagation de retards sur le réseau
ferroviaire. Il se base sur une modélisation linéaire en variables entières qui a
démontré être une technique générale particulièrement efficace pour affronter
les problèmes de Recherche Opérationnelle. Le modèle fait face à un problème
de multiplication exponentielle des variables de décision lorsque l’infrastructure
considérée devient trop grande et/ou complexe et des méthodes de résolution
plus sophistiquées doivent être envisagées pour faire face à ces situations.

Objectifs:
Ce stage vise à l’implémentation de méthodes de génération de colonnes afin
de résoudre le problème linéaire en nombres entiers utilisé pour modéliser le
problème de gestion du trafic. Il nécessitera de :
— déterminer le coût réduit des variables de routage, en fonction des variables
duales de la relaxation linéaire du modèle ;
— implémenter la résolution itérative de la relaxation linéaire par la méthode
de génération de colonnes, en déterminant les routes les plus utiles à la
résolution du problème grâce aux coûts réduits déduits précédemment ;
— inclure la méthode de génération de colonnes dans une structure algorith-
mique de branch-and-bound, de sorte à résoudre le problème en nombres
entiers à travers une stratégie de branching ;
— tester l’algorithme de branch-and-price sur une infrastructure où le nombre
de routes devient problématique pour le modèle.

Plan de travail:
1. Étude bibliographique,
2. Design de l’algorithme de branch-and-price,
3. Choix des structures de données,
4. Implémentation et expérimentations,
5. Optimisation des performances.
Profil du candidat
Niveau:
— Bac+4-5 si possible
Durée:
— 3 à 6 mois (rémunéré)
Compétences appréciées (mais non obligatoires):
— Génie logiciel,
— Connaissance des méthodes d’optimisation (Recherche Opérationnelle), de
préférence programmation linéaire en nombres entiers (simplex, dualité...),
— Langage de programmation (C++),
— Système d’exploitation Linux,
— Anglais technique

Encadrement:
Pierre HOSTEINS, Chargé de Recherche
IFSTTAR Villeneuve d’Ascq, 20 Rue Élisée Reclus, 59650
Tel : 03 20 43 83 58
Mail : pierre.hosteins@ifsttar.fr