Advanced Vogel’s Approximation Method (AVAM): A New Approach to Determine Penalty Cost for Better Feasible Solution of Transportation Problem

Advanced Vogel’s Approximation Method (AVAM): A New Approach to Determine Penalty Cost for Better Feasible Solution of Transportation Problem

Utpal Kanti Das Department of Computer Science & Engineering, IUBAT-

International University of Business Agriculture and Technology, Uttara, Dhaka-1230, Bangladesh,

Md. Ashraful Babu Department of Mathematics, IUBAT-

International University of Business Agriculture and Technology, Uttara, Dhaka-1230, Bangladesh,

Aminur Rahman Khan Department of Mathematics, Jahangirnagar

University, Savar, Dhaka-1342, Bangladesh,

Dr.Md. Sharif Uddin Department of Mathematics, Jahangirnagar University, Savar, Dhaka-1342, Bangladesh,

Abstract

In Operation Research, obtaining significant result for Transportation Problems is very important now-a-days. Vogels Approximation Method (VAM) is the very efficient algorithm to solve the transportation problem for feasible solution which is nearer to optimal solution. In this paper we identified a computational error in VAM and approach a logical development of VAM algorithm. The main concept of VAM is to determine penalty cost which obtains from the difference of smallest and next to smallest cost in each row or column and make maximum allocation in lowest

of Linear Programming Problem (LPP) where Vogels Approximation Method (VAM) is known as efficient method to solve TP. The concept penalty cost (difference of smallest and next to smallest cost in row or column) makes this method more effective more than other methods such as North West Corner Rule (NWC), Least Cost Method (LCM) etc. But the way of determining penalty cost is not logical for some cases; we discuss this types of situation in [-,-] and developed an algorithm with new concept where difficulties are resolved in [-,-] and gives the feasible solution very close to optimal solution lower than VAM.

Consider a Transportation Problem with m sources

cost cell of that row or column which have largest

and n destinations where Cij is the unit transportation

penalty. The difficulty arises when smallest cost and next to smallest cost have same magnitude. In that case

cost from ith source to jth destination. Let

Si be the

we find a very logical concept to resolve this and developed a new algorithm Advanced Vogels Approximation Method (AVAM) to find a feasible

supply amount of ith source and D be the demand

j

amount of jth destination. We have to find the

solution of transportation problem which is very close

transported amount of commodity

xij

so that total

to optimal solution more than VAM.

Keyword: AVAM, VAM, Penalty Cost, Feasible Solution, Error Estimation, Transportation Problem (TP).

1. Introduction

   Transportation problem is real life problem where commodities are transferred from factories to retail house so that total transportation cost should be minimized. In Operation research, TP is a special class

   transportation cost will be minimized. The above problem in LPP model can be express as follows:

   Minimize:

   m n

   Total cost Cij xij

   i1 j 1

   Subject to:

   n

   xij Si

   m

   j 1

   xij Dj i1

   xij 0

   for i 1, 2,……m (Supply constrains) for j 1, 2,……n (Demand constrains)

   i, j

   Step-3:

   1. Identify the row and column with the largest penalty, breaking ties arbitrarily. Allocate as much as possible to the variable with the least cost in the selected row or column. Adjust the supply and demand and cross out the satisfied row or column. If a row and column are satisfies simultaneously, only one of them is crossed out and remaining row or column is

      We have to convert this LPP in the following mathematical Model and applying transportation methods to find feasible solution.

      assigned a zero supply or demand.

   2. If two or more penalty costs have same largest magnitude, then select any one of them (or select most top row or extreme left column).

      Source	Destination					Supply
      	D1	D2	D3		Dn
      S1	C11	C12	C13		C1n	S1
      S2	C21	C22	C23		C2n	S2
      Sm	Cm1	Cm2	Cm3		Cmn	Sm
      Demand	D1	D2	D3		Dn

2. Existing Algorithm: Vogels Approximation Method (VAM)

   The Vogel Approximation method is an iterative procedure for computing a basic feasible solution of a transportation problem. This method is preferred over the two methods i.e. North West Corner Rule and Least cost Method. The algorithm of VAM is given below: Step-1:

   1. Identify the cells having minimum and next to minimum transportation cost in each row and write the difference (Penalty) along the side of the table against the corresponding row.

   2. Identify the cells having minimum and next to minimum transportation cost in each column and write the difference (Penalty) along the side of the table against the corresponding column.

      Step-2: If minimum cost appear in two or more times in a row or column then select these same cost as a minimum and next to minimum cost and penalty will be zero.

      Step-4:

      a. If exactly one row or one column with zero supply or demand remains uncrossed out, Stop.

      1. If only one row or column with positive supply or demand remains uncrossed out, determine the basic variables in the row or column by the Least-Cost Method.

      2. If all uncrossed out rows or column have (remaining) zero supply or demand, determined the zero basic variables by the Least-Cost Method. Stop.

      3. Otherwise, go to Step-1.

      2.1. Finding Computational Error of Vogels Approximation Method (VAM)

      The main concept of VAM algorithm is the penalty cost which is determined by the difference of smallest and next to smallest cost of each row and column where highest penalty indicate that one of the value of two minimum costs is too higher than another. For that case VAM select highest penalty cost and give allocation in lowest cost cell in that row or column for avoiding the probability of selecting higher cost in next iteration.

      If there are two or more cells have same smallest magnitude then VAM selects these same smallest cost as minimum and next to minimum cost and penalty will be zero [2. Step-2]. For that case penalty will be lowest in that row or column among all rows or columns so that there is no possibility to select that row or column for allocating commodities. If in that row or column have any higher cost other than same smallest costs then probability will be increased to select the higher cost in next iteration and total transportation cost may be increase.

      In VAM algorithm, allocations are depends on penalty cost. For this above computational error to determine penalty in VAM, lowest cost may not be ensure in all teration so that total cost in feasible solution has a chance to be higher.

3. Proposed Algorithm for Advanced Vogels Approximation Method (AVAM)

   Step-4:

   1. Select max(Pi , Pj ) . Set

      xij :Amount of

      In this section, we solved the computational error of VAM which discussed in above and proposed a new

      commodity from ith

      source

      jth to destination;

      algorithm named Advanced Vogels Approximation Method (AVAM). In our proposed algorithm (AVAM), when smallest cost appear in two or more

      Select lowest cost of that row or column

      which has largest penalty and allocate maximum possible amount

      times in a row or column then penalty determined by

      xij

      i.e. min(Si , Dj ) . If the lowest cost

      difference of two minimum cost taken one of them as a minimum and following smallest cost other than equal smallest costs as a next to minimum. As an example, if 3, 10, 3, 7, 9 are the costs of a row or column then select 3 as a smallest cost and select 7 as a next to smallest cost instead of 3 again and penalty will be 4. In that case penalty is not zero and if this penalty has the largest magnitude then probability of the chance of taking larger cost in next iteration will be decreased because of at least one more smallest cost remains. The algorithm of AVAM is given follows:

      i

      Step-1: Set S : Supply amount of the ith source;

      j

      Set D : Demand amount of the jth

      destination;

      appear in two or more cells in that row or column then choose the extreme left or most top lowest cost cell.

   2. If two or more penalty costs have same largest magnitude, then select any one of them (or select most top row or extreme left column).

      Step-5: Adjust the supply and demand and cross out the satisfied row or column. If row and column are satisfied simultaneously then crossed out one of them and set zero supply or demand in remaining row or column.

      Step-6:

      1. If exactly one row or one column with zero supply or demand remains uncrossed out, Stop.

         Set

         Cij

         :Unit transportation cost of

         ith source

      2. If only one row or column with positive

         supply or demand remains uncrossed out,

         to jth destination;

         determine the basic variables in the row or

         Check: if Si 0 and Dj 0, then Stop.

         Step-2:

         column by the Least-Cost Method.

      3. If all uncrossed out rows or column have (remaining) zero supply or demand,

         1. f

            Si Dj or if

            Si Dj

            determined the zero basic variables by the

            i j i j

            then balance the transportation problem adding dummy demand or supply.

         2. Set Cij : 0 for all dummy rows or columns.

      Step-3:

      1. Identify the smallest and next to smallest cost of each row and column and calculate the difference between them which is called by penalty.

         Set Pi :Row penalty and Set Pj : Column penalty.

         Pi | Cih Cik | and Pj | Chj Ckj |

      2. If smallest cost appear two or more times in a row or column then select one of them as a smallest and following smaller cost other than equal smallest costs as a next to smallest cost.

      3. If there is no more cost other than equal

         Least-Cost Method. Stop.

      4. Otherwise go to Step-3.

4. Numerical Simulation

   Consider some special types of transportation problems where smallest cost is appear in two or more in rows or columns and solve them using Advanced Vogels Approximation Method (AVAM) and compare these results with the solution of Vogels Approximation Method (VAM).

   4.1. Example-1

   Source	Destination				Supply
   	D1	D2	D3	D4
   S1	6	8	10	9	50
   S2	5	8	11	5	75
   S3	6	9	12	5	25
   Demand	20	20	50	60

   Consider a Mathematical Model of a transportation problem in given below:

   smallest costs

   i.e.

   all costs are same then

   select smallest and next to smallest as same and penalty will be zero.

   Table-1.1

   Now solve this problem using AVAM and VAM respectively in below:

   Solution of Example-1 Using Advanced Vogels Approximation Method (AVAM):

   Source	Destination				Supply
   	D1	D2	D3	D4
   S1	6	8 0	10 50	9	50
   S2	5 15	8	11	5 60	75
   S3	6 5	9 20	12	5	25
   Demand	20	20	50	60

   Table-1.2 Total Transportation Cost:

   (0 8) (50 10) (15 5) (60 5) (5 6)

   (20 9) 1085

   Solution of Example-1 Using Vogels Approximation Method (VAM):

   Source	Destination				Supply
   	D1	D2	D3	D4
   S1	6 20	8	10 30	9	50
   S2	5	8 20	11 20	5 35	75
   S3	6	9	12	5 25	25
   Demand	20	20	50	60

   Table-1.3 Total Transportation Cost:

   (206) (3010) (208) (2011) (355) (255) 1100

   Optimal solution of Example-1:

   The optimal solution of Example-1 determined by MODI is 1060.

   1. Example-2

      Consider a Mathematical Model of a transportation problem in given below:

      Source	Destination					Supply
      	D1	D2	D3	D4	D5
      S1	4	4	9	8	13	100
      S2	7	9	8	10	4	80
      S3	9	3	7	10	6	70
      S4	11	4	8	3	9	90
      Demand	60	40	100	50	90

      Table-2.1

      Now solve this problem using AVAM and VAM respectively in below:

      td>

      4

      40

      Source	Destination					Supply
      	D1	D2	D3	D4	D5
      S1	4 60	9	8	13	100
      S2	7	9	8	10	4 80	80
      S3	9	3	7 60	10	6 10	70
      S4	11	4 0	8 40	3 50	9	90
      Demand	60	40	100	50	90

      Solution of Example-2 Using Advanced Vogels Approximation Method (AVAM):

      Table-2.2 Total Transportation Cost:

      (60 4) (40 4) (80 4) (60 7) (10 6)

      (0 4) (40 8) (50 3) 1670

      Solution of Example-2 Using Vogels Approximation Method (VAM):

      Source	Destination					Supply
      	D1	D2	D3	D4	D5
      S1	4 60	4 0	9 40	8	13	100
      S2	7	9	8	10	4 80	80
      S3	9	3	7 60	10	6 10	70
      S4	11	4 40	8	3 50	9	90
      Demand	60	40	100	50	90

      Table-2.3

      Total Transportation Cost:

      (60 4) (0 4) (40 9) (80 4) (60 7)

      (10 6) (40 4) (50 3) 1710

      Optimal solution of Example-2:

      The optimal solution of Example-1 determined by MODI is 1670.

   2. Example-3:

   Consider a Mathematical Model of a transportation problem in given below:

   Source	Destination						Supply
   	D1	D2	D3	D4	D5
   S1	8	8	2	10	2	40
   S2	11	4	10	9	4	70
   S3	5	2	2	11	10	35
   S4	10	6	6	5	2	90
   S5	8	11	8	6	4	85
   Demand	80	55	60	80	45

   Table:3.1

   Solution of Example-3 Using Advanced Vogels Approximation Method (AVAM):

   Source	Destination					Supply
   	D1	D2	D3	D4	D5
   S1	8	8	2 40	10	2	40
   S2	11	4 55	10	9	4 15	70
   S3	5 15	2	2 20	11	10	35
   S4	10	6	6	5 60	2 30	90
   S5	8 65	11	8	6 20	4	85
   Demand	80	55	60	80	45

   Table:3.2 Total Transportation Cost:

   (2 40) (4 55) (4 15) (5 15) (2 20)

   (5 60) (2 30) (8 65) (6 20) 1475

   Solution of Example-3 Using Vogels Approximation Method (AVAM):

   Source	Destination						Supply
   	D1	D2	D3	D4	D5
   S1	8	8	2 40	10	2	40
   S2	11	4 55	10	9 15	4	70
   S3	5 15	2	2 20	11	10	35
   S4	10	6	6	5 45	2 45	90
   S5	8 65	11	8	6 20	4	85
   Demand	80	55	60	80	45

   Table:3.3 Total Transportation Cost:

   (2 40) (4 55) (9 15) (515) (2 20)

   (5 45) (2 45) (8 65) (6 20) 1505

   Optimal solution of Example-3:

   The optimal solution of Example-1 determined by MODI is 1475.

5. Result Analysis:

   We observed in above examples that Advanced Vogels Approximation Method (AVAM) gives the lower feasible solution other than Vogels Approximation Method (VAM). Results using AVAM are very close to or equal to optimal solution. The comparison table of AVAM and VAM result are follows:

   Methods	Transportation Problems
   	Optimal Solution	AVAM	VAM
   Example-1	1060	1085	1100
   Example-2	1670	1670	1710
   Example-3	1475	1475	1505

   Table: 5

6. Conclusion

   In this paper we fixed the computational error of Vogels Approximation Method (VAM) and proposed a new algorithm named Advanced Vogels Approximation Method (AVAM). From the above examples it is shown that AVAM gives the lower feasible solution than VAM and it is very close to optimal solution or equal to optimal solution.

7. References

1. Hamdy A. Taha. Operation Research: An Introduction,

   Eighth Edition, ISBN-13: 978-0132555937

2. P. Rama Murthy. Operation Research, Second Edition,

   ISBN (13): 978-81-224-2944-2

3. TORA Optimizing System Software developed by Hamdy A Taha.

4. Hillier, F. S. and G. J. Lieberman. 1995. Introduction to Operations Research, 6th ed. New York: McGraw-Hill, Inc.

5. Md. Amirul Islam, Aminur Rahman Khan, M. Sharif Uddin and M. Abdul Malek Determination of Basic Feasible Solution of Transportation Problem: A New Aproach Jahangirnagar University Journal of Science, Vol. 35, No. 1, pp. 101 108, ISSN 1022-8594 (2012).

6. Aminur Rahman Khan A Re-solution of the Transportation Problem: An Algorithmic Approach Jahangirnagar University Journal of Science, Vol. 34, No. 2, pp. 49-62 ISSN 1022-8594 (2011).