Projet.
J'ai participé à une ACI "Jeunes chercheuses, Jeunes chercheurs" de 2005 à 2007 dont le thème est "planification et gestion optimisée des ressources en transport: ré-optimisation et hybridation de la génération de colonnes et des métaheuristiques". Le responsable du projet est Anass NAGIH; l'équipe est également composée de Lucas LÉTOCART, Sophie TOULOUSE, Laurent ALFANDARI et Agnès PLATEAU.
Description du projet.
Nous nous sommes intéressés à la résolution de modèles génériques issus des problématiques de planification en transport; ces problèmes sont difficiles de par leur taille et l'intégrité de leurs variables. Le but du projet était double : d'une part, apporter des justifications théoriques au bon comportement des schémas de génération de colonnes existants; d'autre part, améliorer ces méthodes par la ré-optimisation et l'utilisation de méthodes de type métaheuristique
Partenaire industriel. SNCF
Partenaire académique. Groupe d'Études et de Recherche en Analyse des Décisions (GERAD)
Mes Contributions.
- Exposés dans le cadre du groupe de travail ACI.
- Deux Rapports de contrat SNCF-LIPN
- ``Méthodes de décomposition pour l'optimisation discrète: Application aux problèmes de transport'' (48 pages).
- ``Décomposition lagrangienne et génération de colonnes pour la planification optimale de locomotives'' (46 pages).
- Co-encadrement d'un stage de Master 2 Mathématique et Informatique sur la formulation de la décomposition lagrangienne du problème de planification optimale des locomotives et sa résolution avec la génération de colonnes.
- Implémentation de nouveaux modules associés aux différentes approches proposées dans le cadre de mes travaux de recherche et leur intégration dans la plateforme logicielle COGiTO. Pour résumer, les principales implantations sont:
- Deux modules pour l'accélération de la méthode de génération de colonnes lors des premières itérations (basés sur la diversification).
- Un module pour l'accélération de la méthode de génération de colonnes lors des dernières itérations (basé sur la ré-optimisation).
- Trois modules permettant de combiner et hybrider ces deux améliorations (la diversification et la ré-optimisation).
- Un module pour l'accélération de la résolution des sous-problèmes (programmation dynamique par blocs).
Brevet.
La plateforme logicielle COlumn Generation in Transport Optimization (COGiTO) est une des composantes du projet ACI développée au LIPN entre 2004 et 2007.
La plateforme consiste à mettre en application des travaux de recherche basés sur des méthodes de résolution de problèmes d'optimisation. Il s'agit donc de pouvoir résoudre une instance d'un problème pour un modèle à l'aide d'une ou de plusieurs méthodes de résolution paramétrables. Elle a été conçue dans le cadre de la planification et de la gestion des opérations en transport où les problèmes d'optimisation aboutissent à des modèles de très grande taille. La méthode de résolution de base implantée dans le logiciel pour la résolution de ces modèles est un schéma de génération de colonnes. à partir de ce noyau, divers algorithmes sont également disponibles pour la résolution des sous-problèmes (formulés sous forme de Programmes Linéaires (PL) ou de graphes). Ces algorithmes sont de type algorithmes de plus court chemin, de flot et de programmation dynamique.
Une procédure de dépôt de brevet par l'Université Paris 13 a été effectuée. Ce dépôt de brevet porte notemment sur trois contributions de mon travail de thèse à savoir la diversification, la ré-optimisation et la programmation dynamique par blocs.