1.
Define Transportation Problem
(Industrial Engineering)
A programming problem that is concerned with the optimal pattern of the distribution of goods
from several points of origin to several different destinations, with the specified requirements at
each destination.
Seeks the determination of a minimum cost transportation plan
Single commodity
A number of sources
A number of destinations
2. Basic Concept of Transportation Problems Tabular Representation
Specifications:
Level of supply at each source
Amount of demand at each destination
Transportation cost from each source to each destination
One commodity
A destination can receive its demand from one or more sources
The Objective:
To find the amount to be shipped from each source to each destination such
that the total transportation cost is minimized
Types of the Transportation Problems:
Linear transportation problem
Cost on a route is directly proportional to the amount transported
Otherwise – the problem is nonlinear
Terms:
n sources
k destinations
s(i) – the amount of supply at source I
d(j) – the demand at destination j
cost(i,j) – the unit transportation cost between source i and destination j
Xji – the amount transported from i to j
The Transportation Problem is given as:
∑ ∑ ∫ ( Xij )
n k
min i =1 j =1 ij
∑
k
j =1
Xij <= s (i ), i =1,2,....., n
∑
n
i =1
Xij >= d ( j ), j = 1,2,......., k
Xij >= 0, for i = 1,2,…,n and j = 1,2,…,k
3. Methods to Solve Transportation Problems
Linear transportation problem:
if
∫ ( Xij
ij
) =cost (ij ) * Xij
for all i and j, the problem is linear
Balanced transportation problem:
The total supply equal the total demand
Balanced transportation problem:
∑
k
j =1
Xij = s (i ), i =1,2,....., n
∑
n
i =1
Xij = d ( j ), j = 1,2,....., k
Integer solution:
If all s(i) and d(j) are integers
all X(ij) are integers
The number of positive integers among the X(ij) is at most n + k -1
Example:
3 sources
s(1) = 15, s(2) = 25, s(3) = 5
4 destinations
d(1) = 5, d(2) = 15, d(3) = 15, d(4) = 10
Total supply and demand equal 45
The transportation cost:
10 0 20 11
12 7 9 20
0 14 16 18
The optimal solution:
5 15 15 10
15 0 5 0 10
25 0 10 15 0
5 5 0 0 0
Transportation Model Example
Problem Definition and Data
Problem: How many tons of wheat to transport from each grain elevator to each mill on a
monthly basis in order to minimize the total cost of transportation?
Data: Grain Elevator Supply Mill Demand
1. Kansas City 150 A. Chicago 200
2. Omaha 175 B. St. Louis 100
3. Des Moines 275 C. Cincinnati 300
Total 600 tons Total 600 tons
Transportation Model Example
Model Formulation
minimize Z = $6x1A + 8x1B + 10x1C + 7x2A + 11x2B + 11x2C + 4x3A + 5x3B + 12x3C
subject to x1A + x1B + x1C = 150
x2A + x2B + x2C = 175
x3A + x3B+ x3C = 275
x1A + x2A + x3A = 200
x1B + x2B + x3B = 100
x1C + x2C + x3C = 300
xij ≥ 0
Solution of the Transportation Model
Tableau Format
• Transportation problems are solved manually within a tableau format.
• Each cell in a transportation tableau is analogous to a decision variable that
indicates the amount allocated from a source to a destination.
• The supply and demand values along the outside rim of a tableau are called
rim values.
The Transportation Tableau
Solution of the Transportation Model
Solution Methods
• Transportation models do not start at the origin where all decision values are
zero; they must instead be given an initial feasible solution.
• Initial feasible solution determination methods include:
- Northwest corner method
- minimum cell cost method
- Vogel’s Approximation Method
• Methods for solving the transportation problem itself include:
- stepping-stone method and
- modified distribution method.
4. Characteristics of Transportation Problems
• A product is transported from a number of sources to a number of destinations at the
minimum possible cost.
• Each source is able to supply a fixed number of units of the product, and each destination
has a fixed demand for the product.
• The linear programming model has constraints for supply at each source and demand at
each destination.
• All constraints are equalities in a balanced transportation model where supply equals
demand.
• Constraints contain inequalities in unbalanced models where supply does not equal
demand.
5. Special Cases of Transportation Problems
The Northwest Corner Method
The Minimum Cell Cost Method
Vogel’s Approximation Method (VAM)
The Stepping-Stone Solution Method
The Modified Distribution Method (MODI)
The Unbalanced Transportation Model
Degeneracy
