Lower Bounds for the Hub Location Problem

We present a new lower bound for the Hub Location Problem (HLP) where distances satisfy the triangle inequality. Our lower bound is based on a linearization of the problem and its modification obtained by incorporating the knowledge of a known heuristic solution. A lower bound was computed for some standard data sets from the literature ranging between 10 and 25 nodes, with 2, 3, and 4 hubs, and for different values for the parameter α, representing the discount for the flow between hubs. The novel approach of using a known heuristic solution to derive a lower bound in all cases reduced the difference between the upper and lower bound. This difference measures the quality of the best known heuristic solution in percentages above the best lower bound. As a result of this research, for smaller problems (all instances with 10 and 15 nodes) the average difference is reduced to 3.3%. For larger sets (20 and 25 nodes) the average difference is reduced to 5.9%.