Transportation and Assignment problems Methods & techniques: North West Corner, Least Cost, Vogel’s Approximation Method – Operations Research

Transportation and Assignment problems Methods & Techniques are a type of optimization problem – North West Corner (NWC), Least Cost Method (LCM), Vogel’s Approximation Method (VAM) – Operations Research that involves assigning a set of resources to a set of tasks in the most efficient way possible. Operations research techniques are commonly used to solve assignment problems. Here are some of the most common methods and techniques used in solving assignment problems in operations research:

1. Hungarian algorithm: The Hungarian algorithm is a method for solving assignment problems that involves finding the optimal assignment between resources and tasks in a bipartite graph. It has a time complexity of O(n^3) and is commonly used for small to medium-sized problems.
2. Linear programming: Linear programming is a mathematical technique used to optimize a linear objective function subject to a set of linear constraints. It can be used to solve various types of optimization problems, including assignment problems. The simplex method is a commonly used algorithm for solving linear programming problems.
3. Branch and bound: Branch and bound is a general algorithmic technique for solving combinatorial optimization problems. It involves recursively partitioning the search space into smaller subproblems and bounding the solutions to each subproblem in order to eliminate infeasible solutions.
4. Auction algorithm: The auction algorithm is a method for solving assignment problems that involves simulating an auction process in which resources bid for tasks. It has been shown to have good performance for large-scale problems.
5. Genetic algorithms: Genetic algorithms are a type of evolutionary algorithm that involve mimicking the process of natural selection to find optimal solutions to problems. They have been shown to be effective for solving assignment problems with large solution spaces.
6. Simulated annealing: Simulated annealing is a stochastic optimization technique that involves gradually cooling a system from a high temperature to a low temperature in order to find the global minimum of an objective function. It has been applied to various types of optimization problems, including assignment problems.

Overall, there are many methods and techniques available for solving assignment problems in operations research. The choice of method depends on the size and complexity of the problem, as well as the specific requirements of the application.

Operations Research eBook

Types of Transportation Problems in Operational Research

1. Balanced Transportation Problem
2. Unbalanced Transportation Problem

Details about balanced and unbalanced transportation problem you find in attached pdf notes at end of this article.

Solution of the transportation problems

Stage I: Finding an initial basic feasible solution.

Stage II: Checking for optimality

Existence of Feasible Solution: A necessary and sufficient condition for the existence of a feasible solution to the general transportation problem is that

Total supply = Total demand

Existence of Basic Feasible Solution: The number of basic variables of the general transportation problem at any stage of feasible solution must be (m + n – 1). Now degenerate basic feasible solution (a feasible solution) involving exactly (m + n – 1) positive variables is known as non-degenerate basic feasible solution otherwise it is said to be degenerate basic feasible. These allocations should be independent positions in case of non-degenerate basic feasible solutions.

KEY POINTS

• Optimum Solution: A feasible solution is said to be optimal, if it minimizes the total transportation cost.
• Unbalance TP If total supply is not equal to total demand, then it balance with dummy source or destination.

Finding an Initial Basic Feasible Solutions

There are three transportation and assignment problems methods and techniques as given below

1. Northwest corner method
2. Least cost method
3. Vogel’s approximation method (or Penalty method)

Steps for North-West Corner Method (NWM)

1. Allocate the maximum amount allowable by the supply and demand constraints to the variable x11 (i.e. the cell in the top left corner of the transportation tableau).
2. If a column (or row) is satisfied, cross it out. The remaining decision variables in that column (or row) are non-basic and are set equal to zero. If a row and column are satisfied simultaneously, cross only one out (it does not matter which).
3. Adjust supply and demand for the non-crossed out rows and columns.
4. Allocate the maximum feasible amount to the first available non-crossed out element in the next column (or row).
5. When exactly one row or column is left, all the remaining variables are basic and are assigned the only feasible allocation.

Steps for Least Cost Method (LCM)

1. Assign as much as possible to the cell with the smallest unit cost in the entire tableau. If there is a tie then choose arbitrarily.
2. Cross out the row or column which has satisfied supply or demand. If a row and column are both satisfied then cross out only one of them.
3. Adjust the supply and demand for those rows and columns which are not crossed out.
4. When exactly one row or column is left, all the remaining variables are basic and are assigned the only feasible allocation.

Steps for Vogel’s Approximation Method (VAM)

1. Determine a penalty cost for each row (column) by subtracting the lowest unit cell cost in the row (column) from the next lowest unit cell cost in the same row (column).
2. Identify the row or column with the greatest penalty cost. Break the ties arbitrarily (if there are any). Allocate as much as possible to the variable with the lowest unit cost in the selected row or column. Adjust the supply and demand and cross out the row or column that is already satisfied. If a row and column are satisfied simultaneously, only cross out one of the two and allocate a supply or demand of zero to the one that remains.

• If there is exactly one row or column left with a supply or demand of zero, stop.
• If there is one row (column) left with a positive supply (demand), determine the basic variables in the row (column) using the Minimum Cell Cost Method. Stop.
• If all of the rows and columns that were not crossed out have zero supply and demand (remaining), determine the basic zero variables using the Minimum Cell Cost Method. Stop.
• In any other case, continue with Step 1.

transportation and assignment problems methods and techniques

Transportation Problem vs. Assignment Problem

Transportation Problem	Assignment Problem
It is used to optimize the transportation cost.	It is about assigning finite source to finite destination (one source is alloted to one destination).
Number of Source and demand may or may not be equal.	Number of source and number of destination must be equal.
If demand and supply are not equal, then transportation problem is known as Unbalanced Transportation Problem.	If number of rows and number of columns are not equal, then the assignment problem is known as Unbalanced Assignment Problem.
It requires to step to solve: Find Initial Solution using North West, Least Cost or Vogel Approximation Find Optimal Solution using MODI method.	It requires only one step to solve. Hungarian Method is sufficient to find the optimal solutions

Transportation and assignment problems methods and techniques

Transportation and assignment problems methods and techniques

A. North West Corner Method (NWC)

The following are the example of North West Corner Method – Operations Research Assignment Problems

Example: Determine an initial basic feasible solution to the following transportation problem.

B. Least Cost Method (LCM)

The following are the example of Least Cost Method (LCM) – Operations Research Assignment Problems

Example: Determine an initial basic feasible solution to the following transportation problem.

B. Vogel’s Approximation Method (VAM)

The following are the example of Vogel’s Approximation Method (VAM) – Operations Research Assignment Problems

 

Comparison between the three methods

Northwest corner method (NCM) is used when the purpose of completing demand and then the next and is used when the purpose of completing the supply and then the next. Advantage of northwest corner method is quick solution because computations take short time but yields a bad solution because it is very far from optimal solution.

Vogel’s approximation method (VAM) and Least cost method are used to obtain the shortest route. Advantage of Vogel’s approximation method and Least cost method (LCM) yields the best starting basic solution because gives initial solution near to optimal solution but the solution of Vogel’s approximation methods is slow because computations take long time. The cost of transportation with Vogel’s approximation method and Least cost method is less than northwest corner method.

Mock Tests and Test Series