Solving the Classic Transportation Problem withthe Geographic Information Systems:
A Test of Starting Procedures
Uchit Patel
Master’s Degree in Geographic Information Science
Summer 2006
07/31/2006
Abstract:
Intro: Simplex algorithms can be specialized to solve several linear programming models that arise from network flow problems.
Problem Statement: Solve Classic Transportation Problem in GIS Environment.
Literature Review:Formulation of Classic Transportation Problem,Different methods to solve the Classic Transportation Problem.
Methods: Different algorithms will be implemented for solving initial basic feasible solutions and optimal solution in ArcGIS softwareenvironment using VBA and ArcObjects.
Results: Application in ArcGIS environment from which user can select any network, sources and destinations and get transportation solution for different initial solutions and optimal solution.
Keywords:
Classictransportation problem(CTP), Linear Programming(LP),Northwest corner method(NWCM), Least cost method(LCM), Stepping Stone Method, Geographic information systems
Introduction:
Transportation is one of the very important, big and growing fields of GIS. Network analysis is an important sub-discipline within the field of Transportation GIS. There are well-developed methods within network analysis to determine solutions to a wide range of problems regarding the management of products, facilities or vehicles over a network. But these methods are not used in the Network GIS. Unfortunately very few of the methods that have been developed in Network GIShave been implemented in the software of GIS. In order to address one such deficiency, this project seeks to implement Classic Transportation Problem within ArcGIS environment.
One important application of Linear Programming has been in the area of physical distribution (Transportation) of resources from one place to another, to meet a specific set of requirements. It is easy to express a transportation problem mathematically in terms of an LP model, which can be solved by the Simplex Method. Since transportation problem involves a large number of variables and constraints, it takes a very long time to solve it by simple Simplex Method. Simplex algorithms can be specialized to solve several linear programming models that arise from Network flow problems.
What is the Classic Transportation Problem (CTP)?
Suppose we have bunch of stuff at a bunch of places (supply constraints) and we have to deliver the stuff to a bunch of places (demand constraints). We have to minimize our cost in delivering stuff while delivering across a network.
Applications of the CTP
Factories to Warehouses (Nabisco)
Warehouses to Retail Stores
Cash flow models (GM)
Cloth inventory to Sewing line (Farah Manufacturing)
Logs to Mills to Finishing Lines to Markets (Weyerhauser Lumber)
Cotton planting, picking, storing, distribution to gins (NM Dept. of Ag.)
Assigning personnel to sea and shore duty (U.S. Navy)
In the problem statement section, Introduction to CTP, How to formulate CTP as Linear Programming Problem, How to solve Linear Programming Problem is covered in detail. This section also includes a description of the basic steps of the algorithms to be implemented and an explanation of how they allocate resources to demands. In the Literature Review section previous research in the field of CTP is explained. The Data Description section shows the data that has been used to test the performance of the final application. The Methods of Analysis section explains how the analysis and the implementation took place. The Results section shows the results from the analysis and finally the Conclusion and Future Research section states the additional research question and extensions to the present work.
Problem Statement:-
The Classic Transportation problem applies to situations in which a single product is to be transported from several sources to several sinks.
Let there be m sources s1, s2, _ _, sm having ai (i = 1,2,_ _, m) units of supplies or capacity respectively to be transported among n destinations having bj (j = 1,2,_ _,n) units of requirements respectively.
We can set this up as a linear programming problem using the same (or similar) language that we used for the Traveling Salesman Problem
Since we are trying to minimize the transport cost we know that the “sense of optimization” is to minimize.
–Let Z denote total transportation cost
–Let xijdenote the no. of truckloads to be shipped from canneryi to warehousej.
–Let cij denote the cost of shipping a truckload from cannery i to warehouse j.
–The general form of the objective function is then
–Where m is the number of supply centers and n is the number of demand points
–The specific instance of the objective function for our example is
We also have constraints on our supplies and demands
- For each demand location we have to deliver exactly the amount
Demanded
- In our example we would have four of these demand constraints:
(1)We can’t truck negative truckloads of merchandise
Although this isn’t part of the formulation we must ensure that our supply
equals our demand.
- If this isn’t really true we can fudge it:
Add “dummy” locations
Take up the extra supply or give the extra demand
The cost to get to dummy locations is VERY high
(2)Integer Solutions Property
- For transportation problems where every si and djhas an integer value, all
the basic variables (allocations) in every basic feasible solution (including
an optimal one) also have integer values.
- We don’t need integer constraints
(3)Feasible solutions property
- As long as supply equals demand (as stated above) there will be feasible
solutions
(4)The CTP formulation is a linear program
- Each function is a linear function
- There are many variables
Each variable is plotted along an axis that is perpendicular to all other axes
More than 3 axes can’t exist in practical reality, only as a theoretical
construct
- The constraint lines form the boundary of the feasible region
- The optimal solution lies within the feasible region
Linear Programming problems can be solved either graphically or algebraically.
However, a problem with more than three dimensions is cumbersome to graph. Ingeneral, LP problems are solved by a technique called the Simplex Method.
A graphical method of solving an LP problem has the following steps:
1. Determination of the Feasible Solution Space:
First, the non-negativity constraints are accounted for. In figure , the horizontal axis
X and the vertical axis Y represent the exterior and interior- point variables,
respectively. Therefore, it restricts the solution space to the first quadrant.
Figure
To account for the remaining constraints, first, the inequality is removed by an
equation and then the equation is graphed. After all the constraints are accounted
for, a solution space is located and is shaded. This solution space defined by the
constraints is called the set of feasible solutions.
Source:Tapojit Kumar and Susan M. Schilling. Comparison of Optimization Techniques In Large Scale Transportation Problems
2. Determination of the Optimum Solution:
An optimum solution exists at a corner point of the solution space. In figure, the
corresponding corner points are (0, 0), (X1, Y1), (X2, Y2), and (X3, Y3). To find the
optimal value, first, all these corner points are measured and the values are inserted
in the objective function. Then, the obtained values from the objective function are
compared and the lowest value (since it is a minimization problem) is determined to
be the optimum solution.
The Simplex method is a method of solving linear programs
- Starts with a basic feasible solution
- Give values to variables that don’t violate constraints
- Iteratively improves on (makes changes to) that solution until the optimal
solution is found
- The transportation simplex method is a modification of the simplex method that
takes advantage of certain characteristics of the CTP and related problems.
A typical transportation problem is shown in Fig. 1. It deals with sources where a supply of some commodity is available and destinations where the commodity is demanded. The classic statement of the transportation problem uses a matrix with the rows representing sources and columns representing destinations. The algorithms for solving the problem are based on this matrix representation. The costs of shipping from sources to destinations are indicated by the entries in the matrix. If shipment is impossible between a given source and destination, a large cost of M is entered. This discourages the solution from using such cells. Supplies and demands are shown along the margins of the matrix. As in the example, the classic transportation problem has total supply equal to total demand.
Figure 1. Matrix model of a transportation problem.
The network model of the transportation problem is shown in Fig. 2. Sources are identified as the nodes on the left and destinations on the right. Allowable shipping links are shown as arcs, while disallowed links are not included.
Figure 2. Network flow model of the transportation problem.
Only arc costs are shown in the network model, as these are the only relevant parameters. All other parameters are set to the default values. On each supply node the positive external flow indicates supply flow entering the network. On each destination node a demand is a negative fixed external flow indicating that this amount must leave the network.
Variations of the classical transportation problem are easily handled by modifications of the network model. If links have finite capacity, the arc upper bounds can be made finite. If supplies represent raw materials that are transformed into products at the sources and the demands are in units of product, the gain factors can be used to represent transformation efficiency at each source. If some minimal flow is required in certain links, arc lower bounds can be set to nonzero values.
Source: ransportation.html
- Overview of the solution process
- Set up the transportation simplex tableau
- Initialize the problem with any feasible solution by Northwest corner
Method orLeast cost method.
- Iterate
(1) Compute optimal solution by Stepping Stone Method
(2) Test for optimality
(A) If optimal, Stop.
(B) If not optimal, make changes to the solution, and go to
Step 1
- What is the Simplex Tableau?
- It is a way of visualizing our problem to assist in finding the optimal
solution
- Problem Title (Rental Car Problem)
- One row for each Supply location
- One column for each Destination location
- Supply and Demand Totals
- Supply = Demand
- What are the empty boxes in the middle?
- Each empty box in the center represents a decision variable xij
- The empty box holds two things:
Cost and
Either a Basic or a Non-Basic Variable value
- Costs are easy…they are constants
- Make little boxes in the upper left corner of the ij cells
- Put the given cij values in the little boxes
- The variable values are harder
- xij variables with an assignment are called basic variables
- A basic variable is being used to send some stuff from a supply to a
demand
- Basic variables ALWAYS have a circle around them
- You will (MUST) always have m+n-1 basic variables
- xij variables without an assignment are called non-basic variables
Non-Basic variable values represents the rate at which the objective function would change IF some stuff went from this supply to this demand
Non-Basic variables values NEVER have a circle around them
- Use the Northwest corner method or Least Cost method to find an initial basic feasible solution:
- What is a basic solution?
A solution that makes positive assignments to xij variables
xij variables with an assignment are called basic variables
xij variables without an assignment are called non-basic variables
- What is a feasible solution?
One that doesn’t violate any constraints
This is a linear programming problem. The special structure of Transportation Problem will allow us to take a number of shortcuts. The Simplex method suggests first find the initial solution and then look for a simple “Pivot” to improve the solution. If no such improvement can be found then current solution must be optimal.
The first step in the transportation algorithm is to select an initial set of basic variables. There are (m + n -1) independent equations and hence (m + n -1) nonzero xij values in a nondegenerate basic feasible solution. There are many ways of making the choice for an initial basic.
We usedfollowing two methods for finding initial basic feasible solution.
North West Corner Method (NWCM)
If we ignore the total cost then it is trivial to find an initial feasible solution. We simply assign the first group of demand to the first supply until the capacity is exhausted, and then start assigning demand to the second supply until it too is at its capacity, and so on.
The northwest-corner method begins at the north west corner of the array. The maximum numbers of units possible are assigned to X11 consistent with row and column restrictions. That is,
X11 = min(first row constraint, first column constraint)
The source or destination whose capacity has been exhausted is eliminated from further calculation. The available capacity of the remaining source or destination involved in determining X11 is reduced by that amount. One then moves either horizontally or vertically one cell to determine the value of the second basic variable. The direction of the move is governed by whether the source or destination at the last assignment was eliminated. In the event that a source and destination are simultaneously satisfied, the next basic variable with a value zero can come from either the adjacent source or destination entry. In that case we have an initial degenerate basic feasible solution.
Flow Chart – NWCM
Least Cost Method (LCM)
TheNWCMis a quick solution to find a feasible solution. The method ignores any cost information. LCM is very similar to NWCM in that it selects one cell, saturates it and deletes a row or column. This method tries to match demand and supply with some consideration of costs.
The only difference between the least-cost method and the northwest-corner method is in
the choice of entering variables. Here, the strategy is to always select the cell with the
smallest cij value among all remaining cells as the entering cell. Ties are, as usual, broken
arbitrarily.
Flow Chart – LCM
Several other methods for constructing initial basic feasible solutions can be found. These methods offer some differences in terms of total computational effort and interms of the quality of the produced initial basic feasible solutions. In general, it is difficult
to achieve a perfect balance between effort and quality. In fact, it may not even be desirableto do so, since constructing an initial basic feasible solution is only the first phase in thesolution of a problem. In other words, it is the total solution effort for a problem thatmatters in the end. We will, therefore, not attempt to dwell upon a detailed discussion of these other methods.
From initial solution we check its optimality. An optimal solution is one in which there is no opportunity cost. That is, there is no other set of transportation routes that will reduce the total transportation cost. Stepping Stone Methodis used for this.
A little bit of reflection should convince us that the present initial feasible scenario is essentially thesame as that at the start of Phase II of the standard Simplex method. There is, however, alogistical difference, namely that the standard Simplex tableau associated with the currentsolution is not explicitly available to us. Therefore, we need to develop a different set ofprocedures for generating in formations that are necessary for the execution of the Simplexalgorithm. In particular, it is critical that we have corresponding mechanisms for conductingoptimality tests and for performing pivots.
We begin with the question of whether or not the current solution is optimal. In the
standard Simplex method, the optimality test is based on a reading of the coefficients of
the nonbasic variables in the zeroth row of the Simplex tableau; that is, it is based on a
reading of the reduced costs. Since the reduced costs are not explicitly available in a giventransportation tableau, our first task is to develop a method for (re)constructing them.
Source: ransportation.html
The reduced cost associated with a nonbasic variable is defined to be the amount
by which the objective-function value degrades if we increase (nominally) the value of thatnonbasic variable by 1 (while holding all other nonbasic variables at 0). We will apply thisdefinition to constructively generate the reduced costs associated with all nonbasic variables.
The detailed steps involved in Stepping Stone are summarized below.
(1)Determine a closed path, starting at the non basic variable being evaluated and “stepping” from boxes with assignments back to the original empty box. Right angle turns in this path are permitted only at basic variables (boxes with assignments) and at the original non basic variable. Since only the boxes at the turning points are considered to be on the closed path, both empty and assigned boxes may be skipped over. The boxes at the turning points are often called the “Stepping Stone” on the path.
(2)Beginning at the non basic variable cell being evaluated, we assign a + , and then alternate minus and plus signs at the basic variables on the corner points of the path.
(3)Sum the unit costs in the boxes with plus signs, and subtract the unit costs in the boxes with minus signs. If we are minimizing costs the result is the net change in the cost per unit from the changes made in the assignments.
(4)Repeat this procedure for each empty box in the transportation table.
If the net changes are all grater than or equal to 0, and if we are minimizing costs, we have found an optimal solution. Otherwise, we could shift units into an empty box and reduce the cost.
Iterate the same process until net changes are all grater than or equal to zero.
Flow Chart – Stepping Stone Method