Transportation Problem: Initial Basic Feasible Solution

Introduction to Transportation Problem

As the need for goods and services increases globally, so does the importance of transportation. Transportation determines the profits of businesses which move goods and services from one corner of the country to another, especially in scenarios where transportation time and costs are much higher than production time and costs.

The transportation problem is defined as the study of optimal transportation and allocation of resources. A form of transportation problem was first put forward by the French mathematician Gaspard Monge in 1781. Soviet mathematician Leonid Kantorovich greatly added to the field during World War II.

The classical transportation problem is the simplest form of a transportation problem and Hitchcock in 1941 presented its constructive solution, and in 1947, independently by Koopman. In Linear Programming Program (LLP), the physical distribution of commodities from the source to the destination at the lowest possible cost comprises the transportation problem and is also known as the Hitchcock–Koopmans transportation problem. Gavurin (1949) and Dantzig (1951) also helped to develop the field of the transportation problem further.

The transportation problems can be balanced or unbalanced. There are various methods to identify the solution that satisfies the requirements of demand and supply in a transportation problem, i.e., obtaining the initial feasible solution.

In this article, you will study about the transportation problems and mathematical formulation of the transportation problem. You will also study about the methods of obtaining an initial basic feasible solution.

---

What is Transportation Problems?

The transportation problem is a type of LPP related to the study of efficient transportation of goods and services from a set of sources to a set of destinations, with an objective to minimise the total cost of transportation. The transportation problem allows organisations to minimise costs and thus, maximise profits.

The transportation problem has a special mathematical structure, it was realised that the simplex method applied to it can be made more efficient regarding the calculation of the necessary simplex method information i.e., the entering variable, leaving variable and optimality conditions).

---

Types of Transportation Problems

The two types of transportation problems are:

• Balanced
• Unbalanced

Balanced

When the total supplies are equal to the total demand then the problem is a balanced transportation problem, i.e., Total supply= Total demand

Unbalanced

When the supply and demand are not equal then the problem is said to be unbalanced, i.e., Total supply≠ Total demand. For an unbalanced transportation problem, either dummy sources or dummy destinations are added according to the requirement to make it a balanced problem so that it can be solved like a balanced problem.

---

Important Terms Used in Transportation Problems

Let us look at some terms that will often come up in the study of transportation problems:

• Origin/Source: It refers to the location from which shipments are dispatched.
  
  
• Destination: It refers to the location to which shipments are transported.
  
  
• Unit transportation cost: It refers to the cost of transporting a single or one unit of the consignment from the place of origin to the destination.

Other important terms used in the transportation problems are given in the sections below:

• Feasible Solution (FS)
• Basic Feasible Solution (BFS)
• Optimal Solution
• Non-degenerate Basic Feasible Solution
• Degenerate Basic Feasible Solution

Feasible Solution (FS)

A feasible solution refers to the type of solution that satisfies all the source and destination restrictions along with the non-negativity restrictions. It is a set of non-negative allocations, that satisfies the row and column restrictions.

Basic Feasible Solution (BFS)

In a transportation problem with m origins and n destinations, a feasible solution in which the number (total) of allocations are equal to (m + n – 1), is said to be a basic feasible solution.

Optimal Solution

While a basic feasible solution may satisfy all the sources and location restrictions it may not necessarily give a solution with the minimum cost. There may be more than one basic feasible solution but an optimal solution is the basic feasible solution that has the minimum total transportation cost.

Thus, an optimal solution is a feasible solution (not necessarily basic) that minimises the transportation cost. There- fore, optimality tests are conducted on the identified basic feasible solutions to check whether or not it is the best and in case it is not, if it would lead to the better or optimal solution.

Non-degenerate Basic Feasible Solution

A basic feasible solution where the allocations exactly equal (m + n – 1) positive variables is known as a non-degenerate basic feasible solution.

Degenerate Basic Feasible Solution

A basic solution is said to be a degenerate basic feasible solution if one or more of the basic variables are zero. In a transportation problem with m origins and n destinations, if a basic feasible solution has allocations less than m + n – 1, the solution is a degenerate solution.

---

Mathematical Formulation of the Transportation Problem

Mathematically speaking, a transportation problem is simply a special LPP where the objective function is to minimise the cost of transportation, subject to the constraints of demand and supply. It can be applied to scenarios in which a single commodity is to be moved from various sources of supply to various demand centres.

Because the transportation problem is an LPP, we could formulate it as an LPP and apply the simplex method to solve it as with any LPP. However, because of its special mathematical structure, the transportation problem can be solved with a faster, more efficient algorithm than simplex.

For the formulation of a transportation problem, the following information is essential:

• The number of sources (m)
• The number of destinations (n)
• The total quantity available at each source
• The total quantity required at each destination
• The unit transportation cost

There are a few requirements for solving the transportation problem. One is that all the units that are available must be supplied. Another requirement is that the number of constraints must equal the number of rows and number of columns.

Also, the number of routes R should equal the number of origins m plus the number of destinations n minus one, i.e., R = m + n – 1. In case R ≠ m + n – 1, there are either excess routes or degeneracy (more than one exiting cell).

Certain assumptions are also made before using any technique to solve a transportation problem:

• The problem is balanced, i.e., the total quantity available at all the sources equals the total quantity required the destinations. If not, dummy sources or dummy destinations are added to change to a standard balanced problem.
  
  While this may sound unreasonable because it is unlikely that supply always will equal demand, it is acceptable for practical purposes. Provided, the supply is sufficient to satisfy demand, we can ignore the surplus and consider the total supply as equal to the total demand.
  
  
• The unit transportation cost from one origin to one destination is clearly known.
  
  
• The unit cost is independent of the number of goods transported i.e., transported volume.
  
  
• A single commodity is transported.
  
  
• The transportation capacity to ship across any particular transportation route is unlimited.

Say, we have m sources of supply s1, s2…………sm with corresponding ai (i = 1, 2……m) units of supplies to be transported amongst n destinations d1, d2………dn with corresponding bj (j = 1,2……n) units of requirements.

Let cij be the cost for transporting one unit of the commodity from source i, to destination j for each route. Let xij be the units shipped per route from source i, to destination j. Then the problem is to identify the transportation schedule which minimises the total transportation cost of satisfying supply and demand conditions.

The transportation problem can be stated mathematically as a linear programming problem as below:

and xij ≥ 0 for all i = 1,2…….m and j = 1,2…….m

A summary of the transportation problem variables is given in

Variable	Symbol
Origins/Sources (location of supply or production)	m
Destinations (location of demand or consumption)	n
Capacity (supply/production) of source i	ai
Requirement (demand/consumption) at destination j	bj
Unit transportation cost from origin i to destination j	cij
Quantity shipped from origin i to destination j	xij
Total transportation cost	C

Although we have formulated the above transportation problem as an LPP and can solve it using the usual simplex method, there are other easier algorithms developed for solving them. For transportation problem usually, the problem will be given in a tabular form or matrix form called the transportation table or cost-effective matrix.

---

Methods of Obtaining an Initial Basic Feasible Solution

There are five methods to obtain an initial basic feasible solution to a transportation problem are:

• Row Minimum Method
• Column Minimum Method
• North-West Corner Method (NWCM)
• Least Cost Method (LCM)
• Vogel’s Approximation Method (VAM)

Row Minimum Method

In the row minimum method, maximum possible amount is allocated in the lowest cost cell of the first row. The aim is that either the capacity of the first source is exhausted or the demand at the destination centre is satisfied or both.

The row minimum method is summarised in the steps below:

Step 1: Write the given transportation problem in tabular form.

Step 2: Select the cell with minimum unit transportation cost in the first row. If it is not unique, arbitrarily select a cell in the first column with minimum cost.

Step 3: Allocate as much as possible amount X1 = min (ai, bj) to this cell. Three cases may arise:

• X1 = a1 so that the supply at origin O1 is completely exhausted, then delete the first row of the table and move down to the second row.
  
  
• X1 = a1 b1 so that both the capacity at origin a1 is completely exhausted and the demand at destination Dj is completely satisfied. Then, break the tie by arbitrarily by choosing a cell and delete the j column and make the second allocation X1k = 0 to the cell (1k). Now, C1k is the new minimum cost in the first row. Delete the first row and move down to the second row.
  
  
• X1j = bj so that the demand at destination Dj is satisfied. Then delete the j column and go back to the first row with the remaining supply at origin O1.

Repeat the process until all the columns have been deleted and all the supply and demand conditions are satisfied.

Column Minimum Method

In the column minimum method, maximum possible amount is allocated in the lowest cost cell of the first column. The aim is that either the capacity of the first source is exhausted or the demand at the destination centre is satisfied or both.

The column minimum method is summarised in the steps below:

Step1: Write the given transportation problem in tabular form.

Step2: Select the cell with minimum unit transportation cost in the first column. If it is not unique, arbitrarily select a cell in the first column with minimum cost.

Step 3: Allocate as much as possible Xi1= min (ai, bi) to this cell, such that the demand of the first destination centre is satisfied or the capacity of the second is exhausted or both. Three cases can thus arise:

• Xi1 = b1, i.e., the demand of first destination centre is satisfied, delete the first column and proceed to the column on the right.
  
  
• Xi1 = ai, i.e., the capacity of the ith origin is satisfied, delete the ith row and go back to the first column with the remaining demand.
  
  
• Xi1 = bj = ai, i.e., the demand of the first destination centre is completely satisfied and also the capacity of ith origin is exhausted. Make a zero allotment in the second lowest cost cell of the first column. Delete the column as well as the ith row and move to the second column.

Step 4: Repeat the process for the subsequent reduced transportation table until all the conditions are satisfied.

North-West Corner Method (NWCM)

The North-West Corner Method is an approach for calculating a basic feasible solution of a transportation problem, in which the basic variables are selected from the North-West corner i.e., the top left corner.

The steps for determining an initial solution using the North-West Corner Method are given below:

Step 1: Write the given transportation problem in tabular form.

Step 2: Go over to the northwest corner of the table and select the upper left-hand corner cell. Allocate as many units as possible equal to the minimum between available supply and demand i.e., min (ai, bi).

Step 3: In the corresponding rows and columns, adjust the numbers of supply and demand.

Step 4: If the first cell demand is satisfied, then horizontally move to the next cell which is in the 2nd column.

Step 5: If the first row supply is exhausted, then vertically move down to the first cell in the 2nd row.

Step 6: If for any cell the supply is equal demand, then do the next allocation in a cell either in the next row or column. Step 7: Repeat the steps until all origins are exhausted and all demands are fulfilled.

Least Cost Method (LCM)

The least cost or matrix minimum method is used for calculating a basic feasible solution of a transportation problem, in which the basic variables are chosen according to the unit cost of transportation. This method is quite useful as it saves time of computation and also time needed to find the optimal solution. In the least cost method, allocations are made on the basis of economic desirability.

The steps involved in determining an initial solution using this approach are:

Step 1: Write the given transportation problem in tabular form.

Step 2: Identify the cell with minimum unit transportation cost. If it is not unique, you can arbitrarily select any cell.

Step 3: Allocate min (ai, bj) to this cell. In case the min (ai, bj) = ai, then the capacity at the ith origin is exhausted and demand at the jth destination remains to be bj – ai and the ith row is crossed out from the table. In case min (ai, bj) = bj, then demand at the jth destination is satisfied and the availability at the ith origin remains to be ai – bj and the jth column is crossed out from the table.

Step 4: Continue until there is one cell that can be chosen and all restrictions are met.

Vogel’s Approximation Method (VAM)

The Vogel’s Approximation Method (VAM) or unit cost penalty method is an improved version of the least-cost method that often, though not always, generates superior starting solutions. The opportunity or penalty cost for a given supply row or demand column is defined as the difference between the least cost and the next least cost alternative. VAM is based upon the concept of minimising opportunity costs. VAM is preferred as it generates an optimum or near optimum initial solutions.

As a result, the time needed to obtain an optimum solution is greatly reduced if we use the initial solution obtained by VAM and proceed to solve for the optimum solution.

The steps involved in determining an initial solution using VAM are summarised below:

Step 1: Write the given transportation problem in tabular form.

Step 2: Calculate the difference between the least cost and the next lowest cost corresponding to each row and each column which is known as opportunity cost or penalty cost.

Step 3: Recognise the cells which are having the least cost and the next least transportation cost in each row and mention the difference which is termed as a penalty along the side of the table against the corresponding row.

Step 4: Find the maximum penalty. In case it is along the side of the table, make a maximum allotment to the cell with the lowest cost of transportation in that row. In case it is below the table, make maxi- mum allotment to the cell with the lowest cost of transportation in that column.

Step 5: If the penalties corresponding to rows or columns (two or more) are equal, then, you can arbitrarily break the tie.

Step 6: Repeat the iterations until all restrictions have been satisfied.

Ways to confirm the accuracy of the process of the various methods described above:

• The total supply and total demand will remain the same during the steps.
• In the final step, a single the cell will be allocated with either the supply or demand value as both will have the same value.

Which Method to Choose?

The North-West Corner Method has the advantage of generating a quick solution because computations take less time, but the solution is not as good as the others since it is very far from optimal solution.

The Vogel’s Approximation Method and the Least-Cost Method have the advantage of generating the best starting basic solution because the initial solution generated is very close to optimal solution. But the Vogel’s Approximation Method has limitation of being slow because the computations take more time.

The results from the different methods are different. Sometimes, decision maker may run the problem through the different programs and choose the result with the mini- mum unit transportation cost from source i to destination j.