期刊名称：Journal of Computing and Information Technology
印刷版ISSN：1330-1136
电子版ISSN：1846-3908
出版年度：1995
卷号：3
期号：3
页码：183-192
语种：English
出版社：SRCE - Sveučilišni računski centar
摘要：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.
关键词：Hub location; Linear programming; Integer programming; Tabu search
