Oh wait, it's trivial. The shortest distance between two Tesla Supercharger stations is a straight line. To make this more realistic, we could have the distance_on_earth function call the Google Maps Directions API instead of calculating a great circle route. For example, directions from the Auburn, Alabama (32.627837, -85.445105) to the Greenville superstation (31.855989, -86.635765) show a distance of 102 miles. "distance" : {
I can't prove that this shape is longer
We could allow the Tesla salesman to avoid "any combination of tolls, highways and ferries," or even find the shortest path by walking to all the superstations. "text" : "102 mi",
"value" : 163692
},
"duration" : {
"text" : "1 hour 30 mins",
"value" : 5415
}
Is that the shortest road path? He uses geodesic in his post. I thought it might be explained because of the projection used - projected distance measurements can differ from geocoordinate measurements. So I messed around in ArcGIS for a bit, getting WGS 1984 Web Mercator (auxilliary) projection length measurements first - that's the one used by Openstreetmaps, and I assume Google Maps uses the same. Then vanilla geocoordinate system. There wasn't a big difference between planar and geodesic. But I did find your proof that the line is longer: The other length measurement was 565 miles. Am I missing something or is he wrong?
The Pleasant Prarie - Aurora - Highland Park - Country Club Hills portion is more obviously sub-optimal. Then near New York City, the path passes within about three miles of three stations without stopping, then doubles back more than 15 miles to connect them.
The Concorde tool he used "can find the exact optimal path" but I can't tell from the documentation what it returns if it cannot definitely find the shortest path; perhaps it does the best it can. We don't see how Mr. Mehyar used it because he skips a step in his wonderful report: Apparently TSPs with a large number of nodes can be definitively solved, and this has been true for some time. I would be surprised if the Concorde program would report a path as the definite solution when there is still some doubt, but I can't believe that what looks like the long way around New Mexico is actually the shortest path.Am I missing something or is he wrong?
He says this is "the optimal path that I found," which might be understood to mean that it is not the optimal path, but he also says he was "most interested in finding the exact optimum." [13] # create input file for Concorde TSP solver
[14] # after running the Concorde executable, parse the output fileThere wasn't a big difference between planar and geodesic
At 35°N, over a few hundred miles, I wouldn't expect much projection error. A flight plotter shows very minimal curvature.