+33 1 85 76 20 29
contact@citodi.fr

GrubHub et Georgia Tech collaborent pour optimiser les livraisons de repas

GrubHub collabore avec Georgia Tech pour concevoir son algorithme de dispatch automatique

Le numéro 1 de la livraison de repas aux USA collabore avec les chercheurs de la prestigieuse université Georgia Tech pour l’optimisation dynamique et le dispatch automatique des livraisons de repas.

GrubHub, fondée en 2004 à Chicago, est une startup de livraison de repas implantée aux USA et au Royaume-Uni, qui opère selon un modèle similaire à Deliveroo en France. Après plusieurs étapes de croissances externes et de fusions, ainsi qu’une introduction à la bourse de New York en 2014, elle réalise en 2017 un chiffre d’affaire qui dépasse le demi-milliard de dollars. Ils ont récemment collaboré avec des chercheurs de l’université Georgia Tech pour définir le problème de la livraison de repas dynamique et le résoudre.

La livraison de repas : un problème de dispatch particulier

Dans leur article, publié dans Optimization Online le 1er Mars 2018 et intitulé « The Meal Delivery Routing Problem », les chercheurs présentent la livraison de repas comme un problème à part entière, différent des problèmes de tournées (« routing » en anglais) classiques. En effet, il s’agit d’optimiser les trajets d’une flotte de véhicules qui doivent aller chercher des repas préparés dans des restaurants répartis dans la ville, de façon à les livrer en temps limité chez des particuliers qui commandent pendant que les tournées sont réalisées. Ils mentionnent notamment deux particularités qui rendent ce problème inattaquable avec les techniques classiques :

  • Les commandes arrivent au fil de l’eau : on ne sait pas quand les commandes vont arriver, ni quels restaurants elles vont concerner, ni où il faudra les livrer. On ne connait donc qu’une partie des tâches à effectuer, et il faudra adapter les tournées de livraison en fonction des nouvelles commandes.
  • Les stratégies d’attente : contrairement aux tournées classiques où dès qu’un chauffeur a terminé sa livraison, il repart vers son prochain point, la livraison de repas nécessite de mettre en place des stratégies d’attente, notamment pour permettre aux livreurs d’emporter plus de repas avec eux.

Des algorithmes spécifiques à la gestion en temps réel

Dans un premier effort pour résoudre ce problème, les chercheurs proposent un algorithme d’optimisation séquentiel (« rolling horizon ») qui va résoudre le même problème d’optimisation toutes les X minutes en tenant compte des données qui ont changé entretemps. Le problème d’optimisation étant en lui-même difficile à résoudre, il n’est pas possible d’envisager des algorithmes de résolution exacte qui prendraient trop de temps pour converger : il faut répondre rapidement avec de très bonnes solutions de tournées. Ils décrivent donc plusieurs stratégies d’affectation des livreurs aux commandes qui arrivent afin de maximiser l’efficacité du système. Ils présentent énormément de simulations réalisées sur des données réelles de leur algorithme, et ils montrent qu’ils parviennent à obtenir des résultats peu éloignés de ceux qu’on obtiendrait avec un algorithme d’optimisation exact, beaucoup de temps et la connaissance préalable de toutes les commandes qui vont tomber (une situation idéale, inatteignable en pratique).

Le dispatch automatique

Les travaux présentés dans cet article vont dans le sens d’une optimisation qui cherche à coller à la réalité du terrain et à ses aléas. C’est la vision que nous proposons chez Citodi, et nos algorithmes de Dispatch Automatique s’appuient sur des techniques relativement similaires à celles développées dans cet article, notamment en ce qui concerne la gestion des temps d’attente. Mais ces algorithmes peuvent être appliqués à d’autres problématiques qui relèvent également du dispatch automatique, telles que le problème de l’optimisation d’un service de car-sharing ou bien la livraison par coursiers qui ont en commun la gestion d’un flux important de commandes entrantes, une gestion fine des temps d’attente des chauffeurs et de leur éventuel repositionnement. Nous travaillons depuis plusieurs années sur ces sujets .

Pour découvrir notre offre de Dispatch Automatique : cliquez ici !

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *