The Transportation Problem Model

The Transportation Problem Model

To describe the general model for the transportation problem, we need to use terms that are considerably less specific than those for the components of the prototype example. In particular, the general transportation problem is concerned (literally or figuratively) with distributing any commodity from any group of supply centers, called sources, to any group of receiving centers, called destinations, in such a way as to minimize the total distribu- tion cost. The correspondence in terminology between the prototype example and the gen- eral problem is summarized in Table 9.4.

As indicated by the fourth and fifth rows of the table, each source has a certain supply of units to distribute to the destinations, and each destination has a certain demand for units to be received from the sources. The model for a transportation problem makes the following assumption about these supplies and demands:

The requirements assumption: Each source has a fixed supply of units, where this entire supply must be distributed to the destinations. (We let si denote the number of units being supplied by source i, for i = 1, 2, . . . , m.) Similarly, each destination has a fixed demand for units, where this entire demand must be re- ceived from the sources. (We let dj denote the number of units being received by destination j, for j = 1, 2, . . . , n.)

This assumption holds for the P & T Co. problem since each cannery (source) has a fixed output and each warehouse (destination) has a fixed allocation.

This assumption that there is no leeway in the amounts to be sent or received means that there needs to be a balance between the total supply from all sources and the total demand at all destinations.

The feasible solutions property: A transportation problem will have feasible solutions if and only if

Fortunately, these sums are equal for the P & T Co. since Table 9.2 indicates that the sup- plies (outputs) sum to 300 truckloads and so do the demands (allocations).

In some real problems, the supplies actually represent maximum amounts (rather than fixed amounts) to be distributed. Similarly, in other cases, the demands represent maxi- mum amounts (rather than fixed amounts) to be received. Such problems do not quite fit the model for a transportation problem because they violate the requirements assumption. However, it is possible to reformulate the problem so that they then fit this model by in- troducing a dummy destination or a dummy source to take up the slack between the ac- tual amounts and maximum amounts being distributed. We will illustrate how this is done with two examples at the end of this section.

The last row of Table 9.4 refers to a cost per unit distributed. This reference to a unit cost implies the following basic assumption for any transportation problem:

The cost assumption: The cost of distributing units from any particular source to any particular destination is directly proportional to the number of units distrib- uted. Therefore, this cost is just the unit cost of distribution times the number of units distributed. (We let cij denote this unit cost for source i and destination j.)

This assumption holds for the P & T Co. problem since the cost of shipping peas from any cannery to any warehouse is directly proportional to the number of truckloads being shipped.

The only data needed for a transportation problem model are the supplies, demands, and unit costs. These are the parameters of the model. All these parameters can be sum- marized conveniently in a single parameter table as shown in Table 9.5.

The model: Any problem (whether involving transportation or not) fits the model for a transportation problem if it can be described completely in terms of a parameter table like Table 9.5 and it satisfies both the requirements assump- tion and the cost assumption. The objective is to minimize the total cost of distrib- uting the units. All the parameters of the model are included in this parameter table.

Therefore, formulating a problem as a transportation problem only requires filling out a parameter table in the format of Table 9.5. (The parameter table for the P & T Co. problem is shown in Table 9.2.) Alternatively, the same information can be provided by using the network representation of the problem shown in Fig. 9.3 (as was done in Fig. 9.2 for the P & T Co. problem). Some problems that have nothing to do with trans- portation also can be formulated as a transportation problem in either of these two ways. The Solved Examples section of the book’s website includes another example of such a problem.

Since a transportation problem can be formulated simply by either filling out a para- meter table or drawing its network representation, it is not necessary to write out a for- mal mathematical model for the problem. However, we will go ahead and show you this model once for the general transportation problem just to emphasize that it is indeed a special type of linear programming problem.

Letting Z be the total distribution cost and xij (i = 1, 2, . . . , m; j = 1, 2, . . . , n) be the number of units to be distributed from source i to destination j, the linear programming formulation of this problem is

Note that the resulting table of constraint coefficients has the special structure shown in Table 9.6. Any linear programming problem that fits this special formulation is of the trans- portation problem type, regardless of its physical context. In fact, there have been numerous applications unrelated to transportation that have been fitted to this special structure, as we shall illustrate in the next example later in this section. (The assignment problem described in Sec. 9.3 is an additional example.) This is one of the reasons why the transportation problem is considered such an important special type of linear programming problem.

For many applications, the supply and demand quantities in the model (the si and dj) have integer values, and implementation will require that the distribution quantities (the xij) also have integer values. Fortunately, because of the special structure shown in Table 9.6, all such problems have the following property:

Integer solutions property: For transportation problems where every si and dj have an integer value, all the basic variables (allocations) in every basic feasible (BF) solution (including an optimal one) also have integer values.

The solution procedure described in Sec. 9.2 deals only with BF solutions, so it automatically will obtain an integer optimal solution for this case. (You will be able to see why this solution procedure actually gives a proof of the integer solutions property after you learn the procedure; Prob. 9.2-20 guides you through the reasoning involved.) Therefore, it is unnecessary to add a constraint to the model that the xij must have integer values.

As with other linear programming problems, the usual software options (Excel with either the standard Solver or ASPE, LINGO/LINDO, MPL/Solvers) are available to you for setting up and solving transportation problems (and assignment problems), as demonstrated in the files for this chapter in your OR Courseware. However, because the Excel approach now is somewhat different from what you have seen previously, we next describe this approach.