Solving Transshipment and Assignment Problems

In a previous blog, we provided an overview of the transportation problem – the problem of finding minimum cost shipping routes for products or resources between supply locations and demand locations. We also provided a little background on the algorithm for solving such problems along with several examples using an implementation in IMSL.

In this blog, we look at two special cases of the transportation problem – the transshipment problem and assignment problem.

What Is the Transshipment Problem?

The transshipment problem is a special case of the transportation problem in which shipping paths can include intermediate points. For example, shipping from Los Angeles to New York via Denver may be less expensive than shipping directly (non-stop) to New York. Intermediate points also arise when different modes of transportation are available at different costs (for example, shipping via truck versus rail) or when products must be stored for a time at intermediate points for special processing or packaging.

A table display helps illustrate the transshipment problem. In the standard table used for a transportation problem, the transshipment or intermediate points are appended to both the demand center columns and the supply center rows. For each of the transshipment points, the supply and demand are set equal to the total supply and the total demand for the problem (assuming the problem is balanced or has been balanced with dummy variables). In the cost matrix, the point-to-point costs are all still required, except that there will be zero values for the cost where the same label exists in both the supply and demand. Arbitrarily large values are used for any paths that aren’t logistically valid, for example, shipping between transshipment points. This table format is illustrated in the following example.

Transshipment Problem Example

Consider an example where wheat is harvested in Nebraska and Colorado and then must be shipped to grain elevators in Kansas City, Omaha, and Des Moines. These transshipment points then send the product along to Chicago, St. Louis, and Cincinnati.

The farms have outputs of 300 units each, while the demand is 200, 100, and 300 respectively at each destination. In this problem statement, the farms cannot ship to the endpoints directly, and the transshipment points cannot ship to each other.

Each of the point-to-point shipping costs appear in the table below. Wherever a path is not valid, a cost of 1000 is applied. In this case, the farms cannot ship directly to the destinations, and the transshipment points are not allowed to transfer between each other. For the transshipment points, which appear as both sources and destinations, there is zero cost to ship to itself.

Using the table format to formulate the problem and provide the point-to-point shipping costs gives:

Table 1: Cost Matrix for Transshipment of Wheat

The problem is balanced, noting that the transshipment points each have a supply and demand equal to the sum of the actual values, 600. The source code to solve this problem using IMSL is given in the next subsection. The solution matrix is shown below for a total cost of $12,400:

Table 2: Solution Matrix for Transshipment of Wheat

The solution indicates that the 300 units from Nebraska are shipped to Des Moines, while all 300 units from Colorado are shipped to Kansas City. Once in Kansas City, all 300 units are sent off to Cincinnati, but at Des Moines, the shipment is split with 200 heading to Chicago and 100 to St. Louis. Notice the 600 units in Omaha indicate that this point is not part of the solution as the site is meeting its (artificial) demand with its own (artificial) supply.

Solving the Transshipment Problem With IMSL

While this example is small enough to solve manually, most problems are too large to do this practically. The C code to solve this problem using IMSL is given below. Note how the inputs (the supply and demand arrays and the cost matrix) are drawn directly from Table 1. Conceptually, larger sized problems are set up in the same way.

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

#define NS 5
#define ND 6

int main() {
      float cmin, *x;
      float sup[NS] = { 300, 300, 600, 600, 600 };
      float dem[ND] = { 200, 100, 300, 600, 600, 600 };
      float cost[NS][ND] = {
             { 1000, 1000, 1000, 16, 10, 12 },
             { 1000, 1000, 1000, 15, 14, 17 },
             { 6, 8, 10, 0, 1000, 1000 },
             { 7, 11, 11, 1000, 0, 1000 },
             { 4, 5, 12, 1000, 1000, 0 }
      };

      x = imsl_f_transport(NS, ND, sup, dem, &cost[0][0],
             IMSL_TOTAL_COST, &cmin, 0);

      printf("Minimum cost is $%.2f", cmin);

      imsl_f_write_matrix("Solution Matrix", NS, ND, x,
             IMSL_NO_ROW_LABELS, IMSL_NO_COL_LABELS, 0);

      imsl_free(x);
      return 1;
}

What Is the Assignment Problem?

The assignment problem is another special case of the transportation problem. This type of problem arises when assigning workers to different tasks or, as illustrated below, assigning athletes to different legs of a relay.

Assignment Problem Example

Consider the example of a swimming relay team in the Summer Olympics. The objective is to build the best (fastest) swimming medley relay team given the four events and the times of five swimmers for each event. That is, the problem is to assign one and only one swimmer to one and only one leg of the medley relay that gives a minimum overall time. Each supply item (a swimmer) provides only one unit of supply, and each destination item (a leg of the race) demands only one unit, as shown in the following table:

Table 3 Cost Matrix for the Assignment of Swimmers

Note that swim times are measured to the tenths of a second (for example 48.1 seconds); to keep everything integer, the times have been multiplied by ten. Due to the linearity of the problem, scaling the cost matrix has no effect on the solution. With unit supply and demand across the board, the resulting solution will be mostly zeros with a value of one located for the best choice of swimmer for each leg of the medley relay.

No special formulation is required when using the IMSL transport function to solve the assignment problem. The source code is shown in the next subsection. The solution matrix is below, giving an optimal best time of 190.1 seconds.

Table 4 Solution Matrix for the Assignment of Swimmers

With this small example it’s easy to pick out a few characteristics of the solution. First, we see that swimmer E, while not the slowest in any event, is also not the fastest in any event and is not selected for the medley. Swimmer D, who is the slowest swimmer in some events, is nevertheless selected for the backstroke event because other, faster swimmers in that event are needed for other legs. In real life, the coach might average a swimmer’s last 5 times and might also consider the variation in those times. How consistently fast is a swimmer in any given event?

The idea of incorporating variation or additional uncertainties extends to any problem with respect to costs. If there is known or estimable variation in costs, how is it accounted for in the optimal solution? Similarly, how would we account for variation or uncertainties in the supplies and/or demands? These are ideas we will be exploring in future blogs on the transportation problem.

Solving the Assignment Problem With IMSL

The C code to solve this problem definition using the IMSL transport algorithm is as follows:

#include 
#include 

#define NS 5
#define ND 4

int main() {
      float cmin, *x;
      float sup[NS] = { 1, 1, 1, 1, 1 };
      float dem[ND] = { 1, 1, 1, 1 };
      float cost[NS][ND] = {
             { 479, 484, 477, 474 },
             { 481, 477, 481, 467 },
             { 486, 474, 479, 476 },
             { 483, 482, 486, 480 },
             { 485, 483, 484, 479 }
      };
      x = imsl_f_transport(NS, ND, sup, dem, &cost[0][0],
             IMSL_TOTAL_COST, &cmin, 0);

      printf("Minimum time is %.2f sec", cmin/10);

      imsl_f_write_matrix("Solution Matrix", NS, ND, x,
             IMSL_NO_ROW_LABELS, IMSL_NO_COL_LABELS, 0);

      imsl_free(x);
      return 1;
}

Final Thoughts

In this blog, we looked at the transshipment and assignment problems and described how they can be understood and solved as transportation problems.

If you missed our first blog on this topic, you can read about it here: Solving the Transportation Problem.

Easily Solve the Transshipment and Assignment Problems With IMSL

Transshipment and assignment problems along with traditional transportation problems are easily solved using the transportation algorithm 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