The Tree of Hubs Location Problem

被引:120
|
作者
Contreras, Ivan [1 ]
Fernandez, Elena [1 ]
Marin, Alfredo [2 ]
机构
[1] Univ Politecn Cataluna, Dpt Estadist & Invest Operat, Barcelona, Spain
[2] Univ Murcia, Dept Estadist & Invest Operat, Murcia, Spain
关键词
Hub location; Spanning trees; Valid inequalities; SHAPED FACILITIES; NETWORK DESIGN; CUT ALGORITHM; FORMULATIONS; TRANSPORTATION; RELAXATION; BRANCH;
D O I
10.1016/j.ejor.2009.05.044
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper presents the Tree of Hubs Location Problem. It is a network hub location problem with single assignment where a fixed number of hubs have to be located, with the particularity that it is required that the hubs are connected by means of a tree. The problem combines several aspects of location, network design and routing problems. Potential applications appear in telecommunications and transportation systems, when set-up costs for links between hubs are so high that full interconnection between hub nodes is prohibitive. We propose an integer programming formulation for the problem. Furthermore, we present some families of valid inequalities that reinforce the formulation and we give an exact separation procedure for them. Finally, we present computational results using the well-known AP and CAB data sets. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码:390 / 400
页数:11
相关论文
共 50 条