Optimisation de Routage de Véhicule Progressif

Optimisation de Routage de Véhicule Progressif

Profil Etudiant.e niveau fin de bac ou master
Prérequis Bonne maîtrise de la programmation et affinités marquées pour l’algorithmique. Bases en programmation fonctionnelles. (en particulier Scala)
Durée Minimum 12 semaines, possibilité de stage étendu (4 mois) avec phase d’apprentissage des bases nécessaires de Scala.

L’adéquation du candidat sera validée préalablement au démarrage du stage, et le sujet peut être ajusté au stagiaire si nécessaire.

Département: Algorithmique combinatoire ⊕

Expertises:

Algorithmique et Optimisation Combinatoire ⊕

Asset: OscaR.cbls ⊕

Contacts

Contexte

OscaR.cbls est un moteur d’optimisation par recherche locale basé sur des contraintes qui est développé par le CETIC en Scala. OscaR.cbls est open source, sous licence LGPL. OscaR.cbls dispose d’un moteur d’optimisation de routage à l’état de l’art.

Objectif du stage

L’objectif du stage est d’explorer la possibilité de faire du routage de véhicule progressif.

Contrairement à un TSP classique, le problème d’optimisation n’est pas connu dans sa totalité à l’avance. Au lieu de cela, les points à atteindre sont ajoutés petit à petit, et l’algorithme de routage doit à tout moment proposer une solution partielle qui tienne compte des points connus et d’une distribution géographique des points à venir. Cette solution partielle doit spécifier la tâche à accomplir : aller à un point ; attendre, etc.

Le stage se basera sur une approche simple consistant à traduire le problème partiel avec points inconnus en un problème complet où on rajoute des points fictifs représentant la demande future. Le problème complet se traite facilement à l’aide d’OscaR.cbls en utilisant des scripts déjà disponibles.

Le/la stagiaire devra :

  • Définir un format de fichier pour représenter un problème de routage progressif.
  • Développer une procédure de génération aléatoire de points, qui servira à la fois à générer des exemples et à la fois à générer des points fictifs dans le solveur.
  • Implémenter un solveur de problèmes progressifs, qui fonctionnera en mode interactif et utilisera un solveur de routage existant.
  • Développer un simulateur qui injectera les points au fur et à mesure dans le solveur.

L’objectif du stage est de produire un PoC, donc de se focaliser sur la fonctionnalité en simplifiant le problème le plus possible.

Encadrement

Il est prévu que le/la stagiaire aie du temps et de l’encadrement pour apprendre le langage Scala et le moteur OscaR.cbls. Tout le travail sera encadré, mais nécessitera un minimum d’autonomie.

Le stage se déroulera dans le département d’algorithmique combinatoire du CETIC (COAL) comprenant 5 personnes dont 4 PhD et un Master en IT.

Références

Contact : Renaud De Landtsheer