Heuristique de démarrage pour l'optimisation de routage de véhicules

Heuristique de démarrage pour l’optimisation de routage de véhicules

Profil Étudiant(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 fonctionnelle (en particulier Scala)
Durée Minimum 10 semaines, possibilité de stage étendu à condition d’étendre le sujet (4 mois) avec phase d’apprentissage des bases nécessaires de Scala

L’adéquation du candidat ou de la candidate 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 moteurs d’optimisation de routage à l’état de l’art qui permet de traiter des problèmes de routage de véhicule sous contraintes à l’aide de voisinages de recherche et de méta-heuristiques.

Objectif du stage

L’objectif du stage est de développer une heuristique de démarrage pour des problèmes de routage de véhicules en utilisant l’algorithme de Christofides. Il s’agit d’un algorithme bien connu qui construit une route de relativement bonne qualité en se basant notamment un arbre sous-tendant de poids minimal obtenu via l’algorithme de Kruskal.
Le challenge technique consiste à interfacer cette heuristique avec le moteur d’optimisation sachant que cette heuristique sera utilisée pour traiter des problèmes de routage sous contraintes et que l’heuristique ne permet pas de tenir compte de contraintes.

Le stage consistera donc à

  • Implémenter l’algorithme de Christofides
  • Etudier la différence entre une approche constructive comme celle de Christofides et une approche itérative comme la recherche locale
  • Proposer une adaptation logique entre ces eux approches
  • Implémenter un voisinage de recherche locale qui repose sur l’algorithme de Christofides
  • Faire quelque benchmarks de la solution

Encadrement

Il est prévu que le 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