路段通行能力不同的避难点选址模型及算法

摘要：

研究应对突发事件的避难点选址问题.假定一条直线型动态路径网络上有n个顶点,由n-1条边相连,每个顶点有一个权重,每条边有一个容量.边的容量表示路段通行能力,是单位时间内允许进入该路段的最大聚集量.目标是在此网络中选择k个避难点,并为每个顶点指定一个避难点,使得所有顶点的权重到达各自避难点的最大时间最小.首先根据问题的性质,通过建立动态表结构,结合二分法的思想,在O(nlogn)时间内求解单个避难点选址问题.然后在此基础上,针对k-避难点选址问题,通过更新动态表,结合动态规划方法,设计了时间复杂度为O(knlogn)的递归算法求解.

关键词：道路通行能力、动态网络、动态规划、应急管理

所属期刊栏目：25

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

资助基金：国家自然科学基金资助项目71371130,71501019;四川旅游发展研究中心项目LYC16-16;赛尔网络下一代互联网技术创新项目

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

页数：共8页

页码：133-140