路网应急疏散问题——CCRP算法

大家好，欢迎来到IT知识分享网。

引言

路网应急疏散问题是指当城市发生突发性事件时,通过路网将时间区域的人口和交通流疏散到安全区域,最大限度地避免或减少突发事件带来的人员伤亡和财产损失。因此如何将待疏散区域内的人群,在最短的时间内疏散到目的区域,是社会课题城市灾害应急管理的首要目标。 其中CCRP方法是近年大家较为关注的一种可行性算法，本文研究了CCRP算法，并基于该算法进行了代码实现。

输入

包含两个文件，一个是Node.csv，用于描述地图中的所有节点，示例内容如下：
NodeID Occupancy Nodecapacity
1 10 50
2 5 50
3 0 30
4 0 8
5 0 6
6 0 10
7 0 8
8 15 65
9 0 25
10 0 30
11 0 8
12 0 18
13 -15 50
14 -15 50
其中NodeID表示节点的编号，Occupancy列正数表示该节点上待疏散的人群数量，负数表示该节点可容纳疏散人群的数量，Nodecapacity表示每个节点瞬时可容纳的人群数量。
另一个文件是Edge.csv，用于描述地图中所有的路径，示例内容如下：
SourceNodeID DNodeID Edgecapactiy Edgetravaltime
1 3 7 1
2 3 7 1
3 4 3 3
3 5 3 3
4 6 5 4
5 7 3 4
6 10 5 5
7 11 3 5
8 11 3 3
8 9 6 4
8 10 6 3
9 11 6 4
9 10 14 4
10 13 8 1
10 12 6 4
11 14 3 2
12 14 3 3
每一列都表示无向图中的一条边，SourceNodeID表示边的起始节点编号，DNodeID表示边的目的节点编号，Edgecapacity表示这条边最多可容纳多少人群数量通过，Egdetraveltime表示通过这条边所使用的时间。

输出

路径 [(8, 0), (10, 3), (13, 4)] 目前剩余人数 30 将要疏散人数 6
路径 [(1, 0), (3, 1), (5, 4), (7, 8), (11, 13), (14, 15)] 目前剩余人数 24 将要疏散人数 3
路径 [(8, 3), (10, 6), (13, 7)] 目前剩余人数 21 将要疏散人数 6
路径 [(8, 6), (10, 9), (13, 10)] 目前剩余人数 15 将要疏散人数 3
路径 [(1, 6), (3, 7), (5, 10), (7, 14), (11, 19), (14, 21)] 目前剩余人数 12 将要疏散人数 3
路径 [(1, 7), (3, 8), (4, 11), (6, 15), (10, 20), (13, 21)] 目前剩余人数 9 将要疏散人数 3
路径 [(1, 10), (3, 11), (4, 14), (6, 18), (10, 23), (13, 24)] 目前剩余人数 6 将要疏散人数 1
路径 [(2, 11), (3, 12), (4, 15), (6, 19), (10, 24), (13, 25)] 目前剩余人数 5 将要疏散人数 1
路径 [(2, 12), (3, 13), (4, 16), (6, 20), (10, 25), (13, 26)] 目前剩余人数 4 将要疏散人数 1
路径 [(2, 13), (3, 14), (4, 17), (6, 21), (10, 26), (13, 27)] 目前剩余人数 3 将要疏散人数 1
路径 [(2, 14), (3, 15), (4, 18), (6, 22), (10, 27), (13, 28)] 目前剩余人数 2 将要疏散人数 1
路径 [(2, 15), (3, 16), (4, 19), (6, 23), (10, 28), (13, 29)] 目前剩余人数 1 将要疏散人数 1

输出给出了所有的疏散路径，每个路径里包含了人群疏散途径的节点和到达每个节点的时间，包含目前待疏散人群数量和本条路径将要疏散的人数，起始时刻从0开始计算。

算法核心

算法核心依旧是Dijkstra。
1.根据节点时刻容量表和边时刻容量表，得到当前可以规划的路径图，基于该图，利用Dijkstra找到最短路
2.查询节点时刻容量表和边时刻容量表，根据木桶短板原理，找到最短路径中容量最小的，确定为本次最短路径疏散的人群数量，并记录剩余待疏散人群。
3.查询最短路径中每条边的疏散时间，结合本次疏散人群数量，维护节点时刻容量表和边时刻容量表。
4.输出每次的最短路，包含节点编号和到达节点时间。
5.循环1-4，直到剩余待疏散人群数量为0

总结

def change_global(dis,global_edge_capacity,global_node_capacity,t,road,min_capacity): time=dis for i in range(len(road)-1): global_node_capacity[t+time[road[i]]][road[i]]=global_node_capacity[t+time[road[i]]][road[i]]-min_capacity for tt in range(t+time[road[i]],1000): global_node_capacity[tt][road[-1]]=global_node_capacity[tt][road[-1]]-min_capacity for tt in range(t+time[road[0]],1000): global_edge_capacity[tt][road[0]][road[1]]=global_edge_capacity[tt][road[0]][road[1]]-min_capacity for i in range(1,len(road)-1): for tt in range(t+time[road[i]],t+time[road[i+1]],1): global_edge_capacity[tt][road[i]][road[i+1]]=global_edge_capacity[tt][road[i]][road[i+1]]-min_capacity return global_edge_capacity,global_node_capacity