Stepping stone

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 :

cij
D1
D2
D3
D4
D5
offre
O1
7
12
1
5
6
12
O2
15
3
12
6
14
11
O3
8
16
10
12
7
14
O4
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.

Étape 1 : obtention d’une solution de base

Par coin Nord-Ouest

Le principe est simple :

 Nous remplissons la première demande avec la première offre jusqu’à saturation d’un des deux. L’élément saturé passe au prochain et ainsi de suite. Cela revient donc à saturer les éléments en partant du Nord-Ouest.
fij
D1
D2
D3
D4
D5
offre
O1
10
2
12
O2
9
2
11
O3
13
1
14
O4
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 fij de l’offre i vers la demande j.

Par la méthode de 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.

On commence par calculer la différence absolue entre l’élément le plus petit et le deuxième plus petit pour chaque ligne et colonne puis on sature la ligne ou colonne (à l’endroit du plus petit coût) possédant la plus grande différence. Le processus est recommencé sans prendre en compte les offres ou demandes saturées (donc ici la ligne ou colonne sélectionnée).

La première itération de la méthode donne : DO1 = 4, DO2 =  3, DO3 = 1, DO4 = 3,  DD1 = 1, DD2 = 5, DD3 = 9, DD4 = 1, DD5 = 2. La colonne D3 possède la plus grande différence de coût, le plus petit coût est 1, on sature donc l’intersection O1 avec D3 avec le flot min(12, 15). L’offre O1 est donc saturée.

fij
D1
D2
D3
D4
D5
offre
O1
X
X
12
X
X
12
O2
11
O3
14
O4
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 O1. Nous obtenons après 5 itérations à la configuration suivante :

fij
D1
D2
D3
D4
D5
offre
O1
12
12
O2
11
11
O3
10
4
14
O4
3
5
8
demande
10
11
15
5
4

É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 : pO1 = 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 c12, 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 : on soustrait le coût cij si on se sert de pO pour calculer pD (pD = pO – cij) et on ajoute le coût cij si on se sert de pD pour calculer pO (pO = pD + cij), ou inversement. Il est à noter que quelque soit le sens de calcul utilisé, nous obtenons le même résultat final. Nous éviterons d’avoir des potentiels négatifs.

Reprenons l’exemple : pour la colonne 1, pD1 = c11 + PO1 = 7. Pour la ligne 2, pD2 = c12 + PO1 = 12. De même pour les autres lignes et colonnes : pO2  = pD2 – c22 = 12 -3 = 9; pD3 = 21; p03 = 11; PD4 = 23: PO4 = 12; PD5 = 28.

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

Pour chaque case ayant un flot nul, on calcule vij 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 : vij = cij + pOi – pDj.

Nous obtenons le tableau suivant :

vij
D1
D2
D3
D4
D5
pO
O1
-20
-18
-19
0
O2
17
-8
-5
9
O3
12 15
-10
11
O4
23
8
8
12
pD
7
12
21
23
28

É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 vij négatif.
 Pour remplir une case vide, il faut remplir 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 01-D3, nous prenons le circuit suivant f13 -> f12 -> f22 -> f23 -> f13 avec le flot minimal de 2. Nous obtenons le tableau suivant :

fij
D1
D2
D3
D4
D5
pO
O1
2
1
1
0
O2
1
1
9
O3
1
11
O4
12
pD
7
12
21
23
28

En multipliant fij*vij, nous connaissons la variation du coût totale par la modification par le flot fij. Nous choisissons la case ayant le plus grand fij*vij, ici la case O1-D3

É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 :  f13 += 2, f12 -=2, f22 += 2 et f23 -= 2. Le tableau est le suivant :

fij
D1
D2
D3
D4
D5
offre
O1
10
2-2 = –
0+2 = 2
12
O2
9+2 = 11
2-2 = –
11
O3
13
1
14
O4
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 f13*v13 = 2*20 = 40.

On répète les étapes 2 à 5 jusqu’à ne plus avoir de vij 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 :

fij
D1
D2
D3
D4
D5
offre
O1
12
12
O2
11
11
O3
10
4
14
O4
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).

Publicités