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

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

单位：四川大学商学院