A Route to Remember

I was eagerly pacing up and down the waiting room of the Honda Car Service Center. I was looking forward to meeting Ujaval Gandhi the owner of Spatial Thoughts, the primier learning platform for modern geospatial technologies. In the next hour we were going to meeting for coffee. But i had a few errands to do before seeing him.

  • Fedex a package
  • Fill gas at Quiktrip
  • Pick up my prescription medicine at Walgreens
  • Pick up some tools at Home Depot
  • Some grocery at Schnucks

I needed to comeup with a plan to do all the errands in the shortest possible time so i could reach Starbucks in time. I came up with a plan.

  1. Get address of all the locations via Google
  2. Geocode the addresses via "geopy" python module
  3. Plot it on a map to get an idea using "folium" module
  4. Find shortest route to visit the locations using OpenRouteService.org api
  5. Plot the route on folium module
In [15]:
import geopy
from geopy.geocoders import Nominatim
from geopy.extra.rate_limiter import RateLimiter
import pandas as pd
import folium
import requests
import json
In [16]:
# ORS_API_KEY = '<replace this with your key>'
In [17]:
# places to visit
places = [['honda','15532 Manchester Rd, Ellisville, MO 63011'],
         ['fedex','5 Clarkson Rd, Ellisville, MO 63011'],                  
         ['walgreens', '16105 Manchester Rd, Ellisville, MO 63011'],
         ['quiktrip','15902 Manchester Rd, Ellisville, MO 63011'],
         ['home depot', '37 Towne Dr, Ellisville, MO 63011'],
         ['schnucks', '16580 Manchester Rd, Wildwood, MO 63040'],
         ['starbucks', '125 Plaza Dr, Wildwood, MO 63040']
         ]
In [18]:
# Create pandas dataframe
df = pd.DataFrame(places, columns = ['place', 'address'])
df
Out[18]:
place address
0 honda 15532 Manchester Rd, Ellisville, MO 63011
1 fedex 5 Clarkson Rd, Ellisville, MO 63011
2 walgreens 16105 Manchester Rd, Ellisville, MO 63011
3 quiktrip 15902 Manchester Rd, Ellisville, MO 63011
4 home depot 37 Towne Dr, Ellisville, MO 63011
5 schnucks 16580 Manchester Rd, Wildwood, MO 63040
6 starbucks 125 Plaza Dr, Wildwood, MO 63040
In [19]:
# tip: https://towardsdatascience.com/geocode-with-python-161ec1e62b89
# Using Nominatim Geocoding service
locator = Nominatim(user_agent='myGeocoder') 
In [20]:
# function to dalay geocoding calls
geocode_fn = RateLimiter(locator.geocode, min_delay_seconds=2)
In [21]:
# Geocoding
df['location'] = df['address'].apply(geocode_fn)
In [22]:
# create longitude, laatitude and altitude from location column (returns tuple)
df['point'] = df['location'].apply(lambda loc: tuple(loc.point) if loc else None)
In [23]:
# split point column into latitude, longitude and altitude columns
df[['latitude', 'longitude', 'altitude']] = pd.DataFrame(df['point'].tolist(), index=df.index)
In [24]:
df
Out[24]:
place address location point latitude longitude altitude
0 honda 15532 Manchester Rd, Ellisville, MO 63011 (West County Honda, 15532, Manchester Road, El... (38.59175415, -90.5701563705986, 0.0) 38.591754 -90.570156 0.0
1 fedex 5 Clarkson Rd, Ellisville, MO 63011 (5, Clarkson Road, Ellisville, Saint Louis Cou... (38.5933265, -90.5848154, 0.0) 38.593327 -90.584815 0.0
2 walgreens 16105 Manchester Rd, Ellisville, MO 63011 (16105, Manchester Road, Ellisville, Saint Lou... (38.591023, -90.5964036, 0.0) 38.591023 -90.596404 0.0
3 quiktrip 15902 Manchester Rd, Ellisville, MO 63011 (15902, Manchester Road, Ellisville, Saint Lou... (38.5919868, -90.5866775, 0.0) 38.591987 -90.586677 0.0
4 home depot 37 Towne Dr, Ellisville, MO 63011 (Towne Drive, Ellisville, Saint Louis County, ... (38.5979707, -90.5996285, 0.0) 38.597971 -90.599628 0.0
5 schnucks 16580 Manchester Rd, Wildwood, MO 63040 (Schnucks, 16580, Manchester Road, Wildwood, S... (38.580228399999996, -90.61774964813051, 0.0) 38.580228 -90.617750 0.0
6 starbucks 125 Plaza Dr, Wildwood, MO 63040 (125, Plaza Drive, Wildwood, Saint Louis Count... (38.5822086, -90.628069, 0.0) 38.582209 -90.628069 0.0
In [25]:
# tip: https://openrouteservice.org/example-optimize-pub-crawl-with-ors/
# Mapping using folium
my_map = folium.Map(
    location=[38.5933265, -90.5848154],
    tiles='Stamen Toner',
    zoom_start=13)
df.apply(lambda row:folium.Marker(location=[row['latitude'], row['longitude']]).add_to(my_map), axis=1)

# display map
my_map
Out[25]:
Make this Notebook Trusted to load map: File -> Trust Notebook
In [26]:
# Data for finding shortest route
start_location = [df.iloc[0]['longitude'], df.iloc[0]['latitude']]
end_location = [df.iloc[6]['longitude'], df.iloc[0]['latitude']]
vehicle = [{ "id":1,
            "profile":"driving-car",
            "start":start_location,
            "end":end_location,
            "capacity":[6]    
}]
# stops
stops = []
for i in range(5):
    stop = {}
    stop['id'] = i + 1
    stop['service'] = 300
    stop['delivery'] = [1]
    stop['location'] =  [df.iloc[i + 1]['longitude'], df.iloc[i + 1]['latitude']]
    stops.append(stop)  
In [27]:
# api call to openrouteservice

body = {'jobs':stops, 'vehicles': vehicle}
headers = {
    'Accept': 'application/json, application/geo+json, application/gpx+xml, img/png; charset=utf-8',
    'Authorization': ORS_API_KEY,
    'Content-Type': 'application/json; charset=utf-8'
}
response = requests.post('https://api.openrouteservice.org/optimization', json=body, headers=headers)

print(response.status_code, response.reason)
print(response.text)
200 OK
{"code":0,"summary":{"cost":993,"unassigned":0,"delivery":[5],"amount":[5],"pickup":[0],"service":1500,"duration":993,"waiting_time":0,"computing_times":{"loading":76,"solving":2}},"unassigned":[],"routes":[{"vehicle":1,"cost":993,"delivery":[5],"amount":[5],"pickup":[0],"service":1500,"duration":993,"waiting_time":0,"steps":[{"type":"start","location":[-90.5701563705986,38.59175415],"load":[5],"arrival":0,"duration":0},{"type":"job","location":[-90.5848154,38.5933265],"id":1,"service":300,"waiting_time":0,"job":1,"load":[4],"arrival":135,"duration":135},{"type":"job","location":[-90.5866775,38.5919868],"id":3,"service":300,"waiting_time":0,"job":3,"load":[3],"arrival":495,"duration":195},{"type":"job","location":[-90.5996285,38.5979707],"id":4,"service":300,"waiting_time":0,"job":4,"load":[2],"arrival":992,"duration":392},{"type":"job","location":[-90.5964036,38.591023],"id":2,"service":300,"waiting_time":0,"job":2,"load":[1],"arrival":1414,"duration":514},{"type":"job","location":[-90.61774964813053,38.5802284],"id":5,"service":300,"waiting_time":0,"job":5,"load":[0],"arrival":1931,"duration":731},{"type":"end","location":[-90.628069,38.59175415],"load":[0],"arrival":2493,"duration":993}]}]}

In [28]:
# Total Drive Time in minutes
data = response.json()
total_drive_time = data['summary']['cost'] / 60
In [29]:
# Shortest Route
steps = data['routes'][0]['steps']
route_points = []
for step in steps:
    route_step = (step['location'][1], step['location'][0])
    route_points.append(route_step)
route_points
Out[29]:
[(38.59175415, -90.5701563705986),
 (38.5933265, -90.5848154),
 (38.5919868, -90.5866775),
 (38.5979707, -90.5996285),
 (38.591023, -90.5964036),
 (38.5802284, -90.61774964813053),
 (38.59175415, -90.628069)]
In [30]:
# tip: https://deparkes.co.uk/2016/06/03/plot-lines-in-folium/
# Mapping using folium

ave_lat = sum(p[0] for p in route_points)/len(route_points)
ave_lon = sum(p[1] for p in route_points)/len(route_points)
 
# Load map centred on average coordinates
route_map = folium.Map(
    location=[ave_lat, ave_lon],
    tiles='Stamen Toner',
    zoom_start=14)
 
#add a markers
for each in route_points:  
    folium.Marker(each).add_to(route_map)
 
#fadd lines
folium.PolyLine(route_points, color="red", weight=2.5, opacity=1).add_to(route_map)

route_map
Out[30]:
Make this Notebook Trusted to load map: File -> Trust Notebook

Conclusion

The route plan worked like a charm. I was able to reach starbucks on time. It was really wonderful meeting Ujaval. Have a wonderful discussion regarding leveraging Python for GeoSpatial Analysis.