International Journal of Statistics and Applications

p-ISSN: 2168-5193    e-ISSN: 2168-5215

2024;  14(3): 56-64

doi:10.5923/j.statistics.20241403.03

Received: Jul. 10, 2024; Accepted: Aug. 6, 2024; Published: Sep. 27, 2024

 

A Mean Descending Order of Ranking Approach of Finding an Initial Basic Feasible Solution of Transportation Problem

Stephen Chidi Duru, Akobi Emmanuel Ogar

Department of Mathematics and Statistics, University of Port Harcourt, Rivers State, Nigeria

Correspondence to: Akobi Emmanuel Ogar, Department of Mathematics and Statistics, University of Port Harcourt, Rivers State, Nigeria.

Email:

Copyright © 2024 The Author(s). Published by Scientific & Academic Publishing.

This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/

Abstract

This paper centres on another method of solving transportation problems called a Mean Descending Order of Ranking Approach of Finding an Initial Basic Feasible Solution for a Transportation Problem. This is achieved by calculating the row and column mean and rank in descending order thereby allocating as much as possible within the restrictions of the rim conditions to the lowest cost cell in the row(s) or column(s) selected. This calculation is done effortlessly. Results from the numerical examples showed that the mean descending Ranking Approach method was very near optimal or with fewer iteration to optimality and having very few minutes from formulation stage to optimal stage. When compared with other methods, the new proposed algorithm does better in finding IBFS than the North-West Corner Method, Least Cost Method and Vogel’s Approximation Method.

Keywords: Transportation Problem, Transportation Table, Ranking, Initial Basic Feasible Solution, Transportation Cost, Time, Optimal Solution

Cite this paper: Stephen Chidi Duru, Akobi Emmanuel Ogar, A Mean Descending Order of Ranking Approach of Finding an Initial Basic Feasible Solution of Transportation Problem, International Journal of Statistics and Applications, Vol. 14 No. 3, 2024, pp. 56-64. doi: 10.5923/j.statistics.20241403.03.

1. Introduction

Since the 18th century, when transportation difficulties were first formulated mathematically, they have been a well-known subject in operations research, and throughout World War I, their importance increased. During this phase of the war, plans were created to gather troops and the equipment they needed at strategic depots. These forces were then swiftly sent to the assigned location by making effective use of optimization in transportation issues. The achievement of an organization's social and economic objectives is significantly impacted by transportation. The last 20 years have seen a major contribution to the creation of a new generation of transportation systems that fit the value that each rapidly expanding business has to provide, with an emphasis on certain qualities like quality, flexibility, speed, dependability, or affordability. Because of the efficiency and growth of contemporary science and technology, the concepts of logistics in operations research continue to reap substantial benefits. Manufacturing firms aim to minimize their overhead expenses in order to maximize their product costs. For instance, transportation costs make up a sizable amount of the expenditures in the mining and energy sectors. Bienstock and Munoz (2015) state that as freight makes up between one-third and two-thirds of all logistics costs, even a little gain in transportation efficiency would boost the bottom line of the business. To find the best answer to a transportation problem, follow these fundamental steps: (Mohan and Gupta, 2003)
Step 1: Mathematical formulation of the transportation problem
Step 2: Determining an initial basic feasible solution
Step 3: To test whether the solution is an optimal one. If not, improve it further till the optimality is achieved. Most of the time the initial basic feasible solution of transportation problem is calculated by using the methods of North West Corner Method, Row Minima Method, Column Minima Method, Least Cost Method or Vogel’s Approximation Method, and then finally the optimality is checked and calculated by MODI (modified distribution) method or Stepping Stone Method.

2. Related Literature Review

George B. Dantzig first introduced the concept of linear programming in 1947 while serving as a mathematical advisor to the United States Air Force Comptroller. His work focused on creating a mechanized planning tool for time stage deployment, training, and logistical supply programs. Although the term “linear programming” was coined by Koopmans in 1948, it was Dantzig who published the simplex method for solving linear programming problems. Initially, linear programming was concerned with planning and scheduling related to training, logistics, and personnel deployment. Today, its applications have expanded to encompass all economic activities, including the transportation of raw materials and products, agricultural planning, and manufacturing processes like cutting paper rolls to customers specifications. The primary objective of linear programming is to optimize a linear function while adhering to constraints defined by linear inequalities or equalities. Luenberger (1973) noted that linear programming’s popularity stems from the relative ease of problem formulation compared to the complexity of solving them. This method is particularly effective in scenarios where multiple competing candidates seek to utilize limited resources efficiently. Dantzig (2016) and Murthy (2005) emphasized that linear programming is one of the most powerful and versatile decision-making tools available. Sultan (2014) pointed out its significant role in various military operations during critical conflicts. During the World War II, the necessity for effective resource management and planning became evident, highlighting the challenges of transporting personnel and equipment from various sources. Ahmed et al (2016a) described transportation modelling as a strategy for planning the distribution of supplies from multiple sources to various destinations. The primary goal of addressing transportation problems is to minimize distribution costs for goods or products moving from factories to warehouses or other destinations.

3. Proposed Approach to Find Initial Basic Feasible Solution

Transportation modeling is an iterative procedure for solving problems that involve minimizing the cost of shipping products from a series of sources to a series of destination. Heizer and Render (2004) explained the steps for solving the problem as “Based on theory, after all needed data were arranged in tabular form, the next step of the technique is to establish an initial feasible solution to the problem and finally, iterate towards optimal solution using the u-v method or the stepping stone method”. In accordance to the transportation problem, the following steps are to be followed:
The process of lowering the cost of moving goods from a number of origins to a number of destinations is known as transportation modeling, and it is an iterative process. As stated by Heizer and Render (2004), "Based on theory, after all needed data were arranged in tabular form, the next step of the technique is to establish an initial feasible solution to the problem and finally, iterate towards optimal solution using the u-v method or the stepping stone method." This is how the problem is solved. The following actions need to be taken in light of the transportation issue:
Step 1: Form a transportation table (TT) from the given transportation problem.
Step 2: Ensure that the transportation problem (TP) is balanced by .
Step 3: Calculate for all rows and for all columns’.
Step 4: Rank the rows in descending order based on higher value.
Step 5: Rank the column in descending order based on higher value. If multiple columns or rows have equal higher or value, these columns or rows will appear in the same position in ranking.
Step 6: Select 1st ranked row and 1st ranked column.
Step 7: If two or more same ranked columns or rows are existed in the transportation table, select these also. Find the smallest cost cell from these row and column. Allocate as many units as possible to that cell. If the minimum cost exists in several cells, select a cell and allocate goods to satisfy the rim condition. Then eliminate the row or column in which supply or demand is exhausted.
Step 8: If 1st column is eliminated, select the next ranked (2nd) column and also 1st row. Again, if 1st row is eliminated, select the next ranked (2nd) row and also 1st column then go to step7 to make allocation. Adjust the supply and demand and cross out the satisfied row or column. If a row and a column are satisfied simultaneously, either the row or column is crossed out and the remaining row or column is assigned a zero supply or demand. Any row or column with zero demand or supply should not be used in making future allocation.
Step 9: Repeat the process with next higher value (rank) in rows or value (column) in columns and continue until the entire available supply at various sources and demand at various destinations is satisfied.
Step 10: Compute the total transportation cost, .

4. Numerical Illustrations of the Propose Method

We shall consider a few examples including small, medium and large size dimensions of transportation problem which will make clear the technique of formulation and the solutions of transportation problem.
Example 1
A company has three factories and three showrooms. The factories altogether have a surplus of 270 units of a given commodity, divided among them as follows
The three showrooms altogether need 270 units of the commodity. Individual requirements at showrooms D1, D2, and D3 are 70, 120, and 80 units respectively. Cost of shipping one unit of commodity from factory to showroom in naira is given in the matrix below.
Table 1. Matrix of example 1
     
Solution
This consists in expressing supply from origins, requirements at destinations and cost of shipping from origins to destinations in the form of a matrix as shown in table 2
Ø Solving step by step from the proposed algorithm, transportation table is form already which includes the demand row and supply column from step 1.
Ø The transportation problem is balanced according to step2. Clearly, the sum of supply is equal to the sum of demand as shown in row 5 column 5. (table 2)
Ø The mean value of unit transportation cost is calculated in each row and column step3.
Ø All factories and showrooms are ranked accordingly according to step4 and step5.
Table 2. Transportation table containing rows and column mean unit transportation cost and their ranks based on higher mean value
     
Following step 6, 7 and 8, select 1st ranked row in factory 3, 1st ranked column in showroom D1 and also 1st ranked column in showroom D2. The smallest cost cell within these row and column is found in (Factory 1 showroom D2). Hence, 90 units of goods is the maximum that can be allocated in this cell. therefore, factory 1, 3rd ranked row is completely exhausted and is deleted (table 3).
Table 3. Transportation table with selected 1st ranked rows and 1st ranked column
     
Again, following step 6, 7 and 8, select 1st ranked row in factory 3, 1st ranked column in showroom D1 and also 1st ranked column in showroom D2. The smallest cost cell within these row and column is found in (showroom D2, factory 2). Hence, 30 units of goods is the maximum that can be allocated in this cell. therefore, showroom D2, 1st ranked column is completely exhausted and is deleted (table 4).
Table 4. Transportation table with selected 1st ranked rows and 1st ranked column
     
Repeat step 6, 7 and 8, select 1st ranked row in factory 3, 1st ranked column in showroom D1. The smallest cost cell within these row and column is found in (showroom D1, factory 2). Hence, 50 units of goods is the maximum that can be allocated in this cell. therefore, factory 2 2nd ranked row is completely exhausted and is deleted (table 5).
Table 5. Transportation table with selected 1st ranked rows and 1st ranked column
     
According to step 6, 7 and 8, select 1st ranked row in factory 3, 1st ranked column in showroom D1. The smallest cost cell within these row and column is seen in showroom D3, factory 3 in 2nd ranked column. Hence, 80 units of goods is the maximum that can be allocated in this cell. therefore, showroom D3, 2nd ranked column is completely exhausted and is deleted. Finally, since only one cost cell is remaining without allocation in showroom D1 factory 3 with an unsatisfied demand and supply. Therefore, 20 unit of goods is allocated in this cell to complete the allocation (table 6).
Table 6. Transportation table with selected 1st ranked rows and 1st ranked column
     
Table 7. Showing Transportation Table with complete allocation of goods
     
Example 2
A company has factories at F1, F2 ,,,,, F10 that supply products to warehouses at W1, W2 ,,,,,W10. The weekly capacities of the factories are 500, 300, 700, 250, 750, 400, 500, 100, 150 and 150 units respectively. The weekly warehouse requirements are 1000, 500, 200, 300, 300, 600, 100, 200, 400 and 200 units respectively. The units shipping costs (in $) are as follows.
Table 8. Data of example 2
     
Solution:
Table 9. Initial Transportation Problem Results showing equality in demand and supply
     
The allocation of all goods for example 2 is shown in Table 10 using the proposed method step by step.
Table 10. Results Table in higher mean value ranks
Example 3
A product is manufactured at five factories A, B, C, D, and E. Their unit production cost is $2, $4, $3, $1 and $2, respectively. Their production capacities are 200, 300, 200, 400 and 400 units respectively. These factories supply the product to four stores, demand of which are 500, 600, 200 and 200 units respectively. Unit transportation cost in $ from each factory to each store is given as.
Table 11. Data of example 3
     
Solution:
Table 12. The new transportation costs that include both the production and the transportation costs
     
The new transportation table with its production cost is shown in table 13 below.
Table 13. A Modified balanced Transportation Problem
     
Table 14. Results in Descending Order of higher mean value of rank
     
Example 4: The table below provides all the necessary information on the availability of supply to each warehouse, the requirement of each market, and the unit transportation cost (in Naira) from warehouse to each market. Determine the best starting solution to the schedules.
Table 15. Transportation problem
     
Solution:
Table 16. Results Table in higher mean value of ranks
     
Example 5:
The University of Port Harcourt bottling company has factories at , and that supply product to warehouse at (Alakahia), (Rumuosi), (Choba) and (Alu). The weekly capacities of the factories are 22, 15 and 8 unit respectively. The weekly warehouse requirements are 7, 12, 17, and 9 units respectively. The unit shipping costs (in Naira) are as follows
Table 17. Transportation problem
     
Table 18. Results Table in higher mean value ranks
     

5. Presentation of Numerical Results for Optimization Methods

In the results, our calculated results are interpreted with results obtained by other existing methods.
Table 19. Summarizes the results for different examples, including the number of iterations and time taken to reach the optimum solution

6. Comparative Study and Analysis

Clearly, the Vogel Approximation Method, Least Cost Method and North West Corner Method are commonly used methods to find initial basic feasible solution in most of transportation problems in literatures available. Our proposed method, the mean descending order of ranking has been checked to solve transportation problems of different sizes and analysed based on the number of iterations from IBFS to optimality and time taken from formulation stage to optimal solution stage. It is seen from our results that the proposed method gives more efficient solution than other existing algorithms most times in terms of flexibilities, easy to handle and can be used to solve transportation problems of any size in few minutes.

7. Conclusions

A new algorithm has been discussed to solve transportation problems of any dimension. Efficiency and flexibilities of the developed algorithm is also been justified by solving numerical problems. During this process, a comparative study of the proposed method reveals distinct strength across different examples. For smaller datasets, methods like the least cost method and the Vogel’s Approximation method are effective, achieving low initial basic feasible solution and requiring few iterations. However, as the problem size increases, the North West Corner Method tends to perform poorly in both cost and time efficiency. The Mean Descending Order of Ranking method shows promise for achieving optimal solutions quickly. Ultimately, the choice of method should be guided the specific context of the problem, including the size of dataset, the importance of minimizing costs, and the need for timely solutions. For practical applications, a hybrid approach that leverages the strengths of multiple methods may yield the best results required.

References

[1]  Ahmed, M. M., Khan, A. R., Uddin, M. S. and Ahmed, F. (2016), ‘A new approach to solve transportation problems’, Open Journal of Optimization, Vol. 5, No. 1, pp. 22-30.
[2]  Azad, S. M. A. K., Hossain, M. B., Rahman M. M. (2017) ‘An algorithmic approach to solve transportation problems with the average total opportunity cost method’, International Journal of Scientific and Research Publications, Vol. 7, No. 2, pp. 266-270.
[3]  Azad, S. M. A. K., Hossain, M. B. (2017), ‘A new method for solving transportation problems considering average penalty’, IOSR Journal of Mathematics, Vol.13, No 1, pp. 40-43.
[4]  Hakim, M. A. (2012), ‘An alternative method to find initial basic feasible solution of a transportation problem’, Annals of Pure and Applied Mathematics, Vol. 1, No. 2, pp. 203- 209.
[5]  Hosseini, E. (2017) ‘Three new methods to find initial basic feasible solution of transportation problems’, Applied Mathematical Sciences, Vol. 11, No. 37, pp. 1803 – 1814.
[6]  Khan, A. R. (2011), ‘A re-solution of the transportation problem: an algorithmic approach’, Jahangirnagar University Journal of Science, Vol. 34, No. 2, pp. 49-62.
[7]  Gupta P.K and Man Mohan, Problems in Operation Research, Sultan Chand & Sons, New Delhi, 2003.
[8]  Raigar, S. and Modi, D. G. (2017), ‘An effective methodology for solving transportation problem’, International Journal of Scientific and Innovative Mathematical Research (IJSIMR), Vol. 5, No. 10, pp. 23-27.
[9]  Soomro, A. S. Tularam, G. A. & Bhayo, G. M. (2014). A comparative study of initial basic feasible solution methods for transportation problem, mathematical theory and modelling, 2224 – 5804.
[10]  Pandian, P. & Natarajan, G. (2010). A New Approach for Solving Transportation Problems with Mixed Constraints. Journal of physical sciences, 53 – 61.
[11]  Nagoor, A., Abbasin, A. (2014). New average method for solving intuitionistic fuzzy transportation problem. International Journal of pure and Applied Mathematics. 93(4). 491- 499.
[12]  Sourav Paul (2019). A New Proposition to Compute an Initial Basic Feasible Solution of Transportation. Proceedings of the 5th International Conference on Engineering Research, Innovation and Education ICERIE 2019, 25-27 January, Sylhet, Bangladesh.
[13]  Taha, H. Operations Research-Introduction, Prentice Hall of India, New Delhi, 2004.
[14]  F.L. Hitchcock, The distribution of a product from several sources to numerous locations, Journal of Mathematics and Physics 20, 224-230, (1941).
[15]  Koopmans, T.C., Optimum utilization of the transportation system, In Proceedings of the International Statistical Conference, Washington, DC, (1947).
[16]  Dantzig, G.B., Application of the simplex method to a transportation problem, In Activity Analysis of Production and Allocation, (Edited by T.C. Koopmans), John Wiley & Sons, New York, (1951).
[17]  Reinfeld N.V., and W.R. Vogel, Mathematical Programming, Prentice-Hall, New Jersey, (1958).
[18]  Houthakker, H.S., On the numerical solution of the transportation problem, Operations Research 3, 210-214, (1955). 7. E. J. Russell, Extension of Dantzig’s algorithm to finding an initial near-optimal basis for the transportation problem, Operations Research 17, 187-191, (1969).