In part one of this blog post I look at a simplified distance metric: straight line (i.e. big circle) distance between two points on earth. A popular question has been: how about using the actual driving distances? Let's have some fun with this here in part two.
I will actually look at two additional metrics here - driving distances and driving times. Both are availabe via the Google Directions API.
Optimal paths for driving directions¶
The results I found are visualized as follows. There are $3$ different kinds of distance metrics now: as-the-crow-files (as in part one), driving distances, and driving times.
You can see that for the most part the optimal routes are somewhat similar, but there are several sections where the routes differ. I find the area around Albuquerque very interesting. Also interesting is the Marathon Supercharger in the Florida Keys: it clearly makes a big difference in the route whether you can fly over water or not :)
The following are the steps I took to arrive at the results.
Fetch data¶
First we need to get the distance and time data from the Google Directions API. The JSON response contains a large amount of information but we basically only care about the total driving time and distance. See the documentation if you want to try it out yourself. I'll skip the details except to show these functions below that can be used to parse the JSON response:
import json
def get_distance(direction_data):
"""
get distance from google directions api response,
the unit for this field is meter
"""
return json.loads(direction_data)['routes'][0]['legs'][0]['distance']['value']
def get_time(direction_data):
"""
get time from google directions api response,
the unit for this field is seconds
"""
return json.loads(direction_data)['routes'][0]['legs'][0]['duration']['value']
Concorde format¶
After fetching the time and distance data between every pair of superchargers, we can construct the optimization problem. The TSP can be specified by a full weight matrix. The header is as follows:
NAME: tesla196_time
TYPE: TSP
COMMENT: Tesla 196 superchargers with driving time (seconds)
DIMENSION: 196
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: FULL_MATRIX
EDGE_WEIGHT_SECTIONHere are the links for the full TSP files: driving distance and driving time.
Similar to part one, we can now run the Concorde solver to get a .sol file for each .tsp input.
# after running the Concorde executable, parse the output file
def parse_solution(filename):
solution = []
f = open(filename, 'r')
for line in f.readlines():
tokens = line.split()
solution += [int(c) for c in tokens]
f.close()
solution = solution[1:] # first number is just the dimension
return solution
Here I have the optimal routes for driving time and driving distance:
time_solution = parse_solution('../../../../../TSP/concorde/TSP/tesla196_time.sol')
print(time_solution)
dist_solution = parse_solution('../../../../../TSP/concorde/TSP/tesla196_distance.sol')
print(dist_solution)
Using the distance and time data I've gathered, we can compute the total for each of the two solutions above
import requests
import pandas as pd
import numpy as np
rv = requests.get('https://raw.githubusercontent.com/mortada/notebooks/master/blog/TSP/tesla196_distance.tsp')
data = rv.text.split('\n')[7:-1]
dist_data = {}
for i, line in enumerate(data):
dist_data[i] = line.strip().split()
dist_data = pd.DataFrame(dist_data).astype(int)
dist_data.head()
rv = requests.get('https://raw.githubusercontent.com/mortada/notebooks/master/blog/TSP/tesla196_time.tsp')
data = rv.text.split('\n')[7:-1]
time_data = {}
for i, line in enumerate(data):
time_data[i] = line.strip().split()
time_data = pd.DataFrame(time_data).astype(int)
time_data.head()
For each hop in the optimal path, look up the distance in meters
hop_dists = []
for k in range(len(time_solution)):
i = dist_solution[k]
j = dist_solution[(k + 1) % len(dist_solution)]
hop_dists.append(dist_data.ix[i, j] / 1000 * 0.621371) # convert meters to miles
hop_dists = pd.Series(hop_dists)
hop_dists.sum()
Recall that in part one, the as-the-crow-flies total is about $15,673$ miles. Now we see that the actual driving distance is naturally longer at $18,638$ miles. Similarly we can compute the optimal time:
hop_times = []
for k in range(len(time_solution)):
i = time_solution[k]
j = time_solution[(k + 1) % len(time_solution)]
hop_times.append(time_data.ix[i, j] / 60 / 60) # convert seconds to hours
hop_times = pd.Series(hop_times)
hop_times.sum()
hop_times.sum() / 24
That's more than $12$ days without stopping!
This should conclude this fun topic. Hope you enjoy this post!