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

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

中国管理科学 ›› 2015, Vol. 23 ›› Issue (1): 82-88.doi: 10.16381/j.cnki.issn1003-207x.2015.01.011

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

倪冠群¹, 徐寅峰², 徐玖平²

1. 福建农林大学管理学院, 福建福州 350002;
2. 四川大学商学院, 四川成都 610065

收稿日期:2013-01-19 修回日期:2013-06-20 出版日期:2015-01-20 发布日期:2015-01-21
作者简介:倪冠群(1982-),男(汉族),山东人,福建农林大学管理学院副教授,研究方向:应急管理.
基金资助:
中国博士后科学基金资助项目(2013M530404);国家自然科学基金资助项目(71371129,71172197);长江学者和创新团队发展计划(IRT1173)

The LocationModels and Algorithms for Emergency Shelter with Traffic Capacity Constraint

NI Guan-qun¹, XU Yin-feng², XU Jiu-ping²

1. School of Management, Fujian Agriculture and Forestry University, Fujian 350002, China;
2. School of Business, Sichuan University, Chengdu 610065, China

Received:2013-01-19 Revised:2013-06-20 Online:2015-01-20 Published:2015-01-21

摘要/Abstract

摘要： 在k-中心点问题的基础上,考虑道路的通行能力限制,提出了k-避难点问题。在一般树图结构下,重点分析了1-避难点选址问题,并设计了有效的求解算法;在直线图结构下,首先改进了一般图1-避难点的求解算法,其次分析了2-避难点问题的特点,并给出了一个基于"二分思想"的求解算法,在此基础上,为一般的直线图k-避难点问题设计了求解算法,一般算法的时间复杂性为O(nlog^kn)。所提出的模型在理论上扩展了经典的k-中心点选址问题,所设计的求解算法能够为现实的应急管理规划提供良好的理论支持。

关键词: 应急管理, k-避难点, k-中心点, 通行能力

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

中图分类号:

C931
O221

倪冠群, 徐寅峰, 徐玖平. 考虑道路通行能力的应急避难点选址模型及算法[J]. 中国管理科学, 2015, 23(1): 82-88.

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.

参考文献

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

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	陈凤娇,刘德海. 重大传染病多渠道疫情信息发布模式的演化路径分析[J]. 中国管理科学, 2024, 32(4): 237-249.
[2]	杨曼,刘德海. 物理-社会耦合系统下震后多方协同救援的微分博弈模型[J]. 中国管理科学, 2024, 32(1): 115-124.
[3]	金卫健,徐浩,黄传峰,蒋诚智. 基于前景理论的大规模传染疫情应急管理决策研究[J]. 中国管理科学, 2023, 31(10): 225-233.
[4]	高蕾, 龚晶. 基于线性分段恢复函数的基础设施韧性分析模型——以C县电力系统网络为例[J]. 中国管理科学, 2022, 30(12): 86-95.
[5]	刘洋, 刘晓云, 李玉飞. 基于改进物元可拓模型的高校突发事件应急管理能力评价[J]. 中国管理科学, 2022, 30(11): 299-308.
[6]	张鼎华, 李卫俊, 李丞, 申世飞. 基于深度学习的多维情景空间下群体性事件分析与预测研究[J]. 中国管理科学, 2020, 28(8): 172-180.
[7]	宋民雪, 刘德海. 群体性突发事件化解机制的随机演化博弈模型[J]. 中国管理科学, 2020, 28(4): 142-152.
[8]	王熹徽, 张文鑫, 余玉刚, 刘兵兵. 考虑灾民痛苦感知的应急避难所选址与物资分配优化[J]. 中国管理科学, 2020, 28(12): 162-172.
[9]	吴鹏, 强韶华, 高庆宁. 基于SOAR模型的网民群体负面情感建模研究[J]. 中国管理科学, 2018, 26(3): 126-138.
[10]	赵容, 刘克艳, 任佩瑜. 路段通行能力不同的避难点选址模型及算法[J]. 中国管理科学, 2017, 25(9): 133-140.
[11]	邓婕, 池宏, 许保光. 基于有向图相似的应急响应程序模块化问题研究[J]. 中国管理科学, 2017, 25(4): 115-123.
[12]	王长峰, 庄文英. 基于动态微分博弈理论的工程应急决策研究[J]. 中国管理科学, 2017, 25(10): 179-186.
[13]	刘德海. 基于最大偏差原则的群体性事件应急管理绩效评价模型[J]. 中国管理科学, 2016, 24(4): 138-147.
[14]	崔玉泉, 张宪 . 非对称信息下供应链应急管理和信息价值研究[J]. 中国管理科学, 2016, 24(4): 83-93.
[15]	吴忠和, 陈宏, 梁翠莲. 时间约束下不对称信息鲜活农产品供应链应对突发事件协调模型[J]. 中国管理科学, 2015, 23(6): 126-134.