Transportation Problem: Formulation, Solution, and Algorithm

This report delves into the transportation problem, a crucial aspect of operations research, focusing on the efficient distribution of goods from multiple sources to various destinations while minimizing transportation costs. The assignment begins with an introduction to the problem, highlighting its real-world applications in optimizing supply chains and distribution networks. It then provides a detailed problem definition, including the formulation of balanced and unbalanced transportation scenarios. The core of the report focuses on the solution methodology, specifically employing Vogel's Approximation Method (VAM) to determine an initial feasible solution. The report illustrates the VAM process through a practical example, demonstrating the step-by-step allocation of resources and the computation of penalty costs to arrive at an optimal or near-optimal solution. Furthermore, the report outlines a possible algorithm for solving the transportation problem, encompassing problem formulation, the calculation of penalty costs, and the iterative assignment process. The conclusion emphasizes the effectiveness of VAM and summarizes the key contributions of each group member. The report provides a clear understanding of the transportation problem, its solution methods, and its relevance in various industries.

1

Transportation problem
Introduction
Transportation problem is applied in real life daily human activities and it has proved helpful in solving
transportation and distribution of items from one destination to another [1]. In transportation problem,
a product is supposed to be transported from a source(s) which are manufacturing companies to
destination(s) which are many individual stores, thus meeting specified requirement. Major objective of
this type of problem is to meet destinations demand from supply constraints at the lowest possible
transportation cost. To meet the objective, the number of products to be supplied from the source and
that demanded in the destination must be known [2]. Furthermore, locations from the source(s) to
destination(s) must be known so as to find the cost of transportation on an item. The normal simplex
methods are not normally used to solve as it require special methods of solving it. Transportation model
is also used to make wise decisions of selecting optimum routes of allocating manufactured products
from different sources to several distribution stores [3].
Problem definition
Assuming there are more than one sources, from where products need to be transported to more than
one destinations and the cost of transporting each product from one source to one destination is
identical and known, the problem is to carry each item from different sources to different destinations
at the lowest transportation cost possible. Let say, we have n factories manufacturing spares, and are
located in n different towns. Supply of this spares is supplied to m different retail stores in n different
towns, transportation problem will give schedule of transporting the spares. Schedule that will ensure
minimum transportation cost is incurred in delivering the spares from many different factories to many
different retail shops. This model can be used to decide where to locate a new factory or retail stores
considering existing locations that will minimize transportation costs.
Real world applications
We are going to consider real life application based on transportation problem. Transportation problem
comes up with a schedule that will result to minimum transportation cost [3]. Since we are using the
model to determine the lowest cost possible, assumptions has to be made and are as follows
 Cost of transporting one product/item is the same regardless of the amount of products
transported
 One and only one route is chosen from the source to the destination
 Products to be transported are homogeneous
The problem involves determining optimum transportation cost of a specific product from sources to
destinations. Every destination and source has a specified demand, dj and supply, si respectively as
shown in the figure 1.
2

Figure 1 transportation problem model
Transportation problem are of two types namely balanced and unbalanced transportation problems.
Balanced transportation problem is the type whereby the sum of supply from the source is the same as
that demanded by the destination. Unbalanced transportation problem on the other hand is where
quantity supplied by the source is not equal to that demanded by the destination [4].
The following example is used in demonstrating the formulation of the transportation problem.
Harvested wheat in Midwest is kept in different elevators located in Des Moines, Kansas and Omaha,
from the elevators wheat supply three different flour mills namely Chicago, Cincinnati and St. Louis. Each
elevator can supply tabulated quantities in tons per month.
Table 1: Supply
elevator Quantity supplied
1. Kansas city One hundred and fifty
2. Omaha One hundred and seventy five
3. Des Moines Two hundred and seventy five
Total quantity supplied in tons 600
Each mill in one month demands the following quantity of wheat in tons
Table 2: Demand
Millers Demand
A. Chicago Two hundred tons
B. St. Louis One hundred tons
C. Cincinnati Three hundred tons
Total quantity demanded in tons 600 tons
3

Transporting cost per ton of wheat from one specified elevator to a specified mill is obviously different
due to distance variation and maybe due to means of transport and are tabulated in the table below.
For example, transportation cost from Kansas city elevator to a mill in Chicago is 6 dollars
Table 3: Transportation cost
Grain elevator A. Chicago B. St. Louis C. Cincinnati
1. Kansas Six dollars Eighth dollars Ten dollars
2. Omaha Seven dollars Eleven dollars Eleven dollars
3. Des Moines Four dollars Five dollars Twelve dollars
The problem will be to find the quantity of wheat in tons to be transported from specified elevator to
specified mill at the minimum cost on monthly basis. The model is summarized below
Table 4: Transportation table model
Solution to the problem
In linear programming, starting feasible solution is found by introducing variables and going through
several computations [5]. To identify the solution, a set of equations can be represented in form of
transportation table or array. There are various methods that are used and are listed below
 North West Corner Rule (NWCR)
 Stepping stone method
 Row Minima Method
 Modified Distribution Method
 Column Minima Method
 Least Cost method
 Vogel’s Approximation Method (VAM)
The methods above are different in terms quality of the resulting initial solution and the best solution it
can produce, Vogel’s approximation method is used because it gives better solution compared to
methods [6].
To determine the first solution to our real life application given in previous section, VAM model was
used and it’s based on regret or penalty cost [6]. To start the procedure, penalty cost for each
destination and source. Considering column (A) of table 4, supply to destination A can be met by three
sources 1, 2, 3 but the best decision will be to be supplied by source 3 as it has minimum cost of 4
4

dollars. If source 2 was to be wrongly picked, a penalty of 2 dollars would result. The general rule is, to
find a difference between the lowest cost and the next highest cost in each cell for every column and
row [7]. Penalty costs are indicated at the bottom and right as shown in table 5
Table 5: penalty cost table
The initial allocation is made on a column or row with largest penalty cost. Row 2 of table 5 has large
penalty cost. Minimum cost is allocated to the feasible cell in the row (with highest penalty cost) [5],
thus cell with lowest cost of 7 dollars and 175 tons is allocated to it.
After making initial allocation, all penalty costs is recomputed [8], in that case some cost will and others
won’t change, for instance, penalty cost from table 5 for column C has changed from 2 to 1 as row 2 has
been struck out. In the next step, the previous step is repeated to allocate the row and columns with the
largest value of penalty cost and its now column B. The cell with the lowest cost in this column is 3B, and
thus 100 tones is allocated to it, as shown in table 6 below
Table 6: second allocation
New penalty has been computed in table 6. The new largest value of penalty cost is 8 and falls in row 3.
It can be noticed that cell 3A has the lowest cost , remaining 25 tons is thus allocated to it and is
indicated in table 7
5

Table 7: third allocation
Table 7 shows the recomputed penalty cost, and the only column with penalty cost is column C. The
remaining assignments are made to column C, 150 is assigned to cell C of row 1, since it has lowest
transportation cost. The only feasible cell left is C of row 3 and 150 tons is allocated to it and is indicated
in table 8.
Table 8: lnitial allocation.
The method has been successfully to determine how to transport product to a destination with
minimum cost.
Possible algorithm
The algorithm to solving transportation problem involves several steps
Step 1: problem formulation
The given problem in real world application section is formulated, and is set up in matrix form [9]. The
transportation problem is of balanced type. Balanced transportation problem is where demand is equal
to the supply. Thus there is no need of adding dummy destination (column) or dummy source (rows).
Step 2: starting feasible solution [10]
i. Calculating penalties costs for every column and row, it is done by finding the difference
between least cost and the next highest cost in specific column or row. The penalty costs are
indicated at the right and bottom for row and column respectively.
ii. A column or a row with largest penalty cost is selected, assignment is then done to cell with
the least cost in that column and row. If there exist two or more equal penalties, one where
a row/column contains minimum unit cost is picked.
6

iii. The column or row that has already met the supply and demand is deleted.
iv. Steps i. and ii. are repeated until whole demand and supply are satisfied.
v. Starting basic feasible equation is determined
Conclusion
In the paper, Vogel’s Approximation Method was adopted in solving transportation problem since it
gives better results. Case scenario of supplying wheat from different elevators to different mills located
in several cities, was used. Transportation problem was used to determine the lowest possible transport
that can be adopted to deliver the wheat to meet the demand.
Contribution of each member
Each member was tasked with working on a specific section of the assignment. Member A was tasked to
research on introduction, problem definition and real life application. Member B was tasked to research
on solution to the problem and possible algorithms. The findings were then consolidated and the report
of the same written.
7

References
[1]Samuel, A.E. and Venkatachalapathy, M., 2011. Modified Vogel’s approximation method for fuzzy
transportation problems. Applied Mathematical Sciences, 5(28), pp.1367-1372.
[2]Mathirajan, M. and Meenakshi, B., 2004. Experimental analysis of some variants of Vogel's
approximation method. Asia-Pacific Journal of Operational Research, 21(04), pp.447-462.
[3]Korukoğlu, S. and Ballı, S., 2011. A Improved Vogel's Approximation Method for the Transportation
Problem. Mathematical and Computational Applications, 16(2), pp.370-381.
[4]Hakim, M.A., 2012. An alternative method to find initial basic feasible solution of a transportation
problem. Annals of pure and applied mathematics, 1(2), pp.203-209.
[5]Sharma, R.R.K. and Prasad, S., 2003. Obtaining a good primal solution to the uncapacitated
transportation problem. European Journal of Operational Research, 144(3), pp.560-564.
[6] Munkres, J., 2007. Algorithms for the assignment and transportation problems. Journal of the society
for industrial and applied mathematics, 5(1), pp.32-38.
[7] Kaur, A. and Kumar, A., 2012. A new approach for solving fuzzy transportation problems using
generalized trapezoidal fuzzy numbers. Applied soft computing, 12(3), pp.1201-1213.
[8] Sharma, R.R.K. and Prasad, S., 2003. Obtaining a good primal solution to the uncapacitated
transportation problem. European Journal of Operational Research, 144(3), pp.560-564.
[9] Hasan, M.K., 2012. Direct methods for finding optimal solution of a transportation problem are not
always reliable. International Refereed Journal of Engineering and Science (IRJES), 1(2), pp.46-52.
[10] Jaramillo, J.H., Bhadury, J. and Batta, R., 2002. On the use of genetic algorithms to solve location
problems. Computers & Operations Research, 29(6), pp.761-779.
8