Vous attendez la livraison d’un colis pour les fêtes? Il existe un problème mathématique insidieux qui doit être résolu avant que le camion de la compagnie de transport n’arrive à votre porte, et des chercheurs du MIT ont conçu une stratégie qui pourrait accélérer l’obtention d’une solution.
Selon ce qu’ils rapportent, l’approche s’applique à des véhicules chargés du transport dit du « dernier kilomètre », dont l’objectif consiste à livrer des marchandises à partir d’un dépôt central, et à destination de plusieurs villes, tout en minimisant les coûts. S’il existe des algorithmes conçus pour régler ce problème dans quelques centaines de villes, ces solutions deviennent trop lentes lorsqu’elles sont étendues à davantage de municipalités.
Pour surmonter cet obstacle, Cathy Wu, professeure en génie civil et environnemental, ainsi que ses étudiants, ont conçu une stratégie d’apprentissage machine qui permet d’accélérer, par un facteur allant de 10 à 100, la vitesse de certains solutionneurs algorithmiques les plus puissants.
Ceux-ci fonctionnent en morcelant le problème de la livraison en quantité de sous-problèmes pour résoudre, par exemple, 200 sous-problèmes de détermination des trajets pour les véhicules répartis dans 2000 villes. Mme Wu et ses collègues ont renforcé ce processus avec un nouvel algorithme d’apprentissage machine qui identifie les sous-problèmes les plus importants à résoudre, plutôt que de tous les résoudre, ce qui accroît la qualité des solutions, tout en utilisant bien moins de puissance de calcul.
Leur approche, que les chercheurs qualifient « d’apprendre à déléguer », peut être employée par plusieurs solutionneurs servant à résoudre de nombreux problèmes similaires, y compris la planification et la circulati0on de robots dans un entrepôt, disent-ils.
Au dire de Marc Kuo, fondateur de Routific, une plateforme logistique utilisée pour optimiser les trajets de livraison, les nouveaux travaux repoussent les limites lorsque vient le temps de résoudre les problèmes entourant la conception de trajets pour un grand nombre de véhicules de livraison.
« La plupart des travaux dans ce domaine tendent à se concentrer sur des algorithmes spécialisés destinés à résoudre de petits problèmes, en tentant de trouver de meilleures solutions, en sacrifiant le temps de calcul. Mais dans le vrai monde, les entreprises n’ont cure de trouver de meilleures solutions, particulièrement si cela prend trop de temps à déterminer.
« Dans le monde des logistiques du dernier kilomètre, le temps, c’est de l’argent, et vous ne pouvez pas faire attendre l’ensemble des activités de votre entrepôt, histoire qu’un algorithme lent vous revienne avec des trajets. Un algorithme doit être hyper rapide pour être utile. »
Choisir de bons problèmes
Les problèmes de détermination de trajets pour des véhicules font partie d’un groupe de problèmes combinatoires qui nécessitent l’utilisation d’algorithmes spéciaux servant à trouver des solutions « satisfaisantes » à un problème. Il n’est habituellement pas possible de trouver la « meilleure » réponse à ces problèmes, puisque le nombre de solutions est trop élevé.
« Le truc, c’est de concevoir des algorithmes efficaces qui sont optimaux selon certains paramètres », explique Mme Wu. « Mais le but, ce n’est pas de trouver des solutions optimales. C’est trop difficile. Nous voulons plutôt trouver les meilleures solutions possibles. Même une amélioration de 0,5 % de nos solutions peut entraîner une forte hausse des revenus pour une entreprise. »
Au cours des dernières décennies, des chercheurs ont mis au point diverses techniques pour résoudre des problèmes combinatoires. Cela débute habituellement avec une solution peu efficace, mais valide, solution qui est graduellement améliorée, notamment en apportant de petites corrections qui améliorent le transit entre deux villes, par exemple. Pour un problème plus vaste, comme la détermination de trajet pour plus de 2000 villes, cependant, cette approche est simplement trop lente.
Plus récemment, des méthodes d’apprentissage machine ont été développées pour résoudre ce problème, mais si elles sont plus rapides, elles tendent à être imprécises, même à l’échelle de quelques dizaines de villes. Mme Wu et ses collègues ont décidé de voir s’il existait une méthode bénéfique de combiner les deux méthodes pour trouver des solutions rapidement, mais qui sont aussi de bonne qualité.
Chose surprenante, s’il a été déterminé que certains sous-problèmes étaient plus utiles, en un sens, pour s’attaquer au problème principal, plus vaste, Mme Wu et ses collègues disent ne pas savoir, exactement, pourquoi cette situation se produit.
Malgré tout, la chercheuse et ses collègues se disent confiants de pouvoir faire passer la vitesse de résolution des problèmes, qui est maintenant environ deux fois ce qu’elle était avant l’application de la nouvelle méthode, à un facteur allant de 10 à 100, ce qui réduirait d’autant le temps nécessaire pour concevoir ces trajets essentiels pour assurer des livraisons rapides de centaines, voire de milliers de colis par jour.
