Place the cranes (one for each construction sites) in such a way that the overall distance required for the transfer is as small as possible.

Solution:

The cost matrix is

90 75 75 80 35 85 55 65 125 95 90 105 45 110 95 115

1. step: From each row, we find the row minimum and subtract it from all entries on that row.

=>       15 0 0 5 0 50 20 30 35 5 0 15 0 65 50 70

2. step: From each column, we find the column minimum and subtract it from all entries on that column.

=>       15 0 0 0 0 50 20 25 35 5 0 10 0 65 50 65

3. step: We draw lines across rows and columns in such a way that all zeros are covered and that the minimun number of lines have been used (in this case lines across the 1st and the 3rd row and across the 1st column).

4. step: A test for optimality;
If the number of lines just drawn is n (number of rows of the cost matrix), we are done. If the number of lines < n, we go to step 5.
Now the number of lines is 3 < n = 4.

5. step:
We find the smallest entry which is not covered by the lines, which in this case is the (2,3)-entry 20, and subtract it from each entry not covered by the lines. We also add it to each entry which is covered by a vertical and a horizontal line. Now we can go back to step 3.

=>       35 0 0 0 0 30 0 5 55 5 0 10 0 45 30 45

3. step: Draw lines across zeros (1st and 3rd column, 1st row)

4. step: Number of lines = 3 < n => Step 5 and then Step 3 (smallest entry = 5)

=>       40 0 5 0 0 25 0 0 55 0 0 5 0 40 30 40

3. step: Draw lines across zeros (1st and 3rd column, 1st row)

4. step: Number of lines = 4 = n => We are done.

0's positions determine the possible combinations. We have two choices.

Solution:

Crane1 - Constuction site4, Crane2 - Constuction site3, Crane3 - Constuction site2, Crane4 - Constuction site1 ( => overall distance 275 km)
OR
Crane1 - Constuction site2, Crane2 - Constuction site4, Crane3 - Constuction site4, Crane4 - Constuction site1 ( => overall distance 275 km)

---