Contenus

Toggle## Stepping Stone

The problem solved by the Stepping Stone algorithm is as follows:

Let's take an example to show how the algorithm works. Consider four origins and five applicants with costs and quantity according to the table:

vs _{ij} | D _{1} | D _{2} | D _{3} | D _{4} | D _{5} | offer |

O _{1} | 7 | 12 | 1 | 5 | 6 | 12 |

O _{2} | 15 | 3 | 12 | 6 | 14 | 11 |

O _{3} | 8 | 16 | 10 | 12 | 7 | 14 |

O _{4} | 18 | 8 | 17 | 11 | 16 | 8 |

demand | 10 | 11 | 15 | 5 | 4 |

It is possible to perform the algorithm using two tables (one for the costs, one for the flows). It is also possible to display the two values in the same box since only the flow will vary.

## Stepping stone - Step 1: obtaining a base solution

### By Northwest corner

The principle is simple:

2. Adjust the supply and demand values in the allocation of the respective rows and columns

3. If the supply of the first row is exhausted, go down to the first cell of the next row.

4. If the demand for the first cell is satisfied, move horizontally to the next cell.

5. If for a cell supply equals demand, the next allocation can be made in the cell either in the next row or column.

6. Continue the procedure until the total amount available is fully allocated to cells, as needed.

f _{ij} | D _{1} | D _{2} | D _{3} | D _{4} | D _{5} | offer |

O _{1} | 10 | 2 | – | – | – | 12 |

O _{2} | – | 9 | 2 | – | – | 11 |

O _{3} | – | – | 13 | 1 | – | 14 |

O _{4} | – | – | – | 4 | 4 | 8 |

demand | 10 | 11 | 15 | 5 | 4 |

The total cost of the basic solution is: 10 * 7 + 2 * 12 + 9 * 3 + 2 * 12 + 13 * 10 + 12 + 4 * 11 + 4 * 16 = 395.

In many cases it is not possible to meet the demand, this method although fast only gives an unrealistic feasible solution. Here we do not represent the costs but the flows f_{ij} of the offer **i** to the request **j**.

### By the minimum method

_{ij}.

2. If the minimum cost is not unique, you are free to choose any cell.

3. Choose the value of x as much as possible

_{ij}corresponding, depending on capacity and requirement constraints.

4. Repeat steps 1 to 3 until all restrictions are satisfied.

### By the Vogel (or Balas-Hammer) method

This method makes use of the transport difference between the two best choices for supply and demand. The basic solution is often very close to the optimal solution.

1. Determine a penalty cost for each row (column) by subtracting the lowest unit cell cost in the row (column) from the lowest unit cell cost in the same row (column).

3.

- If there is exactly one row or column left with zero supply or demand, stop.
- If there is a row (column) left with a positive supply (demand), determine the basic variables in the row (column) using the minimums method. Stop.
- If all the rows and columns that have not been crossed out have a supply or demand (remaining) of zero, use the minimum method. Stop.

In all other cases, go to step 1.

The first iteration of the method gives: 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. Column D_{3} has the largest cost difference, the smallest cost is 1, so we saturate the intersection O_{1} with_{3} with the min flow (12, 15). The O offer_{1} is therefore saturated.

f _{ij} | D _{1} | D _{2} | D _{3} | D _{4} | D _{5} | offer |

O _{1} | X | X | 12 | X | X | 12 |

O _{2} | – | – | – | – | – | 11 |

O _{3} | – | – | – | – | – | 14 |

O _{4} | – | – | – | – | – | 8 |

demand | 10 | 11 | 15 | 5 | 4 |

For the new cost difference calculation, we will no longer take into account the values in row O_{1}. We get after 5 iterations to the following configuration:

f _{ij} | D _{1} | D _{2} | D _{3} | D _{4} | D _{5} | offer |

O _{1} | – | – | 12 | – | – | 12 |

O _{2} | – | 11 | – | – | – | 11 |

O _{3} | 10 | – | – | – | 4 | 14 |

O _{4} | – | – | 3 | 5 | – | 8 |

demand | 10 | 11 | 15 | 5 | 4 |

## Stepping stone - Step 2: calculating the potentials

Once you have a basic solution, the idea is to modify the solution to make it better. That is to say, it is necessary to modify the flows. For this, we will choose a flow that lowers the total cost of transport the most. The first step in determining this flow is to calculate the potentials. The potentials are calculated ONLY on the cells with a non-zero flow!

_{O1}= 0.

We can then calculate other potentials. The potentials are calculated step by step. In our case, we have calculated the potential of row 1 from c_{12}, it is therefore possible to calculate the potential of column 1 or column 2.

_{D}+ p

_{O}= c

_{ij }which gives N equations with N unknowns.

Let's take the example again: for column 1, p_{D1} = c_{11} + P_{O1} = 7. For row 2, p_{D2} = c_{12} + P_{O1} = 12. The same for the other rows and columns: p_{O2} = p_{D2} - vs_{22} = 12 -3 = 9; p_{D3} = 21; p_{03} = 11; P_{D4} = 23: P_{O4} = 12; P_{D5} = 28.

## Stepping stone - Step 3: calculation of the unit cost variation

_{ij}by adding the potential of the associated origin to the unit cost of the box and subtracting the potential of the corresponding destination: v

_{ij}= c

_{ij}- p

_{Oi}- p

_{Dj}.

We get the following table:

v _{ij} | D _{1} | D _{2} | D _{3} | D _{4} | D _{5} | p _{O} |

O _{1} | – | – | -20 | -18 | -19 | 0 |

O _{2} | 17 | – | – | -8 | -5 | 9 |

O _{3} | 12 | 15 | – | – | -10 | 11 |

O _{4} | 23 | 8 | 8 | – | – | 12 |

p _{D} | 7 | 12 | 21 | 23 | 28 |

## Stepping stone - Step 4: calculating the maximum amount of the flow

_{ij}negative.

For example for box 0_{1}-D_{3}, we take the following circuit f_{13} -> f_{12} -> f_{22} -> f_{23} -> f_{13} with the minimum flow of 2. We obtain the following table:

f _{ij} | D _{1} | D _{2} | D _{3} | D _{4} | D _{5} | p _{O} |

O _{1} | – | – | 2 | 1 | 1 | 0 |

O _{2} | – | – | – | 1 | 1 | 9 |

O _{3} | – | – | – | – | 1 | 11 |

O _{4} | – | – | – | – | – | 12 |

p _{D} | 7 | 12 | 21 | 23 | 28 |

By multiplying f_{ij}* v_{ij}, we know the variation of the total cost by the modification by the flow f_{ij}. We choose the box with the greatest f_{ij}* v_{ij}, here the O box_{1}-D_{3}

## Stepping stone - Step 5: update the table

The flow update calculation is done by the “+ -” rule without counting the return to the original box. So in the circuit: f_{13} + = 2, f_{12} - = 2, f_{22} + = 2 and f_{23} - = 2. The table is as follows:

f _{ij} | D _{1} | D _{2} | D _{3} | D _{4} | D _{5} | offer |

O _{1} | 10 | 2-2 = – | 0+2 = 2 | – | – | 12 |

O _{2} | – | 9+2 = 11 | 2-2 = – | – | – | 11 |

O _{3} | – | – | 13 | 1 | – | 14 |

O _{4} | – | – | – | 4 | 4 | 8 |

demand | 10 | 11 | 15 | 5 | 4 |

The total cost of the basic solution is: 10 * 7 + 2 * 12 + 9 * 3 + 2 * 12 + 13 * 10 + 12 + 4 * 11 + 4 * 16 = 395. The cost of this solution is: 10 * 7 + 11 * 3 + 2 * 1 + 13 * 10 + 12 + 4 * 11 + 4 * 16 = 355. Let the basic solution minus f_{13}* v_{13} = 2*20 = 40.

_{ij}negative. We know then that there is no circuit to reduce the total cost, so we have an optimal solution.

In our example, we finally have the following table:

f _{ij} | D _{1} | D _{2} | D _{3} | D _{4} | D _{5} | offer |

O _{1} | – | – | 12 | – | – | 12 |

O _{2} | – | 11 | – | – | – | 11 |

O _{3} | 10 | – | – | – | 4 | 14 |

O _{4} | – | – | 3 | 5 | – | 8 |

demand | 10 | 11 | 15 | 5 | 4 |

With a total cost of: 10 * 8 + 11 * 3 + 12 * 1 + 3 * 17 + 5 * 11 + 4 * 7 = 259.

## Aside

We talk about flow because the problem is solved as a min cost flow problem (maximum flow at minimum cost) in a graph complete bipartite – a set of sources connected to a set of sinks (hence the “+ –” rule since we go once in the direction of the flow then in the opposite direction in the chosen circuit).