Dans le cadre du problème du voyageur de commerce, il s’agit de déterminer l’itinéraire le plus court que doivent emprunter les représentants des services extérieurs, compte tenu d’une liste de destinations spécifiques.
Essayons de comprendre ce problème à l’aide d’un exemple.
Un voyageur de commerce veut se rendre à quelques endroits pour vendre des marchandises. Les noms des lieux et les distances entre chacun d’eux lui sont connus.
Selon vous, quel est l’itinéraire le plus court que le vendeur devrait suivre pour ne visiter qu’une seule fois chaque endroit avant de revenir au point de départ ?
Le TSP est une extension du problème des circuits hamiltoniens. Il constitue un vieux problème en informatique qui a des implications dans la théorie de la complexité et le problème P versus NP.
La difficulté d’acheminement des véhicules et le problème de l’acheteur voyageur sont tous deux des généralisations du TSP.
Sommaire
Contexte du problème du voyageur de commerce
La formulation du problème du voyageur de commerce (TSP) remonte à 1930. Aujourd’hui encore, c’est l’un des problèmes d’optimisation combinatoire les plus étudiés.
Le problème du cycle hamiltonien, une classe de problèmes d’optimisation combinatoire, est NP-complet, comme l’a prouvé Richard Karp en 1972.
Autrement dit, le TSP était NP-hard. Par ailleurs, la complexité du calcul du meilleur itinéraire augmentera de manière factorielle lorsque davantage de destinations seront ajoutées au problème.
Dans le cas de quatre villes, par exemple, il peut y avoir trois routes possibles. Mais il pourrait y avoir 360 itinéraires possibles dans six villes.
La raison en est que les scientifiques ne calculent pas seulement le chemin le plus efficace, mais aussi celui qui fonctionne.
Cette méthode de calcul utilise la force brute pour résoudre le problème en envisageant toutes les possibilités, puis en choisissant la meilleure. C’est-à-dire qu’il faut rechercher tous les chemins uniques que le vendeur pourrait emprunter.
Malgré le fait que les difficultés de calcul augmentent avec chaque ville ajoutée à l’itinéraire, les informaticiens ont calculé la solution optimale à ce problème pour des milliers de villes depuis le début des années 90.
Plusieurs villes d’un État américain, par exemple, peuvent faire partie de la zone de livraison d’un grand prestataire logistique.
La recherche de l’itinéraire le plus court entre tous les arrêts que le véhicule doit effectuer au quotidien permettrait de gagner beaucoup de temps et d’argent.
En quoi le problème du voyageur de commerce est-il difficile ?
La TSP peut théoriquement être résolue en vérifiant chaque itinéraire aller-retour pour trouver le plus court.
Mais au fur et à mesure que le nombre de villes augmente, le nombre correspondant d’allers-retours dépasse les capacités des ordinateurs les plus rapides.
Avec dix villes, il peut y avoir plus de 300 000 permutations et combinaisons de trajets aller-retour.
En comptant 15 villes, les itinéraires possibles pourraient être plus de 87 milliards.
Dans les débuts de l’informatique, les informaticiens espéraient que quelqu’un développerait un algorithme amélioré pour résoudre le problème en un temps raisonnable.
Mais alors que les scientifiques ont progressé avec des scénarios spécifiques, il n’existait pas de solution efficace au problème du voyageur de commerce.
Il se peut même qu’un algorithme à taille unique ne soit pas possible.
Solutions au problème du voyageur de commerce
La théorie de la planification stratégique des transports trouve toujours des applications dans tous les secteurs verticaux. On trouve des solutions efficaces grâce à la TSP en astronomie, en informatique, et même dans le routage des véhicules.
La TSP permet aux astronomes de déterminer le mouvement d’un télescope pour la distance la plus courte entre différentes étoiles d’une constellation.
Les TSP sont également utilisées pour la planification d’Internet, l’agriculture, la production de puces électroniques et l’art généré par ordinateur.
Enjeux des vendeurs itinérants
Les commerciaux se lèvent presque tous le matin avec l’idée de tirer le meilleur parti de leur journée.
Ils ont de nombreux rendez-vous confirmés avec leurs clients et beaucoup d’autres de dernière minute.
Le planning des vendeurs n’est pas toujours confirmé. De ce fait, ils doivent souvent faire marche arrière et emprunter des itinéraires plus longs pour atteindre les adresses des clients. Il en résulte des rendez-vous manqués et des opportunités perdues.
De nos jours, le vendeur doit faire face aux problèmes supplémentaires que sont les embouteillages, les demandes de dernière minute des clients et les délais de livraison spécifiques. Sans compter les problèmes d’itinéraire rencontrés par les vendeurs d’antan.
Si le PST de l’énigme mathématique vous semblait difficile, envisagez ceci :
Il se peut que vous deviez planifier pour une équipe de représentants commerciaux plutôt que pour un seul vendeur ?
A présent, vous devez répartir les visites et les attribuer à votre équipe !
Imaginez que les commerciaux aient des créneaux de rendez-vous différents, et que votre objectif soit de faire en sorte que leurs itinéraires soient les plus courts, les plus rapides et les plus efficaces ?
Voyez ce qui suit : Si vous avez un total de 100 adresses de clients et que votre équipe compte huit vendeurs, il pourrait y avoir plus d’un million de combinaisons d’itinéraires possibles.
La mise en place d’un algorithme de base qui évalue toutes les combinaisons possibles et sélectionne la meilleure vous prendra des jours, voire des mois.
Voilà un défi à relever dans le monde réel, et voici l’optimisation des routes.
Comment définir l’optimisation des itinéraires ?
La stratégie d’optimisation des itinéraires consiste à trouver l’itinéraire le plus rapide, le plus court et le plus économe en carburant pour un ensemble d’arrêts.
Résoudre le problème du voyageur de commerce avec un planificateur d’itinéraire
Lorsque votre équipe s’agrandit, la planification des itinéraires devient inévitablement trop complexe pour être gérée à l’aide d’un stylo et de papier ou d’outils standard comme Google Maps ou Waze.
En l’absence d’outils performants, vous ne pouvez pas prendre en compte manuellement des éléments tels que les barrages routiers et les conditions météorologiques. Finalement, vous passerez beaucoup de temps à planifier les itinéraires.
En cas de situations imprévues, comme les embouteillages, il est difficile d’arriver à l’heure.
Lorsque vous essayez d’optimiser les horaires manuellement, il est difficile de répartir la charge de travail de manière équilibrée.
De plus, vous risquez d’augmenter vos coûts opérationnels. Cela se traduit souvent par un gaspillage de carburant et de salaires dû à l’allongement du temps de conduite.
De même, vous risquez d’irriter vos clients si vos représentants commerciaux arrivent en retard ou si vos chauffeurs ne respectent pas les délais de livraison.
La solution idéale au problème du voyageur de commerce est un logiciel de routage de véhicules.
Grâce à l’algorithme de Dijkstra, un planificateur d’itinéraire fiable réduira le temps de conduite et la consommation de carburant en trouvant l’itinéraire le plus efficace pour votre équipe en quelques secondes.
L’application s’attaque efficacement au TSP complexe qui consiste à trouver la route la plus efficace vers une destination. Déterminer la route la plus efficace est physiquement impossible. Cependant, il est possible de trouver un « itinéraire très efficace » ou un itinéraire qui est « plus efficace que ce que les humains ne pourront jamais faire ». À cet égard, une application de planification d’itinéraire peut être utile.
Cette application garantit la ponctualité des livraisons et des rendez-vous, la réduction des coûts et la sécurité du conducteur. De même, un optimiseur d’itinéraire réduit le temps de conduite de vos agents de terrain et a un impact sur vos résultats. Mais ce n’est pas tout.
Fin de la discussion sur le problème du voyageur de commerce
De nombreuses autres situations similaires à la TSP existent, où des personnes et des véhicules sont aux prises avec des itinéraires imprécis et des retards.
Depuis des décennies, les scientifiques tentent de résoudre des problèmes comme celui de la TSP. Les algorithmes complexes utilisés dans les applications de planification d’itinéraire faciles à utiliser sont ceux qui s’en rapprochent le plus, même si c’est de manière imparfaite.
