Transportation Problem: Finding an Optimal Solution

The transportation problem is an important Linear Programming Problem (LPP). This problem depicts the transportation of goods from a group of sources to a group of destinations. The whole process is subject to the availability and demand of the sources as well as destination, respectively in a way, where entire cost of transportation is minimised.

Sometimes, it is known as Hitchcock problem. Generally, transportation costs are involved in such problems but the scope of problems extends well beyond to hide situations that do not have anything to try with these costs.

The term ‘transportation’ is related to such problems principally because in studying efficient transportation routes, a special procedure was used which has come to be referred to as the transportation method.

A typical transportation problem is a distribution problem where transfers are made from various sources to different destinations, with known unit costs of transfer for all source-destination combinations, in a manner that the total cost of transfers is the minimum. In this chapter, you will discuss how to improve an optimal solution by stepping stone method and describe the special cases in the transportation problems.

Finding Optimal Solution Using the Stepping Stone Method

A typical transportation problem is like this. Let’s consider that a man- ufacturer of refrigerators runs three plants located at different places called A, B and C. Suppose further that his buyers are located in three regions X, Y and Z where he has got to supply them the products.

So, the need within the three regions as well as production in several plants per unit time period are known and equal in aggregate and further that the cost of one transporting refrigerator from each plant to each of the requirement centres is given and constant.

The manufacturer’s problem is to determine as to how he should route his product from his plants to the marketplaces so that the total cost involved in the transportation is minimized. In other words, he needs to decide on how many refrigerators should be supplied from A to X, Y and Z, how many from B to X, Y and Z and how many from C to X, Y and Z to attain it at the least cost.

The places where the products originate from (the plants in our example) are called the sources or the origins and places where they are to be supplied are the destinations. In this terminology, the trouble of the manufacturer is to decide on how many units are transported from different origins to different destinations in order that the overall transportation cost is the minimum.

The transportation method is an efficient alternative to the simplex method for solving transportation problems.

Step 1: Obtaining the Initial Feasible Solution

To use the transportation method is to get a feasible solution, namely, the one that satisfies the rim requirements (i.e., the requirements of demand and supply). The initial feasible solution may be obtained by various methods.

• Row Minima Method
• Column Minima Method
• North-West Corner (NWC) Rule
• Least Cost Method (LCM)
• The Vogel’s Approximation Method (VAM)

Step 2: Testing the Optimality

After obtaining the initial basic feasible solution, the successive step is to check whether it is optimal or not. There are two methods of testing the optimality of a basic feasible solution. One of these is named the stepping-stone method within which the optimality test is applied by calculating the opportunity cost of each empty cell.

The other method is named as the Modified Distribution Method (MODI). It is based on the concept of dual variables that are used to evaluate the empty cell. Using these dual variables, the opportunity cost of each of the empty cell is determined. Thus, while both methods involves determining opportunity costs of empty cells, the methodology employed by them differs.

Both the methods can be used only when the solution is a basic feasible solution so that it has m + n – 1 basic variables. If a basic feasible solution contains less than m + n – 1 non-negative allocation, then the transportation problem is said to be a degenerate one. Incidentally, none of the methods used to find initial solution would yield a solution with greater than m + n – 1 number of occupied cells.

Step 3: Improving the Solution

By applying stepping stone method, if the answer is found to be optimal, then the process terminates because the problem is solved. If the answer is not seen to be optimal, then a revised and improved basic feasible solution is obtained. This can be done by exchanging a non-basic variable for a basic variable.

In simple terms, rearrangement is formed by transferring units from an occupied cell to an empty cell that has the largest opportunity cost, then adjusting the units in other related cells in a way that each one of the rim requirements are satisfied. The solution obtained is again tested for optimality and revised, if necessary. You continue this manner until an optimal solution is finally obtained.

Stepping Stone Method

This is a procedure for determining the potential, if any, of improving upon each of the non-basic variables in terms of the objective function.

To determine this potential, each of the non-basic variables (empty cells) is taken into account one by one. For each such cell, you discover what effect on the overall cost would be if one unit is assigned to the present cell. With this information, then, you come to understand whether the solution is optimal or not.

If not, you improve that solution. This method is derived from the analogy of crossing a pond using stepping stones. It concludes that the whole transportation table is assumed to be a pond and the occupied cells are the stones required to build specific movements inside the pond.

Stepping stone method helps in determining the change in net cost by presenting any of the vacant cells into the solution. The main rule of the stepping stone method is that every increase (or decrease) in supply in one occupied cell must be associated with a decrease (or increase) in supply in another cell. The same rule also holds for demand.

The steps involved in the stepping stone method are as follows:

• Determine Initial Basic Feasible Solution (IBFS). Make sure the number of occupied cells is exactly equal to m + n − 1. 2. Evaluate the cost-effectiveness of shipping goods via transpor- tation routes for the testing of each unoccupied cell. For this, se- lect an unoccupied cell and trace a closed path using the straight route in which at least three occupied cells are used.
  
  
• Assign plus (+) and minus (−) signs alternatively in the corner cells of the closed path (identified in step 2). The unoccupied cell should be assigned with a plus sign.
  
  
• Add the unit transportation costs associated with each of the cell traced in the closed path. This would give the net change in terms of cost.
  
  
• Repeat steps 2 to 4 until all unoccupied cells are evaluated.
  
  
• Check the sign of each of the net change in the unit transportation costs. If all the net changes calculated are more than or equal to zero, an optimal solution has been attained. If not, then it is possible to advance the current solution and minimise the total transportation cost.
  
  
• Select the vacant cell with the highest negative net cost change and calculate the maximum number of units that can be assigned to this cell. The smallest value with a negative position on the closed path indicates the number of units that can be shipped to the entering cell. Add this number to the unoccupied cell and all other cells on the route having a plus sign and subtract it from the cells marked with a minus sign.
  
  
• Repeat the procedure until we get an optimal solution.

Special Cases in the Transportation Problems

Transportation is all about getting a product from one place to another, put the product on a truck or railcar and you are good to go. Well, not exactly. There’s a bit more that goes into it. It becomes particularly complicated when there are multiple places the product is coming from, and multiple places the product is going to.

Transportation managers must do to some calculations to find the optimum path for getting their product to the customer. Let us look at some common problems a transportation manager might encounter. One common transportation issue has to do with supply and demand.

Some variations that often arise while solving the transportation problem could be as follows:

Degeneracy in Transportation Problem

In a standard transportation problem with m sources of supply and n demand destinations, the test of optimality of any feasible solution requires allocations in m + n – 1 independent cells. Degeneracy occurs whenever the number of individual allocations are but m + n – 1, where m and n are the number of rows and columns of the transportation problem, respectively. Degeneracy in transportation problem can develop in two ways.

• The basic feasible solution might have been degenerate from the initial stage
• They may become degenerate at any immediate stage

To resolve degeneracy a little positive number, Δ is assigned to at least one or more unoccupied cell that have lowest transportation costs so on make N = m + n – 1 allocations. (Δ is an infinitesimally small number almost equal to zero.)

Although there is a great deal of flexibility in choosing the unused square for the Δ stone, the general procedure, when using the North West Corner Rule, is to assign it to a square in such how that it maintains an unbroken chain of stone squares. However, where Vogel’s method is used, the Δ allocation is carried during a least cost independent cell.

An independent cell during this context means a cell which cannot cause a closed path on such allocation. After this, the test of optimality is applied and if necessary, the solution is improved within the normal way until optimality is reached.

Unbalanced Transportation Problem

When the total supply of all the sources is not equal to the total demand of all destinations, the problem is an unbalanced transportation problem.

Two situations are possible: 1. If supply < demand, a dummy supply variable is introduced in the equation to make it equal to demand 2. If demand < supply, a dummy demand variable is introduced in the equation to make it equal to supply

Then before solving you must balance the demand and supply. The unit transportation cost for the dummy column and dummy row are assigned zero values, because no shipment is really made just in case of a dummy source and dummy destination.

Alternative Optimal Solutions

An alternate optimal solution is additionally called as an alternate optima, which is when a linear / integer programming problem has more than one optimal solution. Typically, an optimal solution may be a solution to a problem which satisfies the set of constraints of the problem and, therefore, the objective function which is to maximise or minimise. It is possible for a transportation problem to possess multiple optimal solutions.

This happens when one or more of the development indices zero within the optimal solution, which suggests that it’s possible to style routes with an equivalent total shipping cost. The alternate optimal solution is often found by shipping the foremost to the present unused square employing a stepping-stone path. Within the world, alternate optimal solutions provide management with greater flexibility in selecting and using resources.

Maximisation Transportation Problem

The main motive of transportation model is used to minimise transportation cost. However, it also can be used to get a solution with the objective of maximising the overall value or returns. Since the criterion of optimality is maximisation, the converse of the rule for minimisation will be used. The rule is: a solution is optimal if all – opportunity costs dij for the unoccupied cell are zero or negative.

Hence, how does all this help the business overall? If a business’ objective is to maximise profits, then finding the answer to transportation problems allows the companies to use the results from the matrixes to maximise their objective and obtain the foremost profit they will. Profit is often calculated by using this easy formula.

Profit = Selling price – Production cost – Transportation cost

If the objective of a transportation problem is to maximise profit, a minor change is required in the transportation algorithm. Now, the optimal solution is reached when all the development indices are negative or zero. The cell with the most important positive improvement index is chosen to be filled by employing a stepping-stone path. This new solution is evaluated and therefore the process continues until there are not any positive improvement indices.

Prohibited Routes

At times there is transportation problems during which one among the sources is unable to ship to at least one or more of the destinations. When this happens, the problem is claimed to have an unacceptable or prohibited route.

In a minimisation problem, such a prohibited route is assigned a really high cost to prevent this route from ever getting used within the optimal solution. In a maximisation problem, the very high cost utilised in minimisation problems is given a negative sign, turning it into an awfully bad profit.

Sometimes there could also be situations, where it is unacceptable to use certain routes during a transportation problem. For example, road construction, bad road conditions, strike, unexpected floods, local traffic rules, etc.

Such restrictions (or prohibitions) will be handled within the transportation problem by assigning a very high cost (say M or [infinity]) to the prohibited routes to make sure that routes will not be included within the optimal solution then the matter is solved within the usual manner.