Solving the Traveling Tesla Salesman Problem with Python and Concorde

http://mortada.net/drafts/the-traveling-tesla-salesman.html

by _dps • 11 years ago

111 36 11 years ago

_dps2• 11 years ago

Disclosure / for dang: I edited the title per my interpretation of the guidelines. In context it's not misleading, but on HN I figured "The Traveling Tesla Salesman" in isolation would cause many mistaken clicks and could be taken to be linkbait.

Dan, please edit back (and bury this comment) if I overstepped :)

dang• 11 years ago

It looks fine to me.

pvdebbe2• 11 years ago

The map doesn't actually show the optimal path. It is proven that "loops" (the ways crossing each other) can be straightened, and the new version will be shorter. There is one east of Alberquerque.

_dps2• 11 years ago

That's an interesting result; do you happen to have a citation? I couldn't find one with a few minutes of Google Scholar.

If I understand Concorde's claims correctly, there is still the question of finite numerical precision (it doesn't seem to use MPFR or any other arbitrary precision library). Perhaps the suboptimality of the path is less than 1e-7 or 1e-16 (depending on precision) times the distance between the "looped" cities?

Having said that, one of the authors of Concorde is R. Bixby, a co-author of CPLEX (which was for decades, and may still be, the industry standard LP solver including for branch-and-bound problems). And Chvatal is another very widely regarded LP researcher. So I would take Concorde's claims of optimality at face value (though of course there could be a data input error somewhere).

Edit: Ah, I misunderstood the sense of "loop"; I thought there was a subcircuit (which I believe can be optimal in some cases), but instead there are two segments crossing each other that, per wrk1's comment below, should really be shorter if their destinations were "swapped". Rough Google-maps math suggests that would reduce the distance by ~10 miles out of ~16k, which seems well above numerical precision.

wrk1• 11 years ago

You don't need a citation - look at NM. By straightening the loop, the path will be shorter, due to the triangle inequality.

pvdebbe2• 11 years ago

I don't have a citation at hand, but the proof is simple enough. It does rely on the triangle inequality and can be used to construct a quick approximator for this Euclidean variation of TSP. Granted, the math is different on a surface of a sphere. The error could be caused by imprecise input values.

pkhuong• 11 years ago

In operations research, it's common to stop when a solution is provably within 1e-4 of optimum. Off the top of my head, reasons include: we don't want to optimize FP error, limited precision in the input data, and negligible real world impact.

That said, it's also well known that non-OR practitioners have less confidence in our results when there are trivial local suboptimalities, in some cases even when they don't affect the objective function (e.g., off the critical path in a scheduling problem); I've heard of several professionals who pass the output of exact (modulo stopping criteria) methods through stupid local searches just for that reason.

TeMPOraL• 11 years ago

Aside from that, those are paths for birds, not for people. I wonder how an optimal path would look like if it was forced to follow actual roads.

towelguy• 11 years ago

Also, do Teslas have enough autonomy to travel each of those distances?

Bill_Cook2• 11 years ago

Very nice blog post Mortada! I used Concorde to build an optimal tour where the geodesic distances are scaled to meters (rather than kilometers), using the TSPLIB GEOM norm. Here is a Google Map drawing http://www.math.uwaterloo.ca/tsp/tours/tesla/tesla196_tour.h... If you zoom in, you will see that it does not have the crossings that are mentioned in the comments. The data set can be found at http://www.math.uwaterloo.ca/tsp/tours/tesla/tesla196.tsp The Concorde run time on my Mac Mini was 0.88 seconds.

Scea91• 11 years ago

Just a side note:

The mentioned Christofides algorithm only works for metric TSP. In metric TSP the edges satisfy triangle inequality.

There doesn't exist any polynomial approximation algorithm for general TSP. If it existed we would be able to solve existence of Hamiltonian circuit in polynomial time by a simple reduction and therefore would be able to prove that P = NP.

gus_massa• 11 years ago

I agree. Another side note. From the article:

Note that we are making the simplifying assumptions that the Earth is a perfect sphere, and that the distance is a simple Euclidean distance, instead of a driving distance. Although one can certainly plug in a different distance metric and follow the same procedure outlined here.

I think that the deformation of the Earths surface are not important, and just change the values but not the metric properties.

But the driving distance (or driving time) are not long a metric, in particular the driving distance between A and B is not equal to the driving distance between B an A. Anyway, the superchargers are so far away that the polynomial algorithm will give the correct result (probably).

chiph• 11 years ago

I think that the deformation of the Earths surface are not important

This probably only matters if the distances are larger. Probably larger than the distance a Tesla can go on a single charge. And so can be dropped from consideration.

mrgoldenbrown2• 11 years ago

Thank you for this clarification - I was quite surprised when I read that "1.5 times optimum" sentence.

NoWhiteHorse• 11 years ago

Nice code examples.

willvarfar• 11 years ago

A great read but I really was hoping it would involve at least one jet leg using the real Concorde :)

ohitsdom• 11 years ago

Tesla superchargers lend themselves well to this problem because of the way the sites were selected. Tesla obviously wants these sites to form clear routes, and they advertise when they hit certain milestones ("NY to San Francisco all on the supercharger network!"). Which explains why the optimal route looks so nice. Very interesting read, well done.

haser_au• 11 years ago

Great write up.

Question: At the moment, you have Columbus -> Dayton -> Lima -> ... -> Indianapolis -> Cincinnati. What's the extra distance travelled if you were to go Columbus -> Lime -> ... -> Indianapolis -> Dayton -> Cincinnati? The second option just looks like a shorter path, so I'm curious.

sirclueless• 11 years ago

Not to mention the situation in New Mexico, which is trivially suboptimal by the triangle inequality.

I think there was either some kind of rounding error getting data into the TSP solver, Concorde is just giving an approximate solution, or the data preparing code in python has a bug.

ck2• 11 years ago

Tesla should have a contest, visit all 200 chargers and take a photo of yourself and get a model X

callesgg• 11 years ago

The Concorde site is Gone. 404

jordigh2• 11 years ago

I was excitedly reading through this article eager to learn how the solution worked. Instead, there was a bunch of (to me, as a mathematician) uninteresting detail about how to massage the data with Python. Once the data was in the right shape, feed it to something we will treat as a black box.

I get it that sometimes this is ok. It's perfectly fine to not care about how everything works. I am just disappointed that a blog post about the TSP doesn't contain any actual details about how to solve the TSP. If I were to write such a blog post (and I have written things of this ilk), I would spend a lot more time trying to elucidate the solver's algorithm. I like explaning algorithms.[1] That's how I feel that I've really understood a particular subject.

I suppose overall this makes me quite a different sort of person than the author. I could never tolerate running Mac OS X for any length of time, because being inconvenienced to use the debugger I want (Mac OS X's signing makes it very annoying to run gdb) and being unable to put debugging calls into my OS kernel are unacceptable compromises for me. But people who like black boxes seem to really like black boxes all the way down to the OS they're using.

[1] https://en.wikipedia.org/wiki/Medcouple#Fast_algorithm

glaberficken• 11 years ago

Checkout the link below for a sublime iPython exploration of the TSP problem.

By Peter Norvig: http://nbviewer.ipython.org/url/norvig.com/ipython/TSPv3.ipy...

HN discussion: https://news.ycombinator.com/item?id=9481423

jordigh2• 11 years ago

Thank you. This is indeed more to my liking.

stickydink• 11 years ago

Billings MT to Lusk WY is ~380 miles. That puts it well out of range of any model?

A solution that accounts for routes which are possible using only the Superchargers, would be interesting!

vvanders• 11 years ago

You could do it at 35MPH but that's pretty unrealistic.

toomuchtodo• 11 years ago

Or include destination chargers that are open to the public:

http://www.teslamotors.com/findus#/bounds/49.38,-66.94,25.82...,

mrgoldenbrown2• 11 years ago

For that you would you also want to measure distance by road, vs the distance by flying that the current solution used.

karussell• 11 years ago

We've a similar example using real world travel times here: https://graphhopper.com/api/1/examples/#optimization (use the temporary API key: 7e76e228-d7fa-4795-a8c5-ad1048de42f1)

This demonstrates that jsprit and GraphHopper combined (both open source) can be used to achieve similar performance with a lot more precise output (due to read real world data) and if you need to calculate the optimal route with multiple vehicles, time windows, capacity etc that is also not a problem. Also not by bike ;)

And if there is no charger for the Tesla I recently thought also about a solution :) https://karussell.wordpress.com/2015/05/05/solving-the-elect...

hackguru• 11 years ago

Is he gonna run out of charge between any two stations?

jashkenas• 11 years ago

The resulting "optimal" path sure doesn't look it. For example, Phoenix:

http://cl.ly/bewA

Surely it would be more optimal to cut straight across from Casa Grande to Gila Bend, and then hit the next station on the way north. No?

It would be fun to throw these same markers into the Google Maps Directions TSP engine, and see how it does... https://developers.google.com/optimization/routing/tsp#solvi...

carlob• 11 years ago

Kinda the same thing in the Wolfram Language:

    With[{
    	geopositions = ParallelMap[
    		First[
    			StringCases[
    				URLFetch["http://www.teslamotors.com" <> #],
    				("https://maps.google.com/maps?daddr=" ~~ a: Except["\""]..) :> Interpreter["StructuredGeoCoordinates"][a]
    			]
    		]&,
    		StringCases[
    			URLFetch["http://www.teslamotors.com/findus/list/superchargers/United+States"],
    			"/findus/location/supercharger/" ~~ WordCharacter..
    		]
    	]},
    	GeoGraphics[GeoPath[geopositions[[Last[FindShortestTour[geopositions]]]]]]
    ]

and the result

http://imgur.com/THIwnIY

joehuchette• 11 years ago

I believe they also use Concorde behind the scenes to actually solve the TSP instance.

shashwat986• 11 years ago

There's an appreciable suboptimality in the path near Chicago.

It would be shorter to go from Pleasant Prarie to Highland Park and then Aurora and Markham, instead of the path shown.

Solving the Traveling Tesla Salesman Problem with Python and Concorde

Related Stories