AM-42 - The Classic Transportation Problem

You are currently viewing an archived version of Topic . If updates or revisions have been published you can find them at .

The classic transportation problem concerns minimizing the cost of transporting a single product from sources to destinations. It is a network-flow problem that arises in industrial logistics and is considered as a special case of linear programming. The total number of units produced at each source, the total number of units required at each destination and the cost to transport one unit from each source to each destination are the basic inputs. The objective is to minimize the total cost of transporting the units produced at sources to meet the demands at destinations. The problem solution includes three basic steps: 1) finding an initial basic feasible solution, 2) checking if the current solution is optimal (with the lowest costs), and 3) improving the current solution through iteration. Modeling and solving the classic transportation problem rely strongly on network models, least-cost path algorithms, and location-allocation analysis in the field of geographic information science (GIScience). Thus, it represents a key component in the network analytics and modeling area of GIS&T.

Author and Citation Info:

Song, Y. (2017). The Classic Transportation Problem. The Geographic Information Science & Technology Body of Knowledge (4th Quarter 2017 Edition), John P. Wilson (ed.). DOI: 10.22224/gistbok/2017.4.7

This version was published on November 15, 2017.

This Topic is also available in the following editions: DiBiase, D., DeMers, M., Johnson, A., Kemp, K., Luck, A. T., Plewe, B., and Wentz, E. (2006). The classic transportation problem. The Geographic Information Science & Technology Body of Knowledge. Washington, DC: Association of American Geographers. (2nd Quarter 2016, first digital).

Topic Description:

Definitions
Modeling the Classic Transportation Problem
Solving the Classic Transportation Problem
The Classic Transportation Problem and GIS&T

1. Definitions

networks: a network may be defined as a directed graph G=(V, A) where V is the set of vertices or nodes, and A is the set of arcs or links corresponding to the feasible routes between nodes. Each arc/link is often assigned with a weight reflecting the movement cost and some additional constraints (e.g. flow capacities).

linear programming: a linear programing problem may be defined as problem of maximizing/minimizing a linear function subject to linear constraints. The constraints can be either equalities or inequalities. The linear function to be minimized/maximized is the objective function.

industrial logistics: in general, industrial logistics is the management of the resources between sources and destinations to meet demands of customers or corporations. The resources include both physical items such as food and equipment, and abstract one such as time and resource.

heuristic: a heuristic trades optimality, completeness, accuracy, and/or precision for speed while solving a problem. Based on available information, a heuristic ranks the alternatives at each step to decide which direction to follow. For instance, a greedy heuristic selects a local optimum value at each stage, attempting to find a global optimum.

2. Modeling the Classic Transportation Problem

The classic transportation problem has long been an indispensable research problem in industrial and transportation logistics. The problem is driven by the need to transport a single commodity from sources (plants and factories) to destinations (warehouses and consumer markets). The total units produced at each source, the total units required by each destination, the cost to transport one unit from each source to each destination are assumed to be known. And the objective is to minimize the total cost of shipping units from sources to meet demands at destinations. The problem is also driven by the need to move people between activity locations such as home and office. In traditional four-step models, the problem can be applied to distribute trips between origin zones and destination zones (a.k.a. trip distribution).

The classic transportation problem is a typical network problem. The sources and destinations are represented as nodes, and the transportation route from each source to each destination is represented as a link. Figure 1 represents a network model with m sources and n destination.

Transporting a commodity from sources to destination

Figure 1. Transporting a commodity from sources to destinations, a_i and b_i denote units supplied and units demanded.

The number of its supplied by source i is a_i, for i = 1, 2, ..., m. The number of units required by destination j is b_j, for j = 1, 2, ..., n. Th cost of transporting one unit along the link from source i to destination j is c_ij, and the number of units transported along the link is x_ij. The total cost of transporting units from source i to all destinations {j} is:

$\sum _{j=1}^{n}c_{ij}x_{ij}=c_{i1}x_{i1}+c_{i2}x_{i2}+...+c_{in}x_{in}, \quad for \; i=1, 2, ..., m$ Equation (1)

Similarly, the total cost of transporting units to destinations j from all sources {i} is:

$\sum_{i=1}^{m}c_{ij}x_{ij}=c_{1j}x_{1j}+c_{2j}x_{2j}+...+c_{mj}x_{mj}, \quad for \; j=1, 2, ..., n$ Equation (2)

Thus, the classic transportation problem can be formulated as a linear equation:

$\mathbf{Minimize} \quad z=\sum_{i=1}^{m}\sum_{j=1}^{n}c_{ij}x_{ij}=\sum_{j=1}^{n}\sum_{i=1}^{m}c_{ij}x_{ij}$ Equation (3)

subject to:

$\sum_{j=1}^{n}x_{ij}\leq a_i, \quad for \; i=1, 2, ..., m$ Equation (4)

$\sum_{i=1}^{m}x_{ij}\geq b_j, \quad for \; j=1, 2, ..., n$ Equation (5)

$x_{ij}\geq 0, \quad for \; i=1, 2, ..., m ; \; j=1, 2, ..., n$ Equation (6)

Equation (3) represents the total transportation cost and is the objective function of the classic transportation problem. Equation (4) indicates that the total units shipped from source i should not exceed the available units a_i at source i. Equation (5) indicates that the total units shipped to destination j should meet its demand b_j.

The network model above can be balanced or unbalanced. When the total supply at all resources, $\sum \, _{i=1}^{m}\, a_i$ is equal to the total demand at all destinations, $\large \sum \, _{j=1}^{n}\, b_j$ , the model is balanced. Otherwise, the model is unbalanced, with excess demand or excess supply. For the case of excess demand, $\sum \, _{i=1}^{m}\, a_i\: <\, \sum \, _{j=1}^{n}\, b_j$ , a dummy source is created to reflect the penalty cost, P, for every unit of unsatisfied demand. For the case of excess supply, $\sum \, _{i=1}^{m}\, a_i\: > \, \sum \, _{j=1}^{n}\, b_j$ , a dummy warehouse is created to reflect the storage cost S for every unit of surplus production.

Besides using equations, the classic transportation problem can also be formulated as matrices. Figure 2 shows a balanced network model with m source and n destinations.

Figure 2. A balanced network model formulated as a matrix.

3. Solving the classic transportation problem

The classic transportation problem can be formulated using Equations (3) to (6), which are all linear equations. Hence, the problem can be structured as a linear program and solved using the simplex method. The three steps are: 1) finding an initial basic feasible solution, 2) checking if the solution is optimal, and 3) keeping improving the solution.

3.1 Finding an initial basic feasible solution

For the balanced transportation problem, the constraints set in Equation (4) and (5) are reformulated as linear questions:

$\large \sum_{j=1}^{n}x_{ij} = a_i, \quad for \; i=1, 2, ..., m$ Equation (7)

$\large \sum_{i=1}^{m}x_{ij} = b_j, \quad for \; j=1, 2, ..., n$ Equation (8)

Since the total supply is equal to the total demand, we have:

$\large \sum_{i=1}^{m}a_i=\sum_{i=1}^{m}\sum_{j=1}^{n}x_{ij}=\sum_{j=1}^{n}\sum_{i=1}^{m}x_{ij}=\sum_{j=1}^{n}b_j$ Equation (9)

Therefore, one of the equations in the constraint set is redundant, and the total number of independent equations becomes (m + n - 1). This is because if a_i, i = 1, 2, ..., m and b_j, j = 1, 2, ..., (n-1) are specified, b_n can be calculated as $b_n = \sum \, _{i=1}^{m}\, a_i\: - \, \sum \, _{j=1}^{n-1}\, b_j$ . In a linear program, the basic variables are referred to the variables that are not zeros, and the number of basic variables in a basic feasible solution is the same as the number of independent constraint equations (Luenberger and Ye, 2015). Therefore, solutions of the balanced transportation problem should have exactly (m + n - 1) basic variables; the remaining (mn - m - n + 1) variables are non-basic variables and equal to zero.

Common methods to generate an initial basic feasible solution include: 1) northwest corner method, 2) minimum matrix method (a.k.a. least cost method), 3) row minimum or column minimum method, and 4) Vogel’s approximation method. Given the problem formulated as a matrix (see Figure 2), the northwest corner method simply starts with the northwest corner of the matrix and assign x₁₁ ; and the other three methods attempt to generate an initial solution “closer” to the optimal solution by assigning more units to matrix cells with lower costs c_ij .

Figure 3 is an example of northwest corner method. The method starts with the cell in the northwest corner from Source 1 to Destination 1, x₁₁ . Since the demand from the Destination 1 is 5 units and the supply from the Source 1 is 8 units, the cell x₁₁ takes the smaller value 5 units. Since the first row has 3 units left, the method moves one step to the east and processes the cell x₁₂ . The second column has 9 units left and the first row has 3 units; therefore, the cell x₁₂ takes the value 3 units. Now, the second column has 6 units left, so the method moves one step to the south and processes the cell x₂₂. In each of the following steps, the method moves one step to the east or south and the cell takes the smaller value left in its column and row. The method stops when it reaches the east-south corner of the matrix.

Figure 3. Finding an initial basic feasible solution using the northwest corner method.

3.2 Check optimality

Given the initial initial basic feasible solution, the next step is to check if the current solution is optimal. The optimization criteria can be formulated by defining two sets of shadow costs for the current solution {x_ij}: 1) a dispatch cost u_i to transport one unit from source i to any destination, and 2) a reception cost v_jto transport one unit to destination j from any source. These shadow costs should satisfy:

$\large c_{ij} = u_i + v_i \quad for\: x_{ij} > 0$ Equation (10)

Hence, the current solution is optimal if non-basic variables cannot offer lower costs:

$\large c_{ij} \geq u_i - v_i \quad for\: x_{ij} = 0$ Equation (11)

These optimization criteria can be implemented by determining values of {u_i} and {v_i} based on Equation (10), calculating cost differences $\large \Delta c_{ij}= c_{ij} - u_i - v_i$ for all the non-basic variables, and checking whether all $\large \Delta c_{ij}$ are non-negative. Since the number of basic variables in the basic feasible solution is (m + n - 1) and the total number of shadow prices {u_i, v_j} is (m + n), we can always find a basic solution for {u_i, v_j}. It is common to set u₁ = 0. Figure 4 shows an example based on the initial basic feasible solution in Figure 3; the price differences are placed on the left-bottom corners. Given the calculation result, the initial basic feasible solution is not optimal because the cost differences $\Delta c_{13}, \Delta c _{14}, \textup{and}\, \Delta c_{32}$ are negative.

Figure 4. Checking possible price reductions.

3.3 Improving the solution through iteration

If the current solution is not optimal, there is at least one non-basic variables x_ij = 0 with cost difference $\large \Delta c_{ij} < 0$ that can reduce the overall transportation cost of the system. A direct and possible method to improve the solution is to set the non-basic variable with the most negative $\large \Delta c_{uv}$ and increasing the corresponding shipping units x_uv as much as possible. For instance, the most negative difference is $\large \Delta c_{32}$ in Figure 4 And if x₃₂ increases by $\large \varepsilon$ , it will break the sequence used to generate the initial basic feasible solution, starting from x₂₂. Consequently, we have basic variables adjusted as $x_{22} - \varepsilon, \, x_{23} + \varepsilon,\, x_{33} - \varepsilon, x_{34}+ \varepsilon, and \, \, x_{35} - \varepsilon$ . Since we need adjusted variables to be non-negative, $\textup{max }(\varepsilon )$ = 1 is given by $x_{33} - \varepsilon = 1 - \varepsilon \geq 0$ . After adjusting the basic variables, the solution is improved and becomes current. Unless the current solution is optimal, we repeat the above improvement procedure.

Major extensions to the formulations and solutions of the classic transportation problem above are: 1) introducing intermediate transfer stops (a.k.a. network hubs) (O’Kelly and Miller, 1994), 2) considering changes in supply and demand amounts, and dynamic unit transportation costs (a.k.a. dynamic transportation problem) (Powell, et al. 1995), 3) adding constraints to reflect network and/or loading capacities (Nahmias & Cheng, 1993), and 4) setting multiple objectives beside minimizing shipping costs (Ulungu & Teghem, 1994). These extensions correspond to real-world planning and operation scenarios and improve the practical merits of the basic model; however, they also bring great challenges, especially when dealing with large networks.

Many existing software packages for optimization have linear programming solvers in them. Some packages require users to purchase licenses such as LGO (Lipschitz-continuous Global Optimizer) and MINOPT (A Modeling Language and Algorithmic Framework for Linear, Mixed-Integer, Nonlinear, Dynamic, and Mixed-Integer Nonlinear Optimization). Some packages provide free versions with limited functions and full-versions upon purchase such GAMS (General Algebraic Modeling System) and LINDO (Linear, Interactive, and Discrete Optimizer). Some are available as open-source packages such as AMPL (A Modeling Language for Mathematical Programming). For the complex problems and large network, these solvers typically apply heuristics to reduce the computational complexity. In addition, various algorithms have been employed to improve the formulation, solution and evaluation process. Some common methods are fuzzy and neuro-fuzzy methods, genetic algorithms, tabu search, and branch-and-bound approaches (Srivastava, 2007).

4. The Classic Transportation Problem and GIS&T

Geographic information systems for transportation (GIS-T) deal with information about and related to transportation systems, and have been recognized as a major application of geographic information science (GIS) (Miller and Shaw, 2001). With respect to the classic transportation problem, GIS-T provides models and algorithms for collecting, managing, analyzing, and distributing spatial information. These include, but are not limit to, collecting or estimating supplies and demands, modeling and storing the transportation networks, calculating least-cost paths for use in determining unit transportation costs, and supporting more complex analysis (e.g. dynamic costs and multi-objectives).

A few GIS software packages have linear programing solvers embedded in them (e.g. TransCAD by Caliper Corporation, CPLEX by ILOG, Xpress-MP by Dash Optimization and ArcGIS by Esri). There are some open-source GIS packages available too (such as LP-Solver by Michel Berkelaar at Eindhoven University of Technology). Although LINDO and other optimization packages are more powerful and flexible while solving linear programming, GIS packages can provide additional supports to defining and modeling the problem and communicating information. For instance, GIS software can directly show spatial distributions of the source and destination locations, and the amount of supplies and demands at those locations. This would allow visual exploration of the problem, and detection of possible errors existing in the data (e.g. incorrect locations and unrealistic total units). Another example is GIS tools that can calculate least-cost path(s) between sources and destinations, and derive the corresponding cost matrix for all sources and destinations. Compared to Euclidean distances, this distance matrix can provide more accurate estimation of shipping costs.

A special example of this type of GIS tools is the location-allocation analysis layer in the network analyst extension provided by Esri's ArcGIS. First, it allows users to import or manually locate facilities (sources) and demand points (destinations). Secondly, the tool enables users to assign or update supplies and demands at those locations. Thirdly, the underlying network can be updated to reflect the traffic situation and achievable speeds. Fourthly, the tool provides different options for problem objectives, such as minimizing impedance, maximizing coverage, and maximizing market share. Last but not the least, the results are tied to each facility and demand point, as long as links are loaded with units to be transported between sources and destinations.

The classic transportation problem in 21^st century GIScience is confronting new opportunities and challenges (Miller and Shaw 2015). First, the increasing demands on international trade and travels requires more efficient transportation systems to move people and goods globally. Secondly, the advances in information and communication technologies (ICTs) and location-aware technologies (LATs) allow us to collect large amounts of data and derive up-to-date user demands and transportation times between locations. However, the popularity of ICTs and LATs also bring new challenges to the problem. For instance, a shifted popularity toward online shopping leads to more dispersed demands, and rely more heavily on warehouses as intermediate stops for distribution.

References:

Luenberger, D. G., & Ye, Y. (2015). Linear and Nonlinear Programming (Vol. 228). Springer.

Miller, H. J., & Shaw, S. L. (2001). Geographic Information Systems for Transportation: Principles and Applications. Oxford University Press on Demand.

Miller, H. J., & Shaw, S. L. (2015). Geographic Information Systems for Transportation in the 21st Century. Geography Compass, 9(4), 180-189. DOI: 10.1111/gec3.12204

Nahmias, S., & Cheng, Y. (1993). Production and Operations Analysis (Vol. 2). Homewood, IL: Irwin.

O'Kelly, M. E., & Miller, H. J. (1994). The Hub Network Design Problem: A Review and Synthesis. Journal of Transport Geography, 2(1), 31-40.

Powell, W. B., Jaillet, P., & Odoni, A. (1995). Stochastic and Dynamic Networks and Routing. Handbooks in Operations Research and Management Science, 8, 141-295.

Srivastava, S. K. (2007). Green Supply-Chain Management: A State-Of-The-Art Literature Review. International Journal of Management Reviews, 9(1), 53-80. DOI: 10.1111/j.1468-2370.2007.00202.x

Ulungu, E. L., & Teghem, J. (1994). Multi-objective combinatorial optimization problems: A survey. Journal of Multi-Criteria Decision Analysis, 3(2), 83-104.

Learning Objectives:

Demonstrate how to model the real-world transportation problems as linear programs.
Define the classic transportation problem analytically using graphs, equations, and matrices.
Distinguish between balanced and unbalanced problems, and explain why, if supply equals demand, there will always be a feasible solution.
Delineate two major steps toward solving the classic transportation problem as linear program, and use simplex methods to get the optimal solution.
Describe the major contributions of GIS to the classic transportation problem, and new opportunities and challenges presented by the 21st century.

Instructional Assessment Questions:

In the example provided in Figure 3, suppose that the demand of destination #3 increases from 2 units to 4 units, and there is a penalty cost of 1 for each unmet unit. Use the northwest corner method to find the initial feasible solution and use the simplest method to find the optimal solution for this unbalanced problem.
Imagine that there are three local farms that provide dairy supplies to five retail stores in a metropolitan area. Each farm has a limited supply, and each store has demands based on historical records. Model this classic transportation problem using graphs, equations and matrices
If Esri's ArcGIS is available, use the location-allocation analysis to solve the above problem. Try different objectives and settings, and compare the analysis results. Otherwise, use the open-source GIS package Flowmap to create distance matrix and conduct analysis.
Think about the ridesharing services that have dynamic demands and supplies. Is it possible to model this problem as a classic transportation problem?

Additional Resources:

Robert J. V. (2013). Linear Programming: Foundations and Extensions. 4th Ed. Springer. (a website dedicated to this author: http://www.princeton.edu/~rvdb/LPbook/)

Stephen P. B., Arnolodo C. H., and Thomas L. M. (1977). Solving Linear Program, Applied Mathematical Programming, Addison-Wesley. (http://web.mit.edu/15.053/www/)

Location-allocation analysis in Esri's ArcGIS, available with Network Analyst license, (http://desktop.arcgis.com/en/arcmap/10.3/guide-books/extensions/network-analyst/location-allocation.htm)

Search form

Keywords: