Les sociétés de livraison se heurtent aux problèmes de routage de leur véhicule : trouver l’itinéraire le plus court pour effectuer les remises de marchandises pour réduire les coûts de carburant. Plus les points de livraison sont nombreux, plus trouver l’itinéraire idéal est complexe. Des algorithmes ont été conçus pour répondre à ce problème pour quelques centaines de villes, mais ces solutions deviennent trop lentes lorsqu’elles sont appliquées à un plus grand nombre de villes. Des chercheurs du MIT (Massachussets Institute of Technology) ont utilisé l’apprentissage automatique pour accélérer les solutions aux problèmes de routage des véhicules pour de grands ensembles de villes.
Le problème de routage des véhicules
Le plus étudié des problèmes de routage des véhicules (Vehicle Routing Problem ou VRP) est celui qu’a énoncé William Rowan Hamilton en 1859 : celui du voyageur de commerce. Sous sa forme la plus classique, son énoncé est le suivant : « Un voyageur de commerce doit se rendre une et une seule fois un nombre défini de villes et revenir à son point de départ. Trouvez l’ordre de visite des villes qui minimise la distance totale parcourue par le voyageur ». Ce problème d’optimisation combinatoire, qui appartient à la classe des problèmes NP-Complets, devient très complexe lorsqu’il est appliqué à un grand de villes et sa résolution demande alors un temps beaucoup trop long. Des méthodes approchées, ou algorithmes d’approximation, sont utilisées.
Les dépôts qui sont chargés de livrer les colis aux clients (ce qu’on appelle communément la livraison au dernier kilomètre), doivent prendre en considération divers éléments : la localisation des points de livraison, les horaires des chauffeurs et les plages horaires auxquelles les clients aimeraient être livrés, le coût du carburant… Les plus importants comme Fedex par exemple, choisissent de faire appel à des sous-traitants qui se voient attribuer un secteur de livraison, divisant ainsi le problème de routage.
C’est le même genre de démarche qui a été suivie par les chercheurs du MIT en abordant leur étude intitulée : « Apprendre à déléguer pour le routage de véhicules à grande échelle ». L’étude ne porte que sur l’itinéraire le plus court et ne tient pas compte des autres problèmes du routage.
Accélérer les solveurs algorithmiques
Sirui Li, Zhongxia Yan et Cathy Wu, professeure adjointe en développement de carrière Gilbert W. Winslow, membre du département en génie civil et environnemental et de l’Institut des données, des systèmes et de la société, ont mis au point une stratégie d’apprentissage automatique qui accélère certains des plus forts solveurs algorithmiques de 10 à 100 fois. Cathy Wu a déclaré:
« Pour nous, c’est là que l’apprentissage automatique entre en jeu. Pouvons-nous prédire lequel de ces sous-problèmes, qui, si nous devions les résoudre, conduirait à une plus grande amélioration de la solution, économisant du temps et des dépenses de calcul ? »
Les algorithmes du solveur ont divisé le problème de livraison en sous-problèmes plus petits à résoudre (200 sous-problèmes pour l’acheminement des véhicules entre 2 000 villes). L’équipe de Cathy Wu et ses collègues a créé un réseau de neurones qui identifie les sous-problèmes les plus utiles à résoudre, au lieu de les résoudre tous, pour augmenter la qualité de la solution tout en utilisant moins de calculs. Marc Kuo, fondateur et PDG de Routific, une plateforme logistique intelligente pour optimiser les itinéraires de livraison, déclare:
« La plupart des recherches universitaires ont tendance à se concentrer sur des algorithmes spécialisés pour les petits problèmes, en essayant de trouver de meilleures solutions au détriment des temps de traitement. Mais dans le monde réel, les entreprises ne se soucient pas de trouver de meilleures solutions, surtout si elles prennent trop de temps pour le calcul », explique Kuo. Dans le monde de la logistique du dernier kilomètre, le temps c’est de l’argent, et vous ne pouvez pas faire attendre l’ensemble de vos opérations d’entrepôt qu’un algorithme lent renvoie les itinéraires. Un algorithme doit être hyper-rapide pour être pratique. »
Trouver la meilleure solution possible
Il n’est généralement pas possible de trouver la bonne réponse aux problèmes de routage, car le nombre de solutions possibles est bien trop important. Cathy Wu explique :
« Le nom du jeu pour ces types de problèmes est de concevoir des algorithmes efficaces… qui sont optimaux dans un certain facteur. Mais le but n’est pas de trouver des solutions optimales. C’est trop dur. Nous voulons plutôt trouver les meilleures solutions possibles. Même une amélioration de 0,5 % des solutions peut se traduire par une augmentation considérable des revenus d’une entreprise. »
L’approche, que les chercheurs ont appelée « apprendre à déléguer », a accéléré le processus de sélection des sous-problèmes de 1,5 à 2 fois, à la surprise de Cathy Wu et ses collègues:
« Nous ne savons pas pourquoi ces sous-problèmes sont meilleurs que d’autres sous-problèmes. C’est en fait une ligne intéressante de travaux futurs. Si nous avions des idées ici, celles-ci pourraient conduire à la conception d’algorithmes encore meilleurs. »
D’autre part, la qualité des résultats obtenus a également surpris les chercheurs. « Un réseau neuronal formé sur les solutions de sous-problèmes de “qualité moyenne” disponibles en tant que données d’entrée “donnerait généralement des résultats de qualité moyenne». Dans ce cas, cependant, les chercheurs, avec des solutions de qualité moyenne ont obtenu des résultats de haute qualité, beaucoup plus rapidement que les méthodes de pointe. Cette méthode pourrait trouver de nombreuses applications comme le cheminement d’un robot dans un entrepôt… Cathy Wu conclut :
« Étant donné que la méthode peut fonctionner avec une variété de solveurs, elle peut être utile pour une variété de problèmes d’allocation de ressources. Nous pouvons débloquer de nouvelles applications qui seront désormais possibles car le coût de résolution du problème est 10 à 100 fois inférieur. »
Marc Kuo ajoute :
« Ce travail repousse les limites de la résolution rapide des problèmes d’acheminement des véhicules à grande échelle. Certaines des récentes avancées algorithmiques de Routific ont été inspirées par les travaux de Wu. »
Wu, le doctorant en systèmes sociaux et d’ingénierie Sirui Li, et le doctorant en génie électrique et informatique Zhongxia Yan ont présenté leur recherche cette semaine lors de la conférence NeurIPS 2021, recherche qui a été la source de cet article.
