Accueil > FR > Informations générales > Stages > Amélioration des voisinages de routing de véhicules

Amélioration des voisinages de routing de véhicules

Profil Etudiant universitaire, niveau master
Prérequis Connaissances de la programmation (si possible : Scala), de l’algorithmique (recherche locale)
Durée Minimum 6 semaines

Contexte

OscaR est un toolkit Open Source de recherche opérationnelle. Il comprend notamment un moteur de type recherche locale basée sur des contraintes (CBLS) et un moteur de programmation p ar contrainte (CP).

Le principe de base est de représenter un problème par une formule, découpée en opérateurs et variables intermédiaires, et de construire un graphe représentant cette formule. Sur base de ce graphe, on peut rapidement mettre à jour les variables de sorties suite à une modification sur les variables d’entrées. Cette mise à jour s’appelle la propagation.

Cette approche est très efficace et permet de résoudre des problèmes de grande taille. Par exemple, le problème des "N reines" à 50000 reines peut être résolu en une grosse vingtaine de seconde, et des problèmes de scheduling de plusieurs centaines de tâches peuvent être traités efficacement.
Le module CBLS d’OscaR est écrit en Scala, un langage multiparadigme très efficace pour programmer ce type d’application.

Oscar.CBLS dispose déjà d’un module de routing implémentant les voisinages classiques de recherche locale : 3-opt, 1pt move, etc. Le stage consiste à améliorer l’efficacité de ce moteur en implémentant un mécanisme d’accélération spécifique à l’approche par recherche locale. Lorsqu’on utilise un voisinage, on essaie une série de mouvements, jusqu’à en trouver un qui permette d’améliorer la solution. Ce mouvement est appliqué, et l’exploration recommence, ou continue, typiquement à partir du point où elle s’est arrêtée.

Actuellement, le constat est que procédure recherche essaie de manière récurrente les mêmes mouvements qui se révèle généralement tout aussi non prometteurs que lors de leur première évaluation.

Travail à réaliser

L’idée est d’éviter de réévaluer les mêmes mouvements de manière répétée, et ne se consacrer en priorité qu’à vérifier un ensemble de mouvements prometteurs. Lorsqu’on fait un mouvement, de nouveaux mouvements intéressants peuvent probablement être trouvés dans la zone concernée par ce mouvement. Le principe est donc, de consigner les zones modifiées comme « hot spots », et de chercher des améliorations en priorité dans ces « hot spots ». Une zone « hot spot » serait « refroidie » suite à une exploration de voisinage infructueuse.

Le but de ce stage est de proposer une implémentation de ce principe, de manière à accélérer la recherche pour des problèmes de routage.
Le sujet vise à proposer :

  • Une implémentation ou un principe efficace de gestion des hotspot
  • Une adaptation des voisinages existants qui explore préférentiellement les zones marquées comme « hot spots ». Cela concerne tous les voisinages disponibles (point insert, point remove, one point move, two-opt, swap, three-opt)
  • Une étape de benchmarking permettant de mettre en évidence le gai réalisé par cette amélioration

On peut aussi noter que d’autres dimensions peuvent intervenir, tels le temps libre avant le commencement d’une tâche, si l’on utilise des time window. La solution proposée devra donc permettre de customiser le marquage des hot spots sur base de critères adaptable facilement à toute situation.

Tout le travail sera encadré, mais nécessitera un minimum d’autonomie. Il s’agit d’un stage à forte connotation algorithmique, sur un outil Open Source en pleine expansion.

Encadrement

Tout le travail sera encadré, mais nécessitera un minimum d’autonomie. Il s’agit d’un stage à forte connotation algorithmique, sur un outil Open Source en pleine expansion.

Profil souhaité : universitaire

Références

Contact : Renaud De Landtsheer email : rdl@cetic.be