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.