An exact solution approach based on shortest-paths for p-hub median problems

A. T. Ernst, M. Krishnamoorthy

Research output: Contribution to journalArticleResearchpeer-review

113 Citations (Scopus)


The problem of locating hub facilities arises in the design of transportation and telecommunications networks. The p-hub median problem belongs to a class of discrete location-allocation problems in which all the hubs are fully interconnected. Nonhub nodes may be either uniquely or multiply allocated to hubs. The hubs are uncapacitated and the total number of hubs, p is specified a priori. We describe a novel exact-solution approach for solving the multiple-allocation case of the p-hub median problem and show how a similar method can be adapted for solving the more difficult single-allocation case. The methods for both of these solve shortest-path problems to obtain lower bounds, which are used in a branch-and-bound scheme to obtain the exact solution. Numerical results show the superiority of this new approach over traditional LP-based methods.

Original languageEnglish
Pages (from-to)149-162
Number of pages14
JournalINFORMS Journal on Computing
Issue number2
Publication statusPublished - Mar 1998
Externally publishedYes


  • Facilities/equipment planning
  • Models
  • Network
  • Transportation

Cite this