Principe
Le problème de tournées de véhicules (VRP) cherche les meilleurs circuits sous contraintes : capacité du véhicule, fenêtres horaires, durée de travail, accès. Les logiciels d'optimisation (heuristiques, métaheuristiques) remplacent la construction manuelle et s'adaptent chaque jour aux commandes.
Comprendre pas à pas
1. La situation
Un grossiste en produits frais livre chaque matin 24 restaurants avec des camionnettes de 8 livraisons. Le chauffeur organise sa tournée dans l'ordre des bons de livraison. Question : comment construire des tournées plus courtes ?
2. Les contraintes
| Contrainte | Valeur |
|---|---|
| Clients à livrer | 24, répartis sur 100 × 100 km |
| Capacité d'une camionnette | 8 clients |
| Départ et retour | dépôt au centre de la zone |
| Coût kilométrique | 0,60 € / km (carburant, entretien) |
3. L'idée
Le problème des tournées (VRP, Vehicle Routing Problem) consiste à répartir les clients entre véhicules et à ordonner chaque tournée pour minimiser la distance. Il est trop complexe pour être résolu exactement à la main, mais des heuristiques simples donnent de bons résultats.
Balayage
On trie les clients selon leur direction depuis le dépôt (comme l'aiguille d'une montre) et on remplit les camions secteur par secteur.
Plus proche voisin
Dans chaque tournée, on va toujours au client le plus proche non encore livré.
Logiciels
Les outils de tournées gèrent en plus les créneaux horaires, le trafic, les temps de déchargement.
4. Le résultat
Avant. Ordre des bons : chaque camionnette traverse la zone plusieurs fois.
Balayage. 3 tournées de 8 clients, chacune dans un secteur.
Ordre dans la tournée. Plus proche voisin depuis le dépôt.
Gain. Environ 40 à 50 % de kilomètres en moins sur l'exemple (voir le simulateur), soit plusieurs milliers d'euros par an et une heure de travail gagnée par chauffeur et par jour.
5. À vous de jouer
Faites varier le nombre de clients et la capacité des camions : la carte montre les tournées optimisées, et les indicateurs la comparaison avec l'ordre de saisie.
6. Ce qu'il faut retenir
- Répartir les clients par secteur, puis ordonner chaque tournée.
- Des heuristiques simples font déjà gagner beaucoup.
- Les logiciels ajoutent créneaux, trafic et temps de service.
Mise en œuvre
- Acteurs
- Exploitation transport
- Durée
- Quotidien avec un logiciel
- Livrables
- Tournées optimisées
- Collecter les donnéesAdresses géocodées, volumes, fenêtres horaires, temps de service.
- Paramétrer les véhiculesCapacités, horaires, contraintes d'accès.
- OptimiserLogiciel de tournées, puis ajustements manuels.
- MesurerKilomètres, remplissage, respect des créneaux.
Exemple d'application
Logiciel de tournées pour 12 véhicules de livraison : −16 % de kilomètres et 1 véhicule de moins, à service égal.
Points de vigilance
- Temps de service chez le client sous-estimés : tournées irréalistes