根据已知站点寻找路网的最短路径

背景

接上期，基于MATSim的交通仿真，其中有一块非常重要的就是公交的仿真，这也是当初选择MATSim技术路线的一个重要原因，现在业务给出的场景是上传一些有序站点及其经纬度，需要通过算法来适配对应的路网，由于路网只有一套，注意这些站点不一定是路网的的节点，且大多数情况不是，所以需要做2件事情，第一件是将所有站点绑定到路网中对应的link，第二件是在路网中找出一条路线串起所有有序站点，称为绑路，简而言之，一个是绑路，一个是绑站。往往绑路先行，原因后续会论述，这一期，先来聊聊绑路。

思路

经调研发现最短路径往往只支持起点终点为路网中节点的情况，既然有序站点不是路网中的节点，那我先将其映射到路网中的节点，然后再去调用最短路径算法生成任意两点的最短路径，返回经过的link，最后把所有link按先后顺序拼接起来便得到经过所有站点的路径，严格来说是经过所有映射后节点的路径，具体的

1，为每个stop按最近距离法则建立站点到node的映射关系，找到其对应的node，记得node去重(可选)，形成映射后的有序node_list；
2，对node_list循环，找出每相邻两个node的最路径，返回segement_node;
3，将所有的segement_node拼接起来形成整个route的route_node;
4，再以route_node去整个路网的link池（link_pool）寻找对应的link_list;

核心代码

def route_schedule(stop, network): #根据有序的站点列表按最短路径构建线路# print(stop, network.edges, network._node)node = {} #用来存放路网的所有节点id及对应的几何对象for (k,v) in network._node.items(): #node_id+xy坐标if bool(v):p = Point(v.get('x'), v.get('y'))node[k] = p# print("\n所有节点\n", node)tree = STRtree(list(node.values())) #利用路网的所有节点构造一个r-treestop_map = {} #用来存放站点映射后的节点,并且以站点的id作为键for (k,v) in stop.items():idx = tree.nearest(Point(v)) #为每个站点找出路网中与该站点最近的节点序号stop_map[k] = list(node.keys())[idx]print('\n每个站点映射后的路网节点\n', stop_map) # stop_map = unique_dict_values(stop_map) # # 此处可以加一个stop_map的相邻相同节点去重# print('\n去重后每个站点最近的路网节点\n', stop_map) path =[] #用来存放经过所有站点的最短路径for i in range(len(stop_map) -1): #对映射后的节点循环len(stop_map) -1start_node = list(stop_map.values())[i]end_node = list(stop_map.values())[i+1]# print("起始节点", start_node, end_node)shortest_path = nx.dijkstra_path(G, start_node, end_node)# print("从起点到终点最短路径", shortest_path)if i == 0: #如果是第一段path.extend(shortest_path)else: #其余的去掉第一个节点path.extend(shortest_path[1:])print("\n最短路径经过哪些节点\n", path)route  = [] #用来存放路线经过的linklink_pool = {} #用来存放路网所有的link的id及几何对象,做成一个link池for edege in network.edges:# print(edege)if network._node[edege[0]] and network._node[edege[1]]:link_id = str(network[edege[0]][edege[1]]['path_id'])link_pool[link_id] = edege# print("\nlink池子\n", link_pool)for i in range(len(path)-1): #根据路径中的node对去link池索引对应的linknode_pair = (path[i], path[i+1]) #node对# print(node_pair)route_link = find_key_by_value(link_pool, node_pair) #根据值找键route.append(route_link)print("\n路线经过的link\n", route)return route

优缺点分析

首先，该方法简单直白高效，在建立站点与节点映射的时候，也会存在多对一的情况，如’557023’: ‘9635081392’, ‘557024’: ‘9635081392’,相邻两个站点对应同一个节点，可以加一个限定对应的节点均为起点，也就是在起点里面找对应点，然后再去重，同时，最短路径找出来的路径应该是连贯的，这么做出来连贯是连贯，但是会形成环路，回路，分路叉支，如下图所示，问题关键应该在站点映射到节点环节出问题了，可以对应的优化，其实，更本质的是"在一个有向图中，如何利用networkx寻找经过有序点的最短路径，这些有序点不一定是节点"的算法构建，可以考虑将这些站点作为节点插入到原始路网中；

效果预览
百度的金泽5路上行

迭代优化思路1

在建立站点与节点映射的时候，很有可能站点及节点经纬度的经度问题出些问题，可以考虑将这些站点作为节点插入到原始路网中，本次围绕这个关键点进行迭代优化

核心代码1

  # 将站点作为虚拟节点插入到图中stop_attribution = stop_df[['stop_id', 'x', 'y']].set_index('stop_id').to_dict(orient='records') #经纬度合并成dictdf_stops = pd.DataFrame({"stop_id": stop_df['stop_id'], "attribution": stop_attribution})network.add_nodes_from((attr['stop_id'], attr['attribution']) for row, attr in df_stops.iterrows()) #Use (node, attrdict) tuples to update attributes for specific nodes.

由于桥接的node没有link接入网络会报错networkx.exception.NetworkXNoPath: No path to 557011.

迭代优化思路2

既然将所有的站点映射到原始路网的节点可能会存在环路，回路，岔路等问题，根本可能站点周边没有合适的节点，所以可以加一个逻辑筛选，如果站点周边150米范围内有节点则进行按最短距离去匹最近的节点，这样一来，有些站点有映射节点，有些站点没有映射节点，而且前者居多，只用有映射的节点的来进行后续的最短路径算法也是可行的。
站点映射出岔子了

核心代码2

 stop_map = {} #用来存放站点映射后的节点,并且以站点的id作为键for (k,v) in stop_dict.items():if any(tree.query(Point(v).buffer(0.0008))): #如果站点周围200米有节点的话print("站点周边200米有节点", [list(node.keys())[idx] for idx in tree.query(Point(v).buffer(0.0008))])idx = tree.nearest(Point(v)) #为每个站点找出路网中与该站点最近的节点序号stop_map[k] = list(node.keys())[idx]print('\n每个站点映射后的路网节点\n', stop_map)