Transportation Model

1

Transportation Problems
• Transportation Problem
– A distribution-type problem in which supplies of goods that are held at various locations are to be distributed to other receiving locations. – The solution of a transportation problem will indicate to a manager the quantities and costs of various routes and the resulting minimum cost.
– Used to compare location alternatives in deciding where to locate factories and warehouses to achieve the minimum cost distribution configuration.
– Some of the examples are: Shipment from factories to warehouses, Shipment between departments within a company, Shipment from warehouses to retailers
2

Formulating the Model
• A transportation problem
– Typically involves a set of sending locations, which are referred to as origins, and a set of receiving locations, which are referred to as destinations.
– To develop a model of a transportation problem, it is necessary to have the following information:
1. Supply quantity (capacity) of each origin.
2. Demand quantity of each destination.

3. Unit transportation cost for each origin-destination route.
3

Transportation Model Example
Harley’s Sand and Gravel Ltd. (Top soil Shipment)
Problem: How many tons of Top soil to transport from each location (Farms) to each
Project sites on a monthly basis in order to minimize the total cost of transportation ?
Top soil can be supplied from 3 different locations
Location

Monthly Supply (in Tons)

Farm A

100

Form B

200

Form C

200

Demand for each project sites is given below
Project

Monthly Demand (in Tons)

1

50

2

150

3

300

The estimated cost per ton to ship per ton of shipment to each of the possible routes are given below. To
From

Project 1

Project 2

Project 3

Farm A

4

2

8

Farm B

5

1

9

Farm C

7

6

3

Schematic of a Transportation Problem

5

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.

Rim Values

Equal Supply and
Demand

Rim Values

Transportation Table for Harley’s Sand and Gravel
(Topsoil Shipment)

7

Transportation network: LP formulation
Decisions:
Xij = the tons of top soil shipment from a source Farm i to a demand Project j.
(i = 1,2,3 & j = 1,2,3)

Objective function:
Minimize

Total Cost = ∑i ∑j cijXij

Transportation network: LP formulation
Constraints
A. Supply constraints…
From Farm A (i=1) X11+X12+X13

= 100

X21+X22+X23

From Farm B (i=2)

= 200
X31+X32+X33 = 200

From Farm C (i=3)

B. Demand constraints…
To Project 1 (j=1) X11
X12
To Project 2 (j=2)
To Project 3 (j=3)

+X21

+ X31

+X22

X13

C. Non-negativity constraints?
D. Any other constraints? Integer?

= 50

+X32

+X23

Xij >= 0

+X33

= 150
= 300

Total supply equals total demand and hence all constraints are written as equalities Input and Output Worksheet for the Transportation
(topsoil) Problem

10

Parameter Specification Screen for the Topsoil
Transportation Problem

11

Solver Options Screen

12

Solver Results

13

Answer Report for the Topsoil Transportation
Problem

14

Sensitivity Report for the Topsoil Transportation
Problem

15

Input and Output Sheet for the Revised Transportation (topsoil) Problem
When the Shipping Route between Farm B and Project 1 is Prohibited

16

Special Cases of Transportation Problems
• Maximization
– Transportation-type problems that concern profits or revenues rather than costs with the objective to maximize profits rather than to minimize costs.

• Unacceptable Routes
– Certain origin-destination combinations may be unacceptable due to weather factors, equipment breakdowns, labor problems, or skill requirements that either prohibit, or make undesirable, certain combinations (routes).

17

Special Cases of Transportation Problems
(cont’d)
• Unequal Supply and Demand
– Situations in which supply and demand are not equal such that it is necessary to modify the original problem so that supply and demand are equalized.
– Quantities in dummy routes in the optimal solution are not shipped and serve to indicate which supplier will hold the excess supply, and how much, or which destination will not receive its total demand, and how much it will be short.

– The dummy is assigned unit cost of zero for each cells.
18

The Unbalanced Transportation Model
(1 of 2)
- When demand exceeds supply a dummy row is added to the tableau.

An Unbalanced Model
(Demand > Supply)

The unit transportation cost is zero

The Unbalanced Transportation Model
(2 of 2)
- When supply exceeds demand, a dummy column is added to the tableau.

An Unbalanced Model (Supply > Demand)

The unit transportation cost is zero

Transshipment Model

21

A Network Diagram of a Transshipment Problem

22

Example
Transshipment Problem
The manager of Harley’s Sand and Gravel Pit has decided to utilize two intermediate nodes as transshipment points for temporary storage of topsoil. The revised diagram of the transshipment problem is given in previous slide
Table

Cost of Shipping One Unit from the Farms to Warehouses

Table

Cost of Shipping One Unit from the Warehouses to Projects

23

A Network Diagram of Harley’s Sand and Gravel Pit
Transshipment Example

24

Transshipment network: LP formulation

Decisions:
Xij = the shipment from a source i to a Transshipment Point j. (i = 1,2,3 & j = 4,5)
Xjk = the shipment from Transshipment Point j to a demand k. (k = 6,7,8)
Objective function:

Minimize

Total Cost = ∑i ∑j cijXij + ∑j ∑k cjkXjk

Transshipment network:
LP formulation

Constraints
A. Supply constraints…
From Farm A (i=1) X14+X15

= 100
X24+X25

From Farm B (i=2)

= 200
X34+X35 = 200

From Farm C (i=3)
B. Demand constraints…
To Project 1 (k=6) X46
To Project 2 (k=7) X47
To Project 3 (k=8)

+X56

= 50

+X57

X48

= 150

+X58

C. Transshipment Balance…
X14+X24 + X34 = X46+X47 + X48
X15+X25 + X35 = X56+X57 + X58
D. Non-negativity constraints?
E. Any other constraints? Integer?

Xij >= 0

= 300

Excel Input and Output Screen for the Transshipment Problem

27

Parameter Specifications Screen for the Transshipment Problem

28

Assignment Model

29

The Assignment Model
Characteristics
• Special form of linear programming model similar to the transportation model.
• Supply at each source and demand at each destination limited to one unit (special case of the transportation problem)
• In a balanced model supply equals demand.

• In an unbalanced model supply does not equal demand. 30

Example
A manager has prepared a table that shows the cost of performing each of five jobs by each of five employees (see Table in next slide).
According to this table, job I will cost $15 if done by Al. $20 if it is done by
Bill, and so on. The manager has stated that his goal is to develop a set of job assignments that will minimize the total cost of getting all four jobs done. It is further required that the jobs be performed simultaneously, thus requiring one job being assigned to each employee.
In the past, to find the minimum-cost set of assignments, the manager has resorted to listing all of the different possible assignments
(i.e., complete enumeration) for small problems such as this one. But for larger problems, the manager simply guesses because there are too many possibilities to try to list them. For example, with a 5X5 table, there are 5!
= 120 different possibilities; but with, say, a 7X7 table, there are 7! = 5,040 possibilities. 31

Numerical Example for the
Assignment Problem

32

Excel Input and Output Worksheet for the Assignment Problem

33

Parameter Specifications Screen for the
Assignment Problem

34

Backup

35