An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions

被引：5
|
作者：
Berger, Andre [1 ]
Grigoriev, Alexander [1 ]
Winokurow, Andrej [1 ]
机构：
[1] Maastricht Univ, POB 616, NL-6200 MD Maastricht, Netherlands
来源：
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 2017年 / 68卷 / 03期
关键词：
1-median; Single facility location problem; Rectilinear norm; Polyhedral norm; Exact algorithm;
D O I：
10.1007/s10589-017-9935-4
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
The single facility location problem with demand regions seeks for a facility locationminimizing the sum of the distances from n demand regions to the facility. The demand regions represent sales markets where the transportation costs are negligible. In this paper, we assume that all demand regions are disks of the same radius, and the distances are measured by a rectilinear norm, e.g. l(1) or l(infinity). We develop an exact combinatorial algorithm running in time O(n log(c) n) for some c dependent only on the space dimension. The algorithm is generalizable to the other polyhedral norms.
引用
收藏
页码：661 / 669
页数：9
相关论文
共 46 条
  • [1] An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions
    André Berger
    Alexander Grigoriev
    Andrej Winokurow
    Computational Optimization and Applications, 2017, 68 : 661 - 669
  • [2] A BSSS algorithm for the single facility location problem in two regions with different norms
    Zaferanieh, M.
    Kakhki, H. Taghizadeh
    Brimberg, J.
    Wesolowsky, G. O.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 190 (01) : 79 - 89
  • [3] Solving a minisum single facility location problem in three regions with different norms
    Gökhan Altay
    M. Hakan Akyüz
    Temel Öncan
    Annals of Operations Research, 2023, 321 : 1 - 37
  • [4] Solving a minisum single facility location problem in three regions with different norms
    Altay, Gokhan
    Akyuz, M. Hakan
    Oncan, Temel
    ANNALS OF OPERATIONS RESEARCH, 2023, 321 (1-2) : 1 - 37
  • [5] EFFICIENT ALGORITHM FOR CAPACITATED FACILITY LOCATION PROBLEM
    NAUSS, RM
    OPERATIONS RESEARCH, 1975, 23 : B334 - B334
  • [6] An efficient algorithm for facility location in the presence of forbidden regions
    Butt, SE
    Cavalier, TM
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 90 (01) : 56 - 70
  • [7] Bender's Algorithm for Facility Location Problem with Uncertain Demand
    Li, Haibin
    Yan, Jun
    Ren, Mingming
    INNOVATIVE COMPUTING AND INFORMATION, ICCIC 2011, PT I, 2011, 231 : 115 - +
  • [8] Heuristics for a continuous multi-facility location problem with demand regions
    Dinler, Derya
    Tural, Mustafa Kemal
    Iyigun, Cem
    COMPUTERS & OPERATIONS RESEARCH, 2015, 62 : 237 - 256
  • [9] Greedy algorithms for the single-demand facility location problem
    Cheung, Sin-Shuen
    Williamson, David P.
    OPERATIONS RESEARCH LETTERS, 2017, 45 (05) : 452 - 455
  • [10] THE SINGLE FACILITY MINIMAX DISTANCE PROBLEM UNDER STOCHASTIC LOCATION OF DEMAND
    CARBONE, R
    MEHREZ, A
    MANAGEMENT SCIENCE, 1980, 26 (01) : 113 - 115
12345