Parlez à un sympathique expert maintenant:
+1-888-552-9045
Essai Gratuit - 7 jours

Mieux comprendre le problème de routage de véhicule (VRP)

Crédit image en vedette: Olivier Le Moal/iStockphoto.com

Le problème de l’acheminement des véhicules ( ou VRP en anglais ) n’est pas nouveau et représente un défi majeur pour toutes les entreprises de service après-vente depuis des décennies.À première vue, les problèmes de routage et de planification des véhicules peuvent ressembler à des problèmes commerciaux typiques. Cependant, ils sont compliqués par de multiples paramètres et des contraintes de ressources.Supposons que vous ayez près de 1 000 livraisons à effectuer chaque jour avec 20 véhicules.Comment décidez-vous quels véhicules doivent servir, quelles livraisons et dans quel ordre ?Vous devez faire tout cela en tenant compte de la consommation de carburant, des heures de pointe de la circulation, des sous-constructions ou des routes en mauvais état, et des fenêtres horaires spécifiques pour chaque client.Dans la vraie vie, la planification des itinéraires comporte de nombreuses incertitudes, telles que les demandes changeantes des clients, les embouteillages et les conditions météorologiques imprévues.Ces incertitudes peuvent entraîner une augmentation des coûts de transport si elles ne sont pas traitées correctement. Pire encore, ces complexités augmentent de façon exponentielle à mesure que le nombre de véhicules et de clients augmente.Il va sans dire que la résolution du VRP est cruciale pour faciliter le mouvement transparent des biens et des services d’un endroit à un autre, mais trouver la bonne solution au VRP est une tâche herculéenne. Alors, comment pouvez-vous résoudre le VRP dynamique ?Avant d’en discuter, commençons par bien comprendre les bases, en commençant par ce qu’est le VRP.

Quel est le problème de routage des véhicules ?

Le VRP est le défi de déterminer les itinéraires optimaux d’un dépôt à un ensemble de destinations ayant chacune des contraintes opérationnelles ou métiers. Ces contraintes comprennent le contrôle des coûts, les limitations des véhicules, la longueur de l’itinéraire et les fenêtres horaires.Le VRP a été nommé et documenté pour la première fois dans les années 1950, mais le premier VRP classique, connu sous le nom de problème du voyageur de commerce, est né dans les années 1800.Examinons maintenant de plus près les VRP les plus courants et les outils que vous pouvez utiliser pour les démêler.

Quels sont les VRP les plus habituels ?

Vous trouverez ci-dessous quelques-uns des VRP réels auxquels les entreprises de services sur le terrain sont souvent confrontées dans leurs opérations quotidiennes.

Problème de tournées de véhicules avec fenêtres de temps (VRPTW)

Les clients exigent souvent que leurs livraisons soient effectuées pendant une période spécifique. Cela limite les délais de ramassage et de livraison, car votre chauffeur doit se présenter à la porte d’un client dans un délai prioritaire.Notez que le chauffeur peut arriver avant l’heure de livraison prévue, mais jamais en dehors de la fenêtre horaire définie.Prendre du retard va ennuyer vos clients et entraîner une augmentation de l’attrition des clients et une baisse significative des revenus et de la marge bénéficiaire.Vous devez donc prendre en compte les fenêtres horaires de la manière la plus rentable possible, lors de la planification de vos itinéraires. C’est en quoi consiste VRPTW.Les fenêtres temporelles peuvent être :

  • Fenêtres temporelles simples : Servir en dehors de la fenêtre de temps est autorisé, mais cela s’accompagne de lourdes pénalités.
  • Fenêtres temporelles difficiles : les violations de temps ne sont pas du tout autorisées. Un conducteur doit attendre s’il arrive bien avant l’heure prévue jusqu’à ce que la fenêtre horaire s’ouvre et il ne doit pas non plus se présenter en retard.
  • Fenêtres temporelles disjointes : apparaissant entre deux fenêtres de temps, un pilote doit attendre jusqu’à ce que la fenêtre de temps suivante s’ouvre.
  • Fenêtres horaires temporelles : ensemble de fenêtres horaires non superposées de différentes longueurs.

Maintenant, comprenons cela avec un scénario réel et l’approche d’une solution.

Scénario réel

Prenons l’exemple de FedEx. Un colis est arrivé dans le pays de destination et est accepté par un transporteur du dernier kilomètre.Le colis doit être déplacé vers le centre de distribution. De là, un coursier prendra le colis pour le livrer à un client qui l’attendra le mercredi, de 10 à 11 heures du matin. Cela ne ressemble pas à une fenêtre temporelle simple, non ?Ainsi, le chauffeur ne peut pas se permettre d’être en retard. Mais, 15 autres colis doivent être livrés, chacun avec un délai spécifié également.Les VRPTW doivent être résolus partout, des livraisons postales, aux restaurants ou dans les supermarchés aux services de patrouille de sécurité et au routage des bus.

Approche vers la solution

Maintenant, comment le conducteur peut-il se présenter à l’heure partout, tout en empruntant les itinéraires les plus courts ?Nous devons relier les points : Identifier un ensemble d’itinéraires avec le moins de frais de déplacement et une satisfaction maximale du client qui, dans ce cas, peut être atteint en respectant les fenêtres de temps prioritaires.

Problème d’acheminement des véhicules de ramassage et de livraison (PDVRP)

Les entreprises de livraison à la demande, telles que les entreprises de livraison de courrier et de livraison de nourriture, doivent planifier chaque jour les itinéraires de livraison ; parfois même plusieurs fois par jour, selon la nature et l’ampleur de l’entreprise.Plusieurs contraintes de ressources, paramètres et horaires doivent être pris en compte lors de l’établissement de ces itinéraires.Habituellement, avec PDVRP, le défi consiste à combiner les points de livraison et de ramassage pour aider à réduire le temps de trajet et réduire les coûts de carburant.Un itinéraire idéal doit associer les points de livraison et de ramassage tout en gardant l’itinéraire le plus court ou le plus rapide possible.

Scénario réel

Prenons l’exemple d’Uber. Le système doit assigner efficacement les chauffeurs aux emplacements en limitant le temps de trajet et la prise de client.

Approche vers la solution

Attribuer des itinéraires aux chauffeurs ou aux véhicules pour récupérer et livrer les passagers. La demande du client doit être satisfaite dans les plus brefs délais en réduisant la longueur totale des itinéraires du véhicule.

Problème de routage de véhicule à contrainte de capacité (CVRP)

Chaque véhicule a une capacité de charge maximale (à la fois poids et volume) qui doit être prise en compte. Il est donc souvent difficile de réduire les coûts en chargeant plus d’articles et en servant plus de clients en un seul voyage sans dépasser la capacité du véhicule.Il peut également y avoir des complications supplémentaires, telles que :

  • Les différentes tailles de colis pour la livraison et le ramassage,
  • Les différentes capacités de tous les véhicules et de multiples dépôts
  • Dépôts multiples
  • Véhicules à compartiments multiples

Scénario réel

Prenons l’exemple de Tesco, un détaillant d’épicerie et de marchandises diverses. Ils utilisent des véhicules routiers pour une bonne distribution. Ils transportent les marchandises sur des palettes et chaque véhicule ne peut accueillir qu’un nombre limité de palettes, tandis que chaque unité commerciale (BU) demande un nombre de palettes différent. Par exemple, un grand magasin de détail nécessite bien plus de palettes que le véhicule ne peut en contenir.

Approche vers la solution

La meilleure approche devrait être d’attribuer les itinéraires les plus courts afin que le nombre total d’unités pour le véhicule réponde à ses limites de capacité.

Pourquoi le VRP est-il difficile à résoudre ?

Bien que nous ayons décrit les VRP ci-dessus de manière isolée, ils sont souvent combinés dans la vie réelle, ce qui fait exploser la taille globale du problème.Par exemple, le placement des adresses de livraison et de ramassage dans un itinéraire détermine si vous disposez de suffisamment d’espace dans votre véhicule pour un autre ramassage.De plus, si vous avez de l’espace, l’ajout ou la suppression d’un autre ramassage ou d’une livraison aura un impact sur votre fenêtre de temps pour les autres clients.Il est donc difficile de résoudre le VRP, même pour les répartiteurs les plus expérimentés et les chauffeurs chevronnés. Parce qu’il s’agit d’un problème d’optimisation combinatoire où les facteurs contributifs sont parfois incertains, non pris en compte et ne peuvent être prédits.

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!

Démarrez un essai gratuit de 7 jours

Pourquoi avez-vous besoin d’une solution efficace pour VRP ?

La principale raison pour laquelle vous avez besoin d’une solution VRP efficace est de réduire les dépenses logistiques. Il existe d’autres raisons, notamment les suivantes :

  • Il contribue à une croissance durable.
  • Il augmente l’efficacité et la productivité.
  • Cela fait gagner du temps et augmente la satisfaction des clients, augmentant ainsi les revenus et améliorant la rentabilité.

Comment résoudre le problème de routage des véhicules ?

Il existe plusieurs solutions pour résoudre le problème du VRP, telles que :

Résolution manuelle (y compris Google Maps)

Sur la base de l’expérience précédente, le conducteur idéal devrait être en mesure de réaliser un plan d’itinéraire manuellement. Mais ce sera une tâche fastidieuse et angoissante à faire.De plus, il est fort probable que les conducteurs commettent des erreurs au cours du processus manuel. En termes simples, la résolution manuelle est la méthode la plus inefficace pour traiter le VRP.Un planificateur d’itinéraire gratuit comme Google Maps ne peut pas non plus vous aider. Il serait en mesure de guider votre chauffeur vers le meilleur itinéraire compte tenu du trafic, mais ne peut pas fournir le bon ordre que votre chauffeur doit suivre pour livrer tous les colis à temps.Le planificateur d’itinéraire Google Maps n’est pas destiné à un usage quotidien, en particulier lorsque vous gérez une grande flotte de véhicules avec 100 livraisons ou plus. Un tel outil de base ne peut résoudre que certains des problèmes de routage.Découvrez si Google Maps convient à votre entreprise de livraison.

Solveurs prédéfinis

C’est une méthode plus rapide et meilleure que la résolution manuelle du VRP. Cependant, les solveurs prédéfinis ne satisfont ou ne résolvent que deux ou trois contraintes de base. Elle ne peut être appliquée que dans des « contextes universitaires » qui nécessitent des recherches approfondies, mais pas dans le monde réel.

Logiciel planificateur d’itinéraire

Un logiciel d’optimisation d’itinéraire est la meilleure solution pour résoudre le VRP.Avec un planificateur d’itinéraire, les VRP insolubles et toutes les contraintes peuvent être adressées en moins de 30 secondes. Il vous offrira même des itinéraires optimaux plus rapides, économisera du carburant, réduira les coûts et respectera les fenêtres de temps de chaque client.Un planificateur d’itinéraire de livraison est une solution économique et évolutive qui offre un routage multi-véhicules et multi-arrêts ainsi que la sécurité des livraisons et de vos chauffeurs.

Comment choisir le bon planificateur d’itinéraire pour résoudre le VRP ?

Lors de l’évaluation des différents planificateurs d’itinéraire, faites attention à ceux qui offrent les fonctionnalités de base suivantes :

Visualisation des plans d’itinéraire

La planification d’itinéraire est un processus visuel. Cela signifie que le fait de pouvoir voir où se trouve chaque emplacement client, quel chauffeur le servira et comment l’insertion ou la suppression d’une adresse affectera l’itinéraire global rendra la planification d’itinéraire beaucoup plus transparente.Alors, trouvez un logiciel VRP qui peut vous aider à modifier itinéraires à la volée.

Algorithme avancé

Une application de planification d’itinéraire doit être livrée avec un algorithme alimenté par l’IA qui créera des itinéraires optimaux avec des directions précises pour travailler en tenant compte de toutes les contraintes, y compris les embouteillages, les fenêtres horaires spécifiques, les capacités de charge des véhicules et les horaires de ramassage et de livraison, tandis que, au même temps, économie de carburant et de temps de conduite.

Preuve de livraison

Les meilleurs planificateurs d’itinéraire sont dotés d’une fonction de signature électronique qui aide les conducteurs à capturer les signatures électroniques des clients et à les stocker ou les enregistrer comme preuve de livraison numérique. Donc, vous devez considérer cette fonctionnalité.

Suivi en temps réel

Lorsqu’il s’agit de votre entreprise de service sur site, il est essentiel de connaître l’emplacement de vos véhicules et de vos chauffeurs.Par exemple, si un représentant sur le terrain est en retard sur le calendrier, vous pouvez suivre les véhicules en temps réel pour en découvrir la raison et comprendre comment le retard affectera les ETA des livraisons restantes.Vous pouvez alors soit réajuster les itinéraires instantanément, soit informer les clients des ETA mises à jour. Cela améliorera votre service client et augmentera la responsabilité de vos chauffeurs.Ainsi, le suivi GPS est un must pour toute entreprise de service sur le terrain.

Capacités de géocodage

Vous ne voudriez pas que vos chauffeurs se retrouvent à la mauvaise adresse ou perdent du temps à chercher la bonne adresse. C’est pourquoi vous avez besoin d’une application de planification d’itinéraire dotée de capacités de géocodage.Un géocodeur corrige automatiquement toutes les mauvaises adresses entrées dans le système afin que vous n’ayez jamais à vous soucier de l’exactitude des adresses des clients.Afin de vous assurer de choisir un logiciel de planification de livraison qui fonctionne vraiment pour vous, considérez dix-huit points supplémentaires comme indiqué dans notre article : Comment choisir le meilleur planificateur d’itinéraire.

Conclusion sur le problème de routage des véhicules

Quelle que soit l’expérience de vos gestionnaires et chauffeurs, vous ne pouvez pas toujours anticiper ce qui se passera sur la route et ajuster instantanément votre itinéraire pour répondre aux demandes imprévues de vos clients.Vous avez donc besoin d’une solution technologique avancée pour planifier vos itinéraires et suivre vos conducteurs et vos véhicules. Essentiellement, l’utilisation d’un optimiseur d’itinéraire avancé est le moyen le plus efficace de résoudre vos VRP et de faire en sorte que la planification et la modification des itinéraires ressemblent à une promenade dans le parc !Vous avez des questions sur le problème de routage des véhicules ? N’hésitez pas à laisser vos commentaires ci-dessous.

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!

Démarrez un essai gratuit de 7 jours

 

Qui sommes-nous

Route4Me compte plus de 32 000 clients sur presque tous les continents. Les applications mobiles Android et iPhone de Route4Me ont été téléchargées plus de 2 millions de fois depuis 2009. Extrêmement faciles à utiliser, les applications synchronisent les itinéraires, permettent une communication bidirectionnelle avec les chauffeurs, offrent des instructions détaillées, une confirmation de livraison, etc. Dans les coulisses, la plate-forme d'optimisation opérationnelle de Route4Me combine des algorithmes haute performance avec la science des données, l'apprentissage automatique et le big data pour planifier, optimiser et analyser des itinéraires de presque toutes les tailles en temps réel.