La ROADEF
R.O.A.D
Événements
Prix
Publications
Plus
Forum
Connexion

Solving Vehicle Routing Problem with linear programming optimized by Machine Learning

Forum 'Stages' - Sujet créé le 01/02/2022 par Faye (682 vues)


Le 01/02/2022 par Faye :

Stage en Data Science et Recherche Opérationnelle
Comment combiner les méthodes de recherche opérationnelle et d?apprentissage
automatique ?
 

Durée : 6 mois

Qui sommes-nous ?

Quantmetry, c?est une équipe de 120 personnes qui travaillent de concert pour accompagner
ses clients dans leurs réflexions, POC, industrialisation autour de la Data, l?Intelligence
Artificielle, le Machine Learning. Nous sommes un cabinet de conseil pure player en Data, et
nous sommes parfois amenés à travailler sur des problématiques de Recherche
Opérationnelle. N?étant pas sectorisés, nous intervenons sur différents sujets : la
maintenance prédictive, la segmentation clients, le scoring ; la détection de fraude, de
corruption, de blanchiment d?argent ; le développement des architectures de plateformes
Data ; l?analyse de textes et d?images dans le cadre de la lutte contre le cancer du sein.

Descriptif de l?offre
Déterminer la route optimale qu?un livreur doit emprunter pour remettre l?ensemble de ses
colis tout en minimisant le temps du parcours fait partie de la classe de problèmes de
recherche opérationnelle VRP (Vehicle Routing Problem). La résolution de cette typologie de
problèmes peut se faire grâce aux méthodes d?optimisation sous contraintes et est
approfondie depuis des décennies [1].
Néanmoins, certains livreurs expérimentés disposent d?une connaissance tacite de
l?environnement : par exemple, ils peuvent connaître les heures de pointes de certains
quartiers, les portions de routes moins roulantes, quand et où se garer facilement pour
desservir plusieurs clients en même temps. De telles informations sont difficiles, voire
impossibles à formaliser dans un modèle d'optimisation et sont donc très rarement contenues
dans la plupart des outils de planification d'itinéraires utilisé par les entreprises.
Les méthodes classiques d?optimisation sous contraintes permettent donc d?obtenir des
routes satisfaisant toutes les contraintes (ex : tous les arrêts sont desservis une unique fois)
mais ne peuvent pas tirer profit de l?historique des routes effectivement empruntées par les
bons livreurs. À l?inverse, les méthodes d?apprentissage automatique permettent de tirer
profit de cet historique sans toutefois garantir les contraintes.
L?objectif de ce stage est de faire un état de l?art des outils et méthodes à l?interface de du
Machine Learning et de la Recherche Opérationnelle, et développer une solution du Last Mile
Routing Research Challenge [2] proposé en 2021 par Amazon et le MIT Center for
Transportation and Logistics. Quantmetry a contribué aux travaux issus de ce challenge, et
souhaite les approfondir pour produire des solutions au problème de séquençage d'itinéraires
qui permettent d?obtenir des routes « optimales » plus proches de celles observées dans la
vraie vie.
La modélisation du problème d?optimisation sera faite en Python, en comparant les
bibliothèques (par ex : CVXPY, Pyomo, Google OR-Tools, scipy.optimize) ainsi que les solveurs
disponibles (ex : CBC, GLPK,?). Le stage pourra repartir de la solution initialement développée
dans le cadre d?une collaboration entre Quantmetry et l?ENSIIE (www.ensiie.fr).
Pour développer des approches hybridant Optimisation et Machine Learning, nous pourrons
utiliser les travaux récents sur l?optimisation différentiable [3], qui permet d?apprendre des
problèmes d?optimisation.

Objectifs :
- Étudier les données mises à disposition, et les solutions proposées par les participants
du Last Mile Routing Research Challenge.
- Recenser les différentes bibliothèques de modélisation d?optimisation sous
contraintes en Python, ainsi que les différents solvers, les prendre en main puis les
comparer afin d?en comprendre les forces et faiblesses.
- Analyser les modèles basés sur l?optimisation différentiable et les propriétés de ces
modélisations hybrides (complexité, performance,?), et développer une approche
innovante permettant de résoudre le problème du VRP.

Conditions :
- Connaissances en Recherche Opérationnelle / optimisation sous contraintes
- Connaissances en machine learning
- Maîtrise de Python

Références :
- [1] Rich Vehicle Routing Problem: Survey : https://dl.acm.org/doi/10.1145/2666003
- [2] Last Mile Routing Research Challenge : https://routingchallenge.mit.edu
- [3] Differentiable Convex Optimisation, https://arxiv.org/abs/1910.12430

Profil recherché
Vous êtes étudiant(e) en école d?ingénieur ou en Master 2, avec un fort intérêt pour la
Recherche Opérationnelle, la Data Science et l?Intelligence Artificielle. Vous avez une bonne
capacité à interagir en équipe sur une problématique requérant autonomie et une certaine
rapidité d?action. Nous recherchons une personne dynamique et curieuse, qui saura s'intégrer
et faire progresser l?expertise « Time Series » en travaillant sur une problématique de R&D.

Contact :
Pour des informations techniques sur le projet, vous pouvez contacter Massinissa Merabet
(massinissa.merabet@ensiie.fr), Nicolas Brunel (nbrunel@quantmetry.com).
Candidater sur www.welcometothejungle.com (Data Scientist ? Stage ? Recherche
Opérationnelle)
 







Moteur de recherche
Tous les forums


  La Société française de Recherche Opérationnelle et Aide à la Décision ROADEF est une association Loi 1901 Plus d'informations sur la ROADEF