CODEWITHSUNDEEP
pythonnetworkxpolylineosmnx
Mohammad
Mohammad

Reputation: 57

OSMnx: Shortest path for a set of origins and destinations

Suppose I have a point shapefile with origins and destinations.

1) How can I use nx.shortest_path to calculate for each origin and its destination? 2) How can save the corresponding route as a shapefile? I've checked Save a route and conserve its curvature with Python OSMnx it shows how to get a MultiLineString for the route but it doesn't show how to export the route.

Upvotes: 4

Views: 4306

Answers (2)

Rajesvari Parasa
Rajesvari Parasa

Reputation: 41

Thanks to @gboeing for the steps. Also adding code snippets that worked for me to implement the solution outlined.

from shapely.geometry import shape
from shapely.geometry import LineString

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


G= ox.graph_from_place('Bangalore, India')

fig, ax = ox.plot_graph(G)

#Read the Origin-Destination csv
od_table = 'E:/OD_pairs1.csv'
df = pd.read_csv(od_table)

Here's how my input CSV looks like with coordinates for Origin (o_long, o_lat) and Destination (d_long, d_lat) points:

df

Out[]:  o_id  o_long    o_lat      d_id d_long      d_lat
        o1  77.548349   12.996800   d1  77.554137   12.995225
        o2  77.555820   13.009082   d2  77.570458   12.995690
        o3  77.576325   13.014630   d3  77.583616   13.009188
        o4  77.564848   12.990121   d4  77.551316   12.988570
        o5  77.590529   12.992340   d5  77.598469   12.988289

Part 1 of the answer (methods to calculate the routes): (In the method shortestpath(), you may want to return the length variable instead of total_length if you do not want distance from O & D points to the nearest network nodes be added to the route length.)

def nodes_to_linestring(path):
    coords_list = [(G.nodes[i]['x'], G.nodes[i]['y']) for i in path ]
    #print(coords_list)
    line = LineString(coords_list)
    
    return(line)

def shortestpath(o_lat, o_long, d_lat, d_long):
    
    nearestnode_origin, dist_o_to_onode = ox.distance.get_nearest_node(G, (o_lat, o_long), method='haversine', return_dist=True)
    nearestnode_dest, dist_d_to_dnode = ox.distance.get_nearest_node(G, (d_lat, d_long), method='haversine', return_dist=True)
    
    #Add up distance to nodes from both o and d ends. This is the distance that's not covered by the network
    dist_to_network = dist_o_to_onode + dist_d_to_dnode
    
    shortest_p = nx.shortest_path(G,nearestnode_origin, nearestnode_dest) 
    
    route = nodes_to_linestring(shortest_p) #Method defined above
    
    # Calculating length of the route requires projection into UTM system.  
    inSpatialRef = osr.SpatialReference()
    inSpatialRef.ImportFromEPSG(4326)
    outSpatialRef = osr.SpatialReference()
    outSpatialRef.ImportFromEPSG(32643)
    coordTransform = osr.CoordinateTransformation(inSpatialRef, outSpatialRef)
    
    #route.wkt returns wkt of the shapely object. This step was necessary as transformation can be applied 
    #only on an ogr object. Used EPSG 32643 as Bangalore is in 43N UTM grid zone.
    geom = ogr.CreateGeometryFromWkt(route.wkt)
   
    geom.Transform(coordTransform)
    length = geom.Length()
    
    #Total length to be covered is length along network between the nodes plus the distance from the O,D points to their nearest nodes
    total_length = length + dist_to_network
    #in metres
    
    return(route, total_length )

Applying the above methods on the dataframe to get geometries and lengths of the shortest routes for all the O-D pairs:

start_time = time.time()

df['osmnx_geometry'] = df.apply(lambda x: shortestpath(x['o_lat'], x['o_long'], x['d_lat'], x['d_long'])[0] , axis=1)
df['osmnx_length'] = df.apply(lambda x: shortestpath(x['o_lat'], x['o_long'], x['d_lat'], x['d_long'])[1] , axis=1)

print("Time taken: ", (time.time() - start_time), "seconds")

The resulting dataframe will have the relevant geometries for routes and the route lengths (in metres):

df
    Out[]:
    o_id    o_long  o_lat   d_id    d_long  d_lat      osmnx_geometry     osmnx_length
    o1  77.548349   12.996800   d1  77.554137   12.995225   LINESTRING (77.5482836 12.9966618, 77.54976259...   827.718256
    o2  77.555820   13.009082   d2  77.570458   12.995690   LINESTRING (77.555814 13.0090627, 77.5556026 1...   2588.006507
    o3  77.576325   13.014630   d3  77.583616   13.009188   LINESTRING (77.57588320000001 13.0146859, 77.5...   1107.137060
    o4  77.564848   12.990121   d4  77.551316   12.988570   LINESTRING (77.56473080000001 12.9898858, 77.5...   1744.708360
    o5  77.590529   12.992340   d5  77.598469   12.988289   LINESTRING (77.5901456 12.9920295, 77.5905355 ...   1097.493520

Part 2 of the answer. Saving this dataframe as a shapefile:

df = df.rename(columns = {'osmnx_geometry': 'geometry'})
gpdf = gpd.GeoDataFrame(df, geometry =df['geometry'])
gpdf.to_file('osmnx_shortestpaths.shp')

I also explore OSRM (for fastest routes) and Gmaps Directions API (for traffic-based most efficient routes) to calculate routes for the same set of O-D pairs, the scripts for the same can be found here.

Upvotes: 4

gboeing
gboeing

Reputation: 6442

The following steps would work:

  1. Open your shapefile with geopandas
  2. For each origin point in your shapefile, use OSMnx to find the nearest network node, then do the same for each destination point
  3. Calculate the shortest path between each origin/destination node pair, using nx.shortest_path
  4. Save the route to a MultiLineString wkt
  5. As the wkt is plain-text, just save this text to disk using any Python serialization method. Or assemble all the MultiLineStrings themselves into a geopandas GeoSeries and save that to disk as a shapefile or a GeoJSON file.

Upvotes: 2

Related Questions