Transportation problem: Construction of starting solution 2
Authors: Patrick Göring and Ralf Dobinsky
Large transportation problems cause enormous computational effort despite fast optimization proceedings. With the right initiation one can create a good starting solution which can be turned into the optimum in few iterations. In the following article we present 7 methods to find an initial solution.
Inhaltsverzeichnis
North-west corner method
The north-west-corner method is the simplest method and delivers just a starting solution. The method’s name derives from the beginning: the north-west corner (first row, first column). The proceeding ends when the south-east corner is reached.
In our example, we start with the transport from New York to Moscow (north-west corner). New York supplies 90, but Moscow demands only 50, so the transported quantity amounts to 50. The rest of New York (40) gets allocated to the neighboring field New York/Shanghai. New York’s supply quantity is dead, so you regard the next supply city Cairo. At first you have to cover the rest of the demand of Shanghai with 30. Now the next field (London) gets the maximal amount which is limited by the supply of 70 minus the already exhausted 30 from the transportation between Cairo and Shanghai. The total demand of London is not yet covered by this amount of 40. This is reason why Santiago de Chile sends an amount of 20. At last Dubai gets an amount of 40 from Santiago de Chile. At the end you can see that the condition supply = demand is satisfied. Consequently there is no uncovered demand and all the supply is distributed. The total transportation costs amount to 18,750.
As already mentioned this method delivers a vague initial solution because it does not consider the costs at all, so the number of iterations to be taken to reaching the optimal solution can be enormous.
Simple row sequence or column-sequence methods
Starting point is the cheapest field in the first row (column) which gets allocated the maximal possible amount. You proceed in the same row (column) until the supply (demand) quantity is exhausted. Then you continue with the next row (column). We only apply the row sequence method to our example. The procedure of the column sequence method works respectively.
The cheapest field in the first row is New York/London. There you allocate the maximal amount of 60. Afterward the next cheapest field of the row gets allocated the remaining supply quantity (30). There is no more supply quantity left from New York, so you move on to the next supply city Cairo. You start with the cheapest field which still needs to be supplied. In this case it's Dubai which gets delivered 40 units. The next cheapest transport in this row is to Moscow where the transport qunatity amounts to the remaining demand of 20. Now you can just send the last 10 units in this row to Shanghai. After these allocations there is only one possibility left: the transport from Santiago de Chile to Shanghai with an amount of 60 possible.
The total transportation costs amount to 18,850.
The column-sequence method works in principle same as the row sequence method, but starts with the the first column instead. Afterward you run through the matrix column by column.
Row-column succession
You start with the cheapest field of the whole matrix. To this field you allocate the highest amount of transportation possible. This amount is restricted by the minimum of the supply in the regarded row and the demand of the corresponding column. In this example the minimum costs are 20 per unit. You can transport 40 units from Cairo to Dubai. Cairo still has 30 units to supply to another city. This residual amount goes to the city with the second lowest costs. You could transport the rest to Moscow or London, both have would cost 30. But you can see that from the other two supply cities to Moscow the transportation is more expensive than to London. This is the reason why the amount of 30 from Cairo has to be transported to Moscow. The next cheapest field is New York/London. The possible amount here is 60. We still have 30 units to send from New York. 20 go to Moscow and the rest goes to the next cheapest city Shanghai. At the end you can see that there is one possibility left: 60 from Santiago de Chile to Shanghai.
The total costs amount to 18,700.
Matrix-minimum method
You start with the cheapest field of the whole matrix. To this field you allocate the highest amount of transportation possible. This amount is restricted by the minimum of the supply in the regarded row and the demand of the corresponding column. In this example the minimum costs are 20 per unit. You can transport 40 units from Cairo to Dubai. After this you look for the next cheapest field of the whole matrix. You find Moscow and London both supplied by Cairo with costs of 30 per unit. But you can see that from the other two supply cities to Moscow the transportation is more expensive than to London. This is the reason why the amount of 30 from Cairo has to be transported to Moscow. The next cheapest field is New York/London. The possible amount here is 60. With costs of 75 per unit, New York/Moscow is the cheapest field of the remaining matrix. It is possible to serve an amount of 20 there. After this allocation Shanghai is the last one still demanding the good. New York can just send 10 units anymore and the rest of 60 comes from Santiago de Chile.
The total costs amount to 18,700.
Cost difference method
The Cost difference method is more complex than the procedural methodes before, but provide the best approximation of solution. Sometimes this method is called after his innovator as Vogel’s Approximation Method (VAM). The basic idea is to determine the cost difference between the cheapest and the second cheapest field for every row and column.
At the first iteration in the example the differences are:
For the rows:
75 – 60 = 15; 30 – 20 = 10; 150 – 110 = 40
For the columns:
75 – 30 = 45; 110 – 80 = 30; 60 – 30 = 30; 120 – 20 = 100
Afterward you take this row or column whose difference is the highest and allocate the cheapest field in this row or column the maximal amount. In this case the price difference of 100 at the column of Dubai is highest. The cheapest supply city in this column is Cairo with costs per unit of 20. The maximal amount you can transport from Cairo to Dubai is 40. You repeat the action all time, but if the demand or supply of a row or column is depleted you have to cross out this row or column, so it is not relevant anymore. Now you see that the highest difference is in the first column of Moscow. The cheapest field in this column is Cairo/Moscow. Cairo supplies 30 units to Moscow. For the next iteration you have to find the highest cost difference without using the supply city Cairo and the demand city Dubai. The highest difference is given in the column of Moscow. The cheapest cost per unit in this column is from New York. There we allocate 20 units. The cost difference changes another time, because you don’t have to consider Moscow anymore. Now the highest difference is given in Shanghai and Santiago de Chile. In their row and column the minimal costs per unit are 110. Normally you compare the cheapest costs per unit, if the maximal difference is the same. In this example there is no difference for the costs per unit, so you can freely choose on which field you transport the maximal amount. We register first the amount of 70 from New York to Shanghai and then we complete the tableau with transporting 60 units from Santiago de Chile to London.
The total costs amount to 17,500.
Frequency method according to Habr
Habr considers the interdependence of costs even further than Vogel (cost difference method). He uses the matrix-minimum method but modifies the cost elements to express the relations of costs between the elements as follows:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): k_{ij}=mnc_{ij}-n\sum_{p=1}^m c_{pj}-m\sum_{q=1}^n c_{iq}+\sum_{p=1}^m\sum_{q=1}^n c_{pq}
For example:
=3*4*75-4*(75+30+150)-3*(75+110+60+120)+(75+30+150+110+80+180+60+30+110+120+20+150)=-100
=3*4*110-4*(110+80+180)-3*(75+110+60+120)+(75+30+150+110+80+180+60+30+110+120+20+150)=-140
and so on.
We attain the following modified cost matrix:
After you have calculated the new cost matrix, you apply the matrix-minimum method and the allocation results in: 40 from Cairo to Dubai, 60 from Santiago de Chile to London, 70 from New York to Shanghai, 20 from New York to Moscow and 30 from Cairo to Moscow.
The total transportation costs amount to 17,500.
The frequency method according to Habr leads in the majority of cases to results near the optimum. Certainly, the effort to calculate the new elements is exacting.
Modified north-west corner method
The beginning is the same as of the normal north-west corner method: First we allocate the maximal of Moscow’s demand to the field New York/Moscow, namely 50. We continue with the neighbouring field New York/Shanghai to whom we allocate the remaining 40 of New York’s supply.
In contrast to the normal north-west corner method we don’t automatically satisfy Shanghai’s demand by the next supply city Cairo, but we try to find out, if it is cheaper to reallocate Cairo’s supply quantity to Moscow instead, reduce New York/Moscow and increase New York/Shanghai respectively. Therefor we compare the two alternatives’ costs.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{C/M}-c_{NY/M}+c_{NY/S}=30-75+110=65
So it is cheaper to reallocate 30 from NY/M to K/M and therefor increase NY/S by 30 in place of allocating them to K/S. According to the north-west corner method we allocate 40 to Cairo/London and 20 to Santiago de Chile/London because thereto are no alternatives.
Hereafter the next field according to the north-west corner method would be Santiago de Chile/Dubai to allocate the remaining 40. But there is an alternative we have to take into consideration. It could be cheaper to allocate these 40 to Cairo/London and therefor reduce Cairo/London and add to Santiago de Chile/London respectively. A comparison of costs delivers the decision:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{C/D}-c_{C/L}+c_{SdC/L}=20-30+110=100
We reallocate the 40 from Cairo/London to Santiago de Chile/London and therefor we can allocate 40 to the field Cairo/Dubai.
The total costs amount to 17,500.
Literatur
Müller-Merbach, Heiner "Operations Research: Methoden und Modelle der Optimalplanung". Vahlen, München 1973
