La solution du problème du voyageur de commerce pour les entreprises de livraison et de service

Calculer l'itinéraire le plus efficace entre plusieurs villes est un défi majeur. Il existe des centaines d'options possibles qui changent en fonction de centaines de variables différentes.

Par exemple, dans seulement 15 villes, il y a plus de 87 milliards de voyages aller-retour possibles. 

C'est le problème du voyageur de commerce. 

Et c'est un problème incroyablement coûteux pour toute entreprise de livraison, de service ou de transport.

Pour résoudre le problème du voyageur de commerce, vous avez besoin d'algorithmes robustes et d'une puissance de calcul sérieuse.

Si vous ne souhaitez pas investir dans une équipe interne de mathématiciens et d'ingénieurs experts, vous avez besoin d'une solution tierce.

Dans cet article, nous explorerons ce qui rend le problème du voyageur de commerce (TSP) si difficile et comment les propriétaires d'entreprises peuvent utiliser des solutions logicielles intelligentes pour le résoudre, réduire le kilométrage et améliorer l'efficacité de la flotte.

Pour naviguer vers la section qui vous intéresse le plus, cliquez ci-dessous :

• Qu'est-ce que le problème du voyageur de commerce ?
• Pourquoi le problème du voyageur de commerce est-il toujours difficile à résoudre en 2020
• Comment The Little Posy Co. planifie des itinéraires pour 1 000 destinations en quelques minutes

Qu'est-ce que le problème du voyageur de commerce ?

Le problème du voyageur de commerce (TSP) est un problème qui demande, avec une liste d'arrêts et les distances entre chacun d'eux, quel est le chemin le plus court/possible qui visite chaque lieu et retourne à l'origine ?

Depuis des décennies, le TSP est un défi pour de nombreuses entreprises qui dépendent de la planification d'itinéraires — par exemple, les entreprises de services sur le terrain, d'expédition et de livraison.

Avec juste un point de départ et quelques arrêts, planifier un itinéraire peut sembler déjà assez compliqué.

Mais une fois que vous commencez à planifier des itinéraires à travers le pays, cela atteint un niveau de complexité presque impensable. Avec des permutations infinies de routes potentielles entre différents arrêts (généralement appelés nœuds), identifier l'itinéraire le plus court et le plus efficace est un énorme défi.

Voici à quoi ressemblerait un itinéraire planifié pour chaque ville des États-Unis avec plus de 500 habitants :

(Source de l'image)

Imaginez simplement le nombre de routes possibles que vous pourriez emprunter lorsqu'une seule solution possible est aussi complexe.

Pourquoi le problème du voyageur de commerce est-il toujours difficile à résoudre en 2021

Le mathématicien Karl Menger a découvert le TSP en 1930, il y a plus de 90 ans.

Depuis lors, de nombreuses solutions et algorithmes ont été proposés. Mais ils ont souvent du mal avec l'ampleur du problème, car le nombre de itinéraires de vente augmente de façon exponentielle à chaque nouvel arrêt.

Et la vérité est que la planification d'itinéraires en 2021 pour les entreprises réelles est plus complexe qu'une simple liste d'arrêts — ce qui complique encore les choses.

Dans le monde réel, ce n'est pas aussi simple que de trouver simplement le chemin le plus court.

Il ne s'agit pas seulement des destinations et des distances, de nombreux autres facteurs entrent en jeu.

Ce n'est pas aussi simple que de prendre une liste d'adresses et de créer un itinéraire. 

Un représentant commercial sur le terrain , un chauffeur-livreur ou un technicien doit également prendre en compte de nombreux autres facteurs, comme les créneaux horaires, les capacités des véhicules, et plus encore.

Créneaux horaires de livraison et réunions de vente planifiées

Que se passe-t-il si vos chauffeurs-livreurs ou vos commerciaux ont des horaires de livraison ou des réunions de vente planifiés ? Alors il ne suffit pas de considérer la distance, il faut aussi tenir compte du moment où ils doivent être à chaque endroit.

Cela ajoute un tout nouveau niveau de complexité, et c'est un défi que la plupart des planificateurs d'itinéraires ne peuvent tout simplement pas gérer.

Cette instance particulière du problème est également connue sous le nom de Problème de Tournées de Véhicules avec Fenêtres de Temps (VRPTW). 

Capacités requises des véhicules ou qualifications des techniciens

Pour les livraisons, chaque colis que vous planifiez peut avoir des exigences spécifiques en termes d'expédition et de manutention, allant de la réfrigération aux dimensions de déchargement.

Vous devez également prendre en compte la capacité de chargement globale de chaque véhicule.

Mais même pour les entreprises de maintenance et de services sur le terrain, vous devez considérer les qualifications uniques de chaque technicien, et si elles correspondent à un travail.

Cela est également connu sous le nom de Problème de Tournées de Véhicules Capacités (CVRP).

Planification d'itinéraires efficaces incluant à la fois les ramassages et les livraisons

Si votre entreprise livre des emballages réutilisables ou des matériaux recyclables à vos clients, il y a de fortes chances que la logistique inverse soit une priorité majeure.

Pour maximiser l'efficacité de votre entreprise, vous souhaitez intégrer à la fois le ramassage et la livraison dans tous les itinéraires planifiés.

Cela ajoute une autre dimension et un niveau de complexité que la plupart des outils d'optimisation des itinéraires ne peuvent pas gérer.

Cela est également appelé le Problème de Tournées de Véhicules avec Ramassage et Livraison (PDVRP)

Prendre en compte la priorité des prospects, des clients existants et des livraisons

Pour gérer une entreprise efficacement et garder les clients VIP satisfaits, vous devez également vous assurer que votre personnel priorise les choses correctement.

Si vos itinéraires ne prennent pas en compte la priorité, chaque client sera traité de la même manière. Vous risquez donc d'aliéner les clients fidèles si vous passez soudainement à une solution automatisée qui ne peut pas gérer cela.

Équilibrer les charges de travail entre plusieurs conducteurs

Bien sûr, lors de la planification des itinéraires pour plusieurs conducteurs, vous devez également prendre en compte leurs charges de travail.

Les conducteurs sont humains et ont une durée de service maximale de 14 heures avec des pauses obligatoires.

À quoi bon un « itinéraire efficace » s'il est impossible pour un conducteur de le gérer dans le temps imparti ?

De bons outils d'équilibrage de la charge de travail vous aideront à réduire les heures supplémentaires et à diminuer les coûts des conducteurs, tout en vous assurant que tous les conducteurs respectent les heures de service à tout moment.

Comment The Little Posy Co. Planifie des Itinéraires pour 1 000 Destinations en Quelques Minutes avec OptimoRoute

The Little Posy Co. est une entreprise australienne de livraison de fleurs, proposant chaque jour des centaines de fleurs et de bouquets uniques.

Comme toute entreprise de livraison de fleurs ou fleuriste, elle fait face à d'énormes fluctuations de la demande en fonction des différentes fêtes.

Le jour de la Saint-Valentin en 2019, le volume de commandes a explosé à plus de 1 000 commandes en une journée, le même volume qu'une semaine normale.

Normalement, cela serait une tâche impossible pour la petite équipe de Posy, mais l'algorithme d'optimisation d'OptimoRoute a aidé à rationaliser tout le processus.

« OptimoRoute a transformé l'impossible en absolument possible le jour de la Saint-Valentin. Cela enlève la pression - je ne pouvais pas imaginer comment le flux de travail pourrait fonctionner aussi bien sans ce logiciel. » – Gabby Maynard, The Little Posy Co.

Importation en Masse des Commandes et Planification Automatique Rapide des Itinéraires

Avec OptimoRoute, il n'est pas nécessaire d'ajouter individuellement des arrêts ou des adresses, ni de planifier des itinéraires pour un seul conducteur à la fois.

Vous pouvez simplement importer votre liste de commandes dans une feuille de calcul Excel ou un fichier CSV.

À partir de là, OptimoRoute planifie automatiquement les itinéraires, en s'ajustant aux contraintes du monde réel comme les horaires de livraison, les zones de service des conducteurs, les horaires des conducteurs, et plus encore.

« Je ne pouvais même pas imaginer devoir expédier 1 000 commandes sans OptimoRoute car cela se fait littéralement en quelques clics de souris et les itinéraires sont parfaitement tracés. » Gabby Maynard, The Little Posy Co.

Les Données Historiques et les Analyses Aident à Prévoir la Demande

Les données historiques des itinéraires et les analyses détaillées ont aidé Maynard à prévoir la demande et à ajuster la flotte en conséquence.

« Nous nous appuyons fortement sur les données historiques – savoir combien de conducteurs je dois recruter pour la journée, combien de commandes chaque conducteur peut prendre, combien de temps ces livraisons prendraient, et combien de conducteurs ont été dépêchés. » Gabby Maynard, The Little Posy Co.

Réflexions Finales

En tant que propriétaire d'entreprise, la dernière chose que vous voulez faire est de perdre du temps inutilement à rester sur Google Maps en essayant de planifier des itinéraires sans obtenir de solutions optimales (L'optimisation des itinéraires Google Maps n'est pas faite pour les entreprises).

Le problème du voyageur de commerce affecte les entreprises car planifier des itinéraires manuellement demande beaucoup de travail, augmentant les heures de travail et les coûts totaux de votre logistique.

Cela peut souvent signifier des départements de répartition et de planification surdimensionnés, et une flotte lente à réagir aux annulations et aux commandes de dernière minute.

Heureusement, vous n'avez pas besoin d'avoir un diplôme en informatique, de créer un algorithme d'approximation, ou d'être mathématicien pour trouver la meilleure solution pour le TSP.

OptimoRoute offre une expérience de planification d'itinéraires sans problème, avec des fonctionnalités intelligentes qui aident les répartiteurs à planifier des itinéraires en quelques minutes. Il rend également votre flotte plus flexible, aidant les répartiteurs à s'adapter aux changements en temps réel.

Pour voir comment OptimoRoute peut aider votre entreprise à surmonter le TSP, commencez votre essai gratuit de 30 jours dès aujourd'hui.

FAQ sur le problème du voyageur de commerce

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

Les mathématiciens et les informaticiens ont proposé un certain nombre d'heuristiques ou de solutions approximatives pour résoudre le problème du voyageur de commerce. Une solution courante, appelée méthode de séparation et évaluation, consiste à diviser le problème en une série de sous-problèmes plus petits qui sont plus faciles à résoudre mathématiquement que de tenter de le résoudre en une seule fois.

Quel est un exemple du problème du voyageur de commerce ?

Outre l'exemple évident (eh bien, un voyageur de commerce), prenons l'exemple d'un service de livraison qui livre à un certain nombre de lieux différents dans une ville. Le répartiteur doit déterminer l'ordre dans lequel ils s'arrêtent (en dehors du point de départ). Vous pourriez penser : il suffit de s'arrêter à l'endroit le plus proche du point de départ, puis au plus proche de celui-ci, etc. 

Mais que se passe-t-il si l'arrêt le plus proche du point de départ vous éloigne de tous les autres arrêts ? Vous devez considérer la distance des prochains lieux par rapport au premier arrêt que vous choisissez. Comme vous pouvez le voir, le nombre de variables se multiplie rapidement, et trouver le chemin le plus court devient extrêmement complexe à mesure que vous ajoutez de plus en plus de variables.

Pourquoi le problème du voyageur de commerce est-il considéré comme NP-difficile ?

Le problème du voyageur de commerce est considéré comme un problème NP-difficile car il n'existe pas de solution simple ou directe, et la difficulté de calculer l'itinéraire optimal avec le temps d'exécution le plus court augmente à mesure que l'on ajoute plus de destinations.