Transportation problem: Construction of starting solution 1
Transportation problem: Find an initial solution
Introduction
The transportation problem is a general problem for every company, especially in logistics, to get a balance between supply and demand quantity. That means, you have locations which need the product and locations which could send it to each of these. The supply quantity is declared by the variable , the quantity of demand by the variable . A necessary condition for this is that the total supply is equal to the total demand. Furthermore the problem consists of an allocation of the quantity in a cost minimal way. That shows basically the theoretical problem.
Mathematical formulation of a general transportation problem
: supply quantity at location
: demand quantity at location
: transportation cost per unit from supply location to demand location
: transportation quantity from to
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Minimize K= \sum_{i} \sum_{j} c_{ij}*x_{ij}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{j} x_{ij} = a_{i} \lor i
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i} x_{ij} = b_{j} \lor j
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{ij} \ge 0 \lor i,j
A solution only exists, if Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i} a_{i} = \sum_{j} b_{j}
Example
The company "Physics Rules The World" has four manufacturing bases. It produces high technology light amplification by stimulated emission of radiation, short LASER in Rome, Lisbon, Berlin and Moscow. An important furnisher is placed in Madrid, Istanbul and Beijing.
The following cost matrix is depending on the distance between the place of supply and the place of demand. In addition there are a few possibilities to send the material like by truck, plane or train. That is the reason why the shortest distance does not have to be the possibility with the shortest costs.
In the following part possibilities to find an initial solution are explained.
1. North-West corner method
2. Simple row sequence or column sequence methods
3. Row-column succession
4. Matrix-Minimum method
5. Cost difference method
6. Frequency method
7. Modified North-West corner method
1.North-West corner method
The North-West corner method is not really an approximation procedure and is only of historical importance. The reason is that it offers mostly a bad starting solution because it does not consider the costs.
The method works as follow: you start in the left upper field, which is in this example Madrid-Rome. The supply of Madrid is 60 quantity units (QU) while the demand of Rome is 45 QU. So Rome is allocated 45 QU from Madrid. Then the neighbouring connection between Madrid and Lisbon is examined. Lisbon has a demand of 60 QU and therefore Madrid gets allocated the remaining QU from Madrid of 15. Lisbon has now a remaining demand of 60 QU. Consequently it gets the whole supply from the neighbouring Istanbul which is 40 QU and also needs 20 QU from the next delivering city, which is Beijing. Then Berlin with 30 QU and Moscow with 50 QU get the remaining QU of Beijing. This allocation has a total amount of costs of 8675 monetary units.
The principle of this method is, starting from the north-western field, to allocate every field the minimum of the (remaining) supply of the row and the (remaining) demand of the column. Depending on the rest of the row or column you go to the next column or row. You go down staircase-like to the south-eastern corner.
2.Simple row sequence or column sequence methods
The Simple Row Sequence offers better solutions than the North-West corner method. The allocation starts in the field of the first row with the lowest costs. In this case it is Madrid-Lisbon. Lisbon gets allocated 60 QU from Madrid. Then you continue with the second row because the first one has no remaining capacity. There Moscow gets 40 QU from Istanbul because it has the lowest costs of the row. In the next step the amount of Beijing is allocated. Berlin has got the lowest costs of the row so it is first allocated 30 QU. After that Rome gets 45 QU, Lisbon 15 QU and Moscow the remaining 10 QU.
This allocation has a total amount of costs of 6175 monetary units.
The simple column sequence method works equally but the columns are used instead of the rows.
3. Row-column succession
Order of steps:
1. Allocate the cheapest field of the whole matrix the highest possible quantity.
2. The next cheapest field in row or column should get the remaining quantity.
3. Move forward till every demand is tiled.
As the order is depending on the lowest costs it shows a good approximation to the optimal solution.
In this example the field with minimal costs is Madrid-Lisbon with 15 monetary units per quantity unit. The maximal quantity which you can place there is 60 restricted by the row. Then you are finishing the according column and allocate 15 QU to Istanbul-Lisbon. After that the next row is taken into consideration. The field Istanbul-Moscow gets 25 QU. There is only Beijing remaining yet. Next 25 QU are sent from Beijing to Moscow, then 30 QU Beijing-Berlin and at last step to complete supply= demand Beijing-Rome 45 QU.
4. Matrix-Minimum method
In order to generate an initial solution with the Matrix-Minimum method you look for the cheapest option and allocate the maximum quantity there (Madrid - Lisbon, cost 15). Afterwards choose the second cheapest option to allocate there a maximum amount, too. (in our example: Istanbul - Moscow, cost 20) This procedure is done till till all restrictions are fulfilled. In conclusion an initial solution is reached if there are no amounts left to distribute. In our example tableau you can track this method by following the green arrows. Matrix-Minimum method is a very easy alternative to reach an intermediate starting solution. In our example you get a total of monetary units by 6175.
5. Cost difference method
Establishing an initial solution through Cost-Difference Method is little extensive. Anyway it will serve an outstanding starting solution.
In the first iteration you have to calculate the differences between the cheapest and second cheapest option of every column and row (blue) . You allocate the maximum amount to the cheapest field of the row/column with highest difference. (Istanbul - Moscow, difference of 30) Afterwards you do the same and calculate the new differences( pink ). Rows and columns, where the capacity is reached you don't take in consideration. Likewise with all filled fields (Moscow-Istanbul, first iteration). Through each iteration you allocate capacities until all are distributed ( last iteration ) or one row/ column is left over (from red ) - then all remaining QUs can easily be allocated. In the example the detailed way is depicted.
At least you get total costs of this starting solution of 6175 monetary units.
6. Frequency method by Habr:
The frequency method considers the interdependence of costs. In addition a modified matrix minimum method is part of this algorithm. In the most cases the results of frequency method are adequate solution and nearly optimal. The problem of this method is based on the time which you need to determine the modified matrix. You get this modified matrix by following this mathematical formulation.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): k_{ij}= m*n*c_{ij}-n\sum\nolimits_{p=1}^m c_{pj} -m \sum\nolimits_{q=1}^n c_{iq}+\sum\nolimits_{p=1}^m \sum\nolimits_{q=1}^n c_{pq}
= row ; = column
= number of rows; = number of columns;
Example:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): k_{11}= 3*4*20- 4*(20+30+40) -3*(20+15+25+60)+ (20+15+25+50+30+35+60+20+40+55+35+80) = 240-360-360+465= -15
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): k_{21}= 3*4*30- 4*(20+30+40) -3*( 30+35+60+20) +465= 30
The remaining are defined by using the mathematical formulation for every element.
Modified matrix of the costs
After that we have to use the matrix minimum method. That is why we add the highest possible quantity to the field with the lowest costs. So at first Moscow/ Istanbul with the costs of -330 gets 40 QU. Then Istanbul can’t send quantity anymore. The next lowest element is Beijing/Berlin. We store the possible 30 QU. Berlin is finished now. Go on with Madrid/ Lisbon and store 60 QU. Madrid is closed now. The remaining quantity has to be in the row of Beijing to fulfil supply=demand.
Solution tableau
7.Modified North-West corner method
The modified North-West corner method is a preoptimizing method. It starts like the North-West corner method with the allocation of 45 QU to Madrid-Rome and 15 QU to Madrid-Lisbon. Normally the connection Istanbul-Lisbon would get an allocation. But with the modified method this allocation is compared with a reallocation. Istanbul gets an allocation, the amount of Madrid-Rome is reduced and the one of Madrid Lisbon is increased. Then the total amount of the upcoming costs is compared:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{I-R} - c_{Mad-R} + c_{Mad-L}=30-20+15<c_{I-L}
The reallocation has lower costs so Istanbul-Rome is allocated 40 QU, because this is the highest amount Istanbul proposes, the amount of Madrid-Rome is reduced by 40 QU and the one of Madrid-Rome is increased by 40 QU.
According to the North-West corner method next field to be considered is Beijing-Lisbon with Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{Bei-L}=55
. This is compared with the reallocation via Beijing-Rome, Madrid-Rome and Madrid-Lisbon:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{Bei-R} - c_{Mad-R} + c_{Mad-L}=40-20+15
.
The second possibility has lower costs so 5 QU are reallocated, and Lisbon is allocated the remaining demand from Beijing which is 15 QU.
In the next step the allocation Beijing-Berlin with Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{Bei-Ber} = 35
is compared with the reallocations
1. Beijing-Lisbon, Madrid-Lisbon, Madrid-Berlin: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{Bei-L} - c_{Mad-L} + c_{Mad-Ber}=65
2. Beijing-Rome, Istanbul-Rome, Istanbul-Berlin: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{Bei-R} - c_{I-R} + c_{I-Ber}=70
The allocation Beijing-Berlin has the lowest costs, so Berlin is allocated 30 QU from Beijing.
Finally the field Beijing-Moscow with Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{Bei-M}=80
is taken into consideration. The costs are compared with the reallocations
1. Beijing-Rome, Istanbul-Rome, Istanbul-Moscow: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{Bei-R} - c_{I-R} + c_{I-Mos}=30
2. Beijing-Lisbon, Madrid-Lisbon, Madrid-Moscow: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{Bei-L} - c_{Mad-L} + c_{Mad-Mos}=90
Reallocation 1 has the lowest costs. So Moscow gets the whole amount of 40 QU from Istanbul and 10 QU from Beijing.
So finally the total costs of this starting solution are 6175 monetary units.
Sources
Operations Research Script
H.Müller Mehrbach, Operations Research p. 311 ff.
Operations Research Wiki
