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

摘要：

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

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

所属期刊栏目：23

分类号：C931;O221(管理学)

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

在线出版日期：2015-04-03（万方平台首次上网日期，不代表论文的发表时间）

页码：82-88