Faire venir la marchandise, répartir le travail, organiser les trajets. Une même histoire, celle d'un dépôt qui livre ses clients, traverse cinq problèmes classiques, du plus facile au plus difficile.
L'histoire de la page. Trois usines approvisionnent quatre dépôts régionaux (planche 1). Dans l'un d'eux, cinq chauffeurs se partagent cinq secteurs (planche 2). Il faut ensuite livrer neuf clients : d'abord avec une seule camionnette (planche 3), puis avec des camions de capacité limitée (planche 4), enfin avec des clients qui imposent une plage horaire (planche 5).
Une journée de livraisons : les deux camions de la planche 5 partent du dépôt (carré), servent chacun leurs clients dans leur créneau, puis reviennent. L'horloge tourne de 8 h à 18 h.
Les lieux et les chiffres sont inventés. Les résultats sont calculés sur place dans votre navigateur et confrontés à une seconde méthode, souvent l'examen de toutes les possibilités. Ce cahier consacre déjà une page entière au problème de transport, au problème d'affectation et au voyageur de commerce : ici, on les voit côte à côte, et l'accent porte sur les tournées de véhicules, qui les réunissent.
Planche 1
Le problème de transport : des fournisseurs vers les clients
Trois usines produisent 45, 35 et 30 palettes. Quatre dépôts en demandent 30, 25, 35 et 20. Chaque liaison a un coût par palette. Combien envoyer de chaque usine vers chaque dépôt, pour satisfaire toutes les demandes au moindre coût ?
Les envois du plan choisi : l'épaisseur est proportionnelle au nombre de palettes, la couleur va du vert (liaison bon marché) au rouge (liaison chère).
Cliquez sur une case du tableau pour la choisir, puis modifiez son coût avec le curseur.
Coin nord-ouest–
Moindre coût d'abord–
Plan optimal (programme linéaire)–
Contrôle : flot à coût minimal, écart–
Liaisons utilisées par l'optimum (au plus 3 + 4 − 1)–
Ce qu'il faut retenir. Remplir le tableau dans l'ordre (coin nord-ouest) coûte 13 % de plus que l'optimum ; prendre d'abord les liaisons les moins chères fait mieux, mais pas assez. Le problème de transport est un programme linéaire très particulier : avec des quantités entières au départ, l'optimum est entier, sans qu'on le demande, et il n'utilise jamais plus de 6 liaisons sur 12.
Planche 2
L'affectation : une tâche par personne, une personne par tâche
Au dépôt, cinq chauffeurs et cinq secteurs. Le tableau donne la durée, en minutes, que met chaque chauffeur à préparer chaque secteur : il dépend de son expérience, du camion qu'il connaît, de son domicile. Qui prend quel secteur, pour que le total soit le plus petit ? C'est un problème de transport où chaque offre et chaque demande vaut 1.
Cliquez sur une case pour donner ce secteur à ce chauffeur : les deux affectations concernées s'échangent, et chaque chauffeur garde exactement un secteur.
À gauche les chauffeurs, à droite les secteurs. Trait bleu : votre affectation. Trait vert pointillé : l'optimum, quand il diffère.
–
Votre affectation–
Le moins cher d'abord–
Optimum–
Contrôle : les 120 affectations examinées, la pire–
Relaxation linéaire : valeur, plus grand écart à un entier–
Ce qu'il faut retenir. La règle « le moins cher d'abord » commence par la case à 30 minutes, puis se retrouve coincée et doit accepter des cases chères : 195 minutes contre 174. Avec 5 chauffeurs, on peut tout examiner (120 cas) ; avec 20, il y en aurait 2,4 milliards de milliards, mais la méthode hongroise résout le problème en un instant. Et comme pour le transport, on peut résoudre sans exiger des entiers : la solution sort entière d'elle-même.
Planche 3
Le voyageur de commerce : une camionnette, neuf clients
Une seule camionnette part du dépôt, passe une fois chez chacun des neuf clients et revient. Dans quel ordre ? Ce problème a l'air simple, mais ses possibilités explosent : 181 440 tournées différentes pour 9 clients, 60 milliards de milliards pour 25. Construisez la vôtre en cliquant sur les clients dans l'ordre, puis comparez.
Carré : le dépôt. Ronds : les clients. Orange : votre tournée. Bleu : la tournée de la méthode choisie. Distances en kilomètres.
Les 181 440 tournées, rangées par longueur (histogramme). Les traits marquent les méthodes : chacune ne fait que placer un trait, l'énumération seule voit toute la courbe.
–
Votre tournée–
Plus proche voisin–
Après 2-opt–
Optimum (programmation dynamique de Held et Karp)–
Contrôle : 362 880 ordres énumérés, écart–
Tournées plus courtes que la vôtre–
Ce qu'il faut retenir. « Aller toujours au plus proche » est naturel et finit mal : les derniers clients, oubliés, imposent un long retour. Le 2-opt défait les croisements : si deux trajets se croisent, on gagne toujours à les décroiser. Ici, deux améliorations suffisent pour atteindre l'optimum, 96,48 km ; ce n'est pas garanti en général. La page Le voyageur de commerce de ce cahier va beaucoup plus loin.
Planche 4
Organiser des tournées de véhicules : la contrainte de capacité
Les clients commandent maintenant des palettes (le nombre près de chaque rond), et un camion n'en porte que Q. Il faut plusieurs tournées, et deux décisions à la fois : quels clients chaque camion sert (une affectation, comme planche 2), et dans quel ordre (un voyageur de commerce par camion, comme planche 3). C'est le problème des tournées de véhicules.
Une couleur par camion, avec sa charge. Pour Clarke et Wright, les fusions successives s'affichent pas à pas.
Distance totale de l'optimum selon la capacité Q (barres, avec le nombre de camions). Points : les deux méthodes approchées.
–
Palettes à livrer ; camions au minimum–
Clarke et Wright : km ; camions–
Balayage : km ; camions–
Optimum : km ; camions–
Contrôle : partitions examinées par programmation dynamique–
Deux idées de construction.Clarke et Wright part d'un aller-retour par client, puis fusionne deux tournées quand cela économise de la route : d(dépôt, i) + d(dépôt, j) − d(i, j). Le balayage tourne autour du dépôt comme une aiguille, et remplit un camion jusqu'à Q avant d'en prendre un autre. À Q = 10, le balayage n'utilise que 2 camions, mais l'optimum en distance en prend 3 : moins de camions ne veut pas dire moins de kilomètres. Il faut décider ce qui coûte le plus cher.
Planche 5
Organiser les livraisons d'un dépôt : capacité et créneaux horaires
Chaque client n'accepte la livraison que dans un créneau : on ne peut pas arriver après sa fin, et si l'on arrive avant son début, on attend. Les camions roulent à 30 km/h (2 minutes par kilomètre), chaque livraison dure 15 minutes, la journée va de 8 h à 18 h, et un camion porte 10 palettes. On cherche d'abord le moins de camions, puis le moins de kilomètres.
Les tournées du plan choisi. Les camions se déplacent selon l'horloge du planning ci-dessous.
Le planning, une ligne par client. Bande grise : le créneau du client. Bloc de couleur : la livraison, de la couleur du camion. Hachures : l'attente devant un client fermé. Trait rouge : l'heure de l'horloge.
–
Camions ; kilomètres du plan–
Attente totale devant les clients–
Retours au dépôt–
Insertion la moins chère : camions ; km–
Sans créneaux (planche 4) : camions ; km–
Contrôle : créneaux non respectés dans le plan–
Ce que coûtent les créneaux : kilomètres de l'optimum selon leur largeur (bleu), nombre de camions (barres), et méthode d'insertion (orange). Trait vertical : la largeur choisie.
Le prix de l'exactitude. Des créneaux d'une demi-heure obligent à sortir un troisième camion. Dès 45 minutes, deux camions suffisent, mais au prix de 205 km de zigzags, car il faut passer chez chacun à son heure. En élargissant à 5 heures, on retombe à 131 km, le mieux que deux camions puissent faire sans aucune contrainte horaire. Un créneau étroit a donc un coût, que l'on peut maintenant chiffrer et négocier avec le client. Enfin, les méthodes rapides souffrent : l'insertion la moins chère prend souvent un camion de trop, alors que l'optimum se calcule ici en quelques millisecondes, car il n'y a que 9 clients.
Ce qu'il faut garder
Deux problèmes faciles
Transport et affectation sont des programmes linéaires dont la solution sort entière d'elle-même. On les résout exactement, même très grands.
Un problème difficile
Le voyageur de commerce n'a pas de méthode rapide connue garantissant l'optimum. On combine constructions simples, améliorations locales et, quand c'est possible, preuve d'optimalité.
Le réel les combine
Une tournée de livraison affecte des clients aux camions, ordonne chaque tournée, et respecte capacités et horaires. Chaque contrainte ajoutée se paie en kilomètres ou en camions, et ce prix se calcule.
Pour aller plus loin
Dans ce cahier.Le problème de transport (tableau, potentiels, paradoxe), Le problème d'affectation (méthode hongroise), Le voyageur de commerce (heuristiques, bornes, recuit simulé), Graphes et optimisation dans les réseaux (flot à coût minimal, qui contient transport et affectation).
Sur les calculs. L'optimum des tournées est calculé exactement en deux temps : d'abord la meilleure tournée de chacun des 511 groupes de clients possibles, par programmation dynamique ; avec créneaux, chaque étape garde toutes les solutions non dominées, sur l'heure de fin et la distance. Ensuite, le meilleur découpage des neuf clients en groupes. Cela n'est possible que pour quelques clients : un vrai dépôt en compte des centaines, et l'on utilise alors des métaheuristiques ou la génération de colonnes. Les distances sont à vol d'oiseau.