A vertex ranking algorithm for the fixed-charge transportation problem

S. Sadagopan, A. Ravindran

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


In many distribution problems, the transportation cost consists of a fixed cost, independent of the amount transported, and a variable cost, proportional to the amount shipped. In this paper, we propose an efficient algorithm for solving the fixed-charged transportation problem, based on Murty's extreme point ranking scheme. An improved lower bound on the fixed costs developed in the paper and dynamic updating of upper bound on linear costs and ranking limits are demonstrated to improve the computational requirements of Murty's scheme significantly. The ideas developed are illustrated with the aid of an example. Finally, a stopping criterion with an ∈-optimum solution is introduced using Balinski's approximation scheme.

Original languageEnglish (US)
Pages (from-to)221-230
Number of pages10
JournalJournal of Optimization Theory and Applications
Issue number2
StatePublished - Jun 1982

All Science Journal Classification (ASJC) codes

  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'A vertex ranking algorithm for the fixed-charge transportation problem'. Together they form a unique fingerprint.

Cite this