《交通规划》——最短路分配方法

说明：下面内容，将用python、networkx实现刘博航、杜胜品主编的《交通规划》P198页的例题，主要是实现最短路径分配方法。

1. 题目描述如下：

2. networkx构建网络

import networkx as nx
import matplotlib.pyplot as plt

# 带权重的边列表
edges = [(1,2,10), (1,3,4), (2,3,3), (2,4,5),(3,4,12),
         (2,1,10), (3,1,4), (3,2,3), (4,2,5),(4,3,12)]
nodes = [1,2,3,4]

# 创建无向图
G = nx.DiGraph()

# 添加节点
G.add_nodes_from(nodes)
G.add_weighted_edges_from(edges)

# 绘制图形
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=500, font_size=16, font_weight='bold')
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels, font_size=12, font_color='red')
plt.show()

nx.write_gexf(G,'./net9_2.gexf')

构建的网络为有向图：

3. 输入OD矩阵，表9-8

import pandas as pd
import numpy as np
od = pd.DataFrame(
    data=
    {'A':[0,100,300],
    'B':[100,0,200],
    'C':[300,200,0]}
)

od.index = ['A', 'B', 'C']
od
od.to_csv('./OD_9-8.csv')

4. 流量分配

思路：

• 处理OD矩阵，处理成OD对
• 遍历每一对OD对，找出OD对对应的最短路径，并存储
• 遍历最短路径所经过的边，将流量分配到对应的边上

4.1 OD矩阵 -->OD对

import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt

#输入网络
G=  nx.read_gexf('./net9_2.gexf')

# 输入OD
od = pd.read_csv('./OD_9-8.csv',index_col=0)
od

# 将OD点和网络节点进行对应
od_map_nodes_dict = {
    'A':1,
    'B':3,
    'C':4
}
# 将OD表处理成OD对
od_new = od.unstack()
od_new = od_new.reset_index()
od_new = od_new.rename(dict(zip(list(od_new.columns),['O','D','q'])),axis=1) #q 表示交通小区之间的出行分布量
od_new

4.2 初始化网络中的流量

# 初始化G中的flow属性
for u,v,data in G.edges(data = True):
    data['flow'] =0

边视图如下：

4.3 遍历每对OD,查找最短路径，并分配流量

#!分配OD量
# 将各OD点对的OD量分配到该OD点对应的最短路径上，并进行累加
df = od_new
# 遍历DataFrame的每一行
for _, row in df.iterrows():
    # 获取流量
    flow = row['q']
    O = str(od_map_nodes_dict[row['O']])
    D = str(od_map_nodes_dict[row['D']])
    # 获取路径
    path = nx.shortest_path(G,O,D,'weight')
    print(row['O'],'-',row['D'],'shortest_path:',path)
    
    # 分配流量到路径上的每一条边
    for i in range(len(path) - 1):
        # 如果边已经存在，增加流量
        if G.has_edge(path[i], path[i+1]):
            if 'flow' in G[path[i]][path[i+1]]:
                G[path[i]][path[i+1]]['flow'] += flow
            else:
                G[path[i]][path[i+1]]['flow'] = flow
        # else:
            # G.add_edge(path[i], path[i+1], flow=flow)

# 输出结果
G.edges(data= True)

for u, v, data in G.edges(data=True):
    print(f"Edge: {u}-{v}, Flow: {data['flow']}")

结果（和书中一致）：

5. 完整代码：

import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
#************************************************************************************************
od = pd.DataFrame(
    data=
    {'A':[0,100,300],
    'B':[100,0,200],
    'C':[300,200,0]}
)

od.index = ['A', 'B', 'C']
od
od.to_csv('./OD_9-8.csv')

#************************************************************************************************
# 带权重的边列表
edges = [(1,2,10), (1,3,4), (2,3,3), (2,4,5),(3,4,12),
         (2,1,10), (3,1,4), (3,2,3), (4,2,5),(4,3,12)]
nodes = [1,2,3,4]

# 创建无向图
G = nx.DiGraph()

# 添加节点
G.add_nodes_from(nodes)
G.add_weighted_edges_from(edges)

# 绘制图形
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=500, font_size=16, font_weight='bold')
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels, font_size=12, font_color='red')
plt.show()

nx.write_gexf(G,'./net9_2.gexf')


#************************************************************************************************
#输入网络
G=  nx.read_gexf('./net9_2.gexf')

# 输入OD
od = pd.read_csv('./OD_9-8.csv',index_col=0)
od

# 将OD点和网络节点进行对应
od_map_nodes_dict = {
    'A':1,
    'B':3,
    'C':4
}
# 将OD表处理成OD对
od_new = od.unstack()
od_new = od_new.reset_index()
od_new = od_new.rename(dict(zip(list(od_new.columns),['O','D','q'])),axis=1) #q 表示交通小区之间的出行分布量
od_new

# # 确定最短OD对之间的最短路径
# od_new['shortest_path'] = od_new.apply(lambda x:nx.shortest_path(G,str(od_map_nodes_dict[x['O']]),str(od_map_nodes_dict[x['D']]),weight='weight'),axis=1)
# # 将路径中的节点从字符串转化为整数，因为图G中的节点是整数
# od_new['shortest_path'] = od_new['shortest_path'].apply(lambda x: [int(node) for node in x])


#!分配OD量
# 将各OD点对的OD量分配到该OD点对应的最短路径上，并进行累加
df = od_new
# 初始化G中的flow属性
for u,v,data in G.edges(data = True):
    data['flow'] =0



G.edges(data = True)

#!分配OD量
# 将各OD点对的OD量分配到该OD点对应的最短路径上，并进行累加
df = od_new
# 遍历DataFrame的每一行
for _, row in df.iterrows():
    # 获取流量
    flow = row['q']
    O = str(od_map_nodes_dict[row['O']])
    D = str(od_map_nodes_dict[row['D']])
    # 获取路径
    path = nx.shortest_path(G,O,D,'weight')
    print(row['O'],'-',row['D'],'shortest_path:',path)
    
    # 分配流量到路径上的每一条边
    for i in range(len(path) - 1):
        # 如果边已经存在，增加流量
        if G.has_edge(path[i], path[i+1]):
            if 'flow' in G[path[i]][path[i+1]]:
                G[path[i]][path[i+1]]['flow'] += flow
            else:
                G[path[i]][path[i+1]]['flow'] = flow
        # else:
            # G.add_edge(path[i], path[i+1], flow=flow)

# 输出结果
G.edges(data= True)

for u, v, data in G.edges(data=True):
    print(f"Edge: {u}-{v}, Flow: {data['flow']}")