The Geography of Transport Systems
FOURTH EDITION
Jean-Paul Rodrigue (2017), New York: Routledge, 440 pages.
ISBN 978-1138669574
Linear Programming (to be changed to Location-Allocation Models)
Author: Dr. Jean-Paul Rodrigue
1. Method
Linear programming aims at minimizing an objective linear function subject to a set of constraints. This methodology has a wide array of applications. For transportation problems, it involves an assignment that considers several origins and destinations with the goal to optimize a solution at minimal cost by minimizing transport costs with fixed demand, origins and destinations. It considers linear transport costs, known surpluses (origins), demands (destinations), and possible paths. Linear programming consequently has a lot of relevance in the field of logistics, as it enables to assess an optimal distribution system that can help setting or improving a real-world distribution system. The linear programming formulation for a distribution problem is basically expressed as:
Where Q(a,b) is the traffic between origin a and destination b and g is a cost function. So g(Q(a,b)) is the transport cost related to traffic Q(a,b). The goal of this equation is to minimize the summation of transport costs of each origin-destination pair. The traffic of each pair must be superior or equal to 0 (rule of non-negativity).
2. Problem
The manager of a distribution system between factories (A, B and C) and distributors (W, X, Y and Z) wishes to minimize the global transport costs between a set of origins (factories) and destinations (distributors). Consider the following two matrices; the supply matrix:
Factories having surpluses Supply
A 400
B 1500
C 900
Total 2800
And the demand matrix:
Distributors having demands Demand
W 700
X 600
Y 1000
Z 500
Total 2800
The amount of units produced and demanded is the same, implying a market equilibrium. Any additional unit being produced would not be transported because there is no additional demand and any additional demand will not be transported because there is no additional supply. The transport cost matrix in dollars per unit transported between factories and distributors is also available:
Costs W X Y Z
A 20 40 70 50
B 100 60 90 80
C 10 110 30 200
For instance, it costs $20 to transport 1 unit from factory A to distributor W. This problem can be represented in a graphic form where each factory and distributor is a node and where each transport cost pair is a vector between a factory and a distributor.
3. Heuristic Solution
With the data provided, linear programming will find the traffic assignment having the minimal transport cost. This problem can also be solved using the "Solver" add-on in Excel. Below is the heuristic method where relatively simple problems (grids of about 5 by 5) can be solved "by hand" in several stages:
1. Cost Ranking
The first step is to order the transport costs for each cell by beginning by the lowest, which has a rank of 1, to the highest. The same rank is assigned to cells having equal costs.
  W X Y Z
A 2 4 7 5
B 10 6 9 8
C 1 11 3 12
2. Flow Assignment
Take the cell having the lowest transport cost. In this case, it is the C-W cell ($10 per unit). Assign the highest possible number of units on this cell. Subtract this number from the number of surpluses and demands for the respective row and column. Continue the same procedure by order of rank until all surpluses are used and all demands are answered (origins and destinations having 0). The result is the following assignment matrix:
  W X Y Z  
A   400     400
B   200 800 500 1500
C 700   200   900
  700 600 1000 500 2800
3. Total Transport Cost
Calculate the transport costs of this assignment by multiplying the flow of each cell in the flow assignment matrix by its related unite cost in the transport cost matrix:
  W X Y Z  
A   16,000     16,000
B   12,000 72,000 40,000 124,000
C 7,000   6,000   13,000
          153,000
The total transport cost of this assignment is $153,000.
4. Estimation Costs Matrix
To find if this assignment is the least cost distribution the estimation costs matrix must be built. This process is stepwise. First, write down the transport cost per unit in each cell that was used in step 3 and leave the other cells blank. Second, put a value of 0 to the summation of the first row (row A):
  W X Y Z Sum 
A   40     0
B   60 90 80  
C 10   30    
Sum           
Third, use the value(s) of each cell in row 1 to find the summation of each column that has a value. For this example, only cell A-W has a value (40), which means that the value 40 must be placed in the summation of column X (0 + 40 =40):
  W X Y Z Sum 
A   40     0
B   60 90 80  
C 10   30    
Sum    40       
Fourth, for the summation of remaining rows and columns enter the difference between 'column 1, row 1' and 'column 1, row n' where 'n' is the number of the current row'. For the example, the next step would be to fill the summation cell of row B with the value of 20 since cell B-X has a value of 60 and that the value of 40 is already in the summation cell of column X:
  W X Y Z Sum 
A   40     0
B   60 90 80 20 
C 10   30    
Sum    40       
Fifth, continue the procedure until all the empty cells are filled and keeping in mind that cells must be the summation of the values at the summation of their respective rows and columns. The outcome is the completed estimation costs matrix:
  W X Y Z Sum 
A 50 40 70 60 0
B 70 60 90 80 20
C 10 0 30 20 -40
Sum  50 40 70 60  
5. Cost Comparison
The next step is the comparison between the estimation costs matrix and the transport cost matrix. There can be only two alternatives to this comparison:
  • First, that the estimation costs are higher than the real costs. In this case the solution is not optimal and a readjustment is necessary.
  • Second, the estimation costs are equal or smaller than the real costs. In this case, no readjustments are necessary since the assignment is optimal and therefore a solution has been found.
In this example, cell A-W has higher estimation costs (50) than real costs (20). Cell A-Z has also higher estimation costs (60) than real costs (50). This assignment is not an optimal solution and a readjustment will thus be necessary.
6. Readjustment Cell Selection
If a readjustment is necessary, choose the cell that has the highest difference between its estimation and real costs. If two cells have equal differences, choose the cell that has the smallest real costs. In this example, it is cell A-W having a difference of 30. Cell A-Z has a difference of only 10.
7. Readjustments
Readjustments are done by transferring values between cells (partial or full flows). They are performed according to three rules.
  • First, transfers are done along a circuit from an unused cell and by altering vertical and horizontal stages and by only using occupied cells.
  • Second, each transfer is the exact opposite value of the other.
  • Third, the value of a transfer is determined by the maximum value that all cells could subtract while still respecting the supply and demand constraints. For instance, if
  W X Y Z  
A (+400) 400
(-400)
    400
B   200
(+400)
800
(-400)
500 1500
C 700
(-400)
  200
(+400)
  900
  700 600 1000 500 2800
400 is the highest readjustment possible in cell A-W because cell A-X cannot subtract more since it would exceed the supply constraint of row A (producer A produces 400 units). The new traffic assignment matrix is consequently:
  W X Y Z  
A 400       400
B   600 400 500 1500
C 300   600   900
  700 600 1000 500 2800
8. Total Transport Costs
Calculate again the costs related to this distribution (as in step 3).
  W X Y Z  
A 8,000       8,000
B   36,000 36,000 40,000 112,000
C 3,000   18,000   21,000
          141,000
The transport cost of this new assignment is $141,000, which is lower than the initial figure of $153,000.
9. Estimation Costs Matrix
Calculate again the estimation costs matrix (as in step 4):
  W X Y Z Sum 
A 20 10 40 30 0
B 70 60 90 80 50
C 10 0 30 20 -10
Sum  20 10 40 30  
10. Costs Comparison
No cell has estimation costs higher than real costs. The solution is thus optimal ($141,000 is the minimal cost) and can be represented in a graphic form.