Contents
ToggleStepping Stone
The problem solved by the Stepping stone algorithm is the following:
Let's take an example to show how the algorithm works. Consider four origins and five applicants with the costs and quantity according to the table:
vsij
|
D1
|
D2
|
D3
|
D4
|
D5
|
offer
|
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
|
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 both values in the same box since only the flow will vary.
Stepping stone – Step 1: obtaining a basic solution
By Northwest corner
The principle is simple:
2. Adjust the bid and ask values in respective row and column allocation
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 available quantity is fully allocated to the cells, as needed.
fij
|
D1
|
D2
|
D3
|
D4
|
D5
|
offer
|
O1
|
10
|
2
|
–
|
–
|
–
|
12
|
O2
|
–
|
9
|
2
|
–
|
–
|
11
|
O3
|
–
|
– | 13 |
1
|
–
|
14
|
O4
|
–
|
–
|
–
|
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 satisfy the request, this method although fast only gives an unrealistic feasible solution. Here we do not represent the costs but the flows fij of the offer i to the request j.
By the minimum method
2. If the minimum cost is not unique, you are free to choose any cell.
3. Choose the value of x as much as possibleij corresponding, depending on the constraints of capacity and requirement.
4. Repeat steps 1-3 until all restrictions are satisfied.
By the Vogel (or Balas-Hammer) method
This method uses the transport difference between the two best choices for supply and demand. The base 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 bid or ask, stop.
- If a row (column) remains with a positive supply (demand), determine the base variables in the row (column) using the method of minimums. Stop.
- If all rows and columns that have not been crossed out have a (remaining) bid or ask of zero, use the method of minimums. Stop.
In all other cases, go to step 1.
The first iteration of the method gives: DO1 = 4, DO2 = 3, DO3 = 1, DO4 = 3, DD1 = 1, DD2 = 5, DD3 = 9, DD4 = 1, DD5 = 2. Column D3 has the largest cost difference, the smallest cost is 1, so we saturate the intersection O1 with3 with the stream min(12, 15). The O offer1 is therefore saturated.
fij
|
D1
|
D2
|
D3
|
D4
|
D5
|
offer
|
O1
|
X
|
X
|
12
|
X
|
X
|
12
|
O2
|
–
|
–
|
–
|
–
|
–
|
11
|
O3
|
–
|
– | – |
–
|
–
|
14
|
O4
|
–
|
–
|
–
|
–
|
–
|
8
|
demand
|
10
|
11
|
15
|
5
|
4
|
For the new cost difference calculation, we will no longer take into account the values in row O1. We get after 5 iterations to the following configuration:
fij
|
D1
|
D2
|
D3
|
D4
|
D5
|
offer
|
O1
|
–
|
–
|
12
|
–
|
–
|
12
|
O2
|
–
|
11
|
–
|
–
|
–
|
11
|
O3
|
10 | – | – |
–
|
4
|
14
|
O4
|
–
|
–
|
3
|
5
|
–
|
8
|
demand
|
10
|
11
|
15
|
5
|
4
|
Stepping stone – Step 2: calculation of potentials
Once you have a basic solution, the idea is to modify the solution to make it better. That is to say, the waves must be modified. For this, we will choose a flow that lowers the total transport cost the most. The first step in determining this flow is to calculate the potentials. The potentials are calculated ONLY on the squares with a non-zero flow!
We can then calculate other potentials. The potentials are calculated step by step. In our case, we calculated the potential of row 1 from c12, it is therefore possible to calculate the potential of column 1 or column 2.
Let's take the example again: for column 1, pD1 = c11 + PO1 = 7. For row 2, pD2 = c12 + PO1 = 12. The same for the other rows and columns: pO2 = pD2 - vs22 = 12 -3 = 9; pD3 = 21; p03 = 11; PD4 = 23: PO4 = 12; PD5 = 28.
Stepping stone – Step 3: calculation of the unit cost variation
We get the following table:
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
|
Stepping stone – Step 4: calculating the maximum amount of flow
For example for box 01-D3, we take the following circuit f13 -> f12 -> f22 -> f23 -> f13 with the minimum flow of 2. We obtain the following table:
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
|
By multiplying fij* vij, we know the variation of the total cost by the modification by the flow fij. We choose the box with the greatest fij* vij, here the O box1-D3
Stepping stone – Step 5: Updated table
The flow update calculation is done by the “+ –” rule without counting the return to the original box. Thus in the circuit: f13 + = 2, f12 - = 2, f22 + = 2 and f23 - = 2. The table is as follows:
fij
|
D1
|
D2
|
D3
|
D4
|
D5
|
offer
|
O1
|
10
|
2-2 = –
|
0+2 = 2 |
–
|
–
|
12
|
O2
|
– | 9+2 = 11 |
2-2 = –
|
–
|
–
|
11
|
O3
|
– | – | 13 |
1
|
–
|
14
|
O4
|
–
|
–
|
–
|
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 f13* v13 = 2*20 = 40.
In our example, we finally have the following table:
fij
|
D1
|
D2
|
D3
|
D4
|
D5
|
offer
|
O1
|
–
|
–
|
12 |
–
|
–
|
12
|
O2
|
– | 11 |
–
|
–
|
–
|
11
|
O3
|
10 | – | – |
–
|
4
|
14
|
O4
|
–
|
–
|
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).