Stepping stone

Stepping Stone

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:

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
 The idea of stepping stone is to start from a feasible (non-optimal) basic solution 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.
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 meet the demand, 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

1. Identify the box with the minimum unit transport cost cij.
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 capacity and requirement constraints.
4. Repeat steps 1 to 3 until all restrictions are satisfied.
algorithme stepping stone problème de planification 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.
 

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: 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 min flow (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: 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: pO1 = 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 c12, it is therefore 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 unknowns.

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

For each cell with zero flow, we calculate vij by adding the potential of the associated origin to the unit cost of the box and subtracting the potential of the corresponding destination: vij = cij - pOi - pDj.

We get the following table:

vij
D1
D2
D3
D4
D5
pO
O1
-20
-18
-19
0
O2
17
-8
-5
9
O3
1215
-10
11
O4
23
8
8
12
pD
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 vij 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 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: update the table

The flow update calculation is done by the “+ -” rule without counting the return to the original box. So 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
44
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.

We repeat steps 2 to 5 until no more vij 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:

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 speak of 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 linked 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).

algorithme stepping stone problème de planification balas-hammer vogel

To share
en_GBEN
%d bloggers like this: