NEW ALGORITHMS FOR ASSIGNMENT AND TRANSPORTATION PROBLEMS

A new method for solving the classical assignment problem is proposed. In some ways the algorithm resembles the Hungarian method. The worst case computational complexity of one implementation of the algorithm for full dense, all integer, NxN problems is the same as the Hungarian method. However, the average complexity of the algorithm seems to be considerably better than the Hungarian method. In a large number of randomly generated problems the algorithm has consistently outperformed an efficiently coded version of the Hungarian method by a broad margin. On heuristic grounds, it appears that the new method owes its good performance principally to a phenomenon referred to as "outpricing", a property of the method whereby during the course of the algorithm the prices of some sinks are increased by large increments, much larger than in the Hungarian method. As a consequence, these sinks are temporarily or permanently outpriced by other sinks and are, in effect, driven out of the problem in the sense that they do no get labeled and scanned further for relatively long time periods. As a result, the algorithm requires fewer row operations since it deals with a problem of lower dimension.

• Corporate Authors:

  Massachusetts Institute of Technology

  Laboratory for Information and Decision Systems
  Cambridge, MA  United States  01239

  National Science Foundation

  Engineeing and Applied Science, 1800 G Street, NW
  Washington, DC  United States  20550
• Authors:
  • Bertsekas, D P
• Publication Date: 1979-9

Media Info

• Pagination: 46 p.

Subject/Index Terms

• TRT Terms: Algorithms; Linear programming; Network analysis (Planning); Optimization; Traffic assignment; Traffic flow
• Uncontrolled Terms: Network flows
• Subject Areas: Highways; Operations and Traffic Management; I71: Traffic Theory;

Filing Info

• Accession Number: 00326910
• Record Type: Publication
• Source Agency: National Technical Information Service
• Report/Paper Numbers: LIDS-R-945, NSF/RA-790509
• Contract Numbers: NSF-ENG79-06332
• Files: TRIS
• Created Date: Feb 18 1981 12:00AM