Stepping stone

FacebookEmailLinkedInWhatsAppTelegramCopy Link

Stepping Stone

The problem solved by the Stepping stone algorithm is the following:

Either different origins, offering a certain quantifiable offer; and destinations requiring a certain quantity; a transportation cost is assigned for each origin-destination combination; how best to satisfy demand at the lowest cost?

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
 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 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:

1. Select the northwest corner cell and assign as many units as possible (minimum needs) available to supply and demand.
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

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

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

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!

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 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 space 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
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

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 allowing the total cost to be reduced. This calculation is done only for vij negative.
 To fill an empty box, you must empty a full box. When looking for a circuit (a “loop”), we must ensure that a square with a flow always follows the last chosen square of the circuit. Thus, the circuit is composed of an empty square and full squares. The maximum flow that can be moved to fill the empty box is the minimum of the flows of the non-zero boxes.

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.

We repeat steps 2 to 5 until there are no more vij negative. We then know 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 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).

FacebookEmailLinkedInWhatsAppTelegramCopy Link
en_GBEN
FR
FR
EN
ES
Exit mobile version