The capacitated single-allocation hub location problem revisited: A note on a classical formulation

被引：58

作者：

Correia, Isabel ^{[2
]}

Nickel, Stefan ^{[1
,3
]}

Saldanha-da-Gama, Francisco ^{[4
]}

机构：

[1] KIT, Inst Operat Res, Karlsruhe, Germany

[2] Univ Nova Lisboa, Fac Ciencias & Tecnol, Dept Matemat CMA, P-2829516 Caparica, Portugal

[3] Fraunhofer Inst Ind Math ITWM, Kaiserslautern, Germany

[4] Univ Lisbon, Fac Ciencias, DEIO CIO, P-1716049 Lisbon, Portugal

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2010年 / 207卷 / 01期

关键词：

Hub location; MIP formulations; Transportation; ALGORITHMS; ASSIGNMENT;

D O I：

10.1016/j.ejor.2010.04.015

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper a well-known formulation for the capacitated single-allocation hub location problem is revisited. An example is presented showing that for some instances this formulation is incomplete. The reasons for the incompleteness are identified leading to the inclusion of an additional set of constraints. Computational experiments are performed showing that the new constraints also help to decrease the computational time required to solve the problem optimally. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：92 / 96

页数：5

共 13 条

[1] Network hub location problems: The state of the art [J].

Alumur, Sibel ;

Kara, Bahar Y. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 190 (01) :1-21

[2] Preprocessing and cutting for multiple allocation hub location problems [J].

Boland, N ;

Krishnamoorthy, M ;

Ernst, AT ;

Ebery, J .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 155 (03) :638-653

[3] INTEGER PROGRAMMING FORMULATIONS OF DISCRETE HUB LOCATION-PROBLEMS [J].

CAMPBELL, JF .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 72 (02) :387-405

[4] Lagrangean relaxation for the capacitated hub location problem with single assignment [J].

Contreras, Ivan ;

Diaz, Juan A. ;

Fernandez, Elena .

OR SPECTRUM, 2009, 31 (03) :483-505

[5] Capacitated single allocation hub location problem -: A bi-criteria approach [J].

Costa, Maria da Graca ;

Captivo, Maria Eugenia ;

Climaco, Joao .

COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (11) :3671-3695

[6]

Ernst A. T., 1996, Location Science, V4, P139, DOI 10.1016/S0966-8349(96)00011-3

[7] Solution algorithms for the capacitated single allocation hub location problem [J].

Ernst, AT ;

Krishnamoorthy, M .

ANNALS OF OPERATIONS RESEARCH, 1999, 86 (0) :141-159

[8] Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem [J].

Ernst, AT ;

Krishnamoorthy, M .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 104 (01) :100-112

[9]

*ILOG INC, 2009, ILOG CPLEX US MAN

[10] A branch and cut algorithm for hub location problems with single assignment [J].

Labbé, M ;

Yaman, H ;

Gourdin, E .

MATHEMATICAL PROGRAMMING, 2005, 102 (02) :371-405

← 1 2 →