Transportation problem is a special type of linear programming problem and typically involves a situation where goods are required to be transferred from some sources or manufacturing plants to some distribution centres, markets or warehouses at minimum cost. Typically in such a problem, the matrix gives the sources row-wise and the destinations are given column-wise. The unit cost of transportation from each source to each destination is provided. The purpose is to work out dispatch schedules to reduce shipping cost within the limitations of the supply and demand quantities. The transportation model can be used in other areas such as inventory control, employment scheduling and personal assignment. The transportation model can be represented as follows:
where
ai = quantity at supply point
bj = quantity at demand point
Xij = transportation cost per unit from source to destination
ytj = quantity shipped from source to destination
There are m sources and n destinations as shown in the model. The general form of the transportation problem in linear programming is as follows:
Even though computer solutions are used to find the optimum solution to any transportation problem, it is necessary to know the algorithms for manual computation. The methods used in manual computation are:
- Northwest corner method
- Least cost method
- Modified distribution method (stepping stone method)
Northwest Corner Rule Method
According to this rule, you start allocating quantities to cells from the top left hand corner cell. Allocate the maximum possible quantity in this cell to make allocation for a row/column complete. From this cell, move to the next row/column. Keep on allocating maximum possible quantities till the allocation is complete. Total number of “occupied cells“ must be m + n — 1, where m is the number of supply centres and n the number of demand centres.
If the number of occupied cells is less than m + n — 1, the solution is said to be “degenerate.” In such a case, assume “O” allocation to a suitable cell to make occupied cells equal to m + n — 1.
In the following example, the demand of four warehouses is fulfilled from four factories. The cost of transportation is indicated in the matrix. The logistics manager has to find out the solution for sourcing the right quantity from different factories to fulfil warehousing demand at the optimum transportation cost.
Row Minima Method
Make maximum possible allocation to the minimum cost cell in a row.
Column Minima Method
Make maximum possible allocation, column by column, to the minimum cost cell in each column.
Matrix Minima Method
Make maximum possible allocation to the minimum cost cell and proceed in the same manner for the remaining allocations.
Vogel’s Approximation Method
For every row and every column, find the difference in cost between the least-cost cell and next best least-cost cell. This difference is the penalty for failing to make an allocation to the least-cost cell.
Make maximum possible allocation to the row or column where penalty is maximum. Cancel the row or column for which allocation is complete and proceed in the same manner till all allocations are complete. Vogel’s approximation method (VAM) gives a near-optimal initial feasible solution.
Distribution Method
In this method, an arbitrary initial allocation is made and it is improved upon step-by-step till the optimum schedule is reached.
Modified Distribution Method
In modified distribution (MODI) method, the test of optimality is simplified. In this method, a set of dummy row numbers sp s2, . . . , s,, . . . , sm and a set of dummy column numbers dl, d2, . . . , dj, . . . , dn are decided in the following manner:
Any one number is arbitrarily chosen as zero.
Then for every occupied cell, Cij = di + sj.
From this equation one can decide all numbers step by step.
Now for every unoccupied cell, the cell value is given by:
This cell value, as mentioned earlier, is the increase in cost per unit of material transported, by making an allocation to the cell. Once the cell values are known, one can make an allocation to the cell giving the maximum saving and adjusting the other allocations accordingly. The process for finding dummy numbers is a part of the test for optimality and it is repeated for every new allocation.
The negative cell value indicates incremental cost per unit, if an allocation is made to that cell. This helps in analyzing the costs, if for some reason one is constrained to make an allocation to a particular cell. If the cost of making the supply from a supply centre to a demand centre changes, the cell value will change accordingly. Thus, one can compute how much increase in cost per unit is allowed without making a cell value negative. Similarly, the effect of an increase or decrease in the capacity of a supply centre and the effect of increase or decrease in requirement of a demand centre can be worked out by analyzing changes in allocations and cell values.
In practice, there exist alternative solutions to the problems. In case the supply is not equal to the demand, introducing the dummy supply or dummy demand can solve the problem. In many situations, there always exist constraints that prohibit the use of some routes in the transportation network. In such cases, assign the number (positive or negative as the case may be) to the restricted route and carry out the algorithm. The other solution using the transportation model will be for maximizing the profit, minimizing the cost or optimizing the solution.
Source: Sople V.V (2013), Logistics Management, Pearson Education India; Third edition.
I’d have to check with you here. Which is not one thing I usually do! I take pleasure in studying a publish that can make individuals think. Also, thanks for permitting me to comment!