American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) ISSN (Print) 2313-4410, ISSN (Online) 2313-4402 © Global Society of Scientific Research and Researchers http://asrjetsjournal.org/ A Modified Vogel Approximation Method for Solving Balanced Transportation Problems Stephen Akpana*, Thomas Ugbeb , John Usenc, Ofem Ajahd aDepartment of Statistics, University of Calabar, Cross-River State, Nigeria. bDepartment of Statistics, University of Calabar, Cross-River State, Nigeria. cDepartment of Statistics, University of Calabar, Cross-River State, Nigeria. dDepartment of Computer Science, University of Calabar, Cross-River State, Nigeria. Abstract A modified Vogel Approximation Method is proposed and compared with those of the existing methods available for solving balanced transportation problems (in linear programming) for Basic Feasible Solutions (IBFS). The method is shown to be better than existing ones (excluding Vogel Approximation Method) since it does not only considers each unit cost in its solution algorithm, but also minimises total cost (comparatively) just like Vogel Approximation Method. Keywords: Balanced Transportation Problem; Modified Vogel Approximation Method; Vogel Approximation Method; Standard Deviation of Costs. 1. Introduction The problem of physical distribution (transportation) of goods and services from several supply origins to several demand destinations is one important application of linear programming,[1]. To express a transportation problem in terms of a linear programming model, which can be solved by the method of Simplex, is quite easy [1]. But because a transportation problem usually involves a large number of variables and constraints, solving it with the Simplex method is often time-consuming. However, instead of using the regular simplex tableau, advantage is taken of the special structure of the transportation model to present the algorithm in a more convenient form [2,1]. ------------------------------------------------------------------ * Corresponding author. 289 http://asrjetsjournal.org/ American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2015) Volume 14, No 3, pp 289-302 Transportation algorithms such as the “Stepping Stone Method” and the MODI (Modified Distribution) Method have been developed for this purpose [1]. The structure of transportation problem involves a large number of shipping routes from several supply origins to several demand destinations [3]. The objective is to determine the number of units of an item (commodity or product) that should be shipped from an origin to a destination in order to satisfy the required quantity of goods or services at each destination centre. This should be done within the limited quantity of goods or services available at each supply origin, at the minimum transportation cost and/or time [4,1,5]. There are various types of transportation models and the simplest of them was first presented in 1941. It was further developed in 1949 and in 1951. Thereafter, several extensions of transportation models and methods have been subsequently developed. The general problem is represented by the network below. Figure 1: Network for a General Transportation Problem There are m sources and n destinations, each represented by a “node”. The “arcs” linking the sources and destinations represent the routes between the sources and the destinations. Arcs ( )ji, joining source i to destination j carries two pieces of information: (1) the transportation cost per unit - ijc , and (2) the amount shipped - ijx . The amount of supply at source i is - ia and the amount of demand at destination j is - jb , [2,6,7]. The objective of the model is to determine the unknowns ijx that will minimize the total transportation cost while satisfying all the supply and demand restrictions [8,2,1]. Mathematically, the problem, in general, may be stated as follows: 2b nb 1b ma 2a 1a 2 2 1 1 m n 1111 : xc mnmn xc : 290 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2015) Volume 14, No 3, pp 289-302 jix njDx miSxts xCCMin ij j m i ij i n j ij m i n j ijij ,,0 ,,3,2,1 ,,3,2,1:. 1 1 1 1 ∀≥ == == = ∑ ∑ ∑∑ = = = =   Where; origin iSupply at Si = n jdestinatioDemand at D j = tion jto destina rigin i ped from ounits shipNumber of xij = tg al shippinis the totxCC m i ij n j ij cos 1 1 ∑∑ = = = and ( )conditionsrimsolutionfeasibleofexistencetheforconditionDS m i n j ji −=∑ ∑ = =1 1 A balanced transportation problem having m - origins and n - destinations is usually represented in tabular form as shown below [1,9]. Table 1: Transportation Problem Destination Origin 1 2 3 . . . N S 1 C11 C11 C11 . . . C11 S1 2 C21 C11 C11 . . . C11 S2 3 C31 C32 C11 . . . C11 S3 . . . . . . . . . . . . . . . . . . . . . . . . . . . M Cm1 C11 C11 . . . Cnm Sm Dj D1 D2 D3 . . . Dn The balanced transportation problem is indeed a linear programming problem. But due to its special structure and intricacies, simple special algorithms have been developed for solving it. These existing methods are basically for finding the initial basic feasible solution and the optimal basic feasible solution to any given 291 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2015) Volume 14, No 3, pp 289-302 balanced transportation problem [9,1]. They are: Northwest-corner, Least-cost and Vogel Approximation methods. 2. The Algorithms for Existing Methods The following are the algorithms for the existing methods in their order of efficiency in terms of minimization of total cost, usage of the given unit costs in the solution steps, and approximation of the optimal solution for any given tractable balanced transportation problem. However we remark that this paper would only be restricted to making comparison of the techniques using their abilities of minimizing total costs. Northwest-corner Method [2,1]: Step 1: Assign the maximum possible number of units to the cell at the Northwest corner. That is, cell - ( )1,1 . Hence, ( )1111 ,min DSx = Step 2: If there is any remaining unit in row one, set - 111 Dx = , 11 DS = and move to cell - ( )2,1 . But if 111 Sx = then set 111 SDD −= and move to the next cell. Step 3: Repeat step 2 until the bottom right corner cell is reached at which point, all the quantity of units available have been exhausted while all the demands have been satisfied. Least-cost Method [2,1]: Step 1: Identify the least cost cell/route and assign the maximum possible number of units to it. Step 2: Delete the row or column having exhausted supply at that origin or having satisfied demand at that destination respectively. Step 3: If the supply at every origin is exhausted and the demand at every destination satisfied, then stop. Otherwise return to step one. Vogel Approximation Method [5]: Step 1: Identify two lowest costs in each row and column. Find the row difference and column difference. Step 2: Identify the row or column with the greatest cost difference and assign the maximum possible number of units to the least cost route in that row or column. Step 3: If the assignment in step two satisfies the demand at that destination then delete the corresponding column. Otherwise delete the corresponding row when it exhausts the supply at the origin. Step 4: If every supply is exhausted and every demand satisfied stop. Otherwise, return to step one. 3. Application of the Existing Method Case Study: 292 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2015) Volume 14, No 3, pp 289-302 Table one is a display of a balanced transportation problem. Find the initial basic feasible solution and optimal solution using: Northwest-corner Method, Least-cost Method and Vogel Approximation Method. Table 2: Case Study Destination Origin 1 2 3 4 Si 1 8 6 10 9 35 2 9 12 13 7 50 3 14 9 16 5 40 Dj 45 20 30 30 Using the Northwest-corner Method to solve the above problem we have the following initial basic feasible solution below. 3511 =x , 1021 =x 2022 =x 2023 =x 1033 =x 3034 =x With this initial basic feasible solution we calculate the total cost - C . That is, 343433332323222221211111 cxcxcxcxcxcxC +++++= ( ) ( ) ( ) ( ) ( ) ( )530161013201220910835 ×+×+×+×+×+×=⇒ C 1180=⇒ C Using the Least-cost Method to solve the above problem we have the following initial basic feasible solution below. 1512 =x , 293 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2015) Volume 14, No 3, pp 289-302 2013 =x 3021 =x 2023 =x Table 3: Northwest-corner Method Destination Origi n 1 2 3 4 Si Stag1 Stag2 Stag3 Stag4 Stag5 Stag6 1 8 6 10 9 35 35/35 =0 0 0 0 0 0 2 9 12 13 7 50 50 50/10= 40 40/20= 20 20/20 =0 0 0 3 14 9 16 5 40 40 40 40 40 40/10= 30 30/30 =0 Di 45 20 30 30 12 5 Stag 1 45/35= 10 20 30 30 90 Stag 2 10/10= 0 20 30 30 80 Stag 3 0 20/20 =0 30 30 60 Stag 4 0 0 30/20= 10 30 40 Stag 5 0 0 10/10= 0 30 30 Stag 6 0 0 0 30/30 =0 0 1032 =x 3034 =x With this initial basic feasible solution we calculate the total cost - C . That is, 294 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2015) Volume 14, No 3, pp 289-302 343432322323232313131212 cxcxcxcxcxcxC +++++= ( ) ( ) ( ) ( ) ( ) ( )53016101320930620815 ×+×+×+×+×+×=⇒ C 1080=⇒ C Table 4: Least-cost Method Destination Origi n 1 2 3 4 Si Stag1 Stag2 Stag3 Stag4 Stag5 Stag6 1 8 6 10 9 35 35 35/20= 15 15/15 =0 0 0 0 2 9 12 13 7 50 50 50 50 50/30= 20 20/20 =0 0 3 14 9 16 5 40 40/30= 10 10 10 10 10 10/10 =0 Di 45 20 30 30 12 5 Stag 1 45 20 30 30/30 =0 95 Stag 2 45 20/20 =0 30 0 75 Stag 3 45/15= 30 0 30 0 60 Stag 4 30/30= 0 0 30 0 30 Stag 5 0 0 30/20= 10 0 10 Stag 6 0/ 0 10/10 0 0 Table 5: Key for the Least-cost Method Order of Deletion Name of Colour Colour Description First – Fourth column Red Second – Second column Yellow Third – Cells (1, 1) & (1, 3) Green 295 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2015) Volume 14, No 3, pp 289-302 Fourth – Cells (2, 1) & (3, 1) Deep Blue Fifth – Cell (2, 3) Blue Sixth – Cell (3, 3) White Using Vogel Approximation Method to solve the above problem we have the following initial basic feasible solution below. 1012 =x , 2513 =x 4521 =x 523 =x 1032 =x 3034 =x With this initial basic feasible solution we calculate the total cost - C . That is, 343432322323212113131212 cxcxcxcxcxcxC +++++= ( ) ( ) ( ) ( ) ( ) ( )5309101359451025610 ×+×+×+×+×+×=⇒ C 1020=⇒ C 4. Modified Vogel Approximation Method This method is developed as follows. Rather than using the idea of identifying two lowest costs as we have it in the algorithm of the existing Vogel Approximation Method, we make use of the idea of “standard deviation of row/column costs”. Table 6: Vogel Approximation Method Destination St1 St2 St3 St4 St5 Ori gin 1 2 3 4 Si Rd 1 1 Rd2 2 Rd3 3 Rd4 4 R d5 5 1 8 6 10 9 3 5 8/6 =2 35 8/6 =2 35 8/6 =2 35/10 =25 10/ 8=2 25 10 25 2 9 12 13 7 5 9/7 50 12/ 50 12/ 50 13/ 50/4 13 5/5 296 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2015) Volume 14, No 3, pp 289-302 0 =2 9=3 9=3 9=4 5=5 =0 3 14 9 16 5 4 0 9/5 =4 40/30 =10 14/ 9=5 10/1 0=0 - 0 - 0 - 0 Di 45 20 30 30 1 2 5 Cd 1 9/8= 1 9/6=3 13/1 0=3 7/5= 2 1 45 20 30 30/3 0=0 95 Cd 2 9/8= 1 9/6=3 13/1 0=3 - 2 45 20/10 =10 30 0 85 Cd 3 9/8= 1 12/6= 6 13/1 0=3 - 3 45 10/10 =0 30 0 75 Cd 4 9/8= 1 - 13/1 0=3 - 4 45/4 5=0 0 30 0 30 Cd 5 - - 13/1 0=3 - 5 0 0 30/5 =25 0 25 Cd 6 - - 10 - 6 0 0 25/2 5=0 0 St6 Rd6 6 10 25/25=0 - 0 - 0 297 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2015) Volume 14, No 3, pp 289-302 0 Table 7: Key for the Vogel Approximation Method Order of Deletion Name of Colour Colour Description First – Fourth column Red Second – Cells (3, 1), (3,2) & (3, 3) Yellow Third – Cells (1, 2) & (2, 2) Green Fourth – Cells (1, 1) & (2, 1) Deep Blue Fifth – Cell (2, 3) Sky Blue Sixth – Cell (1, 3) White Step 1: Find the row and column costs-standard deviations. Step 2: Identify the row or column with the greatest costs-standard deviation and assign the maximum possible number of units to the least cost route in that row or column. Step 3: If the assignment in step two satisfies the demand at that destination then delete the corresponding column. Otherwise delete the corresponding row when it exhausts the supply at the origin. Step 4: If every supply is exhausted and every demand satisfied, stop. Otherwise return to step one. Using this algorithm to solve the same selected balanced transportation problem of section three gives: 1012 =x , 2513 =x 4521 =x 523 =x 298 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2015) Volume 14, No 3, pp 289-302 1032 =x 3034 =x With this initial basic feasible solution we calculate the total cost - C . That is, 343432322323212113131212 cxcxcxcxcxcxC +++++= ( ) ( ) ( ) ( ) ( ) ( )5309101359451025610 ×+×+×+×+×+×=⇒ C 1020=⇒ C Table 8: Modified Vogel Approximation Method Destination St1 St2 St3 St4 St5 Ori gin 1 2 3 4 Si RS D1 1 RS D2 2 RS D3 3 RS D4 4 RS D5 5 1 8 6 10 9 3 5 1.5 35 1.6 35 1.6 35 2.0 35/10 =25 0.0 25/2 5=0 2 9 12 13 7 5 0 2.3 50 1.7 50 1.7 50/4 5=5 0.5 5 0.0 5 3 14 9 16 5 4 0 4.3 40/30 =10 2.9 10/1 0=0 0.0 - 0.0 - 0.0 - Di 45 20 30 30 1 2 5 CS D1 2.6 2.4 2.4 1.0 1 45 20 30 30/3 0=0 95 CS D2 2.6 2.4 2.4 0.0 2 45 20/10 =10 30 - 85 CS D3 0.5 3.0 1.5 0.0 3 45/4 5=0 10 30 - 40 CS D4 0.0 3.0 1.5 0.0 4 - 10/10 30 - 30 299 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2015) Volume 14, No 3, pp 289-302 =0 CS D5 0.0 0.0 1.5 0.0 5 - - 30/2 5=5 - 5 CS D6 0.0 0.0 0.0 0.0 6 - - 5/5= 0 - RSD6 6 0.0 - 0.0 5/5=0 0.0 - Table 9: Key for Modified Vogel Approximation Method Order of Deletion Name of Colour Colour Description First – Fourth column Red Second – Cells (3, 1), (3,2) & (3, 3) Yellow Third – Cells (1, 1) & (2, 1) Green Fourth – Cells (1, 2) & (2, 2) Deep Blue Fifth – Cell (1, 3) Blue Sixth – Cell (1,4) White 300 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2015) Volume 14, No 3, pp 289-302 The table below gives a comparison of the existing methods and the proposed Modified Vogel Approximation Method in terms of minimization of total cost. Table 10: Comparison of Methods Method IBF Solution 1 Northwest-corner 1180 2 Least-cost 1080 3 Vogel Approximation 1020 4 Modified Vogel Approximation 1020 5. Conclusion The concept of balanced transportation problems and the existing methods available for solving this type of linear programming problem in their order of efficiency has been examined. Our paper proposes a Modified Vogel Approximation Method - which is so far the best available method for solving balanced transportation problems. We have used our modification as well as other existing methods in solving a selected balanced transportation problem; and have compared the efficiency of all the methods at reducing the total cost using the same selected problem. Following the above, it is evident that the modified method is of better status than its predecessors (except Vogel Approximation Method which has the same IBF solution) in terms of reducing total cost. References [1] J. K. Sharma. Transportation Problem: Operations Research – Theory and Applications, Macmillan Publishers India Limited: Delhi, 2009, pp. 259-312. [2] H. A. Taha. Transportation Problem: Operations Research – Theory and Applications, Prentice-Hall International, Inc: USA 1997,pp. 165-185. [3] T. Pawan, P. Bhagivah, and H. S. Dhami. “Development of an Algorithm for all Types of Transportation Problems.” International Journal of Computer Applications,Vol. 30, No. 6, pp. 24 – 30, 2011. [4] H. Denis, G. K. Leo, M. L. Ramon and J. C. M. Vromans. “Operations Research in Passenger Railway Transportation.” Econometric Institute Report E12005 – 16, 2002. [5] D. Bijulal. (2013). “Transportation Problem: MBA 202 – Operations Research. College of Engineering” 301 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2015) Volume 14, No 3, pp 289-302 Trivaddium. (http://kbase.cet.ac.in/el/cet/pluginfile.php/...) [6] J. Y. Wang. “The Transportation and Assignment Problems” in Operations Research, College of Management, NCTU,2008, [7] S. Gaurav, S. H. Abbas, and V. J. Gupta. “Solving Transportation Problem with the Various Method.” Asian Journal of Current Engineering and Maths Vol. 1, No. 3, pp. 81 – 83, 2012. [8] D. Klingman and R. Russell. “The Transportation Problem with Mixed Constraints.” Journal of Operational Research Society. Vol. 25, pp. 447-455, 1974. http://www.palgrave-journals.com) [9] J. Reeb and S. Leavengood. “Transportation Problem – A Special Case Linear Programming Problems.”Operations Research. Performance Excellence in the Wood Products Industry, 2002. 302 http://kbase.cet.ac.in/el/cet/pluginfile.php/ http://www.palgrave-journals.com/