Implémentation de contrainte de fenêtre de temps pour le routage de véhicule pour l’optimisation par recherche locale

Implémentation de contrainte de fenêtre de temps pour le routage de véhicule pour l’optimisation par recherche locale

Profil Etudiant en fin de master universitaire en informatique
Prérequis Bonnes notions d’optimisation et programmation fonctionnelle (en Scala)
Durée min 15 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 par 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 dizaine 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 multi paradigme très efficace pour programmer ce type d’application.

Objectif du stage

Le moteur CBLS a récemment été enrichit d’un nouveau type de variable : les variables de type séquence d’entier. Ce nouveau type de variable permet de développer des algorithmes efficaces pour représenter diverses contraintes ou fonctions objectifs notamment pour l’optimisation de routage de véhicules.
Par exemple, la distance parcourue par un véhicule en cas de matrice symétrique, peut être mise à jour en O(1) pour tous les voisinages de recherche standard (1-opt, 2-opt, 3-opt). Grâce à cette efficacité, il est possible d’optimiser un voyageur de commerce de 10.000 points avec matrice de distance symétrique en moins d’une minute.

L’objectif du stage est d’enrichir la librairie des contraintes globales portant sur ces séquences d’entier en se focalisant sur une contrainte de fenêtre de temps. Chaque point doit être atteint au sein d’une fenêtre de temps donnée. Si le véhicule arrive trop tôt, il doit attendre. S’il arrive trop tard, la contrainte est violée. L’objectif est de proposer un algorithme qui permette de savoir très rapidement si une modification du trajet induirait une violation de la contrainte. L’algorithme peut s’appuyer sur des pré-calculs sui sont effectués à des moments décidés par le moteur OscaR.cbls.

Des algorithmes ont été proposés pour traiter ce problème, et s’appuient sur du pré-calcul ainsi que proposé ci-dessus. Il s’agit du Backward Time Slack par exemple, qui calcule une marge de temps disponible à chaque étape du trajet, et s’appuie sur cette donnée pour identifier rapidement une violation de cette contrainte entraînée par une modification de la route.
Travail à réaliser

Travail à réaliser

Le travail est structuré en quatre taches comme suit :

  • Tâche 1 : étudier le fonctionnement du moteur OscaR.cbls et en particulier le fonctionnement de la variable de type séquence d’entier. Une implémentation naïve de la contrainte de capacité sera développée.
  • Tâche 2 : Faire un revue de la littérature des algorithmes existants pour traiter ce problème
  • Tâche 3 : formuler un algorithme adéquat, en découpant les algorithmes existants de manière à) les faire « rentrer » dans les API de OscaR.cbls
  • Tâche 4 : Implémenter l’algorithme proposer et le tester. Une application est disponible pour effectuer ces tests comparatifs.

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.

Références