Transportation Problems

Problem Statement

There are m = 3 suppliers and n = 4 destinations (points of demand). The sources are labeled as *S*_{1}, *S*_{2}, ..., *S*_{m}. The destination are labeled as *D*_{1}, *D*_{2}, ..., *D*_{n}. Each of the suppliers (*S*_{1}, *S*_{2}, ..., *S*_{m}) can ship goods to each of the consumers (*D*_{1}, *D*_{2}, ..., *D*_{n}), at a fixed unit transportation cost, *c*_{ij}, i = 1,2,...,m; j = 1,2,...,n. Decision variables *x*_{ij}, i = 1,2,...,m; j = 1,2,...,n, are the quantities of goods shipped from the suppliers to the consumers. The following models shows this problem graphically and mathematically:

Decision Goal,
Minimize: Z = 2 _{}x_{11} + 3x_{12} + 5x_{13} + 6x_{14} +2 x_{21} + 1x_{22} + 3x_{23} + 5x_{24} +3 x_{31} + 8x_{32} + 4x_{33} + 6x_{34}Supply Constraints: x_{11}+x_{12}+x_{13}+x_{14} = 5x_{21}+x_{22}+x_{23}+x_{24} = 10x_{31}+x_{32}+x_{33}+x_{34} = 15Demand Constraints: x_{11}+x_{21}+x_{31} = 12x_{12}+x_{22}+x_{32} = 8x_{13}+x_{23}+x_{33} = 4x_{14}+x_{24}+x_{34} = 6Variable Limit Constraints: All x_{ij} ≥ 0 | |

Figure 1. A graphical model for a transportation problem. |

This is a balanced problem, meaning that the total supply is equal to the total demand. A feasible solution is a combination of the non-negative shipments that exhaust the supply and satisfy the demand (meet the constraints). The optimal solution is a feasible solution that fulfills the decision goal.

Finding a Feasible Solution with the *North-West Corner Method*

It will be more convenient to present the problem in form of the *X* matrix, representing the decision variables plus two vectors, defining the supply and demand quantities. Initially, the decision variables are all set to zero (no shipment). The supply and demand quantities are at their original levels.

The set and update operations are:

*x*_{11} = min(*s*_{1}, *d*_{1}) = 5

*s*_{1} := *s*_{1} - *x*_{11} = 0

*d*_{1} := *d*_{1} - *x*_{11} = 7

Notice that notation := stands here for an update operation. It means that the new value of the left-hand side variable uses its old value that appears in the right-hand side expression.

Since*S*_{1} has no more supply, it is eliminated from further processing (this is signified by shading row *S*_{1}).

Notice that notation := stands here for an update operation. It means that the new value of the left-hand side variable uses its old value that appears in the right-hand side expression.

Since

The set and update operations are:

*x*_{21} = min(*s*_{2}, *d*_{1}) = 7

*s*_{2} := *s*_{2} - *x*_{21}= 3

*d*_{1} := *d*_{1} - *x*_{21}= 0

Since*D*_{1} is fully satisfied, it is eliminated from further processing.

Since

The set and update operations are:

*x*_{22} = min(*s*_{2}, *d*_{2}) = 3

*s*_{2} := *s*_{2} - *x*_{22} = 0

*d*_{2} := *d*_{2} - *x*_{22} = 5

Since*S*_{2} is fully commited, it is eliminated from further processing.

Since

The set and update operations are:

*x*_{32} = min(*s*_{3}, *d*_{2}) = 5

*s*_{3}_{} :=*s*_{3} - *x*_{32} = 10

*d*_{2} := *d*_{2} - *x*_{32} = 0

Since*D*_{2} (column 2) is fully satisfied, it is eliminated from further processing.

Since

The set and update operations are:

*x*_{33} = min(*s*_{3}, *d*_{3}) = 4

*s*_{3}_{} := *s*_{3}_{} - *x*_{33}= 6

*d*_{3} := *d*_{3} - *x*_{33} = 0

Since demand*D*_{3} (column 3) is fully satisfied, it is eliminated from further processing.

Since demand

The set and update operations are:

*x*_{34} = min(*s*_{3}, *d*_{4}) = 6

*s*_{3}_{}_{} :=*s*_{3}_{}_{} - *x*_{34} = 0

*d*_{4} := *d*_{4} - *x*_{34} = 0

Since demand*D*_{4} (column 4) is fully satisfied, and supply *S*_{3} (row 3) is fully committed, both the entities are closed and the problem is solved. For convenience, the unit transportion cost matrix is also shown.

Since demand

The total transportation cost for this [feasible] solution is equal 2*5 + 2*7 + 1*3 + 8*5 + 4*4 + 6*6 = 119.

Automate this procedure in Excel. Use the following start up workbook: nwc_method.xlsm.

Automate this procedure (*NWCM*) in **R**. Use the following vectors to set supply (s), demand (d), and unit transportion costs (utc):

s = c(5,10,15)

d = c(12,8,4,6)

utc = c(2,3,5,6,2,1,3,5,3,8,4,6)

Finding a Feasible Solution with the *Minimum Cost Method*

This method selects shipping routes that have the lowest unit transportation cost so far. The initial state has no shipments and all routes are available.

The set and update operations are:

*x*_{22} = min(*s*_{2}, *d*_{2})

*s*_{2} := *s*_{2} - *x*_{22}

*d*_{2} := *d*_{2} - *x*_{22}

Since*D*_{2} is fully statisfied, it is eliminated from further processing (this is signified by shading column *D*_{2}).

Since

The set and update operations are:

*x*_{11} = min(*s*_{1}, *d*_{1})

*s*_{1} := *s*_{1} - *x*_{11}

*d*_{1} := *d*_{1} - *x*_{11}

Since supply*S*_{1} is exhausted, it is eliminated from further processing (this is marked up by shading row *S*_{1}).

Since supply

The set and update operations are:

*x*_{21} = min(*s*_{2}, *d*_{1})

*s*_{2} := *s*_{2} - *x*_{21}

*d*_{1} := *d*_{1} - *x*_{21}

Since supply*S*_{2} is exhausted, it is eliminated from further processing (this is marked up by shading row *S*_{2}).

Since supply

The set and update operations are:

*x*_{31} = min(*s*_{3}, *d*_{1})

*s*_{3} := *s*_{3} - *x*_{31}

*d*_{1} := *d*_{1} - *x*_{31}

Since demand*D*_{1} is fully statisfied, it is eliminated from further processing (this is signified by shading column *D*_{1}).

Since demand

The set and update operations are:

*x*_{33} = min(*s*_{3}, *d*_{3})

*s*_{3} := *s*_{3} - *x*_{33}

*d*_{3} := *d*_{3} - *x*_{33}

Since demand*D*_{3} is fully statisfied, it is eliminated from further processing (this is signified by shading column *D*_{3}).

Since demand

The set and update operations are:

*x*_{34} = min(*s*_{3}, *d*_{4})

*s*_{3} := *s*_{3} - *x*_{34}

*d*_{4} := *d*_{4} - *x*_{34}

Since demand*D*_{4} (column 4) is fully satisfied, and supply *S*_{3} (row 3) is fully committed, both the entities are closed and the problem is solved.

Since demand

The total transportation cost for this [feasible] solution is equal 2*5 + 2*2 + 1*8 + 3*5 + 4*4 + 6*6 = 89.

Automate this procedure in Excel. Use the following start up workbook: mc_method.xlsm

Automate this procedure (*MCM*) in **R**. Use the following vectors to set supply (s), demand (d), and unit transportion costs (utc):

s = c(5,10,15)

d = c(12,8,4,6)

utc = c(2,3,5,6,2,1,3,5,3,8,4,6)

Finding an Optimal Solution

Excel workbook TransportationExampleOptimal.xlsx shows how to find the optimal solution, using Solver.

Notice the the *Minimum Cost Method* shown above provided [coincidently] the same solution.

Use the following code to solve this problem in R.

install.packages("linprog") # Skip it if this package is already installed.

library(linprog)

s = c(5,10,15) # Supply

d = c(12,8,4,6) # Demand

utc = c(2,3,5,6,2,1,3,5,3,8,4,6) # Unit Transportation cost

m = length(s)

n = length(d)

C = matrix(utc, nrow=m, ncol=n, byrow=TRUE)

sr = rep("=",m)

dr = rep("=",n)

optX = lp.transport( cost.mat=C, direction="min", row.signs=sr, row.rhs=s, col.signs=dr, col.rhs=d )

optX

Success: the objective function is 89

X = optX$solution

colnames(X) = paste("D", 1:n, sep="")

rownames(X) = paste("S", 1:m, sep="")

X

D1 D2 D3 D4 S1 5 0 0 0 S2 2 8 0 0 S3 5 0 4 6

This is it!