Stepping stone (english version)

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

Taking different origins which offer a quantifiable quantity of elements; and destinations requesting a certain amount of those elements; a transportation cost is assigned for each origin-destination combination; how to optimize demand at the lowest cost?

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

cij
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
demande
10
11
15
5
4
The idea of stepping stone is to start from a feasible (non-optimal) basic solution to improve iteratively until an optimal solution. It is important to check that supply and demand are equal, if it is not the case you have to add a fictitious cost demand for each offer.

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

Step 1: To obtain a basic solution

By North-west corner

1. Select the north west corner cell and allocate as many units as possible equal to the minimum available supply and demand requirements.
2. Adjust the supply and demand numbers in the respective rows and columns allocation
3. If the supply for the first row is exhausted, then move down to the first cell in the next row
4. If the demand for the first cell is satisfied then move horizontally to the next cell
5. If for any cell supply equals demand then the next allocation can be made in cell either in the next row or column
6. Continue the procedure until the total available quantity is fully allocated to the cells as required.
fij
D1
D2
D3
D4
D5
offer
O1
10
2
12
O2
9
2
11
O3
13
1
14
O4
4
4
8
demande
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.

By minimum’s method

1. Identify the box having minimum unit transportation cost cij.
2. If the minimum cost is not unique, then you are at liberty to choose any cell.
3. Choose the value of the corresponding xij as much as possible subject to the capacity and requirement constraints.
4. Repeat steps 1-3 until all restrictions are satisfied.
transport3

By Vogel’s approximation (or Balas-Hammer)

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

2. Identify the row or column with the greatest penalty cost. Break the 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 the supply and demand and cross out the row or column that is already satisfied. If a row and column are satisfied simultaneously, only cross out one of the two and allocate a supply or demand of zero to the one that remains.

3.

  • If there is exactly one row or column left with a supply or demand of zero, stop.
  • If there is one row (column) left with a positive supply (demand), determine the basic variables in the row (column) using the Minimum Cell Cost Method. Stop.
  • If all of the rows and columns that were not crossed out have zero supply and demand (remaining), determine the basic zero variables using the Minimum Cell Cost Method. Stop.

In any other case, continue with 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. The column D3 have the biggest cost difference, its lowest cost is 1 so we saturate this element  O1 D3 with the flow min(12, 15). The row O1 is saturated.

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

For the new cost difference calculation, we will no longer consider the values of raw 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
demande
10
11
15
5
4

Step 2: Calculating potentials MODI

Once you have a basic solution, the idea is to modify the solution in order to improve the objective function. That is to say that the flow must be modified. For that, we will choose a flow lowering at most the total cost of transport. The first step in determining this flow is to calculate the potentials. The potentials are calculated ONLY on the boxes having a non-zero flow!

Set a potential of 0 to the row with the box having a flow with the highest cost. Here we will take the basic solution provided by the North West corner method: pO1 = 0.

We can then calculate other potentials. The potentials are calculated gradually. In our case, we calculated the potential of raw 1 from c12, so it is possible to calculate the potential of column 1 or column 2.

To calculate the potentials we apply the following rule:  pD + pO = cij which gives N equations with N variables.

We can solve for column 1, pD1 = c11 + PO1 = 7. For raw 2, pD2 = c12 + PO1 = 12. Dnd so on: pO2  = pD2 – c22 = 12 -3 = 9; pD3 = 21; p03 = 11; PD4 = 23: PO4 = 12; PD5 = 28.

Step 3: Calculation of unit cost variation

For each element with a zero flow, we calculate vij: vij = cij – pOi – pDj.
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

Step 4: Calculation of the maximum amount of flow

We now know the variation of the cost of a unit according to the origin and the destination compared to the initial solution. We must now determine the flow circuits to reduce the total cost. This calculation is done only for negative vij.
To fill an empty element, we fill out a non-zero element. When looking for a circuit (a « loop »), we must ensure that a box with a flow always succeeds the last selected box of the circuit. Thus, the circuit is composed of an empty element and full elements. The maximum flow that can be moved to fill the empty box is the minimum of the non-zero box flows (if we can’t found a non-zero element, we can alternate non-zero and zero elements).

For example, the element 01-D3 takes the following circuit f13 -> f12 -> f22 -> f23 -> f13with a minimum flow of 2.

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 element with the largest fij*vij, here it is O1-D3

Step 5: To update the table

The computation of update of the waves is done by the rule of the « + – » without counting the return to the box of origin. 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
demande
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. This is the basic solution minus f13*v13 = 2*20 = 40.

Steps 2 to 5 are repeated until there is no negative vij. We know that there is no circuit to reduce the total cost, so we have an optimal solution.

In our example, we have in the end the following table:

fij
D1
D2
D3
D4
D5
offer
O1
12
12
O2
11
11
O3
10
4
14
O4
3
5
8
demande
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 problem of min cost flow (maximum flow at minimum cost) in a complete bipartite graph – a set of sources connected to a set of sinks (hence the rule of « + – » since we go once in the direction of the flow then in the wrong direction in the chosen circuit).

Publicités