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 :

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.
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 des minimums

1. Identifier la boîte ayant le coût de transport unitaire minimum cij.
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 xij 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.
transport3

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.

3.

  • 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 : 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 : pD + pO = cij ce qui donne N équations à N inconnues.

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 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 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