Taking into account the capacity constraint of road, the k-shelter problem is proposed based on the k-center problem. The problem for the case of k=1 on the general tree graph is analyzed and one strategy searching the optimal location for the shelter is designed. On the line graph, the strategy for the case of k=1 is firstly improved and then the properties for the cases of k=2 and k>2 are analyzed, respectively. According to these properties, a kind of binary search algorithms whose time complexity equals O(nlogkn) is proposed for the general case of k on the line graph. The proposed model extends the classical k-center problem, and the designed algorithms are contributed to the practice of emergency management.
NI Guan-qun, XU Yin-feng, XU Jiu-ping
. The LocationModels and Algorithms for Emergency Shelter with Traffic Capacity Constraint[J]. Chinese Journal of Management Science, 2015
, 23(1)
: 82
-88
.
DOI: 10.16381/j.cnki.issn1003-207x.2015.01.011
[1] Kariv O, Hakimi S L. An algorithmic approach to network location problems (I): The p-centers [J]. SIAM Journal on Applied Mathematics, 1979, 37(3): 513-538.
[2] Hsu W L, Nemhauser G L. Easy and hard bottleneck location problems [J]. Discrete Applied Mathematics, 1979, 1(3): 209-215.
[3] Hochbaum D S, Shmoys D B. A best possible approximation algorithm for the k-center problem [J]. Mathematics of Operations Research, 1985, 10(2):180-184.
[4] Chen R, Handler G Y. Relaxation method for the solution of the mini-max location-allocation problem in Euclidean space [J]. Naval Research Logistics, 1987, 34(6):775-788.
[5] Averbakh I, Berman O. Algorithms for the robust 1-center problem on a tree [J]. European Journal of Operational Research, 2000, 123(2):292-302.
[6] Handler G Y, Mirchandani P B. Location on networks: Theory and algorithms [M]. Cambridge, MA: MIT Press, 1979.
[7] Frank H. Optimum locations on a graph with probabilistic demands [J]. Operations Research,1966, 14(3):409-421.
[8] Frank H. Optimum locations on a graph with correlated normal demands [J]. Operations Research,1967, 15(3):552-557.
[9] Wesolowsky G O. Probabilistic weights in the one-dimensional facility location problem [J]. Management Science, 1977, 24(2):224-229.
[10] Bhatia R, Guha S, Khuller S, et al. Facility location with dynamic distance functions [J]. Journal of Combinatorial Optimization, 1998, 2(3):199-217.
[11] Charikar M, Khuller S, Mount D M, et al. Algorithms for facility location problems with outliers [C]. Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA, January 7-9,2001.
[12] Chaudhuri S., Garg N, Ravi R. The p-neighbor k-center problem [J]. Information Processing Letters, 1998, 65(3):131-134.
[13] Hochbaum D S, Shmoys D B. A unified approach to approximate algorithms for bottleneck problems [J]. Journal of the ACM, 1986, 33(3):533-550.
[14] Lim A, Rodrigues B, Wang Fan, et al. K-center problems with minimum coverage [J]. Theoretical Computer Science, 2005, 332(1-3):1-17.
[15] Plesník J. A heuristic for the p-center problem in graphs [J]. Discrete Applied Mathematics, 1987, 17(3):263-268.
[16] Gørtz I L, Wirth A. Asymmetry in k-center variants [J]. Theoretical Computer Science, 2006, 361(2-3):188-199.
[17] Berman O, Drezner Z. A new formulation for the conditional p-median and p-center problems [J]. Operations Research Letters, 2008, 36(4):481-483.
[18] Berman O, Simchi-Levi D. Conditional location problems on networks [J]. Transportation Science, 1990, 24(1):77-78.
[19] Chen D, Chen R. New relaxation-based algorithms for the optimal solution of the continuous and discrete p-center problems [J]. Computers & Operations Research, 2009, 36(5):1646-1655.
[20] Chen D, Chen R. A relaxation-based algorithm for solving the conditional p-center problem [J]. Operations Research Letters, 2010, 38(3):215-217.
[21] Gørtz I L. Asymmetric k-center with minimum coverage [J]. Information Processing Letters, 2008, 105(4):144-149.
[22] 杨丰梅, 华国伟, 邓猛, 等. 选址问题研究的若干进展[J]. 运筹与管理, 2005, 14(6):1-7.
[23] 王非, 徐渝, 李毅学. 离散设施选址问题研究综述[J]. 运筹与管理, 2006, 15(5):64-69.
[24] 杨珺, 王玲, 郑娜, 等. 多用途易腐物品配送中心选址问题研究[J]. 中国管理科学, 2011, 19(1):91-99.
[25] 杨玉香, 周根贵. 闭环供应链网络设施竞争选址模型研究[J]. 中国管理科学, 2011, 19(5):50-57.
