The auction algorithm for the transportation problem

Dimitri P. Bertsekas, David A. Castanon

Research output: Contribution to journalArticlepeer-review

126 Scopus citations


The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems.

Original languageEnglish (US)
Pages (from-to)67-96
Number of pages30
JournalAnnals of Operations Research
Issue number1
StatePublished - Dec 1989
Externally publishedYes

ASJC Scopus subject areas

  • General Decision Sciences
  • Management Science and Operations Research


Dive into the research topics of 'The auction algorithm for the transportation problem'. Together they form a unique fingerprint.

Cite this