Next: Minimum Cost Flow
Up: Other Network Models
Previous: Assignment Problem
Continuing our pea shipping example, suppose our company decided to look at using common carriers to ship our goods (common carriers are trucking companies for hire, as opposed to internal trucking divisions). Since no single trucking company serves all of our area, many shipments will need to be transfered to another truck at least once along the way. These transfers can be made at an intermediate cannery or warehouse, or be made at one of three other junctions. These are at Butte, Montana; Boise, Idaho; and Cheyenne, Wyoming. The shipping cost per truck is given in the following table:
So, for instance, peas can go from cannery 1 to warehouse 4 directly at cost 871. They can also go from cannery 1, to junction 2, to warehouse 2, and then to warehouse 4 at cost of 286+207+341 = 834.
The overall problem is to determine how the output from each cannery should be shipped to the warehouses to meet demand and minimize shipping costs.
Note that the above table does not represent a transportation problem. It is a transshipment problem. We can, however, represent any transshipment problem as an equivalent transportation problem.
The fundamental idea is to interpret the individual truck trips as being the shipment from a source to a destination. Therefore, there is both a source and a destination for all of the places in our problem. There is a source node for cannery 1 (representing everything leaving cannery 1) and a destination node (representing everything entering the node). This gives rise to the following cost table (ignore supplies and demands for now):
Impossible shipments are represented by a large cost M. Shipments from a place to itself are assigned cost 0.
The final step is to give every source node a supply and every destination node a demand. Now suppose we knew how much would be shipped through a place. If that amount was 50, then we would increase the supply for the source version of that place by 50 and we would increase the demand for the destination version of that place by 50. This would ensure that 50 units were shipped through that place.
We do not know the amount shipped through each node, but we can place an upper bound on the amount. Since it would not pay to ship something through a place twice, a safe upper bound on the amount shipped through the place is the total supply (300 in this case). This value is added to the supply or demand of each node. So if 50 flow is sent through junction 3, then 250 is sent from the source of junction 3 to the destination of junction 3 (at zero cost). In order to meet supply and demand, 50 units of flow must be sent to the demand node of junction 3, and 50 units of flow are available at the source node and must be sent somewhere else. But the flow through junction 3 can be any value from 0 to 300.
By solving this transportation problem, we get the following optimal solution:
Removing the shipments that remain in place leaves:
so only junction 2 and warehouse 3 are used to transfer goods.
General structure. The transshipment problem is concerned with how to allocate and route flow (peas in our example) from supply centers to destinations via intermediate points. In addition to transshiping flow, supply centers generate a surplus that must be distributed and each destination generates a given deficit. Intermediate points (or transshipment nodes) neither generate nor absorb flow. The total supply must equal the total demand, so dummy nodes should be added appropriately. No connection may have a capacity, and all costs should be nonnegative. This defines a transshipment problem.
Transshipment problems can be solved via a transformation to the transportation problem.
