Table des matières
Le problème du voyageur de commerce (également appelé problème de voyage du commerçant ou TSP) est le problème de déterminer l’itinéraire le plus court pour vos chauffeurs-livreurs, vos vendeurs sur le terrain et vos représentants de service à prendre en fonction d’une liste de destinations spécifiques.Comprenons le problème avec un exemple.
Un vendeur souhaite visiter quelques endroits pour vendre des marchandises. Il connaît les noms des lieux et les distances entre chacun.Quel est l’itinéraire le plus court que le vendeur doit suivre pour ne visiter chaque emplacement qu’une seule fois avant de revenir au point de départ?
Le problème que vous venez de lire est le fameux problème des vendeurs itinérants.Une extension du problème de circuit hamiltonien, le TSP est un vieux problème en informatique qui a des implications dans la théorie de la complexité et le problème P contre NP.Le problème de l’itinéraire des véhicules et le problème des acheteurs itinérants sont tous deux des généralisations du TSP.Nous expliquons en détail le problème du voyageur de commerce ci-dessous.
Le contexte du problème du voyageur de commerce
Le problème du voyageur de commerce (TSP) a été formulé en 1930, mais c’est encore aujourd’hui l’un des problèmes d’optimisation combinatoire les plus étudiés.
En 1972, Richard Karp a prouvé que le problème du cycle hamiltonien était NP-complet qui est une classe de problèmes d’optimisation combinatoire.Cela signifie que le TSP était NP-difficile et que la complexité du calcul du meilleur itinéraire augmentera de façon exponentielle lorsque davantage de destinations s’ajouteront au problème.
Par exemple, il y a trois itinéraires possibles s’il y a quatre villes, mais il y a 360 itinéraires possibles s’il y a six villes. En effet, les scientifiques ne calculent pas seulement le chemin le plus efficace, mais aussi celui qui fonctionne.Ce calcul utilise l’approche de la force brute pour résoudre le problème en déterminant chaque possibilité, puis en choisissant la meilleure. En d’autres termes, recherchez chaque chemin unique que le vendeur pourrait emprunter.
Même si les difficultés de calcul augmentent avec chaque ville ajoutée à l’itinéraire, les informaticiens ont pu calculer la solution optimale à ce problème pour des milliers de villes depuis le début des années 90.Par exemple, de nombreuses villes d’un État américain pourraient faire partie de la zone de livraison du grand fournisseur de services logistiques.Déterminer l’itinéraire le plus court entre tous les arrêts que le véhicule doit effectuer au quotidien permettrait d’économiser beaucoup de temps et d’argent.
Pourquoi le problème du voyageur de commerce est-il si difficile à résoudre?
En théorie, le TSP est facile à énoncer et peut être résolu en vérifiant chaque itinéraire aller-retour pour trouver le plus court.Cependant, à mesure que le nombre de villes augmente, le nombre correspondant d’allers-retours dépasse les capacités des ordinateurs les plus rapides.
Avec 10 villes, il peut y avoir plus de 300 000 permutations et combinaisons aller-retour.Avec 15 villes, le nombre d’itinéraires possibles pourrait dépasser 87 milliards.Dans les premiers jours de l’informatique, les informaticiens espéraient que quelqu’un trouverait un algorithme ou une approche améliorée pour résoudre le problème du voyageur de commerce dans un laps de temps raisonnable.Cependant, alors que les scientifiques ont fait des progrès avec des scénarios spécifiques, il n’y avait pas quelqu’un pour résoudre le problème efficacement pour les vendeurs itinérants.Un algorithme unique pour tous n’est peut-être pas possible.
Vous voulez voir par vous-même comment Route4Me peut augmenter vos profits?
Que vous souhaitiez réduire le temps qu'il vous faut pour planifier les itinéraires de vos chauffeurs, augmenter le nombre d'arrêts qu'ils peuvent effectuer ou satisfaire vos clients en sachant que vos chauffeurs se présentent à l'heure… Route4Me vous aide à y parvenir!
Applications du problème du voyageur de commerce
Le TSP trouve toujours des applications dans tous les secteurs verticaux. Des solutions efficaces trouvées grâce au TSP sont utilisées en astronomie, en informatique et même en routage de véhicules.Le problème du voyageur de commerce peut également être utilisé pour savoir comment un laser doit se déplacer lorsqu’il perce des points dans une carte de circuit imprimé.Les astronomes utilisent les concepts de TSP pour déterminer le mouvement d’un télescope sur la distance la plus courte entre différentes étoiles dans une constellation.Parmi les autres utilisations du TSP, citons la planification Internet, l’agriculture, la production de micropuces et l’art généré par ordinateur.Vous voulez voir par vous-même comment Route4Me peut augmenter vos profits ?Que vous souhaitiez réduire le temps qu’il vous faut pour planifier les itinéraires de vos chauffeurs, augmenter le nombre d’arrêts qu’ils peuvent effectuer ou satisfaire vos clients en sachant que vos chauffeurs se présentent à l’heure… Route4Me vous aide à y parvenir! COMMENCEZ UN ESSAI GRATUIT DE 14 JOURS
Les défis auxquels sont confrontés les vendeurs itinérants
Presque tous les vendeurs se réveillent 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 bien d’autres de dernière minute.Les vendeurs n’ont pas toujours un horaire confirmé.
En raison de cette lacune, les vendeurs doivent souvent revenir en arrière et emprunter des itinéraires plus longs pour atteindre les adresses des clients.
Ce manque de planification d’itinéraire entraîne des rendez-vous manqués et des opportunités perdues.Le vendeur moderne est confronté aux problèmes supplémentaires de congestion du trafic, de demandes des clients de dernière minute et de délais de livraison spécifiques, en plus des problèmes de route rencontrés par le vendeur d’antan.Si vous pensiez que le TSP du casse-tête mathématique était difficile, considérez ceci: que se passerait-il s’il ne s’agissait pas d’un seul vendeur pour lequel vous deviez planifier des itinéraires?Et si vous aviez une équipe de commerciaux?
Et si vous deviez répartir les visites et les affecter à votre équipe? Et si les vendeurs avaient des créneaux de rendez-vous différents et que votre objectif était de garder leurs itinéraires les plus courts, les plus rapides et les plus efficaces?Considérez ceci: 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. Un algorithme de base qui pèse toutes les combinaisons possibles et sélectionne la meilleure vous prendra des jours, voire des mois. Maintenant, c’est un défi du monde réel, et voici l’optimisation des itinéraires. Qu’est-ce que l’optimisation des itinéraires, demandez-vous! L’optimisation d’itinéraire consiste à trouver l’itinéraire le plus rapide, le plus court et le plus économe en carburant pour un ensemble d’arrêts.
Comment résoudre le problème du voyageur de commerce avec un planificateur d’itinéraire?
Au fur et à mesure que votre équipe grandit, la planification d’itinéraire devient inévitablement trop complexe à gérer à l’aide d’un stylo et du papier ou d’outils standard comme Google Maps ou Waze.
Le respect des horaires peut être difficile, voire impossible, si la planification d’itinéraire est effectuée manuellement.
Vous ne serez pas en mesure de prendre en compte manuellement des éléments tels que les fenêtres de temps des clients et les conditions météorologiques sans certains outils lourds et, par conséquent, vous finirez par passer beaucoup de temps à planifier des itinéraires.
Des situations imprévues telles que des embouteillages ou des travaux de construction peuvent rendre difficile la garde de vos représentants sur le terrain dans les délais et de rencontrer les clients à temps.
Vous risqueriez également d’augmenter vos coûts opérationnels, souvent sous forme de gaspillage de carburant et de salaires en raison d’un temps de conduite plus long.
De plus, vos clients n’auront pas une bonne première impression si vos vendeurs sont en retard aux réunions ou si vos livreurs ne se présentent pas à l’heure.
Un logiciel d’optimisation d’itinéraire fiable optimisé par Dijkstra Algorithm vous aidera à réduire le temps de conduite et la consommation de carburant en trouvant l’itinéraire le plus efficace pour votre équipe en quelques minutes.
C’est un outil qui s’attaque efficacement au problème complexe du voyageur de commerce pour trouver l’itinéraire le plus efficace vers une destination. Il n’existe pas de solution dans l’humanité au problème du voyageur de commerce, trouver l’itinéraire le plus efficace est physiquement impossible, mais il est possible de trouver un «itinéraire très efficace» ou un itinéraire «plus efficace que les humains ne pourraient jamais le faire. Et c’est là qu’une application de planification d’itinéraire peut vous aider.
Un planificateur d’itinéraire aidera à assurer des réunions avec les clients en temps opportun et des économies de coûts et à assurer la sécurité des travailleurs sur le terrain.
C’est parce que nous avons tous tendance à conduire vite pour «rattraper» le temps perdu, ce qui augmente le risque d’accident.
Un optimiseur d’itinéraire réduira le temps de conduite de vos représentants du service sur le terrain afin qu’ils passent du temps productif avec les clients et aient un impact positif sur vos résultats.
Conclusion sur le problème du voyageur de commerce
Il y aura beaucoup plus d’instances de type TSP avec des personnes et des véhicules aux prises avec des itinéraires inexacts et des retards si vous regardez autour de vous.Les courriers livrent des colis à votre bureau.Les livreurs vous apportent des produits frais le jour même de votre commande.Les autobus scolaires qui ne ratent jamais la cible et qui récupèrent et déposent vos enfants à la même heure tous les jours.Les scientifiques tentent de résoudre des problèmes tels que le TSP depuis des décennies. Les plus proches que nous ayons rencontrés – imparfaitement – sont des algorithmes complexes via des applications de planification d’itinéraire faciles à utiliser.
Vous voulez voir par vous-même comment Route4Me peut augmenter vos profits?
Que vous souhaitiez réduire le temps qu'il vous faut pour planifier les itinéraires de vos chauffeurs, augmenter le nombre d'arrêts qu'ils peuvent effectuer ou satisfaire vos clients en sachant que vos chauffeurs se présentent à l'heure… Route4Me vous aide à y parvenir!
