Operations Research.

Chapter 3: The Transportation Problems

Dr. Hà Văn Hiếu

University of Economics and Law

6th October 2024

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 1 / 31

 Key terms and Reference

Transportation
Truckload Source
Shipping Cost Destination
Distribute Dummy source
Total distribution cost Dummy destination
Minimize Supply
Network Demand
Occupied cell Improvement Index
Closed loop/path Unit cost
Non-negative Basic feasible (BF) solution
(Un)balanced

Reference: p318

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 2 / 31

 The Transportation problem

Gaspard Monge formalized this problem

in 1781.
Monge–Kantorovich transportation
problem.
Linear programming formulation of the
transportation problem is known as the
Hitchcock–Koopmans transportation
problem.

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 3 / 31

 Example - p. 320

One of the main products of the P & T COMPANY is canned peas.

The peas are prepared
at three canneries (near Bellingham,
Washington; Eugene, Oregon; and
Albert Lea, Minnesota) and then shipped
by truck to four distributing warehouses
in the western United States (Sacramento,
California; Salt Lake City, Utah; Rapid
City, South Dakota; and Albuquerque,
New Mexico), as shown in the map.

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 4 / 31

 Example - Table of shipping data

This information (in units of truckloads), along with the shipping cost per truckload for
each cannery-warehouse combination, is given in the following table.

The problem now is to determine which plan for assigning these shipments to the various
cannery-warehouse combinations would minimize the total shipping cost.
Hà Văn Hiếu (UEL) Operations Research 6th October 2024 5 / 31
 Network representation of the P & T Co. problem.

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 6 / 31

 In terms of LPP

Let xij (i = 1, 2, 3; j = 1, 2, 3, 4) be the number of truckloads to be shipped from

cannery i to warehouse j. Thus, the objective is to choose the values of these 12
decision variables (the xij ) to minimize Z = . . . subject to . . .?
Hà Văn Hiếu (UEL) Operations Research 6th October 2024 7 / 31
 In terms of LPP

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 8 / 31

 A corresponding Excel sheet

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 9 / 31

 The (balanced) Transportation problem Model
Definition
A transportation problem is concerned with distributing any commodity from any group
of supply centers, called sources, to any group of receiving centers, called destinations, in
such a way as to minimize the total distribution cost.

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 10 / 31

 Assumptions of Transportation problems

The requirements assumption: Each source has a fixed supply of units, where this
entire supply must be distributed to the destinations. Similarly, each destination has a
fixed demand for units, where this entire demand must be received from the sources.
The cost assumption: The cost of distributing units from any particular source to
any particular destination is directly proportional to the number of units distributed.
Therefore, this cost is just the unit cost of distribution times the number of units
distributed.

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 11 / 31

 LPP model of a Transportation problem

m P
P n
Minimize Z= cij xij
i=1 j=1
subject to
n
P
xij = si for i = 1, 2, . . . , m
j=1
Pm
xij = dj for j = 1, 2, . . . , n
i=1
xij ≥ 0 for all i, j

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 12 / 31

 Two properties

Integer solutions property: For transportation problems where supplies and

demands of units (s1 , s2 , . . . , sm and d1 , d2 , . . . , dn ) have an integer value, all the basic
variables (allocations) in every basic feasible (BF) solution (including an optimal one)
also have integer values.
The feasible solutions property: A balanced transportation problem will have
feasible solutions if and only if
m
X n
X
si = dj .
i j

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 13 / 31

 Unbalanced transportation problems

Definition
An unbalanced transportation problem is a transportation problem which has excess
supply capacity/excess demand capacity.

This problem can be reformulated into a balanced problem by adding dummy source and
dummy destination.

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 14 / 31

 Solving Transportation problems

Step 1: Constructing an Initial BF Solution.

Northwest corner rule.
Least Cost Method.
Vogel’s approximation method.
Step 2: Determine an optimal BF solution from an initial BF solution.
Transportation Simplex method.
Stepping-stone Solution method.
Modified Distribution Method.

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 15 / 31

 Transportation Table

To A B C Supply
From

6 8 10
1 150

7 11 11
2 175

4 5 12
3 275

Demand 200 100 300 600

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 16 / 31

 Northwest Corner rule
Rule: Distribute as much as possible to the northwest corner of the table.

To A B C Supply
From

6 8 10
1 150

7 11 11
2 175

4 5 12
3 275

Demand 200 100 300 600

 Northwest Corner rule
Rule: Distribute as much as possible to the northwest corner of the table.

To A B C Supply
From

6 8 10
1 150
150
7 11 11
2 175

4 5 12
3 275

Demand 200 100 300 600

 Northwest Corner rule
Rule: Distribute as much as possible to the northwest corner of the table.

To A B C Supply
From

6 8 10
1 150
150
7 11 11
2 175
50
4 5 12
3 275

Demand 200 100 300 600

 Northwest Corner rule
Rule: Distribute as much as possible to the northwest corner of the table.

To A B C Supply
From

6 8 10
1 150
150
7 11 11
2 175
50 100
4 5 12
3 275

Demand 200 100 300 600

 Northwest Corner rule
Rule: Distribute as much as possible to the northwest corner of the table.

To A B C Supply
From

6 8 10
1 150
150
7 11 11
2 175
50 100 25
4 5 12
3 275

Demand 200 100 300 600

 Northwest Corner rule
Rule: Distribute as much as possible to the northwest corner of the table.

To A B C Supply
From

6 8 10
1 150
150
7 11 11
2 175
50 100 25
4 5 12
3 275
275
Demand 200 100 300 600

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 17 / 31

 The Least Cost method
Rule: Distribute as much as possible to the least cost cell.

To A B C Supply
From

6 8 10
1 150

7 11 11
2 175

4 5 12
3 275

Demand 200 100 300 600

 The Least Cost method
Rule: Distribute as much as possible to the least cost cell.

To A B C Supply
From

6 8 10
1 150

7 11 11
2 175

4 5 12
3 275
200
Demand 200 100 300 600
 The Least Cost method
Rule: Distribute as much as possible to the least cost cell.

To A B C Supply
From

6 8 10
1 150

7 11 11
2 175

4 5 12
3 275
200 75
Demand 200 100 300 600
 The Least Cost method
Rule: Distribute as much as possible to the least cost cell.

To A B C Supply
From

6 8 10
1 150
25
7 11 11
2 175

4 5 12
3 275
200 75
Demand 200 100 300 600
 The Least Cost method
Rule: Distribute as much as possible to the least cost cell.

To A B C Supply
From

6 8 10
1 150
25 125
7 11 11
2 175

4 5 12
3 275
200 75
Demand 200 100 300 600
 The Least Cost method
Rule: Distribute as much as possible to the least cost cell.

To A B C Supply
From

6 8 10
1 150
25 125
7 11 11
2 175
175
4 5 12
3 275
200 75
Demand 200 100 300 600

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 18 / 31

 Vogel’s approximation method
Rule: For each row and column remaining under consideration, calculate its difference,
which is defined as the difference between the smallest and next-to-the-smallest unit cost
still remaining in that row or column. In that row or column having the largest difference,
select the variable having the smallest remaining unit cost.
To A B C Supply
From
6 8 10
1 150

7 11 11
2 175

4 5 12
3 275

Demand 200 100 300 600

 Vogel’s approximation method
Rule: For each row and column remaining under consideration, calculate its difference,
which is defined as the difference between the smallest and next-to-the-smallest unit cost
still remaining in that row or column. In that row or column having the largest difference,
select the variable having the smallest remaining unit cost.
To A B C Supply
From
6 8 10
1 150 2

7 11 11
2 175 4

4 5 12
3 275 1

Demand 200 100 300 600

 Vogel’s approximation method
Rule: For each row and column remaining under consideration, calculate its difference,
which is defined as the difference between the smallest and next-to-the-smallest unit cost
still remaining in that row or column. In that row or column having the largest difference,
select the variable having the smallest remaining unit cost.
To A B C Supply
From
6 8 10
1 150 2

7 11 11
2 175 4
175
4 5 12
3 275 1

Demand 200 100 300 600

 Vogel’s approximation method
Rule: For each row and column remaining under consideration, calculate its difference,
which is defined as the difference between the smallest and next-to-the-smallest unit cost
still remaining in that row or column. In that row or column having the largest difference,
select the variable having the smallest remaining unit cost.
To A B C Supply
From
6 8 10
1 150 2

7 11 11
2 175 4
175
4 5 12
3 275 1
100
Demand 200 100 300 600
 Vogel’s approximation method
Rule: For each row and column remaining under consideration, calculate its difference,
which is defined as the difference between the smallest and next-to-the-smallest unit cost
still remaining in that row or column. In that row or column having the largest difference,
select the variable having the smallest remaining unit cost.
To A B C Supply
From
6 8 10
1 150 2

7 11 11
2 175 4
175
4 5 12
3 275 1
25 100
Demand 200 100 300 600
 Vogel’s approximation method
Rule: For each row and column remaining under consideration, calculate its difference,
which is defined as the difference between the smallest and next-to-the-smallest unit cost
still remaining in that row or column. In that row or column having the largest difference,
select the variable having the smallest remaining unit cost.
To A B C Supply
From
6 8 10
1 150 2

7 11 11
2 175 4
175
4 5 12
3 275 1
25 100 150
Demand 200 100 300 600
 Vogel’s approximation method
Rule: For each row and column remaining under consideration, calculate its difference,
which is defined as the difference between the smallest and next-to-the-smallest unit cost
still remaining in that row or column. In that row or column having the largest difference,
select the variable having the smallest remaining unit cost.
To A B C Supply
From
6 8 10
1 150 2
150
7 11 11
2 175 4
175
4 5 12
3 275 1
25 100 150
Demand 200 100 300 600
Hà Văn Hiếu (UEL) Operations Research 6th October 2024 19 / 31
 Transportation Simplex method

Team-work
Given a Linear Programming model of a balanced transportation problem which has m
sources and n destinations.
1 Are the constraints linearly independent?
2 If not, then calculate its rank.
3 Let (x0 , x1 , . . . , xmn ) be a feasible BF solution. How many indices i such that xi ̸= 0?
4 Use Excel-solver to solve the above problems.

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 20 / 31

 The stepping-stone solution method - idea

Step 1: Find an initial BF solution.

Step 2: Calculate the improvement indices I associated to unoccupied cells (and a
(closed) loop).
Optimal test: If all the indices are all non-negative, then the current solution is
optimal.
Construct a better BF solution: If there is a negative index, then select the
smallest one (associated with an unoccupied cell and a loop). In that loop, distribute
as much as possible to the corresponding unoccupied cell.

Remark
The prerequisite condition to solve for the optimality is to ensure that the number of
occupied cells is exactly equal to m + n − 1.

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 21 / 31

 Improvement Indices - constructing a closed Loop
We firstly need to create a closed loop such that:
Cells are selected in a sequence such that one cell is unoccupied, and all other cells
are occupied.
A pair of consecutive occupied cells lies either in the same row or the same column.
No three consecutive occupied cells can either be in the same row or column.
Only horizontal and vertical movement is allowed.

Example

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 22 / 31

 Calculating the Improvement Indices

Step 1: Once the loop (with a corresponding unoccupied cell) is created, assign "+"
or "−" sign alternatively to each corner cell of the loop, but begin with the "+" sign
for the unoccupied cell.
Step 2: The corresponding improvement index of the unoccupied cell is defined as the
sum of all the unit costs on the loop multiplied with the signs determined in Step 1.

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 23 / 31

 Calculating the Improvement Indices - Example

To A B C Supply
From
+ 6 − 8 10
1 150
25 125
7 11 11
2 175
175
− 4 + 5 12
3 275
200 75
Demand 200 100 300 600

Unoccupied cell A closed loop The improvement index

1A 1A-1B-3B-3A 6 − 8 + 5 − 4 = −1
Hà Văn Hiếu (UEL) Operations Research 6th October 2024 24 / 31
 The Stepping-stone solution method - Optimal test

Step 1: Find an initial BF solution.

Step 2: Draw closed loops from all unoccupied cells.
Step 3: If all the improvement indices are ≥ 0, an optimal solution has been reached.
If not, then select the closed loop having the smallest index.
Step 4: Select minimum allocated value among all negative position "−" on closed
path. Assign this value to the selected unoccupied cell (So unoccupied cell becomes
occupied cell). Add this value to the other occupied cells marked with "+" sign.
Subtract this value to the other occupied cells marked with "−" sign.
Step 5: Repeat step 2 to step 4 until optimal solution is obtained. This procedure
stops when all improvement indices are non-negative for unoccupied cells.

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 25 / 31

 Calculating the improvement indices Iij

To A B C Supply
From
+ 6 − 8 10
1 150
25 125
7 11 11
2 175
175
− 4 + 5 12
3 275
200 75
Demand 200 100 300 600

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 26 / 31

 Calculating the improvement indices Iij

To A B C Supply
From
6 − 8 + 10
1 150
25 125
7 + 11 − 11
2 175
175
4 5 12
3 275
200 75
Demand 200 100 300 600

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 26 / 31

 Calculating the improvement indices Iij

To A B C Supply
From
6 + 8 − 10
1 150
25 125
7 11 11
2 175
175
4 − 5 + 12
3 275
200 75
Demand 200 100 300 600

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 26 / 31

 Calculating the improvement indices Iij (2)
To A B C Supply
From
+ 6 − 8 10
1 150
25 125
7 11 11
2 175
175
− 4 + 5 12
3 275
200 75
Demand 200 100 300 600

Cell Closed loop Improvement index

1A 1A-1B-3B-3A 6 − 8 + 5 − 4 = −1

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 27 / 31

 Calculating the improvement indices Iij (2)
To A B C Supply
From
6 − 8 + 10
1 150
25 125
7 + 11 − 11
2 175
175
4 5 12
3 275
200 75
Demand 200 100 300 600

Cell Closed loop Improvement index

1A 1A-1B-3B-3A 6 − 8 + 5 − 4 = −1
2B 2B-2C-1C-1B 11 − 11 + 10 − 8 = 2
Hà Văn Hiếu (UEL) Operations Research 6th October 2024 27 / 31
 Calculating the improvement indices Iij (2)
To A B C Supply
From
6 + 8 − 10
1 150
25 125
7 11 11
2 175
175
4 − 5 + 12
3 275
200 75
Demand 200 100 300 600

Cell Closed loop Improvement index

1A 1A-1B-3B-3A 6 − 8 + 5 − 4 = −1
2B 2B-2C-1C-1B 11 − 11 + 10 − 8 = 2
Hà Văn Hiếu (UEL) 3C 3C-1C-1B-3B
Operations 12 − 10 + 8 − 5 = 5
Research 6th October 2024 27 / 31
 Constructing a better BF solution

1 There is only one negative index. So select unoccupied cell 1A.

2 In the loop 1A-1B-3B-3A, the cells assigned "−" are 1B and 3A which have
corresponding allocated values 25 and 200, respectively. Select cell with smallest
allocated value. In this case, the selected cell is 1B.
3 The cells assigned "+" will be added by the smallest value above. While the cells
assigned "−" will be subtracted by that value. In this case, the cells 1A and 3B will
be added by 25. While the cells 1A and 3B will be subtracted by 25.
4 The new solution determined above is a BF solution, and it is better than the
previous solution.

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 28 / 31

 Constructing a better BF solution

To A B C Supply
From
6 8 10
1 150
25 125
7 11 11
2 175
175
4 5 12
3 275
200 75
Demand 200 100 300 600

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 29 / 31

 Constructing a better BF solution

To A B C Supply
From
6 8 10
1 150

7 11 11
2 175

4 5 12
3 275

Demand 200 100 300 600

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 29 / 31

 Constructing a better BF solution

To A B C Supply
From
+ 6 − 8 10
1 150

7 11 11
2 175

− 4 + 5 12
3 275

Demand 200 100 300 600

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 29 / 31

 Constructing a better BF solution

To A B C Supply
From
6 8 10
1 150
25 125
7 11 11
2 175
175
4 5 12
3 275
175 100
Demand 200 100 300 600

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 29 / 31

 Constructing a better BF solution

To A B C Supply
From
6 8 10
1 150
25 125
7 11 11
2 175
175
4 5 12
3 275
175 100
Demand 200 100 300 600

Group working: Determine whether the above BF solution is optimal. If not, use the
stepping-stone method to find an optimal solution.
Hà Văn Hiếu (UEL) Operations Research 6th October 2024 29 / 31
 Projects

Exercises: 9.1-2, 3, 4, 5, 6, 7
Projects
1 Fuzzy Transportation problems and Applications.
2 New method(s) to find an initial BF solution of a Transpiration problem (must be
different from those 3 methods presented in this presentation).
3 The dual of transportation problems and sensitivity analysis.

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 30 / 31

 Any question?

Thank you!

Hà Văn Hiếu (UEL) Operations Research 6th October 2024 31 / 31