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

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

• 论文 • 上一篇    下一篇

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

倪冠群1, 徐寅峰2, 徐玖平2   

  1. 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-qun1, XU Yin-feng2, XU Jiu-ping2   

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

摘要: k-中心点问题的基础上,考虑道路的通行能力限制,提出了k-避难点问题。在一般树图结构下,重点分析了1-避难点选址问题,并设计了有效的求解算法;在直线图结构下,首先改进了一般图1-避难点的求解算法,其次分析了2-避难点问题的特点,并给出了一个基于"二分思想"的求解算法,在此基础上,为一般的直线图k-避难点问题设计了求解算法,一般算法的时间复杂性为O(nlogkn)。所提出的模型在理论上扩展了经典的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(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.

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

中图分类号: