A STUDY OF THE BOTTLENECK SINGLE SOURCE TRANSPORTATION PROBLEM. MANAGEMENT SCIENCES RESEARCH REPORT

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)

• Corporate Authors:

  Carnegie Mellon University

  Management Sciences Research Group
  Pittsburgh, PA  United States  15213
• Authors:
  • Nagelhout, R V
  • Thompson, G L
• Publication Date: 1980-3

Media Info

• Pagination: 32 p.

Subject/Index Terms

• TRT Terms: Algorithms; Costs; Demand; Freight transportation; Heuristic methods; Integer programming; Optimization; Perishables; Queuing theory; Shipping; Supply; Transportation
• Uncontrolled Terms: Supply and demand
• Old TRIS Terms: Queueing theory
• Subject Areas: Operations and Traffic Management; Transportation (General);

Filing Info

• Accession Number: 00317673
• Record Type: Publication
• Source Agency: National Technical Information Service
• Report/Paper Numbers: MSRR-456, WP-54-79-80
• Contract Numbers: N00014-75-C-0621
• Files: TRIS
• Created Date: Jul 22 1980 12:00AM