Solving the Transportation Problem

Minimizing the cost of transporting products from production and storage locations to demand centers is an essential part of maintaining profitability for companies who deal with product distribution. Since transportation costs are generally not controllable, minimizing total cost requires making the best product routing decisions. This essential problem was first formulated as a linear programming problem in the early 1940’s and is popularly known as the transportation problem.

In this blog, we give an overview of the transportation problem and how the transportation algorithm — as implemented in IMSL — can be used to solve different variations of the transportation problem.

What Is the Transportation Problem?

The transportation problem is a type of linear programming problem designed to minimize the cost of distributing a product from \(M\) sources to \(N\) destinations.

The transportation problem can be described using examples from many fields. One application is the problem of efficiently moving troops from bases to battleground locations. Another is the optimal assignment of agents or workers to different jobs or positions. By far the most common application is of moving goods from multiple factories to multiple warehouse locations, or from warehouses to storefronts.

Transportation Problem Example

Consider the following example:

XYZ Inc. has two factories in different locations around the country where they produce widgets. Their sales partner has three central warehouses where they ship these widgets to their various customers. The factories can produce a given number of widgets per week each and the expected demand for each warehouse is also known. There is a shipping cost from each factory to each warehouse. Which factory should produce and ship how many widgets to which warehouses to meet the demand at each location with minimal cost?

This problem statement has all the components of a typical transportation problem. The sources and destinations are generic — they could be logging sites and sawmills, factories and warehouses, warehouses and stores, bases, and battlefields, and so on.

In each case, there is some demand or need \(D\) at each of \(N\) locations, some supply \(S\) at each of \(M\) locations, and a cost, \(c\), associated with transporting (or using) one unit from a particular \(M\) location to a particular \(N\) location. There will be a total of \(M\) x \(N\) such costs.

The cost, \(c\), can be a calculation involving factors such as time, distance, material costs, and so on, but it may be any quantity that is relevant to the problem.

Once supplies, demands, and costs are known, the problem is to determine the number of units, \(x\), that should be produced and sent from each of the \(M\) supply centers to each of the \(N\) demand locations.

The total cost is the sum of all individual costs times the individual units to be produced and shipped from each supply center to each demand center. Framing this as an optimization problem, the goal is to minimize the total cost:

$$ \sum_{i=1}^M \sum_{j=1}^N c_{ij}x_{ij} $$

Simultaneously, there are some rules (constraints) that must be satisfied:

• The number of units shipped must be less than or equal to the total supply.
• The number shipped must match, or meet, the demand at each location.
• The number of units to ship must be greater than or equal to zero (no negative values).

In the case of a balanced transportation problem, for which the total demand is equal to the total supply, the constraints have the following mathematical representation:

$$ \sum_{j=1}^N x_{ij} = S_{i}, i=1, …, M $$

$$ \sum_{i=1}^M x_{ij} = D_{j}, j=1, …, N $$

$$ x_{ij} \geqslant 0, i=1 …,M, j=1 …N $$

Note that there may be cases of excess supply or excess demand leading to an unbalanced problem. This case is addressed below and can be solved similarly using dummy variables and possibly penalties for unmet demand or storage costs for excess supply.

The total cost function along with the three constraints define a well-formed linear programming (LP) optimization problem with linear constraints. It is known specifically as the balanced transportation problem.

Solving the Transportation Problem

Unlike many LP problems, the transportation problem is feasible to solve by hand using a series of tables and well-documented strategies such as the Northwest-Corner Method to find an initial basic feasible solution and then using techniques like the Least-Cost Method or the Stepping Stone Method.

Working through a problem by hand simply requires repeatedly drawing tables and manual refinement starting with an initial basic feasible solution. While it can be instructive, solving by hand is not practical or scalable for real-world problems.

For larger problems or to realize any level of scalability, a computer-based method is preferred. Spreadsheet solutions are possible as well, but often require significant rework whenever the number of supply or demand centers changes.

The IMSL Library algorithm allows users to solve problems of nearly any size with a simple programming interface. The IMSL C function is imsl_f_transport() with a short list of required arguments and a few optional arguments. Using the terminology introduced above, the calling sequence using only the required arguments is:

x = imsl_f_transport(M, N, S, D, &c[0][0], 0);

where each variable is defined as:

• x = a pointer to the solution matrix of size M x N containing the solution (the optimal routing of supply)
• M = the number of sources (supply locations)
• N = the number of sinks (demand locations)
• S = an array of size \(M\) containing the supply capacities
• D = an array of size \(N\) containing the demand requirements
• c = an array of size \(M\) x \(N\) containing the per-unit cost matrix

Want to try this for yourself? Request a free trial of IMSL C now. >>

Optional arguments to the function provide additional capabilities such as limiting the number of iterations (by default there is no limit) and output of the dual solution and total cost of the optimal routing.

The algorithm used is a revised simplex method to solve a sparse LP problem with \(M\) + \(N\) constraints and \(M\) x \(N\) variables. Further details of the algorithm can be found in chapter 5 of Sewell (2005).

Balanced Transportation Problem Example

Consider the word problem stated above again, but this time with some actual values. XYZ Inc. has two factories with weekly production rates of 40 and 20 widgets. These widgets must be shipped to three warehouses that have a demand of 25, 10, and 25 units. The cost to ship between each location is known (see the grid below). Which factory should produce and ship how many widgets to which warehouses to meet the demand at each location with minimal cost?

The standard table format of this problem is:

This table format is used throughout this paper for both the problem statement and solutions. When the upper leftmost cell is “(solution)” the contents are the solution matrix, otherwise it’s a cost matrix of specified units. The central values in the table represent the point-to-point per unit shipping cost, such that it costs $550 to ship from Factory A to Warehouse 1. Note that this is a balanced problem where the total supply of 60 units equals the total demand.

Balanced Transportation Problem Solution

The C code to solve this problem definition using the IMSL algorithm is as follows, including the optional output parameter to display the total cost:

#include <stdio.h>
#include <imsl.h>

#define NF 2
#define NW 3

int main() {
     int i, j;
     float cmin, *x;
     float fcap[NF] = { 40, 20 };
     float wdem[NW] = { 25, 10, 25 };
     float cost[NF][NW] = {
          { 550, 300, 400 },
	  { 350, 300, 100 }
     };

     x = imsl_f_transport(NF, NW, fcap, wdem, &cost[0][0],
         IMSL_TOTAL_COST, &cmin, 0);

     printf("Minimum cost is $%.2f\n", cmin);
     for (i = 0; i < NF; i++) {
          for (j = 0; j < NW; j++) {
               printf("Ship %3.0f units from factory %c to warehouse %d\n",
                    x[i * NW + j], i + 65, j + 1);
          }
     }

     imsl_free(x);
     return 1;
}

Executing the program produces the following output:

Minimum cost is $20750.00

Ship 25 units from factory A to warehouse 1
Ship 10 units from factory A to warehouse 2
Ship 5 units from factory A to warehouse 3
Ship 0 units from factory B to warehouse 1
Ship 0 units from factory B to warehouse 2
Ship 20 units from factory B to warehouse 3

Using the previous table format, replacing unit costs with the number of units gives:

This table view allows easy confirmation that the supply for each factory and the demand at each warehouse is fully satisfied.

Unbalanced Transportation Problem Example

Not every transportation is necessarily balanced. When supply exceeds demand, an alternate technique is not required, especially if there are no storage costs associated with not sending units to the destination. However, when there is excess demand, the problem statement is infeasible as there is no solution that can satisfy the demand at each destination. The IMSL algorithm will issue a warning of IMSL_INSUFFICIENT_CAPACITY if this condition is encountered, although it will still return the best solution possible. When attempting to solve an unbalanced problem, best practices dictate the use of dummy variables to take up the slack.

Consider an example of allocating rental cars. For simplicity, generic locations will be used and the cars are assumed to be fungible (any car can be substituted for any other car). There is also a storage cost to keep an unwanted car at an origin location which must be accounted for. The base problem given is: Sites A, B, and C have 8, 12, and 10 cars on site, while Destinations X, Y, and Z require 9, 7, and 11 cars respectively. The storage cost for each site is 100, 100, and 80. The cost to move the cars between sites is shown in the table:

Unbalanced Transportation Problem Solution

From this problem statement, it is clear that demand (27 cars) is less than the supply (30 cars), so three cars will need to be kept at one or more source locations. To account for this, one would add a dummy destination site with the appropriate storage cost:

In this form, the problem is balanced. Except for now including the storage cost and location of the extra supply, the solution returned from the IMSL transport function is the same in either case, thus there is no strict requirement in the algorithm for the problem to be balanced. The source code for this problem is included in Appendix A, with the solution matrix as follows, and a total cost of $12,880:

Alternatively, if a problem indicates an excess demand, a similar dummy column can be utilized, especially if there is a known cost for missing the demand (like lost revenue from dissatisfied customers). Sometimes there is no cost associated with missing demand or excess supply, and in those cases the value in the cost matrix for the dummy row or column would simply be zero.

There may also be special cases where one or more destinations cannot be reached from one or more source locations. In this case, the user should use an arbitrarily large number in the cost matrix to encourage the algorithm to allocate zero units for this unreachable condition. A value an order of magnitude or two larger than any other cost in the matrix usually suffices.

References

Sewell, Granville (2005), Computational Methods of Linear Algebra, second edition, John Wiley & Sons, New York.

Final Thoughts

In this blog, we looked at the transportation problem and demonstrated the use of the IMSL C algorithm imsl_f_transport() to solve both balanced and unbalanced transportation problems.

In our next blog, we’ll look at two special cases of the transportation problem, the assignment problem, and the transshipment problem.

Easily Solve the Transportation Problem With IMSL

Solving the transportation problem, regardless of the complexity, is much more surmountable with transportation algorithms included in IMSL.

Whether you’re working in C/C++, Fortran, Java, or Python, you can evaluate the IMSL library for your application free. Try it today via the link below.

Try IMSL Free