The big cube small cube solution method for multidimensional facility location problems

被引:39
作者
Schoebel, Anita [1 ]
Scholz, Daniel [1 ]
机构
[1] Univ Gottingen, Inst Numer & Angew Math, D-37083 Gottingen, Germany
关键词
Approximation algorithms; Facility location problem; p-median problem; Fermat-Weber problem; Continuous location; Global optimization; Non-differentiable optimization; GLOBAL OPTIMIZATION; INTERVAL-ANALYSIS; MULTISECTION; ATTRACTION; MINISUM; DESIGN; CIRCLE;
D O I
10.1016/j.cor.2009.03.031
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
In this paper we propose a general solution method for (non-differentiable) facility location problems with more than two variables as an extension of the Big Square Small Square technique (BSSS). We develop a general framework based on lower bounds and discarding tests for every location problem. We demonstrate our approach on three problems: the Fermat-Weber problem with positive and negative weights, the median circle problem, and the p-median problem. For each of these problems we show how to calculate lower bounds and discarding tests. Computational experiences are given which show that the proposed solution method is fast and exact. (C) 2009 Elsevier Ltd. All rights reserved.
引用
收藏
页码:115 / 122
页数:8
相关论文
共 30 条
[1]  
[Anonymous], 1996, Global Optimization. Deterministic Approaches
[2]  
[Anonymous], 1992, Global optimization using interval analysis
[3]  
Berman O, 2007, J OPER RES SOC, V58, P91, DOI 10.1057/palgrave.jors.2602l26
[4]   The Fermat-Weber location problem revisited [J].
Brimberg, J .
MATHEMATICAL PROGRAMMING, 1995, 71 (01) :71-76
[5]   Locating a minisum circle in the plane [J].
Brimberg, Jack ;
Juel, Henrik ;
Schoebel, Anita .
DISCRETE APPLIED MATHEMATICS, 2009, 157 (05) :901-912
[6]   A new multisection technique in interval methods for global optimization [J].
Casado, LG ;
García, I ;
Csendes, T .
COMPUTING, 2000, 65 (03) :263-269
[7]   WEBER PROBLEM WITH ATTRACTION AND REPULSION [J].
CHEN, PC ;
HANSEN, P ;
JAUMARD, B ;
TUY, H .
JOURNAL OF REGIONAL SCIENCE, 1992, 32 (04) :467-486
[8]   Multisection in interval branch-and-bound methods for global optimization -: I.: Theoretical results [J].
Csallner, AE ;
Csendes, T ;
Markót, MC .
JOURNAL OF GLOBAL OPTIMIZATION, 2000, 16 (04) :371-392
[9]  
Drezner Z, 2002, FACILITY LOCATION APPLICATIONS AND THEORY, P1
[10]   The big triangle small triangle method for the solution of nonconvex facility location problems [J].
Drezner, Z ;
Suzuki, A .
OPERATIONS RESEARCH, 2004, 52 (01) :128-135