Efficient algorithms for the uncapacitated single allocationp-hub median problem

Andreas T. Ernst, Mohan Krishnamoorthy

Research output: Contribution to journalArticleResearchpeer-review

370 Citations (Scopus)


We present a new LP formulation for the single allocation p-hub median problem, which requires fewer variables and constraints than those traditionally used in the literature. We develop a good heuristic algorithm for its solution based on simulated annealing (SA). We use the SA upper bound to develop an LP-based branch-and-bound solution method. We present computational results for well-known problems from the literature which show that exact solutions can be found in a reasonable amount of computational time. We also benchmark our new solution approach on a new data set. This data set, which includes problems that are larger than those used in the literature, is based on a postal delivery network.

Original languageEnglish
Pages (from-to)139-154
Number of pages16
JournalLocation Science
Issue number3
Publication statusPublished - 1996
Externally publishedYes


  • Branch-and- bound
  • Heuristic solution
  • Hub location
  • Linear programming
  • Simulated annealing

Cite this