Stepping stone

Contenus

Le problème résolu par l’algorithme du Stepping stone est le suivant :

Soient différentes origines, proposant une certaine offre quantifiable; et des destinations demandant une certaine quantité; un coût de transport est attribué pour chaque combinaison d’origine-destination; comment satisfaire au mieux la demande au moindre coût ?

Prenons un exemple pour montrer le déroulement de l’algorithme. Soient quatre origines et cinq demandeurs avec les coûts et quantité suivant le tableau :

c_ij	D₁	D₂	D₃	D₄	D₅	offre
O₁	7	12	1	5	6	12
O₂	15	3	12	6	14	11
O₃	8	16	10	12	7	14
O₄	18	8	17	11	16	8
demande	10	11	15	5	4

L’idée du stepping stone est de partir d’une solution de base réalisable (non optimale) afin de l’améliorer itérativement jusqu’à obtenir une solution non optimisable. Il n’existe pas de meilleure solution, donc elle est optimale. Il est important de vérifier que l’offre et la demande soit égales, si ce n’est pas le cas il faut rajouter une demande fictive de coût important pour chaque offre.

Il est possible d’effectuer l’algorithme à l’aide de deux tableaux (un pour les coûts, un pour les flots). Il est aussi possible d’afficher les deux valeurs dans la même case puisque seul le flot va varier.

Stepping stone – Étape 1 : obtention d’une solution de base

Par coin Nord-Ouest

Le principe est simple :

1. Sélectionnez la cellule d’angle nord-ouest et attribuez autant d’unités que possible (besoins minimaux) disponibles en matière d’offre et de demande.
2. Ajustez les valeurs d’offre et de demande dans l’allocation des lignes et des colonnes respectives
3. Si l’approvisionnement de la première rangée est épuisé, descendez à la première cellule de la rangée suivante
4. Si la demande pour la première cellule est satisfaite, déplacez-vous horizontalement vers la cellule suivante
5. Si pour une cellule l’offre est égale la demande, l’allocation suivante peut être faite dans la cellule soit dans la ligne ou la colonne suivante
6. Continuez la procédure jusqu’à ce que la quantité totale disponible soit entièrement allouée aux cellules, selon les besoins.

f_ij	D₁	D₂	D₃	D₄	D₅	offre
O₁	10	2	–	–	–	12
O₂	–	9	2	–	–	11
O₃	–	–	13	1	–	14
O₄	–	–	–	4	4	8
demande	10	11	15	5	4

Le coût total de la solution de base est : 10*7+2*12+9*3+2*12+13*10+12+4*11+4*16 = 395.

Dans de nombreux cas il n’est pas possible de satisfaire la demande, cette méthode bien que rapide ne donne une solution réalisable que peu réaliste. Ici on ne représente pas les coûts mais les flots f_ij de l’offre i vers la demande j.

Par la méthode des minimums

1. Identifier la boîte ayant le coût de transport unitaire minimum c_ij.
2. Si le coût minimum n’est pas unique, vous êtes libre de choisir n’importe quelle cellule.
3. Choisissez autant que possible la valeur du x_ij correspondant, en fonction des contraintes de capacité et d’exigence.
4. Répétez les étapes 1 à 3 jusqu’à ce que toutes les restrictions soient satisfaites.

Par la méthode de Vogel (ou Balas-Hammer)

Cette méthode fait appel à la différence de transport entre les deux meilleurs choix pour l’offre et la demande. La solution de base est souvent très proche de la solution optimale.

1. Déterminez un coût de pénalité pour chaque ligne (colonne) en soustrayant le coût de cellule unitaire le plus bas dans la rangée (colonne) du coût de cellule unitaire le plus bas dans la même rangée (colonne).

2. Identifiez la rangée ou la colonne ayant le plus grand coût de pénalité. Briser les liens arbitrairement (s’il y en a). Allouer autant que possible à la variable avec le coût unitaire le plus bas dans la ligne ou la colonne sélectionnée. Ajustez l’offre et la demande et rayer la ligne ou la colonne déjà satisfaite. Si une ligne et une colonne sont satisfaites simultanément, ne rayer que l’une des deux et allouer une offre ou une demande de zéro à celle qui reste.

S’il reste exactement une ligne ou une colonne avec une offre ou une demande de zéro, arrêtez.
S’il reste une ligne (colonne) avec une offre positive (demande), déterminez les variables de base dans la ligne (colonne) en utilisant la méthode des minimums. Arrêtez.
Si toutes les lignes et colonnes qui n’ont pas été barrées ont une offre ou demande (restant) de zéro, utilisez la méthode des minimum. Arrêtez.

Dans tous les autres cas, passez à l’étape 1.

La première itération de la méthode donne : D_O1 = 4, D_O2 = 3, D_O3 = 1, D_O4 = 3, D_D1 = 1, D_D2 = 5, D_D3 = 9, D_D4 = 1, D_D5 = 2. La colonne D₃ possède la plus grande différence de coût, le plus petit coût est 1, on sature donc l’intersection O₁ avec D₃ avec le flot min(12, 15). L’offre O₁ est donc saturée.

f_ij	D₁	D₂	D₃	D₄	D₅	offre
O₁	X	X	12	X	X	12
O₂	–	–	–	–	–	11
O₃	–	–	–	–	–	14
O₄	–	–	–	–	–	8
demande	10	11	15	5	4

Pour le nouveau calcul de différence de coût, nous ne tiendrons plus compte des valeurs de la ligne O₁. Nous obtenons après 5 itérations à la configuration suivante :

f_ij	D₁	D₂	D₃	D₄	D₅	offre
O₁	–	–	12	–	–	12
O₂	–	11	–	–	–	11
O₃	10	–	–	–	4	14
O₄	–	–	3	5	–	8
demande	10	11	15	5	4

Stepping stone – Étape 2 : calcul des potentiels

Une fois que l’on possède une solution de base, l’idée est de modifier la solution pour qu’elle soit meilleure. C’est-à-dire qu’il faut modifier les flots. Pour cela, nous allons choisir un flot baissant le plus le coût total de transport. La première étape pour déterminer ce flot consiste à calculer les potentiels. Les potentiels se calculent UNIQUEMENT sur les cases ayant un flot non nul !

Fixons un potentiel de 0 à la ligne comportant la case ayant un flot avec le coût le plus élevé. Ici nous prendrons la solution de base fournie par la méthode du coin Nord-Ouest : p_O1 = 0.

Nous pouvons ensuite calculer d’autres potentiels. Les potentiels sont calculés de proche en proche. Dans notre cas, nous avons calculé le potentiel de la ligne 1 à partir de c₁₂, il est donc possible de calculer le potentiel de la colonne 1 ou de la colonne 2.

Pour calculer les potentiels nous appliquons la règle suivante : p_D + p_O = c_ijce qui donne N équations à N inconnues.

Reprenons l’exemple : pour la colonne 1, p_D1 = c₁₁ + P_O1 = 7. Pour la ligne 2, p_D2 = c₁₂ + P_O1 = 12. De même pour les autres lignes et colonnes : p_O2 = p_D2 – c₂₂ = 12 -3 = 9; p_D3 = 21; p₀₃ = 11; P_D4 = 23: P_O4 = 12; P_D5 = 28.

Stepping stone – Étape 3 : calcul de la variation de coût unitaire

Pour chaque case ayant un flot nul, on calcule v_ij en ajoutant au coût unitaire de la case le potentiel de l’origine associée et en retranchant le potentiel de la destination correspondante : v_ij = c_ij – p_Oi – p_Dj.

Nous obtenons le tableau suivant :

v_ij	D₁	D₂	D₃	D₄	D₅	p_O
O₁	–	–	-20	-18	-19	0
O₂	17	–	–	-8	-5	9
O₃	12	15	–	–	-10	11
O₄	23	8	8	–	–	12
p_D	7	12	21	23	28

Stepping stone – Étape 4 : calcul de la quantité maximale du flot

Nous connaissons maintenant la variation du coût d’une unité en fonction de l’origine et de la destination par rapport à la solution initiale. Nous devons maintenant déterminer les circuits de flots permettant de faire diminuer le coût total. Ce calcul se fait uniquement pour les v_ij négatif.

Pour remplir une case vide, il faut vider une case pleine. Au moment de chercher un circuit (une « boucle »), nous devons nous assurer qu’une case ayant un flot succède toujours à la dernière case choisie du circuit. Ainsi, le circuit est composé d’une case vide et de cases pleines. Le flot maximal pouvant être déplacé pour remplir la case vide est le minimum des flots des cases non nulles.

Par exemple pour la case 0₁-D₃, nous prenons le circuit suivant f₁₃ -> f₁₂ -> f₂₂ -> f₂₃ -> f₁₃ avec le flot minimal de 2. Nous obtenons le tableau suivant :

f_ij	D₁	D₂	D₃	D₄	D₅	p_O
O₁	–	–	2	1	1	0
O₂	–	–	–	1	1	9
O₃	–	–	–	–	1	11
O₄	–	–	–	–	–	12
p_D	7	12	21	23	28

En multipliant f_ij*v_ij, nous connaissons la variation du coût totale par la modification par le flot f_ij. Nous choisissons la case ayant le plus grand f_ij*v_ij, ici la case O₁-D₃

Stepping stone – Étape 5 : mise à jour du tableau

Le calcul de mise à jour des flots se fait par la règle du « + – » sans compter le retour à la case d’origine. Ainsi dans le circuit : f₁₃ += 2, f₁₂ -=2, f₂₂ += 2 et f₂₃ -= 2. Le tableau est le suivant :

f_ij	D₁	D₂	D₃	D₄	D₅	offre
O₁	10	2-2 = –	0+2 = 2	–	–	12
O₂	–	9+2 = 11	2-2 = –	–	–	11
O₃	–	–	13	1	–	14
O₄	–	–	–	4	4	8
demande	10	11	15	5	4

Le coût total de la solution de base est : 10*7+2*12+9*3+2*12+13*10+12+4*11+4*16 = 395. Le coût de cette solution est : 10*7+11*3+2*1+13*10+12+4*11+4*16 = 355. Soit la solution de base moins f₁₃*v₁₃ = 2*20 = 40.

On répète les étapes 2 à 5 jusqu’à ne plus avoir de v_ij négatif. Nous savons alors qu’il n’existe pas de circuit permettant de diminuer le coût total, nous avons donc une solution optimale.

Dans notre exemple, nous avons au final le tableau suivant :

f_ij	D₁	D₂	D₃	D₄	D₅	offre
O₁	–	–	12	–	–	12
O₂	–	11	–	–	–	11
O₃	10	–	–	–	4	14
O₄	–	–	3	5	–	8
demande	10	11	15	5	4

Avec un coût total de : 10*8+11*3+12*1+3*17+5*11+4*7 = 259.

Aparté

Nous parlons de flot car le problème est résolu comme un problème de min cost flow (flot maximum au coût minimum) dans un graphe biparti complet – un ensemble de sources reliés à un ensemble de puits (d’où la règle du « + – » puisque l’on va une fois dans le sens du flot puis à contresens dans le circuit choisi).