next up previous
Next: Assignment Problem Up: Examples Previous: Maximum Flow

Transportation Problem

We have already seen an example of the transportation problem: the snow removal problem without the limitation that all the snow from one area go to one disposal site is a transportation problem. In such a problem, there are a set of nodes called sources, and a set of nodes called destinations. All arcs go from a source to a destination. There is a per-unit cost on each arc. Each source has a supply of material, and each destination has a demand. We assume that the total supply equals the total demand (possibly adding a fake source or destination as needed). For the snow removal problem, the network might look like that in figure 3.

Figure 3: Snow Transportation Network

Transportation problems are often used in, surprise, transportation planning. For instance, in an application where goods are at a warehouse, one problem might be to assign customers to a warehouse so as to meet their demands. In such a case, the warehouses are the sources, the customers are the destinations, and the costs represent the per-unit transportation costs.

Michael A. Trick
Mon Nov 11 15:13:01 EST 1996