Le problème du voyageur de commerce en logistique

Le problème du voyageur de commerce, ou Traveling Salesman Problem en anglais, représente l’un des sujets les plus courants dans le domaine de la logistique. De quoi s’agit-il ?

En quoi consiste le problème du voyageur de commerce ?

Dans le domaine de la recherche opérationnelle et de l’informatique théorique, le problème du voyageur de commerce consiste à déterminer l’itinéraire optimal pour passer une seule fois à un certain nombre d’endroits. L’objectif étant d’économiser au maximum les ressources nécessaires à la livraison de marchandises ou au rendez-vous chez un client, par exemple.

Les algorithmes liés au problème du voyageur de commerce sont utilisés par les entreprises pour la planification des itinéraires et l’optimisation des services de livraison. En effet, ces algorithmes leur permettent d’accroître la rentabilité et la durabilité de leurs activités par la réduction des distances parcourues, ce qui se traduit également par une diminution des émissions.

Le problème du voyageur de commerce a beaucoup suscité l’intérêt en informatique théorique au fil des ans, en raison de sa difficulté à être résolu malgré la simplicité de sa description. Le nombre de séquences pour le résoudre croît de manière exponentielle avec le nombre de villes ou de lieux de livraison desservis. C’est pourquoi les informaticiens s’appuient sur des algorithmes d’approximation pour trouver l’itinéraire le plus court à un coût minimal. Certaines des méthodes les plus courantes sont présentées ci-après.

L’origine du problème du voyageur de commerce

L’histoire la plus récente du problème du voyageur de commerce remonte au 20e siècle avec l’économiste Karl Menger. Il a présenté le problème au mathématicien Hassler Whitney, qui l’a exposé quelques années plus tard à l’université de Princeton, aux États-Unis. À cette occasion, A.W. Tucker et Merril Flood ont discuté des possibilités d’application dans le contexte du transport scolaire dans le New Jersey.

Comment résoudre le problème du voyageur de commerce ?

Il existe deux méthodes principales pour répondre à la question posée par le problème du voyageur de commerce à l’aide d’algorithmes :

1. Algorithmes exacts. Cette approche recherche la solution de manière exhaustive, mais elle n’est souvent pas applicable en raison du temps considérable de calcul exigé.
2. Algorithmes heuristiques. Ils fournissent des réponses approximatives en moins de temps.

Nous décrivons ci-dessous les algorithmes heuristiques.

Recherche exhaustive

Elle consiste à calculer tous les itinéraires possibles puis à les comparer avant d’en choisir le plus court et pratique. Elle n’est utile que dans des scénarios simples.

Séparation et évaluation

Cette méthode, appelée branch and bound en anglais, commence par le choix d’un itinéraire initial. Ensuite, elle analyse systématiquement les variantes et, à chaque ajout d’un nœud, l’algorithme calcule la distance à parcourir puis la compare à celle de l’option précédente. Si la distance totale augmente, cette solution est éliminée et n’est plus considérée comme une option.

De cette manière, l’algorithme écarte plusieurs possibilités pour cerner celle qui sera la plus rentable pour le transporteur ou pour l’équipe commerciale à déplacer. Le processus continue à évaluer tous les itinéraires possibles afin d’identifier le plus court comme solution optimale.

Recherche des plus proches voisins

La mise en œuvre de cet algorithme commence à un endroit aléatoire. De là, le nœud le plus proche est localisé et ajouté au séquençage. Cette action est répétée à partir du nœud suivant jusqu’à ce que toutes les villes ou destinations soient incluses dans l’itinéraire. Enfin, on retourne au point de départ pour clore le cycle. Bien qu’elle puisse sembler la manière la plus simple de résoudre le problème du voyageur de commerce, cette approche n’est pas toujours la plus indiquée.

Applications du problème du voyageur de commerce

Bien qu’il puisse s’avérer difficile de trouver la solution optimale au problème du voyageur de commerce, les approximations sont utilisées dans tous les secteurs d’activité :

1. Robotique et automatisation. La rationalisation des mouvements des robots et des machines permet de réduire leur consommation d’énergie et d’améliorer leur efficacité. Le logiciel de gestion de flotte des AMR (robots mobiles autonomes), par exemple, détermine quel robot est le plus proche du point d’origine du mouvement à effectuer, afin de minimiser les délais d’exécution et de prolonger la durée de vie de la batterie.
2. Fabrication et planification de la production. Cette technique peut également être appliquée dans le cadre de la production, où l’itinéraire de maintenance le plus court permettrait d’examiner toutes les machines avec un impact minimal sur le plan de production.
3. Logistique et transport. Les applications du problème du voyageur de commerce en logistique sont nombreuses :
   • Transport de marchandises. Les transporteurs ont recours au problème du voyageur de commerce pour que les camions puissent se rendre dans toutes les villes concernées par les livraisons dans les meilleurs délais. Ainsi, le véhicule se libère plus tôt et peut prendre en charge davantage de demandes.
   • Transport de passagers. De même, les entreprises de transport routier ou d’autres moyens de transport peuvent se servir du problème du voyageur de commerce pour déterminer la meilleure façon d’achever un voyage, la proposer au client et répondre à ses attentes.
   • Assistance technique. Les entreprises de services peuvent créer un itinéraire couvrant tous les sites à inspecter, optimisant ainsi la durée d’intervention des techniciens.

Les autres facteurs influençant le problème du voyageur de commerce

Il est difficile de trouver un algorithme permettant de résoudre tous les problèmes du voyageur de commerce, en raison de certaines contraintes. Par exemple, cette méthode ne prend pas en compte les événements et les imprévus tels que :

• Des rendez-vous programmés à une heure précise ou organisés à la dernière minute
• Des retards dans la circulation
• Des horaires contraignants pour certaines destinations
• Des changements d’itinéraire pour cause de force majeure

Le problème du voyageur de commerce dans l’entrepôt

Le problème du voyageur de commerce s’applique non seulement à l’optimisation des itinéraires routiers, mais aussi à l’intérieur des entrepôts et des centres de distribution. Par exemple, il est possible d’améliorer les opérations de picking afin de minimiser le nombre de déplacements des opérateurs tout en maximisant le nombre de commandes préparées. Les mouvements et les processus sont suivis et coordonnés par un logiciel de gestion d’entrepôt afin d’en multiplier la rentabilité.

Vous souhaitez rendre votre logistique agile ? Chez Mecalux, nous pouvons vous accompagner. Nous avons développé Easy WMS dans le but d’améliorer les performances des entrepôts traditionnels et automatisés, et ce sont déjà des centaines de clients qui s’en servent quotidiennement pour leurs opérations. Pour des conseils sur notre WMS ainsi que sur d’autres solutions de stockage, contactez-nous.