Le transport : flux, tournées de livraison et algorithme des économies
Le problème de transport, le voyageur de commerce et les heuristiques, l'économie de Clarke-Wright démontrée avec un exemple, fenêtres horaires, économie du chargement complet.
https://www.electronics-engineering.com/fr/transport-voyageur-de-commerce-algorithme-des-economies/
Le transport est souvent le premier poste des coûts logistiques. Les décisions vont du choix du mode (route, rail, mer, air) à la planification des flux entre origines et destinations, jusqu’à la tournée quotidienne d’une camionnette qui livre trente clients. Dans cette leçon, nous regardons le problème de transport comme un problème de programmation linéaire, le problème du voyageur de commerce et sa difficulté, l’algorithme des économies avec la démonstration de l’économie et un exemple, et l’économie du chargement complet.
Le problème de transport
Il y a des usines de capacités
, des clients de demandes
et des coûts unitaires
d’expédition de
à
. On cherche les quantités
qui minimisent le coût total :
![]()
C’est un problème de programmation linéaire à structure particulière : si les capacités et les demandes sont entières, il existe toujours une solution optimale entière, et des algorithmes dédiés la trouvent très vite même avec des milliers d’origines et de destinations.
La tournée de livraison
Une camionnette part du dépôt, visite un ensemble de clients et revient : dans quel ordre ? C’est le problème du voyageur de commerce (TSP). Avec
clients, il y a
tournées possibles : avec 20 clients plus de
, impossible à énumérer. Le problème est NP-difficile : on ne connaît aucun algorithme qui le résolve exactement en temps polynomial. On utilise donc :
- des algorithmes exacts avec des techniques de coupes, qui résolvent des instances de milliers de points en des temps acceptables ;
- des heuristiques constructives (plus proche voisin : on va toujours au client non visité le plus proche), rapides mais avec des tournées plus longues de 20-25 % que l’optimum ;
- des heuristiques d’amélioration (2-opt : on retire deux arêtes qui se croisent et l’on reconnecte les chemins sans croisement), qui arrivent à quelques pour cent de l’optimum.
L’algorithme des économies
Avec plusieurs véhicules de capacité limitée (le problème de tournées de véhicules, VRP), l’heuristique classique est l’algorithme des économies de Clarke et Wright (1964). On commence par servir chaque client avec un trajet séparé, aller-retour depuis le dépôt, et l’on fusionne les tournées deux à deux.

Théorème. Fusionner en une seule tournée les trajets vers les clients
et
économise
![]()
où
sont les distances et 0 est le dépôt.
Démonstration. Séparément, les deux trajets parcourent
. La tournée unique 0,
,
, 0 parcourt
. La différence est
. Par l’inégalité triangulaire,
, donc l’économie n’est jamais négative. ∎
Exemple. Avec
,
,
km : séparément 44 km, fusionnés 27 km, économie
. L’algorithme calcule les économies de toutes les paires, les trie de la plus grande à la plus petite, et fusionne les tournées correspondantes si les deux clients sont aux extrémités de tournées différentes et si la charge cumulée ne dépasse pas la capacité du véhicule. Les clients loin du dépôt et proches l’un de l’autre ont de grandes économies et finissent dans la même tournée, ce qui est exactement ce que suggère l’intuition. Le résultat est d’ordinaire à 5-10 % de l’optimum, et on l’améliore avec des heuristiques locales.
Les systèmes réels ajoutent des fenêtres horaires (le client ne reçoit que de 8 h à 12 h), des temps de déchargement, des limites de temps de travail des conducteurs, un trafic variable au fil de la journée ; les logiciels de planification des tournées utilisent des métaheuristiques et calculent des solutions en quelques minutes chaque matin.
L’économie du chargement
Le coût d’un trajet dépend peu du remplissage du véhicule : conducteur, carburant, péages et amortissement se paient de toute façon. Le coût par unité transportée est donc d’environ
, avec
le coût fixe du trajet,
la charge et
un petit coût variable par unité : il diminue avec la charge. D’où les stratégies de consolidation : regrouper de petits envois en chargements complets (plateformes de groupage, transport de messagerie), programmer les livraisons à jours fixes par zone, éviter les retours à vide en trouvant du fret de retour. La même économie vaut pour les émissions (leçon sur la durabilité).






Ciao, sono l'autore di «Trasporti: flussi, giri di consegna e algoritmo dei risparmi». Domande, dubbi, segnalazioni di errori o richieste di approfondimento sono benvenuti: scriveteli qui sotto e vi rispondo io. Potete anche votare la pagina con le stelle all'inizio dell'articolo.Hi, I am the author of “Transport: flows, delivery rounds and the savings algorithm”. Questions, doubts, error reports and requests for more detail are all welcome: write them below and I will answer. You can also rate the page with the stars at the top of the article.