Blog > Livraison du dernier kilomètre

Problème de tournées de véhicules : défis, solutions et exemples concrets

Publié le 3 septembre 2024 • Lecture : 10 min read

Si vous exercez dans le secteur de la livraison, vous savez que gérer une flotte de véhicules et organiser des tournées efficaces n’est pas une tâche facile. Le problème de tournées de véhicules (ou Vehicle Routing Problem, VRP) est un défi majeur pour toute entreprise de livraison. Vous devez déterminer les meilleurs itinéraires pour vos véhicules, afin de livrer vos colis au moindre coût, tout en respectant les contraintes liées aux créneaux horaires des clients, aux capacités des véhicules, et aux restrictions routières. Et avec l’explosion du e-commerce et des attentes des consommateurs, il n’est plus possible de passer outre l’optimisation de tournées.

• Le problème de tournées de véhicules : Qu’est-ce que c’est ?
• Les différents types de problèmes de tournées de véhicules
• Les défis concrets du VRP (Vehicle Routing Problem)
• Quelles solutions pour résoudre les problèmes de tournées de véhicules ?
• Exemple concret : une société de livraison à Metz

Le problème de tournées de véhicules pose des défis complexes aux entreprises de livraison. L’optimisation des itinéraires permet de diminuer les coûts et de respecter les délais clients. C’est une stratégie gagnante pour se démarquer dans un environnement compétitif.

Le problème de tournées de véhicules : Qu’est-ce que c’est ?

Le VRP a été étudié pour la première fois dans les années 1950. Mais il tire ses racines d’une problématique plus ancienne : le problème du voyageur de commerce.

Ce problème mathématique complexe consiste à trouver la meilleure répartition et les meilleurs itinéraires possibles pour une flotte de véhicules. Le but est de minimiser les coûts, que ce soit en termes de distance parcourue, de temps ou de carburant consommé, tout en respectant un ensemble de contraintes spécifiques telles que les demandes clients et la capacité des véhicules.

Imaginez que vous gérez une flotte de 10 véhicules qui doivent livrer chacun 200 colis dans une grande ville française. Chaque véhicule a une capacité d’emport maximale, et chaque client a une fenêtre horaire précise pendant laquelle il peut recevoir son colis. Vous devez trouver le meilleur itinéraire pour chaque véhicule, tout en respectant les contraintes et en optimisant les coûts. Cela n’a vraiment rien d’évident. Ce défi devient encore plus complexe à mesure que le nombre de clients, de véhicules et de contraintes augmente.

Le problème de tournées de véhicules (VRP).

Les différents types de problèmes de tournées de véhicules

Le VRP peut se présenter sous différentes formes, selon les spécificités de votre entreprise et de votre flotte.

On retrouve 4 principales formes de problèmes :

• VRP avec Fenêtres de Temps (VRPTW): Vos clients ne peuvent pas recevoir leurs colis à n’importe quelle heure. Ils ont des créneaux horaires précis. Imaginez par exemple que vous deviez livrer des colis pour FedEx à Paris. Vos clients attendent leur livraison dans un créneau de 1 heure entre 9h et 10h du matin. Si vos véhicules sont bloqués dans les embouteillages ou mal organisés, vous risquez des retards, des réclamations, voire des pénalités.
• VRP avec contrainte de Capacité (CVRP): Chaque véhicule de votre flotte a une capacité d’emport limitée, en termes de volume ou de poids. Vous devez maximiser l’utilisation de chaque véhicule, sans dépasser ses capacités. Sinon, vous risquez de devoir effectuer des allers-retours inutiles, ce qui augmente vos coûts et réduit votre efficacité.
• VRP avec Ramassage et Livraison (PDVRP): Parfois, vos véhicules doivent non seulement livrer des colis, mais aussi en collecter d’autres sur le chemin du retour. C’est un scénario courant pour des entreprises comme Uber, où les chauffeurs doivent déposer et récupérer des passagers, tout en minimisant les distances parcourues​.
• VRP Multi-Dépôts (MDVRP): Si votre entreprise possède plusieurs dépôts ou centres de distribution, la planification des tournées devient encore plus complexe. Il faut alors coordonner les départs de plusieurs points et optimiser les itinéraires pour réduire les coûts au maximum. Ce type de VRP est fréquent dans les grandes chaînes de distribution.

Les différents types de problèmes de tournées de véhicules.

Les défis concrets du VRP (Vehicle Routing Problem)

Au-delà des délais de livraison, de capacité de vos véhicules et lieux de collecte multiple, vous pouvez rencontrer d’autres types de problèmes liés à la fluctuation de la demande ou aux disponibilités de vos conducteurs.

Une mauvaise gestion des tournées peut entraîner une surconsommation de carburant, une usure prématurée de vos véhicules, et des temps de livraison plus longs. En optimisant vos tournées, vous améliorez la rapidité et la fiabilité de vos livraisons, et donc la satisfaction client. Mais vous pouvez également réduire vos coûts de carburant jusqu’à 20 %. Et ce n’est pas seulement une question de rentabilité : c’est aussi un enjeu environnemental, surtout dans les grandes villes où les embouteillages augmentent les émissions de CO2​ et de particule fine. Selon une étude de McKinsey, les émissions liées à la livraison urbaine pourraient augmenter de 32 % d’ici 2030 dans les 100 plus grandes villes mondiales si rien n’est fait​.

De plus en plus d’entreprises de livraison cherchent ainsi à minimiser leurs coûts et leur impact environnemental, en optant pour des véhicules électriques et des pratiques d’écoconduite, en groupant les commandes et en optimisant leurs tournées.

Mais plus vous avez de clients à livrer, plus la planification des tournées devient complexe. Chaque client supplémentaire multiplie les combinaisons possibles pour vos itinéraires, rendant la tâche pratiquement impossible à gérer manuellement. Par exemple, si vous disposez d’une flotte de 50 véhicules devant livrer 1000 colis à travers une grande ville comme Paris ou Lyon, la planification devient un véritable casse-tête. Les aléas de la circulation, les accidents, les conditions météorologiques et les imprévus divers font partie du quotidien de vos chauffeurs. Pour minimiser les retards et optimiser les livraisons, vous devez pouvoir ajuster vos tournées en temps réel. Par exemple, si un embouteillage se forme sur le périphérique parisien, vos véhicules doivent immédiatement être redirigés vers des routes alternatives pour éviter les retards​.

Pour résumer cette complexité, voici les quatre paramètres essentiels à prendre en compte pour résoudre les problèmes liés à vos tournées de véhicules :

Nombre de combinaisons possibles + Coûts opérationnels et environnementaux + Adaptabilité en temps réel + Satisfaction client

Les 4 paramètres à prendre en compte pour résoudre les problèmes liés aux tournées de véhicules.

Quelles solutions pour résoudre les problèmes de tournées de véhicules ?

Pour résoudre les problèmes de tournées de véhicules, différentes approches ont été développées au fil du temps, allant des méthodes traditionnelles aux solutions modernes basées sur la technologie.

Approches traditionnelles

1. Planification manuelle

Pendant des décennies, les entreprises ont planifié manuellement leurs tournées. Cela impliquait l’utilisation de cartes papier, de listes de clients et d’une grande expérience terrain. Bien que cette méthode puisse fonctionner pour de petites opérations, elle devient vite ingérable lorsque le nombre de données à traiter augmente. Elle est aussi sujette à des erreurs humaines, avec des conséquences parfois très coûteuses.

2. Routage heuristique

Certaines entreprises ont adopté des méthodes heuristiques pour simplifier la planification des tournées. Les heuristiques sont des règles simples, basées sur l’expérience. Elles permettent de trouver des solutions approximatives, mais rapidement calculables. Par exemple, une heuristique pourrait consister à toujours livrer les clients les plus proches en premier. Cette approche est plus efficace que la planification manuelle, mais elle n’est pas optimale et peut encore entraîner des surcoûts.

Approches modernes

1. Logiciels d’optimisation de tournées

Les logiciels d’optimisation de tournées calculent automatiquement les meilleurs itinéraires pour vos véhicules. Ils prennent en compte toutes les contraintes (fenêtres, horaires, capacités des véhicules, conditions de circulation, etc.).

Certains logiciels d’optimisation de tournées incluent également une réoptimisation dynamique, pour ajuster les itinéraires en temps réel, en fonction des imprévus. Si un client annule une commande ou si un embouteillage se forme, le logiciel peut réorganiser immédiatement les livraisons pour minimiser les perturbations.

La société DHL aurait réussi à économiser jusqu’à 20 % sur ses coûts de livraison grâce à des algorithmes de routage dynamique.

Le logiciel AntsRoute, que vous pouvez adopter, propose des solutions similaires en adaptant les itinéraires en temps réel.

L’interface du logiciel d’optimisation de tournées AntsRoute.

2. Intelligence artificielle (IA)

L’IA est un atout majeur pour optimiser les tournées. Elle permet de prédire les imprévus (embouteillages, accidents, etc.) et d’ajuster les itinéraires en conséquence. En intégrant l’IA dans son système de gestion de tournées, Tesco aurait ainsi réduit de 11,2 millions de kilomètres les distances parcourues par ses véhicules, tout en économisant 8 % de carburant par commande.

3. Analyse prédictive

L’analyse des données historiques et actuelles aide également à prévoir les meilleures tournées. En anticipant les périodes de pointe, les conditions météorologiques et les événements exceptionnels (comme les grèves ou autres événements majeurs), vous pouvez ajuster vos stratégies de livraison pour éviter les retards.

Exemple concret : une société de livraison à Metz

Prenons l’exemple d’une entreprise de livraison opérant dans une ville provinciale comme Metz. Metz, située au nord-est de la France, est une ville avec un centre historique aux rues étroites, des quartiers résidentiels avoisinants et des zones commerciales plus modernes. Vous devez y gérer environ 300 à 400 livraisons par jour. Voici les défis spécifiques auxquels vous pourriez faire face :

Scénario typique de livraison

Votre entreprise doit livrer dans plusieurs quartiers de Metz, du centre historique aux quartiers résidentiels comme Queuleu et Borny, jusqu’aux zones commerciales de Muse, Waves ou de Metz-Technopôle. Chaque secteur présente ses propres contraintes :

Contrainte 1 : Accès limité au centre-ville

Le centre historique de Metz est en grande partie une zone piétonne avec des accès restreints pour les véhicules entre 11h et 19h. Par conséquent, vous devez planifier vos livraisons tôt le matin ou tard le soir, pour éviter de vous retrouver bloqué.

Imaginez que vous ayez une vingtaine de colis à livrer autour de la place Saint-Jacques, en plein centre de Metz. Les rues étroites et l’affluence piétonne rendent l’accès difficile. Grâce à un logiciel d’optimisation de tournées comme AntsRoute, vous pouvez planifier ces livraisons à des heures où l’accès est autorisé et le trafic moins dense, tout en respectant les créneaux horaires des clients.

Contrainte 2 : Trafic et stationnement dans les quartiers résidentiels

Les quartiers résidentiels comme Queuleu et Borny sont souvent encombrés, notamment aux heures de sortie des écoles ou lors des marchés hebdomadaires. Le stationnement y est difficile, ce qui peut causer des retards.

Imaginez que vous deviez livrer une dizaine de colis à Borny un vendredi matin, jour de marché. Les rues impliquées sont peu praticables, ce qui complique votre parcours. Grâce à AntsRoute, vous pouvez planifier vos livraisons pour éviter ces embouteillages, en choisissant des horaires moins chargés ou en priorisant les livraisons dans des zones moins encombrées à ce moment-là. De plus, en cas de retard, AntsRoute peut réajuster l’ordre des livraisons en temps réel pour minimiser l’impact sur votre tournée.

Contrainte 3 : Fenêtres horaires dans les zones d’entreprises

Dans des zones comme Metz-Technopôle, vous avez affaire à des entreprises qui fonctionnent avec des horaires de bureau stricts. Les livraisons doivent être effectuées entre 9h et 17h, ce qui ne vous laisse que peu de marge de manœuvre. Si un client n’est pas disponible en dehors de ces heures, vous risquez de manquer la livraison et de devoir reprogrammer votre tournée, ce qui entraîne des coûts supplémentaires.

Avec un logiciel d’optimisation de tournées, vous pouvez prioriser les livraisons en fonction des créneaux horaires spécifiques des clients. Par exemple, les livraisons pour Metz-Technopôle peuvent être planifiées en début de journée, pour vous assurer une livraison de tous les colis dans les délais. Si une livraison prend plus de temps que prévu, un logiciel comme celui d’AntsRoute peut réajuster le reste de la tournée pour éviter des retards supplémentaires.

AntsRoute permet de prioriser les livraisons en fonction des créneaux horaires spécifiques des clients.

Contrainte 4 : Conditions météorologiques

Metz, comme de nombreuses autres villes françaises, est sujette à des conditions météorologiques variables. En hiver, la ville peut être confrontée à des chutes de neige ou à des pluies verglaçantes, rendant les routes glissantes et dangereuses. Ces conditions peuvent non seulement ralentir vos livraisons, mais aussi augmenter le risque d’accident.

Ces prévisions météorologiques peuvent être intégrées dans la planification de vos tournées. En cas de mauvaises conditions, certains logiciels peuvent proposer des itinéraires alternatifs plus sûrs ou réorganiser les livraisons pour les reporter à des moments où les conditions seront meilleures. Cela vous permet de minimiser les risques et d’assurer la sécurité de vos chauffeurs, tout en respectant les délais de livraison.

Gérer les tournées de véhicules est un défi quotidien pour les entreprises de livraison, mais ce n’est pas une fatalité. Avec des outils comme le logiciel d’optimisation de tournées d’AntsRoute, vous pouvez non seulement réduire vos coûts, mais aussi améliorer votre efficacité et la satisfaction de vos clients. Que vous opériez à Metz, Lyon, Paris, ou ailleurs, l’optimisation des tournées est essentielle pour rester compétitif dans un marché de plus en plus exigeant.

Les défis auxquels vous faites face, que ce soit les embouteillages, les capacités de vos véhicules, les contraintes horaires ou les conditions météorologiques, peuvent tous être surmontés avec la bonne technologie. AntsRoute se positionne comme un allié incontournable pour toute entreprise cherchant à optimiser ses opérations de livraison. En investissant dans une solution d’optimisation des tournées, vous ne faites pas que suivre une tendance, vous prenez une décision stratégique pour assurer la pérennité et la croissance de votre entreprise.

ÉCRIT PAR

Maryline Lakh
Maryline a travaillé 15 ans pour un grand groupe logistique. Depuis 2022, elle est stratège en communication et rédactrice freelance auprès de sociétés logistiques à impact positif. Elle se passionne pour les nouvelles solutions de logistique durable et écrit pour plusieurs clients, dont AntsRoute.