主管:中国科学院
主办:中国优选法统筹法与经济数学研究会
   中国科学院科技战略咨询研究院
论文

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

展开
  • 1. 福建农林大学管理学院, 福建 福州 350002;
    2. 四川大学商学院, 四川 成都 610065
倪冠群(1982-),男(汉族),山东人,福建农林大学管理学院副教授,研究方向:应急管理.

收稿日期: 2013-01-19

  修回日期: 2013-06-20

  网络出版日期: 2015-01-21

基金资助

中国博士后科学基金资助项目(2013M530404);国家自然科学基金资助项目(71371129,71172197);长江学者和创新团队发展计划(IRT1173)

The LocationModels and Algorithms for Emergency Shelter with Traffic Capacity Constraint

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

Received date: 2013-01-19

  Revised date: 2013-06-20

  Online published: 2015-01-21

摘要

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

本文引用格式

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

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

参考文献

[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.
文章导航

/