Le domaine des stages proposés
est la recherche opérationnelle et plus précisément le domaine des
problèmes de tournées de véhicules
2010-2011 :
-
Sujet 1 : Méta-heuristique pour le problème de recherche de plus
court chemin élémentaire contraint en ressource à coût dépendant du
temps.
Une méthode complexe, basée sur les principes de génération de
colonnes, a été récemment proposée pour résoudre le problème de routage
de véhicules avec fenêtres de temps et routes multiples.
La génération de colonnes est une méthode permettant de résoudre efficacement les programmes linéaires contenant un très grand nombre de variables. Son prince est de résoudre alternativement un « Problème Maitre Restreint » et un « Sous-Problème ». Le « Problème Maitre Restreint » correspond à la relaxation linéaire du programme initial restreint à un sous ensemble de variables. Il est généralement résolu par la méthode du simplexe. Le « Sous-Problème » consiste à rechercher des variables de coûts réduits négatifs dans l’ensemble des variables du programme initial, pour les ajouter à l’ensemble des variables du « Problème Maitre Restreint », avant de commencer une nouvelle itération. Ce processus s’arrête lorsque que le « Sous-Problème » ne trouve plus de variable pouvant améliorer la solution actuelle. Le Sous-problème d’un schéma de génération de colonnes est généralement NP-difficile et constitue la majeure partie du temps consacré à la résolution du programme initial.
L’objectif de ce stage est de proposer un algorithme permettant de résoudre, de façon approché, le sous-problème du schéma de génération de colonne proposé. Ce sous-problème correspond à un problème de recherche de plus court chemin contraint en ressource à travers un graphe. Le candidat devra dans un premier temps faire une revu bibliographique sur les méthodes approchées utilisées dans le domaine des problèmes de routage de véhicules.
Pré-requis : C++, algorithmique
La génération de colonnes est une méthode permettant de résoudre efficacement les programmes linéaires contenant un très grand nombre de variables. Son prince est de résoudre alternativement un « Problème Maitre Restreint » et un « Sous-Problème ». Le « Problème Maitre Restreint » correspond à la relaxation linéaire du programme initial restreint à un sous ensemble de variables. Il est généralement résolu par la méthode du simplexe. Le « Sous-Problème » consiste à rechercher des variables de coûts réduits négatifs dans l’ensemble des variables du programme initial, pour les ajouter à l’ensemble des variables du « Problème Maitre Restreint », avant de commencer une nouvelle itération. Ce processus s’arrête lorsque que le « Sous-Problème » ne trouve plus de variable pouvant améliorer la solution actuelle. Le Sous-problème d’un schéma de génération de colonnes est généralement NP-difficile et constitue la majeure partie du temps consacré à la résolution du programme initial.
L’objectif de ce stage est de proposer un algorithme permettant de résoudre, de façon approché, le sous-problème du schéma de génération de colonne proposé. Ce sous-problème correspond à un problème de recherche de plus court chemin contraint en ressource à travers un graphe. Le candidat devra dans un premier temps faire une revu bibliographique sur les méthodes approchées utilisées dans le domaine des problèmes de routage de véhicules.
Pré-requis : C++, algorithmique
- Sujet 2 : Généralisation d’une méthode de génération de colonnes permettant de résoudre le problème de routage de véhicule avec fenêtre de temps et routes multiples et une de ses variantes.
Une méthode complexe, basée sur les principes de génération de
colonnes, a été récemment proposée pour résoudre le problème de routage
de véhicules avec fenêtres de temps et routes multiples.
La génération de colonnes est une méthode permettant de résoudre efficacement les programmes linéaires contenant un très grand nombre de variables. Son prince est de résoudre alternativement un « Problème Maitre Restreint » et un « Sous-Problème ». Le « Problème Maitre Restreint » correspond à la relaxation linéaire du programme initial restreint à un sous ensemble de variables. Il est généralement résolu par la méthode du simplexe. Le « Sous-Problème » consiste à rechercher des variables de coûts réduits négatifs dans l’ensemble des variables du programme initial, pour les ajouter à l’ensemble des variables du « Problème Maitre Restreint », avant de commencer une nouvelle itération. Ce processus s’arrête lorsque que le « Sous-Problème » ne trouve plus de variable pouvant améliorer la solution actuelle.
L'objectif de ce stage est de modifier l'algorithme utilisé pour résoudre le sous-problème du schéma de génération de colonnes proposé. L'algorithme original gère le routage de véhicules avec fenêtres de temps et routes multiples. Le nouvel algorithme devra permettre de fournir une méthode exacte pour un problème similaire, mais dans lequel la longueur des routes est limitée. Le candidat devra dans un premier temps assimilé les techniques complexes généralement utilisées dans un schéma de génération de colonnes.
Pré-requis : C++, programmation linéaire
La génération de colonnes est une méthode permettant de résoudre efficacement les programmes linéaires contenant un très grand nombre de variables. Son prince est de résoudre alternativement un « Problème Maitre Restreint » et un « Sous-Problème ». Le « Problème Maitre Restreint » correspond à la relaxation linéaire du programme initial restreint à un sous ensemble de variables. Il est généralement résolu par la méthode du simplexe. Le « Sous-Problème » consiste à rechercher des variables de coûts réduits négatifs dans l’ensemble des variables du programme initial, pour les ajouter à l’ensemble des variables du « Problème Maitre Restreint », avant de commencer une nouvelle itération. Ce processus s’arrête lorsque que le « Sous-Problème » ne trouve plus de variable pouvant améliorer la solution actuelle.
L'objectif de ce stage est de modifier l'algorithme utilisé pour résoudre le sous-problème du schéma de génération de colonnes proposé. L'algorithme original gère le routage de véhicules avec fenêtres de temps et routes multiples. Le nouvel algorithme devra permettre de fournir une méthode exacte pour un problème similaire, mais dans lequel la longueur des routes est limitée. Le candidat devra dans un premier temps assimilé les techniques complexes généralement utilisées dans un schéma de génération de colonnes.
Pré-requis : C++, programmation linéaire