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.

Concorde produces a provably optimal tour, but it follows the TSPLIB input format and requires that all distances be integers. There will thus be rounding error in converting the geodesic distances to integers. To obtain greater precision, the geodesic distances should be scaled to meters rather than kilometers.