Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Ingénierie logistique

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/

Pas encore de vote : soyez le premier à noter cette page.

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 a_i, des clients de demandes b_j et des coûts unitaires c_{ij} d’expédition de i à j. On cherche les quantités x_{ij} \ge 0 qui minimisent le coût total :

    \[ \min\sum_{i,j}c_{ij}x_{ij}\qquad\text{subject to}\quad\sum_jx_{ij} \le a_i,\quad\sum_ix_{ij} = b_j \]

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 n clients, il y a (n - 1)!/2 tournées possibles : avec 20 clients plus de 6\cdot 10^{16}, 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.

Algorithme des économies
À gauche, le dépôt 0 sert les clients A et B avec deux trajets séparés, de longueur 2 fois 10 plus 2 fois 12, soit 44. À droite, une seule tournée 0, A, B, 0 de longueur 10 plus 5 plus 12, soit 27. L’économie est de 17, égale à la somme des distances des deux clients au dépôt moins leur distance mutuelle.

Théorème. Fusionner en une seule tournée les trajets vers les clients i et j économise

    \[ s_{ij} = d_{0i} + d_{0j} - d_{ij} \]

où d sont les distances et 0 est le dépôt.

Démonstration. Séparément, les deux trajets parcourent 2d_{0i} + 2d_{0j}. La tournée unique 0, i, j, 0 parcourt d_{0i} + d_{ij} + d_{j0}. La différence est d_{0i} + d_{0j} - d_{ij}. Par l’inégalité triangulaire, d_{ij} \le d_{0i} + d_{0j}, donc l’économie n’est jamais négative. ∎

Exemple. Avec d_{0A} = 10, d_{0B} = 12, d_{AB} = 5 km : séparément 44 km, fusionnés 27 km, économie 10 + 12 - 5 = 17. 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 F/q + c, avec F le coût fixe du trajet, q la charge et c 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é).

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x