Uncapacitated single and multiple allocation p-hub center problems

被引：101

作者：

Ernst, Andreas T. ^{[2
]}

Hamacher, Horst ^{[3
]}

Jiang, Houyuan ^{[1
]}

Krishnamoorthy, Mohan ^{[2
]}

Woeginger, Gerhard ^{[4
]}

机构：

[1] Univ Cambridge, Judge Business Sch, Cambridge CB2 1AG, England

[2] CSIRO Math & Informat Sci, Clayton, Vic 3169, Australia

[3] Univ Kaiserslautern, Fachbereich Math, D-67653 Kaiserslautern, Germany

[4] TU Eindhoven, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands

来源：

COMPUTERS & OPERATIONS RESEARCH | 2009年 / 36卷 / 07期

关键词：

Facility planning and design; Hub center; NP-hard Heuristic; LOCATION-PROBLEMS; NETWORK; FORMULATIONS; ALGORITHM;

D O I：

10.1016/j.cor.2008.08.021

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The hub median problem is to locate hub facilities in a network and to allocate non-hub nodes to hub nodes such that the total transportation cost is minimized. In the hub center problem, the main objective is one of minimizing the maximum distance/cost between origin destination pairs. In this paper, we study uncapacitated hub center problems with either single or multiple allocation. Both problems are proved to be NP-hard. We even show that the problem of finding an optimal single allocation with respect to a given set of hubs is already NP-hard. We present integer programming formulations for both problems and propose a branch-and-bound approach for solving the multiple allocation case. Numerical results are reported which show that the new formulations are superior to previous ones. (C) 2008 Elsevier Ltd. All rights reserved.

引用

页码：2230 / 2241

页数：12

共 25 条

[11] Ernst A. T., 1998, INFORMS Journal on Computing, V10, P149, DOI 10.1287/ijoc.10.2.149
[12] Ernst A. T., 1996, Location Science, V4, P139, DOI 10.1016/S0966-8349(96)00011-3
[13] Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem
Ernst, AT
Krishnamoorthy, M
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 104 (01) : 100 - 112
[14] A NEW SET OF SPATIAL-INTERACTION MODELS - THE THEORY OF COMPETING DESTINATIONS
FOTHERINGHAM, AS
[J]. ENVIRONMENT AND PLANNING A-ECONOMY AND SPACE, 1983, 15 (01): : 15 - 36
[15] HAMACHER H, 2006, 98 TU KAIS FB MATH
[16] Adapting polyhedral properties from facility to hub location problems
Hamacher, HW
Labbé, M
Nickel, S
Sonneborn, T
[J]. DISCRETE APPLIED MATHEMATICS, 2004, 145 (01) : 104 - 116
[17] Juette S., 2007, 109 TU KAIS FB MATH
[18] The latest arrival hub location problem
Kara, BY
Tansel, BÇ
[J]. MANAGEMENT SCIENCE, 2001, 47 (10) : 1408 - 1420
[19] On the single-assignment p-hub center problem
Kara, BY
Tansel, BÇ
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 125 (03) : 648 - 655
[20] New formulations for the uncapacitated multiple allocation hub location problem
Marín, A
Cánovas, L
Landete, M
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 172 (01) : 274 - 292

← 1 2 3 →