Le 06/12/2022 par Alex :

Stage de recherche M2 (6 mois, début février 2023)

Path relinking in feature/criteria space for VRP problems

Localisation : Lab-STICC, UMR CNRS 6285, Université Bretagne Sud, Lorient
Encadrants : Marc SEVAUX, Alexandru OLTEANU
Contact : marc.sevaux@univ-ubs.fr; alexandru.olteanu@univ-ubs.fr

Sujet
Les liens entre les méthodes d’optimisation et les approches d’apprentissage automatique ont commencé à être exploré il y a une vingtaine d’années avec l’apparition des hyper-heuristiques. Ces méthodes cherchent à apprendre à partir des instances de référence pour un problème donné quelle pourrait être la meilleure métaheuristique, sa meilleure configuration ou bien son meilleur paramétrage pour des instances nouvelles. Plus récemment, dans le cadre de problèmes de tournées de véhicules, les approches d’apprentissage automatique ou statistique ont été utilisées afin de caractériser les bonnes solutions et extraire des connaissances qui seraient par la suite intégrées dans des métaheuristiques adaptatives. Les résultats sont cependant mitigés. La difficulté principale réside dans le rapport entre le gain en performance qu’apportent ces connaissances et le coût pour les extraire.
L’objectif de ce stage consiste à s’inspirer de ces travaux et à apporter en même temps une perspective nouvelle. Nous partons de l’approche de Ho et Gendreau (2006) qui prend la forme d’une recherche tabou couplé à du path relinking. La recherche tabou est une méthode de recherche locale qui sort de minimaux locaux en gardant trace des mouvements passés, alors que le path relinking relie deux solutions parmi un ensemble de meilleures solutions explorées à travers des solutions intermédiaires selon un ou plusieurs opérateurs de mouvement. Le path relinking fait à la fois de l’intensification et de l’exploration mais il est sensible aux solutions utilisées. Nous proposons d’étendre cette approche en reliant une des meilleures solutions proposés par la recherche tabou à une solution idéale selon une représentation dans un espace de features/critères.
Une poursuite en thèse dans le cadre d’un projet ANR est possible à l’issue de ce stage.

Profil
• étudiant au niveau M2 avec des connaissances en recherche opérationnelle et métaheuristiques;
• compétences en programmation (idéalement julia).

Candidatures
Pour postuler les candidats doivent envoyer au plus tôt dans un seul document PDF (par email aux
deux adresses) :
• un CV détaillé avec d’éventuels lettres de recommandation;
• un relevé de notes du master ou de l’école d’ingénieur;
• une lettre de motivation.