An Exact Solution Approach Based on Shortest-Paths forp-Hub Median Problems
A. T. Ernst, M. Krishnamoorthy
INFORMS Journal on Computing · 1998 · Volume 10 · Issue 2
Abstract
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.
Keywords
Facilities/equipment planning, Transportation, models, network
Enable JavaScript for citation tools and additional paper interactions.