Stepping stone

Contents

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

Are different origins, proposing a certain quantifiable offer; and destinations requiring a certain quantity; a transport cost is assigned for each origin-destination combination; how to best meet demand at the lowest cost?

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₁	D₂	D₃	D₄	D₅	offer
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
demand	10	11	15	5	4

The idea of stepping stone is to start from a basic fix feasible (non-optimal) in order to iteratively improve it until a non-optimizable solution is obtained. There is no better solution, so it is optimal. It is important to check that the supply and the demand are equal, if this is not the case it is necessary to add a fictitious demand of significant cost for each offer.

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:

1. Select the northwest corner cell and assign as many units as possible (minimum requirements) available for supply and demand.
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₁	D₂	D₃	D₄	D₅	offer
O₁	10	2	–	–	–	12
O₂	–	9	2	–	–	11
O₃	–	–	13	1	–	14
O₄	–	–	–	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

1. Identify the box with the minimum unit transport cost c_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.

algorithm stepping stone planning problem balas-hammer vogel

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

2. Identify the row or column with the greatest penalty cost. Break ties arbitrarily (if there are any). Allocate as much as possible to the variable with the lowest unit cost in the selected row or column. Adjust supply and demand and cross out the row or column that is already satisfied. If a row and column are satisfied simultaneously, cross out only one of the two and allocate a supply or demand of zero to the remaining one.

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₃ has the largest cost difference, the smallest cost is 1, so we saturate the intersection O₁ with₃ with the min flow (12, 15). The O offer₁ is therefore saturated.

f_ij	D₁	D₂	D₃	D₄	D₅	offer
O₁	X	X	12	X	X	12
O₂	–	–	–	–	–	11
O₃	–	–	–	–	–	14
O₄	–	–	–	–	–	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₁. We get after 5 iterations to the following configuration:

f_ij	D₁	D₂	D₃	D₄	D₅	offer
O₁	–	–	12	–	–	12
O₂	–	11	–	–	–	11
O₃	10	–	–	–	4	14
O₄	–	–	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!

Let us set a potential of 0 to the line with the cell with the highest cost flow. Here we will take the basic solution provided by the Northwest corner method: p_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₁₂, it is therefore possible to calculate the potential of column 1 or column 2.

To calculate the potentials we apply the following rule: p_D + p_O = c_ijwhich gives N equations with N unknowns.

Let's take the example again: for column 1, p_D1 = c₁₁ + P_O1 = 7. For row 2, p_D2 = c₁₂ + P_O1 = 12. The same for the other rows and columns: p_O2 = p_D2 - vs₂₂ = 12 -3 = 9; p_D3 = 21; p₀₃ = 11; P_D4 = 23: P_O4 = 12; P_D5 = 28.

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

For each cell with zero flow, we calculate v_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₁	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 - Step 4: calculating the maximum amount of the flow

We now know the variation in the cost of a unit depending on the origin and destination compared to the initial solution. We must now determine the flow circuits allowing to reduce the total cost. This calculation is done only for the v_ij negative.

To fill an empty cell, you must empty a full cell. When looking for a circuit (a “loop”), we must make sure that a cell with a flow always succeeds the last cell chosen in the circuit. Thus, the circuit is made up of an empty box and full boxes. The maximum flow that can be moved to fill the empty cell is the minimum of the flows of the non-zero cells.

For example for box 0₁-D₃, we take the following circuit f₁₃ -> f₁₂ -> f₂₂ -> f₂₃ -> f₁₃ with the minimum flow of 2. We obtain the following table:

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

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₁-D₃

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₁₃ + = 2, f₁₂ - = 2, f₂₂ + = 2 and f₂₃ - = 2. The table is as follows:

f_ij	D₁	D₂	D₃	D₄	D₅	offer
O₁	10	2-2 = –	0+2 = 2	–	–	12
O₂	–	9+2 = 11	2-2 = –	–	–	11
O₃	–	–	13	1	–	14
O₄	–	–	–	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₁₃* v₁₃ = 2*20 = 40.

We repeat steps 2 to 5 until no more v_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₁	D₂	D₃	D₄	D₅	offer
O₁	–	–	12	–	–	12
O₂	–	11	–	–	–	11
O₃	10	–	–	–	4	14
O₄	–	–	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).