Vous avez lu le TSP (ordonner des arrêts) et le VRPTW (respecter les fenêtres horaires). Reste un cas pratique très courant : vous avez plusieurs véhicules. 2 livreurs le matin, 5 auxiliaires de soin sur le terrain, 3 traiteurs qui partent en même temps. Comment répartir les clients entre eux pour minimiser le temps total ?
C'est le VRP (Vehicle Routing Problem) et la méthode la plus utilisée en pratique date de 1964 : l'algorithme de Clarke et Wright, dit Savings algorithm. C'est ce qu'OptiRoad utilise dans son plan Business pour gérer 2 à 10 véhicules.
Le problème en une phrase
Vous avez 1 dépôt et N clients à livrer. Vous avez M véhicules disponibles. Comment répartir les N clients entre les M véhicules pour que le temps total soit minimal ?
Ça paraît simple. Ça ne l'est pas.
Pourquoi c'est dur
Avec 20 clients et 3 véhicules, le nombre de partitions possibles dépasse les 3,5 millions. Et pour chaque partition, il faut encore résoudre un TSP (ou un VRPTW si fenêtres horaires) sur chaque véhicule. Brute force est impossible dès 10 à 15 clients.
Le VRP est, comme le TSP, NP-difficile : aucun algorithme ne garantit la solution optimale en temps raisonnable. On utilise donc des heuristiques. Et celle qui domine depuis 60 ans en monde réel, c'est Clarke-Wright Savings.
L'idée géniale de Clarke-Wright (1964)
George Clarke et John Wright ont publié leur papier "Scheduling of vehicles from a central depot to a number of delivery points" en 1964. L'idée est d'une élégance déconcertante.
Étape 1 : la solution naïve
On commence par une solution dégénérée : chaque client a son propre véhicule. 20 clients = 20 mini-tournées dépôt → client → dépôt. C'est gaspilleur, mais c'est notre point de départ.
Coût total : pour chaque client i, le véhicule fait d(dépôt, i) + d(i, dépôt) = 2 × d(dépôt, i).
Étape 2 : le concept de "saving"
Imaginons qu'on fusionne les tournées de deux clients i et j en une seule. Au lieu de :
dépôt → i → dépôt + dépôt → j → dépôt
On fait :
dépôt → i → j → dépôt
L'économie (le saving) est :
s(i,j) = d(dépôt, i) + d(j, dépôt) - d(i, j)
Plus i et j sont proches l'un de l'autre et loin du dépôt, plus le saving est grand. C'est intuitif : ça vaut le coup de les regrouper.
Étape 3 : la fusion gloutonne
- Calcule s(i,j) pour toutes les paires de clients
- Trie ces savings par ordre décroissant
- Pour chaque paire (i,j), dans l'ordre :
- Si i et j sont sur des tournées différentes
- Et qu'ils sont aux extrémités de leurs tournées respectives
- Et qu'on a encore des véhicules disponibles (≤ M)
- Fusionne les deux tournées
- Continue jusqu'à épuisement des paires utiles
À la fin, tu obtiens M tournées (ou moins) qui couvrent tous les clients, avec une distance totale largement meilleure que la solution naïve, et typiquement à 5 à 10 % de l'optimum théorique.
Savings, balayage ou métaheuristique ?
Clarke-Wright n'est pas la seule famille d'algorithmes pour le VRP. Trois grandes approches coexistent.
L'algorithme de balayage (Gillett et Miller, 1974) regroupe les clients par angle autour du dépôt, comme une aiguille d'horloge qui balaie le plan. C'est extrêmement simple à coder, mais la qualité des tournées reste inférieure : on suit la géométrie, pas le coût réel.
Les métaheuristiques (recherche tabou, algorithmes génétiques) explorent l'espace des solutions de façon plus fine et atteignent des résultats légèrement meilleurs. En contrepartie, elles sont plus lentes et plus délicates à régler : il faut calibrer de nombreux paramètres, ce qui les rend lourdes à industrialiser.
Clarke-Wright Savings se place au point d'équilibre idéal : des résultats proches de l'optimum, une exécution rapide, une robustesse à toute épreuve, et une grande facilité à étendre avec des capacités ou des fenêtres horaires. C'est exactement pour cela qu'il domine l'optimisation de flottes en conditions réelles depuis 60 ans.
Un exemple concret
Imaginons 6 clients à livrer depuis un dépôt à Paris-Centre, avec 2 véhicules disponibles :
| Client | Distance au dépôt |
|---|---|
| A | 4 km |
| B | 5 km |
| C | 8 km |
| D | 6 km |
| E | 9 km |
| F | 7 km |
Solution naïve (1 véhicule par client, 6 véhicules) :
- Coût total : 2 × (4 + 5 + 8 + 6 + 9 + 7) = 78 km
Avec Clarke-Wright Savings et 2 véhicules :
- Calcul des savings pour les 15 paires possibles
- Tri décroissant
- Fusions successives en respectant la contrainte de 2 véhicules max
- Résultat possible : Véhicule 1 =
dépôt → A → B → D → dépôt(~22 km), Véhicule 2 =dépôt → C → F → E → dépôt(~28 km)
- Coût total : ~50 km (-36 % vs naïve)
Sur des cas réels, on observe couramment des gains de 30 à 40 % par rapport à une partition manuelle "à l'œil".
Variantes et extensions
L'algorithme original est pour le VRP de base. En pratique, on l'enrichit :
- Capacités : chaque véhicule a une charge max. On vérifie à chaque fusion qu'on ne dépasse pas la capacité.
- Multi-dépôt : plusieurs dépôts. Heuristique : assigner chaque client au dépôt le plus proche, puis Clarke-Wright sur chaque sous-problème.
- Fenêtres horaires : combiner avec VRPTW. Ne fusionner deux tournées que si l'ordre résultant respecte toutes les fenêtres.
- Borne sur le nombre de véhicules : si on veut exactement M véhicules, on arrête la fusion plus tôt.
- Asymétrie : la distance A→B peut différer de B→A (sens unique, etc.). Le calcul des savings reste valide.
Comment OptiRoad implémente le VRP multi-véhicules
En plan Business, vous pouvez optimiser jusqu'à 10 véhicules en parallèle. Voici ce qu'OptiRoad fait quand vous activez le mode multi-véhicules :
- Configuration : vous indiquez le nombre de véhicules, leur dépôt (commun ou propre à chacun), et optionnellement leur point d'arrivée.
- Clarke-Wright Savings : calcul des savings sur toutes les paires, tri décroissant, fusions gloutonnes en respectant la limite de véhicules.
- Multi-dépôt : si chaque véhicule a un dépôt différent (
sharedDepot: false), pré-affectation des stops par proximité avant l'exécution de Clarke-Wright sur chaque cluster. - TSP local par véhicule : une fois la partition trouvée, chaque tournée est ré-optimisée individuellement avec nearest neighbor + 2-opt pour minimiser sa distance interne.
- Si VRPTW activé : EDF (Earliest Deadline First) sur chaque tournée, en respectant les fenêtres horaires de chaque client.
- Couleurs distinctes : chaque véhicule reçoit une couleur dans la carte (#3B82F6, #EF4444, #10B981, etc.) pour visualiser facilement les tournées.
Timeouts adaptatifs : 15 secondes pour 2 à 4 véhicules, 30 secondes pour 5 à 10 véhicules. Si dépassé, OptiRoad retourne le meilleur résultat trouvé avec un flag partial: true.
Drag and drop pour ajustement manuel
Si la répartition automatique ne vous convient pas (un client doit absolument être chez un livreur précis pour des raisons clients), vous pouvez glisser-déposer un stop d'un véhicule à l'autre dans l'app. OptiRoad recalcule alors l'ordre TSP pour chaque véhicule impacté en respectant la nouvelle partition. Endpoint : POST /api/optimize/reorder (plan Business uniquement).
Équilibrer les tournées
Clarke-Wright dans sa version brute ne cherche qu'une chose : minimiser la distance totale. Conséquence, il peut produire des tournées déséquilibrées, un livreur surchargé de 25 arrêts pendant qu'un autre n'en a que 8. Sur le papier la distance est optimale, dans la vraie vie c'est ingérable côté planning.
En pratique, on plafonne donc le nombre d'arrêts ou la capacité par véhicule pour forcer une répartition plus homogène. Puis on rééquilibre à la main quand le terrain l'exige. OptiRoad vous laisse fixer le nombre de véhicules et déplacer des stops de l'un à l'autre par drag and drop : chaque tournée affectée est aussitôt recalculée, vous gardez donc un ordre optimisé tout en gardant la main sur la charge de chacun.
Quand utiliser le multi-véhicules
- 2 à 3 véhicules : utile dès que votre journée dépasse 30 stops, ou que vous livrez sur des zones géographiques distinctes.
- 5 à 10 véhicules : pour les flottes structurées (services à la personne, traiteurs avec équipe, e-commerce qui scale).
- Au-delà de 10 véhicules : contactez-nous, on peut activer un solveur dédié pour les très grandes flottes.
En pratique : ce que ça change pour vous
Sur une journée typique de 60 livraisons à répartir entre 3 livreurs :
- Sans optimisation (répartition manuelle "à la louche") : ~280 km, 12 h cumulées
- Avec Clarke-Wright Savings d'OptiRoad : ~190 km, 8 h cumulées
- Gain : -32 % de distance, -33 % de temps cumulé
Au-delà des kilomètres, le vrai gain est organisationnel : chaque livreur démarre avec sa feuille de route claire, sa couleur sur la carte, ses ETA précises. Plus de "qui prend qui" le matin.
Pour aller plus loin
Le VRP multi-véhicules est disponible exclusivement en plan Business (49 €/mois). Le plan Pro reste mono-véhicule (avec ou sans fenêtres horaires).
Cette série de 3 articles (TSP → VRPTW → VRP multi-véhicules) couvre les bases conceptuelles d'OptiRoad. Les prochains articles aborderont les sujets pratiques : combien d'économies réelles, comment intégrer l'API à votre boutique e-commerce, etc.
Questions fréquentes
Combien de véhicules OptiRoad gère-t-il ? De 2 à 10 véhicules en plan Business. Au-delà, contactez-nous : on peut activer un solveur dédié pour les très grandes flottes.
Chaque véhicule peut-il avoir un dépôt différent ? Oui, le mode multi-dépôt est prévu pour ça. Les stops sont pré-affectés au dépôt le plus proche avant que Clarke-Wright tourne sur chaque cluster, ce qui garantit des tournées cohérentes par zone.
Puis-je verrouiller un client sur un véhicule précis ? Oui, par drag and drop. Vous déplacez le stop vers le véhicule voulu et OptiRoad recalcule aussitôt l'ordre TSP des véhicules concernés pour garder chaque tournée optimisée.
Quel plan faut-il ? Le plan Business uniquement. Le plan Pro reste mono-véhicule, avec ou sans fenêtres horaires.