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

The Location Models and Algorithms for Emergency Shelter with Traffic Capacity Constraint

作　　者：倪冠群[1] 徐寅峰[2] 徐玖平[2] 

机构地区：[1]福建农林大学管理学院,福建福州350002 [2]四川大学商学院,四川成都610065

出　　处：《中国管理科学》2015年第1期82-89,共8页Chinese Journal of Management Science

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

摘　　要：在k-中心点问题的基础上,考虑道路的通行能力限制,提出了k-避难点问题。在一般树图结构下,重点分析了1-避难点选址问题,并设计了有效的求解算法;在直线图结构下,首先改进了一般图1-避难点的求解算法,其次分析了2-避难点问题的特点,并给出了一个基于"二分思想"的求解算法,在此基础上,为一般的直线图k-避难点问题设计了求解算法,一般算法的时间复杂性为O(nlogkn)。所提出的模型在理论上扩展了经典的k-中心点选址问题,所设计的求解算法能够为现实的应急管理规划提供良好的理论支持。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 = 1on 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=1is firstly improved and then the properties for the cases of k=2and k2are 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 kon the line graph.The proposed model extends the classical k-center problem,and the designed algorithms are contributed to the practice of emergency management.

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

分 类 号：C931[经济管理—管理学] O221[理学—运筹学与控制论]