摘要
在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.
出处
《中国管理科学》
CSSCI
北大核心
2015年第1期82-89,共8页
Chinese Journal of Management Science
基金
中国博士后科学基金资助项目(2013M530404)
国家自然科学基金资助项目(71371129
71172197)
长江学者和创新团队发展计划(IRT1173)
关键词
应急管理
k-避难点
K-中心点
通行能力
emergency management
k-shelter
k-center
traffic capacity constraint
