Double-Pricing Dual and Feasible Start Algorithms for the Capacitated Transportation (Distribution) Problem

Abstract

The primary objectives of this paper are: (1) to present a simplified 'double-pricing' method for solving the capacitated transportation problem by Lemke's dual method which streamlines computer implementation; (2) to give a new and efficient method for obtaining a dual feasible starting basis; (3) to give the results of computational comparison of a code based on these developments with two widely used out-of-kilter production codes. In addition, these codes are compared against a state of the art large scale LP code, OPHELIE/LP. The study shows that the improved dual transportation algorithm is faster than the out-of-kilter codes for problems of up to 150 x 150 (origins x destinations), but tends to fall behind thereafter. The best algorithms was found to be at least 20 times faster than OPHELIE.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1972
Accession Number
AD0757985

Entities

People

  • D. Karney
  • D. Klingman
  • Fred W. Glover

Organizations

  • University of Texas at Austin

Tags

Communities of Interest

  • Air Platforms
  • Counter IED
  • Cyber

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Coefficients
  • Commerce
  • Computations
  • Computer Programming
  • Computers
  • Instructions
  • Linear Programming
  • Mathematical Programming
  • Military Research
  • Operations Research
  • Probability
  • Probability Distributions
  • Security
  • Standards
  • Transportation

Readers

  • Computer Science.
  • Operations Research