Received 24 November 2015; accepted 1 March 2016; published 4 March 2016
Transportation problem is famous in operation research for its wide application in real life. This is a special kind of the network optimization problems in which goods are transported from a set of sources to a set of destinations subject to the supply and demand of the source and destination, respectively, such that the total cost of transportation is minimized. The basic transportation problem was originally developed by Hitchcock in 1941  . Efficient methods for finding solution were developed, primarily by Dantzig in 1951  and then by Charnes, Cooper and Henderson in 1953  . Basically, the solution procedure for the transportation problem consists of the following phases:
・ Phase 1: Mathematical formulation of the transportation problem.
・ Phase 2: Finding an initial basic feasible solution.
・ Phase 3: Optimize the initial basic feasible solution which is obtained in Phase 2.
In this paper, Phase 2 has been focused in order to obtain a better initial basic feasible solution for the transportation problems. This problem has been studied since long and is well known by Abdur Rashid et al.  , Aminur Rahman Khan et al.  - , Hamdy A. T.  , Kasana & Kumar  , Kirca and Satir  , M. Sharif Uddin et al.  , Mathirajan, M. and Meenakshi  , Md. Amirul Islam et al.   , Md. Ashraful Babu et al.  - , Md. Main Uddin et al.   , Mollah Mesbahuddin Ahmed et al.  - , Pandian & Natarajan  , Reinfeld & Vogel  , Sayedul Anam et al.  , Shenoy et al.  and Utpal Kanti Das et al.   .
Again, some of the well reputed methods for finding an initial basic feasible solution of transportation problems developed and discussed by them are North West Corner Method (NWCM)  , Row Minimum Method (RMM)   , Column Minimum Method (CMM)   , Least Cost Method (LCM)  , Vogel’s Approximation Method (VAM)   , Extremum Difference Method (EDM)  , Highest Cost Difference Method (HCDM)   , Average Cost Method (ACM)  , TOCM-MMM Approach  , TOCM-VAM Approach  , TOCM-EDM Approach  , TOCM-HCDM Approach  , TOCM-SUM Approach  etc.
In this paper, a new algorithm is proposed to find an initial basic feasible solution for the transportation problems. A comparative study is also carried out by solving a good number of transportation problems which shows that the proposed method gives better result in comparison to the other existing heuristics available in the literature.
2. Network Representation and Mathematical Model of Transportation Problem
Generally the transportation model is represented by the network in Figure 1. There are m sources and n destinations, each represented by a node. The arcs represent the routes linking the sources and destinations. Arc (i, j) joining source i to destination j carries two pieces of information: the transportation cost per unit, cij and the amount shipped, xij. The amount of supply at source i is Si, and the amount of demand at destination j is dj. The objective of the model is to determine the unknowns’ xij that will minimize the total transportation cost while satisfying the supply and demand restrictions.
Figure 1. Network representation of transportation problem.
Considering the above notations, the transportation problem can be stated mathematically as a linear programming problem as:
Subject to: ;.
for all and.
The objective function minimizes the total cost of transportation (Z) between various sources and destinations. The constraint i in the first set of constraints ensures that the total units transported from the source i is less than or equal to its supply. The constraint j in the second set of constraints ensures that the total units transported to the destination j is greater than or equal to its demand.
3. Proposed Approach to Find an Initial Basic Feasible Solution
In the proposed approach, an allocation table is formed to find the solution for the transportation problem. That’s why this method is named as Allocation Table Method (ATM) and the method is illustrated below:
・ Step-1: Construct a Transportation Table (TT) from the given transportation problem.
・ Step-2: Ensure whether the TP is balanced or not, if not, make it balanced.
・ Step-3: Select minimum odd cost (MOC) from all the cost cells of TT. If there is no odd cost in the cost cells of the TT, keep on dividing all the cost cells by 2 (two) till obtaining at least an odd value in the cost cells.
・ Step-4: Form a new table which is to be known as allocation table (AT) by keeping the MOC in the respective cost cell/cells as it was/were, and subtract selected MOC only from each of the odd cost valued cells of the TT. Now all the cell values are to be called as allocation cell value (ACV) in AT.
・ Step-5: At first, start the allocation from minimum of supply/demand. Allocate this minimum of supply/ demand in the place of odd valued ACVs at first in the AT formed in Step-4. If demand is satisfied, delete the column. If it is supply, delete the row.
・ Step-6: Now identify the minimum ACV and allocate minimum of supply/demand at the place of selected ACV in the AT. In case of same ACVs, select the ACV where minimum allocation can be made. Again in case of same allocation in the ACVs, choose the minimum cost cell which is corresponding to the cost cells of TT formed in Step-1 (i.e. this minimum cost cell is to be found out from the TT which is constructed in Step-1). Again if the cost cells and the allocations are equal, in such case choose the nearer cell to the minimum of demand/supply which is to be allocated. Now if demand is satisfied delete the column and if it is supply delete the row.
・ Step-7: Repeat Step-6 until the demand and supply are exhausted.
・ Step-8: Now transfer this allocation to the original TT.
・ Step-9: Finally calculate the total transportation cost of the TT. This calculation is the sum of the product of cost and corresponding allocated value of the TT.
4. Numerical Examples with Illustration
A company manufactures motor cars and it has three factories F1, F2 and F3 whose weekly production capacities are 300, 400 and 500 pieces of cars respectively. The company supplies motor cars to its four showrooms located at D1, D2, D3 and D4 whose weekly demands are 250, 350, 400 and 200 pieces of cars respectively. The transportation costs per piece of motor cars are given in the transportation Table 1. Find out the schedule of shifting of motor cars from factories to showrooms with minimum cost:
Table 1. Data of the Example-1.
4.1.1. Solution of Example 1 and Its Explanation
Allocation of various cells in the allocation table for Example-1 is shown in Allocation Table 2.
Table 2. Allocation of various cells are in the allocation table.
・ According to Step-2: It is found that the given problem is balanced. Because of the sum of supplies = sum of the demands = 1200.
・ As per Step-3, minimum odd cost is 1 in cost cell (1, 2) among all the cost cells of the Transportation Table 1.
・ Allocation Table 2, is formed according to Step-4, where minimum odd cost is in cell (1, 2) remains same, but this odd cost is subtracted from all other odd valued cost cells of the transportation Table 1. Like in cost cell (1, 1) it is 3 in Transportation Table 1, but in allocation table this cell value is 2 = (3 − 1).
・ According to Step-5, minimum supply/demand is 300 that is allocated in cell (1, 2). After allocating this value it is found that the supply is satisfied. For which F1 row is to be exhausted.
・ After Step-5, only the cells of F2 and F3 rows are to be considered. Where 2 is the lowest cell value in the cells (2, 1), (3, 2), (3, 3) and (3, 4). Among these four cells 50 is the lowest allocation can be made in cell (3, 2). Now column D2 is crossed out after allocating this amount.
・ Again it is found 2 is the lowest cell value in the remaining cells which appears in the cells (2, 1), (3, 3) and (3, 4). Among these three cells, minimum allocation 200 is made in cell (3, 4). So the cells of column D4 are not to be considered for further calculation.
・ After doing the above allocation, it is found 2 is again the minimum cell value that appears in the cells (2, 1) and (3, 3). In both of these cells 250 is the minimum allocation can be made. But in between these two cells, it is found that the minimum cost cell appears in the cell (2, 1) in the Transportation Table 1, so the minimum allocation 250 is allocated in cell (2, 1). Now column D1 is to be exhausted.
・ Finally complete the allocation by allocating 250 and 150 in the cells (3, 3) and (2, 3) respectively. All these allocations are made according to Step-6 and Step-7 of the proposed algorithm.
・ Now according to Step-8, all these allocations are transferred to the Transportation Table 1, which is shown in the Final Allocation Table 3. In this table it is found that the number of basic cells are 6 (=4 + 3 − 1) which represents the initial basic feasible solution according to the proposed algorithm.
Table 3. Initial basic feasible solution according to ATM.
・ Finally according to the Step-9, total transportation cost is (300 × 1 + 250 × 2 + 150 × 5 + 50 × 3 + 250 × 3 + 200 × 3) = 2850.
Consider the following transportation problem (Transportation Table 4) involving three sources and four destinations. The cell entries represent the cost of transportation per unit. Obtain an initial basic feasible solution.
Table 4. Data of the Example-2.
4.2.1. Solution of Example 2 and Its Explanation
From the Transportation Table 4, it is seen that total supply and total demand are equal. Hence the given transportation problem is a balanced one. Now it is found all the cell values are even number in the Transportation Table 4. So according to the Step-3 of proposed algorithm, these cells values are to be continuously divided by 2 until obtain at least an odd value in the cost cells. The obtaining cell values, after dividing each of the cell values by 2 of the transportation Table 4 for the first time is shown in Table 5.
Table 5. All the cost cells of Example-2 are divided by 2.
・ Allocation of various cells in the allocation table for Example 2 is shown in Allocation Table 6.
Table 6. Allocation of various cells are in the allocation table.
・ As per Step-3, minimum odd cost is 15 in cost cell (3, 3) among all the cost cells of Table 5.
・ According to Step-5, minimum supply/demand is 16 that is allocated in cell (3, 3). After allocating this value it is found that the supply is satisfied. Hence F3 row is crossed out.
・ After Step-5, only F1 and F2 rows are to be considered, where 10 is the lowest cell value among the remaining cells, which appears in the cells (1, 1), (1, 4) and (2, 4). Among these three cells 10 is the lowest allocation is made in the cell (1, 1). For this allocation column D1 to be exhausted.
・ After the above allocation, again it is found 10 is the minimum cell value that appears in the cells (1, 4) and (2, 4). In these two cells 10 and 24 are the allocations can be made. But according to the proposed algorithm 10 is the minimum allocation between these two allocations which is made in the cell (1, 4). This allocation satisfies the supply of F1 row and this row is not to be considered for further allocation.
・ Now complete the allocation by allocating 14, 6 and 18 respectively to the cells (2, 4), (2, 3) and (2, 2). All these allocations are made according to Step-6 and Step-7 of the proposed algorithm.
・ Now according to Step-8, all these allocations are transferred to the Transportation Table 4, which is shown in the Final Allocation Table 7. Where it is found that the number of basic cells are 6 (=4 + 3 − 1) which represents the initial basic feasible solution according to the proposed algorithm.
Table 7. Initial basic feasible solution according to ATM.
・ Finally according to the Step-9, total transportation cost is (10 × 50 + 10 × 50 + 18 × 40 + 6 × 70 + 14 × 50 + 16 × 30) = 3320.
5. Numerical Examples without Illustration
Consider the following transportation problem (Transportation Table 8) involving four sources and four
destinations. The cell entries represent the cost of transportation per unit. Obtain an initial basic feasible solution.
Table 8. Data of the Example-3.
5.1.1. Solution of Example-3
Initial basic feasible solution according to the proposed algorithm is shown in the Final Allocation Table 9.
Table 9. Initial basic feasible solution according to ATM.
・ Hence the total transportation cost is (5 × 7 + 5 × 5 + 20 × 9 + 25 × 3 + 20 × 3 + 5 × 2 + 10 × 3) = 415.
Consider the following transportation problem (Transportation Table 10) involving three origins and three destinations. The cell entries represent the cost of transportation per unit. Obtain an initial basic feasible solution.
Table 10. Data of the Example-4.
5.2.1. Solution of Example-4
Initial basic feasible solution according to the proposed algorithm is shown in the Final Allocation Table 11.
Table 11. Initial basic feasible solution according to ATM.
・ Hence, the total transportation cost is (90 × 3 + 30 × 5 + 50 × 4 + 70 × 8 + 30 × 7) = 1390.
6. Result Analysis
After obtaining an IBFS by the proposed “Allocation Table Method (ATM)”, the obtained result is compared with the results obtained by other existing methods is shown in Table 12.
Table 12. Comparison of the results obtained by various methods.
As observed from Table 12, the proposed allocation table method provides comparatively a better initial basic feasible solution than the results obtained by the traditional algorithms which are either optimal or near to optimal. Again the performance of the solution varies for other methods which may happen also in case of the proposed method. It happens because it is quite difficult to assume a prior which of the methods will result in the best solution.
In today’s highly competitive market, various organizations want to deliver products to the customers in a cost effective way, so that the market becomes competitive. To meet this challenge, transportation model provides a powerful framework to determine the best ways to deliver goods to the customer.
In this article, a new approach named allocation table method (ATM) for finding an initial basic feasible solution of transportation problems is proposed. Efficiency of allocation table method has also been tested by solving several number of cost minimizing transportation problems and it is found that the allocation table method yields comparatively a better result.
Finally it can be claimed that the allocation table method may provide a remarkable Initial Basic Feasible Solution by ensuring minimum transportation cost. This will help to achieve the goal to those who want to maximize their profit by minimizing the transportation cost.