Original scientific paper
On Hub Location Models
Darko Skorin-Kapov
; W. A. Harriman School for Management and Policy, Stony Brook, USA
Jadranka Skorin-Kapov
; W. A. Harriman School for Management and Policy, Stony Brook, USA
Abstract
The study of hub location models involves designing communication networks where some of the nodes serve as focal points (i.e. hubs) and other nodes are connected to those hubs. Possible applications include airline traffic flow, telecommunications, and mail delivery networks. In this paper we present an overview of recent results on solvability of some hub location models. The overview includes a heuristic approach based on tabu search, lower bounds for cases where distances satisfy triangular inequality, tight linear programming relaxations, and a linkage between optimal and heuristic solutions. As a result of those studies the range of optimally solvable instances of NP-hard hub location problems was extended. In particular, well known and heavily used bench-mark data set of real world problems (Civil Aeronautics Board (CAB) data set), that has resisted efficient solutions for more than a decade, has been solved to optimality. The paper concludes with the discussion of some avenues for future research.
Keywords
Hub location; Linear programming; Integer programming; Tabu search
Hrčak ID:
150426
URI
Publication date:
30.9.1995.
Visits: 688 *