Solving linear transport problem with lp.transport in R, using lpSolve

The transportation problem is one of the classical problems teached in linear programming classes. The problem, put simply, states that a given set of customers with a specified demand must be satisfied by another set of supplier with certain capacities (“supply”). For a detailed explanation of the transportation problem you can, e.g. read this: https://econweb.ucsd.edu/~jsobel/172aw02/notes8.pdf.

The lpSolve package available in R can be used for modelling and solving the transportation problem.

I will show how to do this. I define a problem in which 3 suppliers seek to satisfy 4 customers. The suppliers have capacities 100, 300, and 400, respectively. The customers have demand 100, 100, 200, and 400, respectively. Furthermore, the cost for supplying customer i by supplier j is defined for every possible combination and stated in a cost matrix.

Using this information we can model and solve the transportation problem (deciding which demand to fulfill by which supplier) with the lpSolve package in R.

First, I prepare the modeling-part:

library(lpSolve)

# specifying cost matrix 
cost.mat <- matrix(nrow=3,ncol=4)
cost.mat[1,] <- 1:4
cost.mat[2,] <- 4:1
cost.mat[3,] <- c(1,4,3,2)

# this is a minimization problem
direction = "min"

# capacity may not be exceeded
row.signs <- rep("<=",3)
row.rhs <- c(100,300,400)

# demand must be satisfied
col.signs <- rep(">=",4)
col.rhs <- c(100,100,200,400)

Then, I solve the problem:

# solve and assign lp object
solution <- lp.transport(cost.mat = cost.mat,
                         direction = direction,
                         row.signs = row.signs,
                         row.rhs = row.rhs,
                         col.signs = col.signs,
                         col.rhs = col.rhs)

Let us review the “optimal” costs:

solution
## Success: the objective function is 1400

Let us review the optimal solution of the transportation problem (i.e., the optimal material flows to this problem):

solution$solution
##      [,1] [,2] [,3] [,4]
## [1,]    0  100    0    0
## [2,]    0    0  200  100
## [3,]  100    0    0  300

The assignment problem is another classical problem, and you can see how I solved it in R here: Cost minimal production scheduling – solving the assignment problem with lpSolve, using lp.assign.

You May Also Like

Leave a Reply

2 comments

Andrew says:

hi.
I am trying to “go to the next level”.
I want to look deeper than this and say, “OK, truck A costs me $100 and takes 3 weeks, but flight A costs me $200 and takes just 1 week to move the good”
For me, i am still trying to move things from A to B, but now i am expanding it to try and look at the total cost of holding the inventory, reduction in cash flow and the cost of delivery. I want to “optimise” my transportation so that maybe 90% of my forecast is shipped via truck, then i can “top up” with the flight if demand requires.
Any suggestions how to approach this issue or where to turn for some guidance?
Thanks

Hi Andrew,

thanks for your comment.

You can try to formulate your problem as a linear optimization problem, from scratch. For example, the cost of holding inventory can be derived from the travel time, and the travel time depends on transportation distance (one variable) and transportation mode (binary or integer variable).

The objective of covering 90% of your forecast by truck could be formulated as a constraint, or maybe a better approach would be to define two objective functions, and to apply multi-goal linear programming.

If you provide some more info I might very well try to model it and post it, maybe in a simplified version!

BR

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.