考虑道路通行能力的应急避难点选址模型及算法

doi:10.16381/j.cnki.issn1003-207x.2015.01.011

Abstract

Abstract: 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(nlog^kn) 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.

Key words: emergency management, k-shelter, k-center, traffic capacity constraint

CLC Number:

C931
O221

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.

References

[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.

The LocationModels and Algorithms for Emergency Shelter with Traffic Capacity Constraint

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 12

Metrics

Comments

Recommended 10

[1]	ZHANG Ding-hua, LI Wei-jun, LI Cheng, SHEN Shi-fei. The Researchon the Analysis and Prediction of Mass Incidentsin Multi-dimensional Scenario Space Based on Deep Learning [J]. Chinese Journal of Management Science, 2020, 28(8): 172-180.
[2]	SONG Min-xue, LIU De-hai. Stochastic Evolutionary Game Model for Resolution Mechanism of Mass Events [J]. Chinese Journal of Management Science, 2020, 28(4): 142-152.
[3]	WANG Xi-hui, ZHANG Wen-xin, YU Yu-gang, LIU Bing-bing. An Optimization Model for Emergency Shelter Location and Relief Materials Allocation Considering Human Suffering [J]. Chinese Journal of Management Science, 2020, 28(12): 162-172.
[4]	ZHAO Rong, LIU Ke-yan, REN Pei-yu. Min-max Multiple Sink Location Problem in Dynamic Path Networks with Different Traffic Capacity Constraint [J]. Chinese Journal of Management Science, 2017, 25(9): 133-140.
[5]	DENG Jie, CHI Hong, XU Bao-guang. The Research on Emergency Response Procedures Modularity Based on the Similarity of Directed Graph [J]. Chinese Journal of Management Science, 2017, 25(4): 115-123.
[6]	WANG Chang-feng, ZHUANG Wen-ying. Study on Emergency Decision Making of Major Projects Based on the Dynamic Differential Game Theory [J]. Chinese Journal of Management Science, 2017, 25(10): 179-186.
[7]	LIU De-hai. Performance Evaluation Two-tuple Linguistic Model in Emergency Management of Mass Incident Based Maximal Deviation Principle [J]. Chinese Journal of Management Science, 2016, 24(4): 138-147.
[8]	QI Ming-liang, QIN Kai-jie, ZHAO Yan. Research on Problem of Scheduling of Helicopter Coordinated with Vehicle for Resources Distribution in Snowstorm [J]. Chinese Journal of Management Science, 2014, 22(3): 59-67.
[9]	ZHU Li, CAO Jie. Supernetwork Optimization of Emergency Resources Allocation under Disaster Risk [J]. Chinese Journal of Management Science, 2012, 20(6): 141-148.
[10]	LIU De-hai, WANG Wei-guo. Co-evolutionary Mechanism of Social Network Structure and Strategy in Mass Emergency with Maintain Legal Rights [J]. Chinese Journal of Management Science, 2012, (3): 185-192.
[11]	LIU De-hai. Evolutionary Game Analysis of Governmental Opportunism Behavior in Unexpected Incidents Involving Mass Participation [J]. Chinese Journal of Management Science, 2010, 18(1): 175-183.
[12]	YAO Jie, CHI Hong, JI Lei. The Application of Structural Equation Model with Latent Variables in the Emergency Management [J]. Chinese Journal of Management Science, 2005, (2): 44-50.