Dans tout le pays, des centaines de milliers de chauffeurs livrent chaque jour des colis et des colis aux clients et aux entreprises, avec de nombreux clics à porte ne durant en moyenne que quelques jours. Coordonner un exploit de chaîne d’approvisionnement de cette ampleur de manière prévisible et opportune est un problème de longue date de la recherche opérationnelle, où les chercheurs s’efforcent d’optimiser la dernière étape des itinéraires de livraison. En effet, la dernière phase du processus est souvent la plus coûteuse en raison d’inefficacités telles que les longues distances entre les arrêts dues à l’augmentation de la demande de commerce électronique, les retards météorologiques, le trafic, le manque de disponibilité de stationnement, les préférences de livraison des clients ou les camions partiellement pleins — des inefficacités qui sont devenues plus importantes. exagéré et évident pendant la pandémie.
Grâce à une technologie plus récente et à des données plus individualisées et nuancées, les chercheurs sont en mesure de développer des modèles avec de meilleures options de routage, mais doivent en même temps équilibrer le coût de calcul de leur exécution. Matthias Winkenbach, chercheur principal au MIT, directeur de recherche au MIT Center for Transportation and Logistics (CTL) et chercheur au MIT-IBM Watson AI Lab, explique comment l’intelligence artificielle pourrait fournir des solutions meilleures et plus efficaces sur le plan informatique pour une optimisation combinatoire. problème comme celui-ci.
Question : Quel est le problème de tournée des véhicules et comment les méthodes traditionnelles de recherche opérationnelle (RO) le résolvent-elles ?
UN: Le problème de l’acheminement des véhicules est rencontré chaque jour par presque toutes les entreprises de logistique et de livraison comme USPS, Amazon, UPS, FedEx, DHL. En termes simples, il s’agit de trouver un itinéraire efficace qui relie un ensemble de clients qui doivent soit être livrés, soit quelque chose doit être récupéré chez eux. Il s’agit de décider à quels clients chacun de ces véhicules – que vous voyez sur la route – devrait rendre visite un jour donné et dans quel ordre. Habituellement, l’objectif est de trouver des itinéraires qui mènent à l’itinéraire le plus court, ou le plus rapide, ou le moins cher. Mais bien souvent, ils sont aussi motivés par des contraintes propres à un client. Par exemple, si vous avez un client qui a un délai de livraison spécifié, ou un client au 15ème étage d’un immeuble de grande hauteur plutôt qu’au rez-de-chaussée. Cela rend ces clients plus difficiles à intégrer dans un itinéraire de livraison efficace.
Pour résoudre le problème des tournées de véhicules, nous ne pouvons évidemment pas effectuer notre modélisation sans informations appropriées sur la demande et, idéalement, sans caractéristiques liées aux clients. Par exemple, nous devons connaître la taille ou le poids des colis commandés par un client donné, ou combien d’unités d’un certain produit doivent être expédiées vers un certain endroit. Tout cela détermine le temps dont vous auriez besoin pour desservir cet arrêt particulier. Pour des problèmes réalistes, vous souhaitez également savoir où le conducteur peut garer le véhicule en toute sécurité. Traditionnellement, un planificateur d’itinéraire devait proposer de bonnes estimations pour ces paramètres. C’est pourquoi vous trouvez très souvent des modèles et des outils de planification qui font des hypothèses générales parce qu’il n’y avait pas de données spécifiques aux arrêts disponibles.
L’apprentissage automatique peut être très intéressant à cet égard, car de nos jours, la plupart des conducteurs disposent de smartphones ou de trackers GPS, il existe donc une tonne d’informations sur le temps nécessaire pour livrer un colis. Vous pouvez désormais, à grande échelle, de manière quelque peu automatisée, extraire ces informations et calibrer chaque arrêt pour qu’il soit modélisé de manière réaliste.
Utiliser une approche OU traditionnelle signifie que vous rédigez un modèle d’optimisation, dans lequel vous commencez par définir la fonction objectif. Dans la plupart des cas, il s’agit d’une sorte de fonction de coût. Ensuite, il existe un tas d’autres équations qui définissent le fonctionnement interne d’un problème de routage. Par exemple, vous devez indiquer au modèle que, si le véhicule rend visite à un client, il doit également quitter à nouveau le client. En termes académiques, cela s’appelle généralement la conservation des flux. De même, vous devez vous assurer que chaque client est visité exactement une fois sur un itinéraire donné. Ces contraintes et bien d’autres du monde réel définissent ensemble ce qui constitue un itinéraire viable. Cela peut nous paraître évident, mais cela doit être codé explicitement.
Une fois qu’un problème d’optimisation est formulé, il existe des algorithmes qui nous aident à trouver la meilleure solution possible ; nous les appelons des solveurs. Au fil du temps, ils trouvent des solutions respectant toutes les contraintes. Ensuite, il essaie de trouver des itinéraires de mieux en mieux, donc de moins en moins chers, jusqu’à ce que vous disiez : « OK, cela me suffit » ou jusqu’à ce qu’il puisse prouver mathématiquement qu’il a trouvé la solution optimale. Le véhicule de livraison moyen dans une ville américaine effectue environ 120 arrêts. Cela peut prendre un certain temps pour résoudre ce problème explicitement, ce n’est donc généralement pas ce que font les entreprises, car cela coûte tout simplement trop cher en termes de calcul. Par conséquent, ils utilisent ce qu’on appelle des heuristiques, qui sont des algorithmes très efficaces pour trouver des solutions raisonnablement bonnes, mais qui ne peuvent généralement pas quantifier la distance entre ces solutions et l’optimum théorique.
Question : Vous appliquez actuellement l’apprentissage automatique au problème d’itinéraire de véhicules. Comment l’utilisez-vous pour exploiter et éventuellement surpasser les méthodes traditionnelles de salle d’opération ?
UN: C’est ce sur quoi nous travaillons actuellement avec des gens du MIT-IBM Watson AI Lab. Ici, l’idée générale est que vous entraînez un modèle sur un large éventail de solutions de routage existantes que vous avez soit observées dans les opérations réelles d’une entreprise, soit que vous avez générées à l’aide de l’une de ces heuristiques efficaces. Dans la plupart des modèles d’apprentissage automatique, vous n’avez plus de fonction objective explicite. Au lieu de cela, vous devez faire comprendre au modèle quel type de problème il examine réellement et à quoi ressemble une bonne solution au problème. Par exemple, de la même manière que pour former un grand modèle linguistique sur des mots dans une langue donnée, vous devez former un modèle d’apprentissage d’itinéraire sur le concept des différents arrêts de livraison et leurs caractéristiques de demande. Tout comme la grammaire inhérente au langage naturel, votre modèle doit comprendre comment relier ces arrêts de livraison de manière à aboutir à une bonne solution – dans notre cas, une solution rapide ou bon marché. Si vous lui lancez ensuite un tout nouvel ensemble de demandes de clients, il sera toujours capable de relier les points de manière assez littérale, comme vous le feriez également si vous essayiez de trouver un bon chemin pour connecter ces clients.
Pour cela, nous utilisons des architectures de modèles que la plupart des gens connaissent dans l’espace de traitement du langage. Cela semble un peu contre-intuitif, car quel est le rapport entre le traitement du langage et le routage ? Mais en réalité, les propriétés de ces modèles, en particulier les modèles de transformation, sont efficaces pour trouver la structure du langage, c’est-à-dire relier les mots de manière à former des phrases. Par exemple, dans une langue, vous avez un certain vocabulaire, et c’est fixe. Il s’agit d’un ensemble discret de mots possibles que vous pouvez utiliser, et le défi consiste à les combiner de manière significative. En routage, c’est pareil. À Cambridge, il y a environ 40 000 adresses que vous pouvez visiter. Habituellement, c’est un sous-ensemble de ces adresses qui doit être visité, et le défi est le suivant : comment combiner ce sous-ensemble – ces « mots » – dans une séquence qui a du sens ?
C’est en quelque sorte la nouveauté de notre approche : tirer parti de cette structure qui s’est avérée extrêmement efficace dans l’espace linguistique et l’intégrer dans l’optimisation combinatoire. Le routage n’est pour nous qu’un excellent banc d’essai car il s’agit du problème le plus fondamental du secteur de la logistique.
Bien entendu, il existe déjà de très bons algorithmes de routage, issus de décennies de recherche opérationnelle. Ce que nous essayons de faire dans ce projet, c’est de montrer qu’avec une approche méthodologique complètement différente, purement basée sur l’apprentissage automatique, nous sommes capables de prédire des itinéraires qui sont à peu près aussi bons, voire meilleurs, que les itinéraires que vous obtiendriez. exécuter une heuristique d’optimisation d’itinéraire de pointe.
Question : Quels avantages une méthode comme la vôtre présente-t-elle par rapport aux autres techniques de bloc opératoire de pointe ?
UN: À l’heure actuelle, les meilleures méthodes sont encore très gourmandes en ressources informatiques nécessaires à la formation de ces modèles, mais vous pouvez concentrer une partie de cet effort en amont. Ensuite, le modèle formé est relativement efficace pour produire une nouvelle solution lorsqu’elle devient nécessaire.
Un autre aspect à considérer est que l’environnement opérationnel d’un itinéraire, notamment dans les villes, est en constante évolution. L’infrastructure routière disponible, les règles de circulation et les limites de vitesse peuvent être modifiées, le parking idéal peut être occupé par autre chose ou un chantier de construction peut bloquer une route. Avec une approche purement basée sur la salle d’opération, vous pourriez en fait avoir des problèmes car vous devrez résoudre l’ensemble du problème instantanément une fois que de nouvelles informations sur le problème seront disponibles. Étant donné que l’environnement opérationnel évolue de manière dynamique, vous devrez le faire encore et encore. Tandis que si vous disposez d’un modèle bien entraîné qui a déjà rencontré des problèmes similaires, il pourrait potentiellement suggérer la meilleure voie à suivre, presque instantanément. Il s’agit plutôt d’un outil qui aiderait les entreprises à s’adapter aux changements de plus en plus imprévisibles de l’environnement.
De plus, les algorithmes d’optimisation sont souvent conçus manuellement pour résoudre le problème spécifique d’une entreprise donnée. La qualité des solutions obtenues à partir de ces algorithmes explicites est limitée par le niveau de détail et de sophistication entré dans la conception de l’algorithme. En revanche, un modèle basé sur l’apprentissage apprend en permanence une politique de routage à partir des données. Une fois que vous avez défini la structure du modèle, un modèle d’apprentissage d’itinéraire bien conçu distillera les améliorations potentielles de votre politique d’itinéraire à partir de la grande quantité d’itinéraires sur lesquels il est formé. En termes simples, un outil de routage basé sur l’apprentissage continuera à améliorer vos itinéraires sans que vous ayez à investir dans la conception explicite de ces améliorations dans l’algorithme.
Enfin, les méthodes basées sur l’optimisation se limitent généralement à l’optimisation pour une fonction objectif très clairement définie, qui cherche souvent à minimiser les coûts ou à maximiser les profits. En réalité, les objectifs auxquels sont confrontés les entreprises et les conducteurs sont bien plus complexes que cela, et souvent aussi quelque peu contradictoires. Par exemple, une entreprise souhaite trouver des itinéraires efficaces, mais elle souhaite également avoir une faible empreinte carbone. Le conducteur veut également être en sécurité et disposer d’un moyen pratique de servir ces clients. En plus de tout cela, les entreprises se soucient également de la cohérence. Un modèle d’apprentissage d’itinéraire bien conçu peut éventuellement capturer à lui seul ces objectifs de grande dimension, et c’est quelque chose que vous ne pourriez jamais atteindre de la même manière avec une approche d’optimisation traditionnelle.
Il s’agit donc du type d’application d’apprentissage automatique qui peut réellement avoir un impact concret et tangible sur l’industrie, sur la société et sur l’environnement. Le secteur de la logistique est confronté à des problèmes bien plus complexes que cela. Par exemple, si vous souhaitez optimiser l’ensemble d’une chaîne d’approvisionnement, par exemple le flux d’un produit depuis le fabricant en Chine via le réseau de différents ports à travers le monde, via le réseau de distribution d’un grand détaillant en Amérique du Nord jusqu’à votre magasin. où vous l’achetez réellement – cela implique tellement de décisions, ce qui rend évidemment la tâche beaucoup plus difficile que l’optimisation d’un seul itinéraire de véhicule. Nous espérons qu’avec ces premiers travaux, nous pourrons jeter les bases des efforts de recherche et de développement du secteur privé afin de créer des outils qui permettront à terme une meilleure optimisation de bout en bout de la chaîne d’approvisionnement.
