The transportation problem

The goal of the transportation problem is to minimize the cost of shipping goods from origins to destinations.

If warehouses are involved, the problem is called a transshipment problem. Otherwise, it is called a transportation problem. In practice, the models to be covered are only starting points for the solution of real problems, which tend to involve many more details.

Consider the production, storage, and shipment of only one item. (Note: All numbers are fabricated for example purposes and may or may not relate to actual numbers).

Assume that plants are at the following locations.

1: Kansas City, MO
2: Houston, TX
3: Denver, CO

Each plant has an associated maximum capacity, For example, in units per month:

1: 4000
2: 5000
3: 6000

Assume that warehouses are at the following locations.

1: Knoxville, TN
2: Harrisburg, PA

In a steady state situation, the amount entering a warehouse must be equal to the amount leaving the warehouse. If the amount entering is less than the amount leaving, the warehouse will eventually become empty. If the amount entering is more than the amount leaving, the warehouse will eventually become full.

Assume that retail outlets are at the following locations.

1: Boston, MA
2: Los Angeles, CA
3: Atlanta, GA
4: Chicago, IL

Each retail outlet has an associated demand. For example, in units per month:

1: 3000
2: 4000
3: 5000
4: 3000

For simplicity, the total production, or supply, must equal the total demand. There are ways to handle situations when the supply does not equal the demand.

There is a cost per unit item shipped associated with each route from each origin to each destination. For example:

From:/To: 1: 2: 3: 4: 1: 3 6 3 6 2: 4 5 5 4 3: 5 4 7 2

The situation can be depicted with the following network diagram (omitted).

Given these constraints, how much should be shipped along each route such
that the total cost is minimized. This amount can be represented by variables
as follows. Let variable x_ij be the amount shipped from source location i to
destination location j. Thus

x11 is the amount shipped from Kansas City, MO, to Boston, MA
x12 is the amount shipped from Kansas City, MO, to Los Angeles, CA
x13 is the amount shipped from Kansas City, MO, to Atlanta, GA
x14 is the amount shipped from Kansas City, MO, to Chicago, IL
x21 is the amount shipped from Houston, TX, to Boston, MA
x22 is the amount shipped from Houston, TX, to Los Angeles, CA
x23 is the amount shipped from Houston, TX, to Atlanta, GA
x24 is the amount shipped from Houston, TX, to Chicago, IL
x31 is the amount shipped from Denver, CO, to Boston, MA
x32 is the amount shipped from Denver, CO, to Los Angeles, CA
x33 is the amount shipped from Denver, CO, to Atlanta, GA
x34 is the amount shipped from Denver, CO, to Chicago, IL

Note that if there were more than 9 locations, another method would be needed to represent variables, since, for example, variable x123 would be ambiguous. That is, does x123 represent the amount shipped from source 1 to destination 23 or from source 12 to destination 3?

The cost to be minimized is the objective function

z = 3 x11 + 6 x12 + 3 x13 + 6 x14 + 4 x21 + 5 x22 + 5 x23 + 4 x24 + 5 x31 + 4 x32 + 7 x33 + 2 x34

There is a constraint from each origin in that a plant cannot produce more than its capacity.

x11 + x12 + x13 + x14 <= 4000 x21 + x22 + x23 + x24 <= 5000 x31 + x32 + x33 + x34 <= 6000

There is a constraint to each destination in that a retail outlet has a (predicted) demand, no more and no less.

x11 + x21 + x31 = 3000 x12 + x22 + x32 = 4000 x13 + x23 + x33 = 5000 x14 + x24 + x34 = 3000

The entire problem, in "LPSolves" format, is as follows.

// File: trans-01.rlp // Title: Transportation problem // Author: Robin Snyder // Created: 1997/11/22 09:47 // Updated: 1997/11/22 09:47 title "Transporation problem" author "Robin Snyder" source "Robin Snyder" linear program var x11 "Kansas City, MO, to Boston, MA" x12 "Kansas City, MO, to Los Angeles, CA" x13 "Kansas City, MO, to Atlanta, GA" x14 "Kansas City, MO, to Chicago, IL" x21 "Houston, TX, to Boston, MA" x22 "Houston, TX, to Los Angeles, CA" x23 "Houston, TX, to Atlanta, GA" x24 "Houston, TX, to Chicago, IL" x31 "Denver, CO, to Boston, MA" x32 "Denver, CO, to Los Angeles, CA" x33 "Denver, CO, to Atlanta, GA" x34 "Denver, CO, to Chicago, IL" min 3 x11 + 6 x12 + 3 x13 + 6 x14 + 4 x21 + 5 x22 + 5 x23 + 4 x24 + 5 x31 + 4 x32 + 7 x33 + 2 x34 "transporation cost" st x11 + x12 + x13 + x14 <= 4000 "capacity of Kansas City, MO" x21 + x22 + x23 + x24 <= 5000 "capacity of Houston, TX" x31 + x32 + x33 + x34 <= 6000 "capacity of Denver, CO" x11 + x21 + x31 = 3000 "demand of Boston, MA" x12 + x22 + x32 = 4000 "demand of Los Angeles, CA" x13 + x23 + x33 = 5000 "demand of Atlanta, GA" x14 + x24 + x34 = 3000 "demand of Chicago, IL" end

The output is as follows.

LPSolves (v0.1, 08-13-97) Copyright (c) 1996 by Robin Snyder File: F:\RLP1\trans-01.rlp Time: 1997/11/22 at 09:47 Title: "Transporation problem" Author: "Robin Snyder" Source: "Robin Snyder" Variables: 1. x11 "Kansas City, MO, to Boston, MA" 2. x12 "Kansas City, MO, to Los Angeles, CA" 3. x13 "Kansas City, MO, to Atlanta, GA" 4. x14 "Kansas City, MO, to Chicago, IL" 5. x21 "Houston, TX, to Boston, MA" 6. x22 "Houston, TX, to Los Angeles, CA" 7. x23 "Houston, TX, to Atlanta, GA" 8. x24 "Houston, TX, to Chicago, IL" 9. x31 "Denver, CO, to Boston, MA" 10. x32 "Denver, CO, to Los Angeles, CA" 11. x33 "Denver, CO, to Atlanta, GA" 12. x34 "Denver, CO, to Chicago, IL" Problem: Minimize 3 x11 + 6 x12 + 3 x13 + 6 x14 + 4 x21 + 5 x22 + 5 x23 + 4 x24 + 5 x31 + 4 x32 + 7 x33 + 2 x34 "transporation cost" Such that x11 + x12 + x13 + x14 <= 4000 "capacity of Kansas City, MO" x21 + x22 + x23 + x24 <= 5000 "capacity of Houston, TX" x31 + x32 + x33 + x34 <= 6000 "capacity of Denver, CO" x11 + x21 + x31 = 3000 "demand of Boston, MA" x12 + x22 + x32 = 4000 "demand of Los Angeles, CA" x13 + x23 + x33 = 5000 "demand of Atlanta, GA" x14 + x24 + x34 = 3000 "demand of Chicago, IL" End Phase 1: A basic feasible solution has been found. Phase 2: R E S U L T S : (* = basis variable) ------------- Objective coefficient ranges: (solution unchanged) Coefficient Lower Current Upper of variable limit value limit ----------- ----- ------- ----- x11 2 3 none Kansas City, MO, to Boston, MA x12 3 6 none Kansas City, MO, to Los Angeles, CA *x13 none 3 4 Kansas City, MO, to Atlanta, GA x14 1 6 none Kansas City, MO, to Chicago, IL *x21 none 4 5 Houston, TX, to Boston, MA *x22 4 5 6 Houston, TX, to Los Angeles, CA *x23 4 5 8 Houston, TX, to Atlanta, GA x24 3 4 none Houston, TX, to Chicago, IL x31 3 5 none Denver, CO, to Boston, MA *x32 3 4 5 Denver, CO, to Los Angeles, CA x33 4 7 none Denver, CO, to Atlanta, GA *x34 none 2 3 Denver, CO, to Chicago, IL Solution (variable) results: Reduced Variable Value cost -------- ----- ------- x11 0 1 Kansas City, MO, to Boston, MA x12 0 3 Kansas City, MO, to Los Angeles, CA *x13 4000 0 Kansas City, MO, to Atlanta, GA x14 0 5 Kansas City, MO, to Chicago, IL *x21 3000 0 Houston, TX, to Boston, MA *x22 1000 0 Houston, TX, to Los Angeles, CA *x23 1000 0 Houston, TX, to Atlanta, GA x24 0 1 Houston, TX, to Chicago, IL x31 0 2 Denver, CO, to Boston, MA *x32 3000 0 Denver, CO, to Los Angeles, CA x33 0 3 Denver, CO, to Atlanta, GA *x34 3000 0 Denver, CO, to Chicago, IL Shadow Variable Value price ---------- ----- ------ $13 0 2 Slack (capacity of Kansas City, MO) *$14 0 0 Slack (capacity of Houston, TX) $15 0 1 Slack (capacity of Denver, CO) #16 0 -4 Artificial (demand of Boston, MA) #17 0 -5 Artificial (demand of Los Angeles, CA) #18 0 -5 Artificial (demand of Atlanta, GA) #19 0 -3 Artificial (demand of Chicago, IL) Right hand side ranges: (solution unchanged) Right side Lower Current Upper constraint limit value limit ----------- ----- ------ ----- 1. 4000 4000 4000 capacity of Kansas City, MO *2. 5000 5000 none capacity of Houston, TX 3. 6000 6000 6000 capacity of Denver, CO 4. 3000 3000 3000 demand of Boston, MA 5. 4000 4000 4000 demand of Los Angeles, CA 6. 5000 5000 5000 demand of Atlanta, GA 7. 3000 3000 3000 demand of Chicago, IL Objective (overall) result: Objective Value --------- ----- z 52000 transporation cost

Variations of the transportation model can be used in the following cases.

the total supply is not equal to total demand
the objective is to maximize rather than minimize
there are route capacities or route minimums
there are unacceptable routes

Draw a network representation of the following problem. Then formulate the problem as a linear programming problem. A company (with one product) has plant 1 with capacity 20, plant 2 with capacity 30, distribution center 1 with demand 24, and distribution center 2 with demand 26. The cost from plant 1 to center 1 is 5, the cost from plant 1 to center 2 is 8, the cost from plant 2 to center 1 is 4, and the cost from plant 2 to center 2 is 6. How much should be shipped from each plant to each distribution center such that the overall cost is minimized?

a. Use the Word drawing tools to draw a network representation of the problem. ( omitted)

b. In order to determine how much should be shipped along each route such that the overall cost is minimized, formulate and solve the problem as a linear programming problem using LPSolves. ( omitted)

( omitted)

The transshipment problem is a transportation problem with intermediate warehouses.

A company (with one product) has 2 plants, 2 warehouses, and 2 outlets. Plant 1 has capacity 20, plant 2 has capacity 30, outlet 1 has demand 24, and outlet 2 has demand 26. The cost (per unit shipped) from plant 1 to warehouse 1 is 5, the cost from plant 1 to warehouse 2 is 8, the cost from plant 2 to warehouse 1 is 4, and the cost from plant 2 to warehouse 2 is 6. The cost from warehouse 1 to outlet 1 is 3, the cost from warehouse 1 to outlet 2 is 4, the cost from warehouse 2 to outlet 1 is 5, and the cost from warehouse 2 to outlet 2 is 5. Draw a network representation of the problem. Then, formulate the problem as a linear programming problem to determine how much should be shipped along each route such that the overall cost is minimized?

a. Use the Word drawing tools to draw a network representation of the problem. ( omitted)

b. In order to determine how much should be shipped along each route such that the overall cost is minimized, formulate and solve the problem as a linear programming problem using LPSolves. ( omitted)

( omitted)

The transportation problem and the transshipment problem are examples of important practical problems that can involve tens, hundreds, or thousands of variables. In practice, one would create a program to extract the needed information from a database, and construct the linear program customized to the particular need.

An integer programming problem is a linear programming problem where the solutions must be integers. Although integer programming problems are of a very practical nature, one cannot just solve the corresponding linear programming problem and the convert the results to integers (e.g., via rounding).

1. Why does Federal Express (i.e., FedEx) not use the transportation model for solving its next day service? That is the overnight delivery mail is sent to Memphis, TN, every night, sorted, and shipped out the next morning.