Lower Bounds for the Hub Location Problem

Morton O'Kelly, Darko Skorin-Kapov and Jadranka Skorin-Kapov
Additional contact information
Morton O'Kelly: Department of Geography, The Ohio State University, 1036 Derby Hall, 154 North Oval Mall, Columbus, Ohio 43210
Darko Skorin-Kapov: W. A. Harriman School for Management and Policy, State University of New York at Stony Brook, Stony Brook, New York 11794-3775
Jadranka Skorin-Kapov: W. A. Harriman School for Management and Policy, State University of New York at Stony Brook, Stony Brook, New York 11794-3775

Management Science, 1995, vol. 41, issue 4, 713-721

Abstract: 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 \alpha , 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%.

Keywords: combinatorial optimization; hub location problem; heuristic solution; lower bound (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.41.4.713 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:41:y:1995:i:4:p:713-721

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().