Amélioration des opérations avec optimisation de la route

Collaborateurs: Feiko Lai, Michal Szczecinski, Winnie So, Miguel Fernandez

Chaque jour, les chauffeurs GOGOVAN arrivent dans des entrepôts à travers l’Asie pour collecter des milliers de commandes que nos partenaires commerciaux nous ont demandé de livrer à leurs clients.

Ces commandes peuvent être diverses et variées - du nouveau téléphone tant attendu au cadeau d'anniversaire commandé à la dernière minute. Tous seront de différentes tailles, formes et poids. Pour chacun d’eux, il y aura une personne qui attend et espère que cette fois la société de courrier arrivera à temps…

C’est pourquoi, chez GOGOVAN, nous mettons tout en œuvre pour assurer des livraisons rapides et sans heurt avec une qualité de service qui étonnera nos clients. Chaque itinéraire de livraison est soigneusement planifié manuellement et revérifié par notre équipe des opérations afin de nous assurer que nous n'échouons jamais.

MANUELLEMENT?!

N'avez-vous pas dit que vous aviez des milliers de commandes par jour?!

Oui c'est correct.

Auparavant, l'équipe des opérations devait trier manuellement les itinéraires de livraison, généralement le matin du ramassage, et veiller à ce que nous respections toutes les exigences en matière de délai de livraison pour cette journée. Comme vous pouvez l’imaginer, ce n’est pas une tâche particulièrement excitante ou facile :)

Il a fallu environ une heure à une personne pour créer un itinéraire sous-optimal pour 100 points de route. Pour les demandes plus importantes que cela, cette période a connu une croissance exponentielle.

Nous avons immédiatement réalisé que ce processus impliquait simplement une automatisation.

Non seulement nous nous sentions désolés pour l'équipe des opérations qui devait faire un travail aussi banal chaque matin, mais nous savions également que, avec l'augmentation du volume de nos commandes, cette tâche deviendrait lentement impossible. Nous y avons vu une opportunité de développer une technologie de pointe qui deviendra un élément central de la pile de données de GOGOVAN.

Comment avons-nous commencé?

Nous sommes très centrés sur le client et le conducteur. Par conséquent, nous essayons toujours d'abord d'analyser un problème de leur point de vue afin de comprendre l'impact potentiel de notre solution. Après beaucoup de brainstorming, voici les objectifs que nous avons définis:

  • Toutes les commandes doivent être livrées à temps.
  • Assurez-vous que les conducteurs ne sont pas pressés de gagner du temps en utilisant des temps de mémoire tampon et une distance en temps réel.
  • Économisez du carburant en réduisant la distance parcourue.
  • Réduisez le temps d'inactivité des conducteurs - personne n'aime attendre avec un coffre rempli de paquets.
  • Améliorer l'utilisation du véhicule.
  • Automatiser complètement le processus.
  • L'algorithme doit pouvoir évoluer avec nous - en prenant en charge différents types de livraisons, véhicules et pays.

Après avoir défini nos objectifs principaux, nous avons décidé d’explorer le monde universitaire et l’open source - il est inutile de redécouvrir la roue. Nous avons réalisé que le problème auquel nous étions confrontés était largement connu sous le nom de problème de routage des véhicules.

Quel est le problème de routage de véhicule?

Le problème de routage de véhicule (VRP) peut être décrit comme le problème de la création d'un ensemble d'itinéraires optimaux d'un ou plusieurs dépôts à plusieurs clients, soumis à un ensemble de contraintes. L’objectif est de livrer les marchandises à tous les clients, tout en minimisant le coût des itinéraires et le nombre de véhicules.

Ce problème est NP-difficile, comme le prouvent Lenstra et Rinnooy Kan¹. Cependant, il existe encore des méthodes de solution exactes, utilisant une programmation branchée-reliée², ou une programmation dynamique³. Cependant, comme décrit dans les documents ci-dessus, elles ne semblent fonctionner que pour 150 points de cheminement.

Actuellement, les solutions de pointe sont obtenues à l'aide des méthodes métaheuristiques suivantes: Algorithmes génétiques⁴, Tabu Search⁵ et Ant Colony Optimization. Ce sont les méthodes principalement utilisées sur le terrain de nos jours.

Pour un examen approfondi du terrain, nous recommandons cette brillante thèse⁷ de Xiaoyan Li.

Notre solution

Les VRP étant un problème largement reconnu, de nombreuses entreprises semblent effectivement s’attaquer au problème.

Cependant, nous ne nous sommes pas sentis satisfaits de leurs solutions…

Nous savions seulement que si nous combinions notre savoir-faire opérationnel, notre expertise en matière de science et de recherche de données, nos grands volumes de données et nos contributions de pointe à la source ouverte, nous pouvons parvenir à une solution interne robuste qui:

  • Est plus à jour, performant et dispose d'algorithmes personnalisables et d'une logique d'itération.
  • Est moins cher, plus efficace et plus évolutif.
  • Permet de développer des actifs de propriété intellectuelle tangibles et de créer un avantage concurrentiel autour de ceux-ci.
  • Nous permet de garantir à nos clients que leurs données de livraison n'iront pas plus loin que GOGOVAN.

Après avoir réfléchi pendant un bon bout de temps, nous avons décidé que si nous voulons être les leaders sur le terrain, nous devons le faire à notre façon, et non utiliser une solution de type boîte noire.

Alors on y va…

Premier algorithme

Mais nous n’avons pas tout de suite plongé dans les journaux universitaires!

Premièrement, nous nous sommes concentrés sur l’élaboration de nos propres approches et sur leur évaluation. Ce processus nous a permis d’avoir une meilleure compréhension du terrain dès le début et de faire face à certains problèmes courants (nous n’avions rien pris pour acquis!). De plus, cela nous a aidés plus tard, car nous pouvions facilement voir le pour et le contre de différentes méthodes présentées dans des articles universitaires et proposer des stratégies pour les combiner.

Un tel processus a été la clé pour comprendre immédiatement comment fonctionnait ce brillant ensemble - Outils d’optimisation Google. Nous avons compris que les employés de Google nous faisaient gagner des mois en codant tous les algorithmes que nous voulions tester. Ils nous ont permis d'entrer immédiatement dans la partie la plus intéressante!

Nous avons passé beaucoup de temps à jouer avec cette bibliothèque, à tester différents scénarios et à constater par nous-mêmes quelles stratégies fonctionnaient à quel moment.

Cela nous a tellement plu que nous avons décidé de construire notre outil autour de cela!

Nous avions tout ce dont nous avions besoin - la transparence, la capacité d’expérimenter, la flexibilité et le soutien.

Le premier algorithme était prêt. Nous l'avons déployé.

Figure 1: Visualisation de l'une de nos premières missions d'optimisation de route

Croissance rapide - comment gérer plus de commandes?

La première version de Route Optimization s’est avérée être un grand succès.

Le volume des commandes passées à Route Optimizer est passé rapidement de 500 articles à plus de 1000. Théoriquement, ça devrait aller.

Mais nous n'étions pas.

Les temps d'exécution de nos algorithmes et notre utilisation de la mémoire ont augmenté incroyablement rapidement - de 1 minute et 500 Mo à 10 minutes et 5 Go. Comme nous l'avons testé pour des volumes de plus en plus élevés, nous avons finalement atteint le maximum: pour 2 000 points de cheminement, le module a utilisé 25 Go de mémoire RAM.

C'était inacceptable.

En gros, nous avions deux options:

  • Construire un tout nouvel itinéraire Route Optimizer capable de prendre en charge de tels volumes par défaut
  • Créer un nouvel algorithme qui s'exécutera par-dessus l'implémentation actuelle - probablement une méthode qui combinera des ordres en lots plus petits qui seraient ensuite soumis à l'algorithme d'optimisation principal

Comme nous sommes pragmatiques (et aimons également nous appuyer sur l'excellent travail que nous avons déjà accompli), nous avons décidé de poursuivre avec la deuxième option.

Comment créer des lots plus petits?

Commençons par un algorithme de cluster réputé - DBSCAN⁸.

Ce que nous avons est une méthode de pointe qui regroupe des points géographiques. Cependant, il a ses inconvénients: chaque cluster doit avoir le même rayon.

Ce n'est pas ce que nous voulons pour une raison simple: un groupe d'un rayon de 1 km à Tsim Sha Tsui peut contenir 1 000 ordres, tandis que d'autres groupes d'un kilomètre à Pok Fu Lam et à Waterfall Bay ne peuvent contenir que 3 ordres chacun.

Ces grappes seraient vraiment inefficaces et inégales…

À Tsim Sha Tsui, la taille de la grappe serait trop grande - nous aurions trop de commandes dans une grappe. Mais dans le même temps, dans certaines autres régions, ce rayon ne serait pas suffisant: les grappes seraient trop petites et les ordres relativement proches les uns des autres seraient séparés.

C'est pourquoi nous avons décidé d'utiliser une approche modifiée, appelée «récursive-DBSCAN».

Recursive-DBSCAN

Il s’appuie sur l’excellence de DBSCAN, mais nous permet en même temps d’approfondir les régions à haute densité de points de passage tout en regroupant les ordres distants.

Pour obtenir une liste des commandes, nous cherchons à déterminer le rayon pour lequel le nombre moyen de points de cheminement sera le plus grand (mais le nombre de clusters sera supérieur à min_no_clusters). Nous le faisons en utilisant un simple algorithme de recherche binaire.

Une fois que nous avons trouvé la solution optimale, nous «entrons» dans les grappes trop grandes et appliquons la même logique jusqu'à atteindre un point où chaque grappe contient moins de max_len_cluster.

Ensuite, pour chaque cluster, nous exécutons l’algorithme Route Optimization que nous avons développé à l’aide des outils d’optimisation Google. Espérons que cela nous donnera un résultat similaire plus rapidement, en utilisant moins de mémoire RAM.

Le pseudocode est le suivant:

Des repères

Nous étions très curieux de savoir comment notre méthode fonctionnerait, mais nous craignions en même temps que la récursion ne dure que très longtemps, ce qui rend donc notre algorithme pas meilleur que la méthode de base.

C'est pourquoi nous avons d'abord décidé de regarder les temps d'exécution:

Il s'est avéré que l'algorithme récursif-dbscan surpassait de beaucoup la méthode des outils d'optimisation de Google. Dans le même temps, il ne différait pas beaucoup des temps d'exécution de la méthode dbscan.

En raison du problème d'utilisation de la mémoire RAM, nous n'avons pu exécuter dbscan que pour 2 000 commandes maximum et les outils d'optimisation Google pour 1 000 commandes: les deux méthodes étaient écrasées lorsque la mémoire requise dépassait 25 Go.

Les durées d’utilisation sont importantes, mais nous nous sommes également intéressés au rendement de notre nouvel algorithme en termes de distance totale et de nombre de véhicules utilisés, par rapport à la méthode de base. Ces deux graphiques montrent que:

Comme nous le voyons, la méthode récursive suit de près la méthode des outils d'optimisation de Google en termes de distance et de nombre de véhicules. En même temps, il surpasse la méthode dbscan.

Cela signifie que notre nouvel algorithme est plus rapide que la ligne de base et que la qualité des solutions trouvées est aussi bonne. En outre, la RAM maximale utilisée est «seulement» 1 Go!

Nous avons compris!

DBSCAN vs Recursive-DBSCAN

Nous voulions également vous montrer comment exactement recursive-dbscan fonctionne mieux pour les points de cheminement distants.

Figure 5: Comparaison des routes DBSCAN et Recursive-DBSCAN. Nous sommes conscients qu'ils ne sont toujours pas parfaits!

Ci-dessus, à gauche, une carte montrant une affectation trouvée à l'aide de l'algorithme DBSCAN normal. Nous pouvons voir que beaucoup de chauffeurs ne livrent qu'une seule commande, car ces commandes sont les seules dans leur lot.

À droite, nous voyons que la méthode récursive résout assez bien ce problème. En utilisant différents rayons pour différentes régions, elle parvient à trouver une solution qui livre toutes les commandes avec 3 véhicules seulement!

Ceci est une visualisation parfaite de la façon dont la méthode recursive-dbscan convient mieux à notre cas d'utilisation et des raisons pour lesquelles nous avons choisi de l'utiliser.

Conclusion (alias TL; DR)

Dans cet article, nous avons présenté notre approche du problème de routage de véhicule par capacité avec fenêtres temporelles pour un grand nombre de points de cheminement (jusqu'à 5 000). En utilisant une méthode récursive-dbscan, nous avons été en mesure de réduire considérablement les temps d'exécution et l'utilisation de la mémoire, tout en maintenant une qualité de résultats similaire à celle de la méthode de base des outils d'optimisation Google.

Cet algorithme est d'une grande aide pour notre équipe des opérations, car il réduit les heures de travail manuel banal à quelques minutes de temps CPU (et vérifie les résultats par un humain).

L'avenir

Nous sommes conscients que notre outil n'est pas parfait.

L'un des principaux problèmes est qu'il s'agit toujours d'une méthode statique. Une fois exécuté, il ne sera pas mis à jour automatiquement si un meilleur itinéraire devient disponible ou si la situation de la route change. Dans ce cas, nous avons quelques options, l'une consistant à mettre en œuvre la géolocalisation, comme Lyft, ou une autre provenant de notre partenaire, le centre de recherche Big Data Analytics de PolyU Hong Kong.

Notre objectif est d’améliorer l’optimisation des tournées afin qu’il surveille en permanence les chauffeurs et envoie des alertes si ceux-ci risquent de ne pas arriver à temps avec certains colis - tout cela pour rendre nos clients plus satisfaits de notre service.

J'espère que cet article vous a fourni une bonne idée des problèmes auxquels nous nous attaquons à GOGOVAN. Si cela vous semble intéressant ou si vous souhaitez simplement en savoir plus, n'hésitez pas à nous contacter.

Il y a naturellement beaucoup de terrain pour des améliorations futures, mais nous espérons partager certaines de nos approches afin de susciter des discussions et de progresser dans un domaine fascinant d'optimisation des opérations logistiques à la demande.
Si vous souhaitez en savoir plus sur notre équipe de données, veuillez consulter l’article de notre responsable des données ici.
Nous sommes toujours à la recherche de talents de haut niveau dans les domaines des opérations appliquées et de la recherche ML. S'il vous plaît entrer en contact si vous êtes intéressé! (Sur site et à distance)
Références:
[1] Lenstra, J. K. et Kan, A. H. (1981), Complexité des problèmes d'acheminement et d'ordonnancement des véhicules. Réseaux, 11: 221–227. doi: 10.1002 / net.3230110211
[2] Fukasawa, R., H. Longo, J. Lysgaard et al. Math. Programme. (2006) 106: 491.
[3] Baldacci, R. & Mingozzi, A. Math. Programme. (2009) 120: 347. https://doi.org/10.1007/s10107-008-0218-9
[4] Nagata Y. (2007) Crossover Assembly Edge pour le problème de routage de véhicule par capacité. Dans: Cotta C., van Hemert J. (eds) Calcul évolutif dans l'optimisation combinatoire. EvoCOP 2007. Notes de cours en informatique, vol 4446. Springer, Berlin, Heidelberg
[5] Bräysy, O. et Gendreau, M. Top (2002) 10: 211. https://doi.org/10.1007/BF02579017
[6] Tan X., Zhuo X., Zhang J. (2006) Système de colonie de fourmis pour optimiser le problème de routage de véhicule avec des fenêtres temporelles (VRPTW). Dans: Huang DS., Li K., Irwin G.W. (eds) Intelligence informatique et bioinformatique. ICIC 2006. Notes de cours en informatique, vol 4115. Springer, Berlin, Heidelberg
[7] Xiaoyan Li (2015), Problème de routage de véhicule par capacité avec fenêtres temporelles: étude de cas sur le ramassage de produits diététiques dans des organisations à but non lucratif.
[8] M. Ester, H. Kriegel, J. Sander et X. Xu, «Un algorithme basé sur la densité pour la découverte de grappes dans de grandes bases de données spatiales avec bruit», dans Proc. 2ème Int. Conf. Découverte de connaissances et exploration de données (KDD’96), 1996, p. 226-231.