Une meilleure approche du « problème des vendeurs itinérants » pourrait améliorer les secteurs de la logistique et des transports

camion de messagerie

Crédit : domaine public Unsplash/CC0

Une nouvelle approche pour résoudre le problème du voyageur de commerce, l’une des questions les plus difficiles en informatique, surpasse de manière significative les approches actuelles.

Question théorique notoire qui a intrigué les chercheurs pendant 90 ans, le problème du voyageur de commerce a également une réelle pertinence pour l’industrie aujourd’hui. Essentiellement une question sur la meilleure façon de combiner un ensemble de tâches afin qu’elles puissent être exécutées de la manière la plus rapide et la plus efficace, trouver de bonnes solutions au problème peut grandement aider à améliorer des secteurs tels que le transport et la logistique.

Des chercheurs de l’Université de Cambridge ont développé une approche hybride, basée sur les données, du problème qui produit non seulement des solutions de haute qualité, mais à un rythme plus rapide que d’autres approches de pointe. Leurs résultats sont présentés cette semaine à la Conférence internationale sur les représentations de l’apprentissage.

“L’importance du système logistique mondial nous a été rappelée pendant la pandémie”, a déclaré le Dr Amanda Prorok du Département d’informatique et de technologie de Cambridge, qui a dirigé la recherche. “Nous dépendons fortement de ce type d’infrastructure pour être plus efficaces, et notre solution pourrait y contribuer car elle cible à la fois la logistique en entrepôt, comme l’acheminement des robots autour d’un entrepôt pour collecter les marchandises à livrer, et celles à l’extérieur comme l’acheminement des marchandises vers les personnes. »

Le problème du vendeur itinérant implique un chauffeur-livreur fictif qui doit appeler dans un certain nombre de villes, disons 20, 50 ou 100, qui sont reliées par des autoroutes en un seul trajet. Le défi est de trouver l’itinéraire le plus court possible qui appelle une fois à chaque destination et de le trouver rapidement.

“Il y a deux éléments clés au problème. Nous voulons ordonner les arrêts, et nous voulons également connaître le coût, en temps ou en distance, d’aller d’un arrêt à un autre dans cet ordre”, a déclaré Prorok.

Il y a vingt ans, l’itinéraire de l’entrepôt aux destinations aurait pu être fixé à l’avance. Mais avec la disponibilité actuelle d’informations sur le trafic en temps réel et la possibilité d’envoyer des messages au chauffeur pour ajouter ou supprimer des lieux de livraison à la volée, l’itinéraire peut désormais changer pendant le trajet. Mais minimiser sa longueur ou sa durée reste la clé.

Il y a souvent un coût attribué à l’attente d’une solution optimale ou à des délais serrés auxquels les décisions doivent être prises. Par exemple, le conducteur ne peut pas attendre qu’une nouvelle solution soit calculée, il peut manquer ses livraisons ou les conditions de circulation peuvent changer à nouveau.

Et c’est pourquoi il existe un besoin d’algorithmes d’optimisation combinatoire généraux, à tout moment, qui produisent des solutions de haute qualité avec un temps de calcul limité.

Pour ce faire, l’approche hybride développée par Cambridge combine un modèle d’apprentissage automatique qui fournit des informations sur les meilleurs itinéraires précédents et un outil “métaheuristique” qui utilise ces informations pour assembler le nouvel itinéraire.

“Nous voulons trouver les bonnes solutions plus rapidement”, a déclaré Ben Hudson, le premier auteur de l’article. “Si je suis chauffeur pour une entreprise de messagerie, je dois décider quelle sera ma prochaine destination pendant que je conduis. Je ne peux pas me permettre d’attendre une meilleure solution. C’est pourquoi, dans nos recherches, nous nous sommes concentrés sur le compromis entre le temps de calcul nécessaire et la qualité de la solution que nous avons obtenue.”

Pour ce faire, Hudson a proposé un algorithme de recherche locale guidée qui pourrait différencier les itinéraires d’une ville à l’autre qui seraient coûteux – en temps ou en distance – des itinéraires qui seraient moins coûteux à inclure dans le voyage. Cela a permis aux chercheurs d’identifier rapidement des solutions de haute qualité plutôt qu’optimales.

Pour ce faire, ils ont utilisé une mesure de ce qu’ils appellent le «regret global» – le coût de l’application d’une décision par rapport au coût d’une solution optimale – de chaque itinéraire de ville à ville dans l’algorithme de recherche locale guidée. Ils ont utilisé l’apprentissage automatique pour arriver à une approximation de ce “regret”.

“Nous connaissons déjà la solution correcte à un ensemble de ces problèmes”, a déclaré Hudson. “Nous avons donc utilisé des techniques d’apprentissage automatique pour essayer d’apprendre de ces solutions. Sur cette base, nous essayons d’apprendre pour un nouveau problème – pour un nouvel ensemble de villes à différents endroits – quels chemins entre les villes sont prometteurs.

“Lorsque nous avons ces informations, elles alimentent ensuite la partie suivante de l’algorithme, la partie qui dessine réellement les itinéraires. Il utilise ces informations supplémentaires sur les bons chemins possibles pour construire une bonne solution beaucoup plus rapidement qu’il n’aurait pu le faire. fait autrement.”

Les résultats qu’ils ont obtenus étaient impressionnants. Leurs expériences ont démontré que l’approche hybride axée sur les données converge vers des solutions optimales à un rythme plus rapide que trois approches récentes basées sur l’apprentissage pour le problème du vendeur itinérant.

En particulier, en essayant de résoudre le problème lorsqu’il y avait un itinéraire de 100 villes, la méthode de Cambridge a réduit l’écart d’optimalité moyen de 1,534 % à 0,705 %, soit une double amélioration. Lors de la généralisation de l’itinéraire de problème de 20 villes à l’itinéraire de problème de 100 villes, la méthode a réduit l’écart d’optimalité de 18,845 % à 2,622 %, soit une amélioration de sept fois.

“De nombreuses entreprises de logistique utilisent des méthodes de routage dans la vraie vie”, a déclaré Hudson. “Notre objectif avec cette recherche est d’améliorer ces méthodes afin qu’elles produisent de meilleures solutions – des solutions qui se traduisent par des distances parcourues plus courtes et donc des émissions de carbone plus faibles et un impact réduit sur l’environnement.”


L’apprentissage automatique accélère le routage des véhicules


Plus d’information:
Graph Neural Network Guided Local Search pour le problème du voyageur de commerce. openreview.net/forum?id=ar92oEosBIg

Fourni par l’Université de Cambridge

Citation: Une meilleure approche du «problème des vendeurs itinérants» pourrait améliorer les secteurs de la logistique et des transports (26 avril 2022) récupéré le 26 avril 2022 sur https://techxplore.com/news/2022-04-approach-salesperson-problem-logistics-sectors .html

Ce document est soumis au droit d’auteur. En dehors de toute utilisation loyale à des fins d’étude ou de recherche privée, aucune partie ne peut être reproduite sans l’autorisation écrite. Le contenu est fourni seulement pour information.