# The Traveling Tesla Salesman (Part 2)

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.

Show Super Chargers Show Optimal Path (as the crow flies)
Show Optimal Path for Driving Distance Show Optimal Path for Driving Time

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:

In [1]:
import json

In [2]:
def get_distance(direction_data):
"""
get distance from google directions api response,
the unit for this field is meter
"""

In [3]:
def get_time(direction_data):
"""
get time from google directions api response,
the unit for this field is seconds
"""


### 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_SECTION

Here 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.

In [4]:
# after running the Concorde executable, parse the output file
def parse_solution(filename):
solution = []
f = open(filename, 'r')
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:

In [5]:
time_solution = parse_solution('../../../../../TSP/concorde/TSP/tesla196_time.sol')
print(time_solution)

[0, 19, 80, 81, 149, 49, 8, 187, 185, 113, 114, 43, 44, 72, 73, 87, 101, 130, 51, 76, 126, 151, 135, 146, 104, 157, 158, 165, 136, 59, 137, 186, 110, 60, 18, 180, 128, 93, 173, 107, 7, 71, 46, 119, 11, 92, 82, 35, 155, 183, 38, 3, 156, 179, 159, 184, 132, 189, 83, 39, 175, 150, 78, 67, 97, 47, 31, 100, 160, 66, 68, 70, 118, 16, 56, 62, 79, 57, 36, 190, 20, 27, 63, 195, 53, 153, 154, 142, 102, 42, 129, 21, 4, 77, 171, 120, 99, 86, 10, 140, 26, 85, 139, 124, 88, 138, 94, 167, 12, 143, 125, 152, 176, 174, 188, 54, 191, 103, 178, 148, 147, 58, 109, 64, 121, 61, 133, 182, 37, 122, 69, 48, 164, 193, 172, 28, 24, 55, 131, 144, 34, 169, 116, 25, 17, 14, 15, 105, 141, 123, 117, 194, 1, 90, 50, 112, 108, 145, 134, 32, 9, 40, 127, 163, 166, 52, 84, 91, 168, 115, 2, 111, 96, 45, 74, 33, 95, 98, 89, 30, 5, 6, 29, 23, 162, 65, 192, 13, 75, 161, 177, 41, 106, 22, 170, 181]

In [6]:
dist_solution = parse_solution('../../../../../TSP/concorde/TSP/tesla196_distance.sol')
print(dist_solution)

[0, 181, 170, 22, 106, 41, 177, 161, 75, 13, 192, 65, 162, 23, 29, 6, 5, 30, 89, 98, 95, 33, 45, 74, 96, 111, 2, 168, 115, 91, 84, 52, 166, 163, 127, 9, 40, 32, 134, 145, 108, 112, 90, 50, 1, 194, 117, 123, 141, 105, 15, 14, 17, 25, 116, 169, 34, 144, 131, 55, 24, 28, 172, 193, 164, 48, 69, 122, 37, 182, 133, 61, 64, 121, 109, 58, 147, 148, 178, 103, 191, 54, 188, 174, 176, 152, 125, 143, 12, 167, 94, 138, 10, 86, 99, 120, 171, 77, 4, 21, 129, 42, 102, 142, 154, 153, 140, 26, 85, 53, 195, 139, 124, 88, 190, 20, 63, 27, 36, 57, 79, 62, 56, 16, 118, 70, 68, 66, 160, 31, 100, 47, 97, 67, 78, 150, 175, 39, 83, 189, 132, 184, 159, 179, 156, 3, 38, 183, 155, 35, 82, 92, 11, 119, 46, 71, 7, 107, 173, 93, 128, 18, 59, 137, 186, 110, 60, 180, 136, 165, 158, 157, 104, 146, 135, 151, 126, 76, 51, 130, 101, 87, 73, 72, 44, 43, 114, 113, 185, 187, 8, 49, 149, 81, 80, 19]


Using the distance and time data I've gathered, we can compute the total for each of the two solutions above

In [7]:
import requests
import pandas as pd
import numpy as np

In [8]:
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)

In [9]:
dist_data.head()

Out[9]:
0 1 2 3 4 5 6 7 8 9 ... 186 187 188 189 190 191 192 193 194 195
0 0 1945315 1054643 2591824 4745197 1620117 1614580 1795659 213925 1368344 ... 2187259 143375 3725380 2347163 4076391 4101661 647570 4749223 2128673 4282383
1 1945315 0 909347 1271497 3171191 1638455 1658375 1734424 2160663 627124 ... 2592915 2090112 2098147 875986 2587359 2474428 1802149 2813032 184157 2793351
2 1054643 909347 0 1614904 3700776 1119175 1139095 1215144 1260719 323923 ... 2073635 1190168 2680959 1361528 3099471 3057240 902205 3704802 1084253 3305463
3 2591824 1271497 1614904 0 2428914 1437258 1444084 1310581 2798646 1392709 ... 2162766 2728095 2250950 397853 1708109 2627231 2192619 3274793 1199155 1957593
4 4745197 3171191 3700776 2428914 0 3722803 3729630 3658901 4949353 3406056 ... 4632687 4878802 1231895 2441244 891413 916442 4464666 1288786 3002792 783575

5 rows × 196 columns

In [10]:
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)

In [11]:
time_data.head()

Out[11]:
0 1 2 3 4 5 6 7 8 9 ... 186 187 188 189 190 191 192 193 194 195
0 0 64756 34969 84827 153716 53273 53027 58998 7404 45808 ... 70193 5292 120466 76635 131997 132338 22390 155144 70559 140084
1 64756 0 30201 40069 101623 53995 54757 58177 71398 20734 ... 83432 69286 68080 27624 85757 79952 60121 93278 5952 93844
2 34969 30201 0 52689 119325 36668 37430 40850 41719 11417 ... 66105 39607 86075 44057 99859 97947 30442 120753 36168 107946
3 84827 40069 52689 0 80278 46651 47280 43987 91491 45717 ... 70068 89379 71257 12835 56181 83129 73534 105935 39209 62054
4 153716 101623 119325 80278 0 120271 120900 119549 160128 109336 ... 145328 158016 41566 81974 29674 30143 145534 43124 97043 26268

5 rows × 196 columns

For each hop in the optimal path, look up the distance in meters

In [12]:
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()

Out[12]:
18638.330102274002

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:

In [13]:
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()

Out[13]:
293.87833333333333
In [14]:
hop_times.sum() / 24

Out[14]:
12.244930555555555

That's more than $12$ days without stopping!

This should conclude this fun topic. Hope you enjoy this post!