Python基于plotly/osmnx/networkx计算坐标点最短路径适配问题

问题根源 #

原有实现逻辑是逐行匹配同序号的起点、终点做1:1计算，既不支持起终点数量不等的场景，也无法覆盖所有起点到所有终点的全组合配对；同时存在三处明显问题：

• 同一条路径两次调用shortestpath函数重复计算，性能浪费严重
• 每次调用函数都重复创建坐标转换对象、重复查询点位对应的最近路网节点
• 隐藏bug：ox.nearest_nodes接口参数要求经度在前、纬度在后，原函数传参顺序颠倒，会匹配到错误的路网节点

实现思路 #

• 拆分独立的起点、终点数据集，做去重处理
• 预初始化公共资源，批量预计算所有点位的最近路网节点、点到路网的接驳距离，避免逐对重复计算
• 生成起点、终点的笛卡尔积配对表，覆盖所有可能的OD组合，不受起终点数量不一致的影响
• 优化路径计算逻辑，单次计算同时返回路径几何和总长度，消除重复计算开销
• 数据量较大时可替换为多源最短路径接口做批量计算，进一步提升运行效率

参考实现代码 #

预计算公共缓存 #

import time
import pandas as pd
import osmnx as ox
import networkx as nx
from osgeo import osr, ogr

# 仅初始化一次坐标转换对象，避免重复创建开销
inSpatialRef = osr.SpatialReference()
inSpatialRef.ImportFromEPSG(4326)
outSpatialRef = osr.SpatialReference()
outSpatialRef.ImportFromEPSG(32614)
coordTransform = osr.CoordinateTransformation(inSpatialRef, outSpatialRef)

# 拆分去重起点、终点集合
# 假设原始数据表中o_lat/o_long为起点经纬度，d_lat/d_long为终点经纬度
starts = df[['o_lat', 'o_long']].drop_duplicates().reset_index(drop=True)
# 批量计算所有起点对应的最近路网节点、点到节点距离（修正经纬度传参顺序）
starts['nearest_o_node'], starts['dist_o_to_onode'] = ox.nearest_nodes(
    G, starts['o_long'], starts['o_lat'], return_dist=True
)

dests = df[['d_lat', 'd_long']].drop_duplicates().reset_index(drop=True)
# 批量计算所有终点对应的最近路网节点、点到节点距离
dests['nearest_d_node'], dests['dist_d_to_dnode'] = ox.nearest_nodes(
    G, dests['d_long'], dests['d_lat'], return_dist=True
)

# 生成全量OD笛卡尔积配对，自动适配任意长度的起点、终点集合
od_pairs = starts.assign(merge_key=1).merge(
    dests.assign(merge_key=1), 
    on='merge_key'
).drop('merge_key', axis=1)

优化后的路径计算逻辑 #

def calc_route(row):
    o_node = row['nearest_o_node']
    d_node = row['nearest_d_node']
    # 计算起点、终点到路网的接驳距离总和
    dist_to_network = row['dist_o_to_onode'] + row['dist_d_to_dnode']
    
    # 求解路网最短路径
    shortest_path = nx.shortest_path(G, o_node, d_node)
    route_geom = nodes_to_linestring(shortest_path)
    
    # 投影后计算路网内路径长度
    geom = ogr.CreateGeometryFromWkt(route_geom.wkt)
    geom.Transform(coordTransform)
    net_length = geom.Length()
    total_length = net_length + dist_to_network
    
    return pd.Series([route_geom, total_length], index=['osmnx_geometry', 'osmnx_length'])

批量执行计算 #

start_time = time.time()
# 单次apply同时返回路径几何和长度，避免重复求解同一条路径
od_pairs[['osmnx_geometry', 'osmnx_length']] = od_pairs.apply(calc_route, axis=1)
print(f"计算耗时: {time.time() - start_time} 秒")

性能优化提示 #

• 当起终点总数量超过100个时，逐对调用nx.shortest_path效率较低，可替换为nx.multi_source_dijkstra_path、nx.multi_source_dijkstra_path_length接口，按起点分组批量计算该起点到所有终点的最短路径，运行速度可提升3~10倍
• 如果路网范围较大，可提前对路网做拓扑简化，减少路径求解时的节点遍历量

内容的提问来源于stack exchange，提问作者Josh Canfield