A Study of the Bottleneck Single Source Transportation Problem

摘要

Given a set of users with known demands, a set of suppliers with known supplies, and known costs of shipping between suppliers and users the Bottleneck Single Source Transportation is that of assigning the users to the suppliers so that the following conditions are satisfied: the demand of each user is satisfied by a single supplier; the amount supplied by each supplier does not exceed its capacity; the maximum cost of supplying any user by its unique supplier is minimal. Applications of this problem include: voter redistricting, shipping perishable goods, assignment of city blocks to emergency facilities, and others. We first discuss a heuristic method which tries to find a feasible solution by assigning the users in order of decreasing demand to the suppliers according to certain orders. In our experience on randomly generated problems, the heuristic was able to find a good, and frequently an optimal feasible solution, most of the time. If the heuristic fails to find a solution, or finds a solution which is not known to be optimal, then a branch and bound algorithm, using ordinary bottleneck transportation problems as relaxations, is employed to find the optimum single source solution. Computational experience on some randomly generated problems up to 100 x 400 is presented which indicated that these problems can be solved in less than 2 minutes. Also several small problems with real data were solved; in all but one of these problems the heuristic succeeded in finding an optimal solution. (Author)