Around The World, And Back

The Travelling Salesman Problem (TSP) is a graph theory problem which requires the most efficient, i.e. shortest, closed loop path through which a salesman can travel to each of n cities, exactly once [1]. Such a loop is called a Hamiltonian cycle [2] and there is no known general solution to the TSP. Practical applications to the solution of the TSP include the scheduling of tasks on a computer and ordering of genome features [3]. Inspired by the last example on this page, I tried projecting the shortest path through every country on the planet and visualising it on a map. To do this, I used the FindShortestTour function, which tries to find the shortest path though all the countries—going through each country once.

I used the following code to gather the names of the countries in the world and to find the shortest path going through the centre of each country.

c = CountryData["Countries"]; geocen = Map[CountryData[#, "CenterCoordinates"] &, c]; {dis, path} = FindShortestTour[geocen];

Next, I visualised the results on a map using the following code.

Export["mapflat.svg", GeoGraphics[{FaceForm[White], EdgeForm[{Thin, Gray}], Polygon[c], GeoPath[c[[path[[1 ;; Length@c]]]]]}, GeoRange -> "World", GeoBackground -> None, ImageSize -> 700]]

. . .

. . .

To view the path using an orthographic projection...

GeoGraphics[{FaceForm[White], EdgeForm[{Thin, Gray}], Polygon[c], GeoPath[c[[path[[1 ;; Length@c]]]]]}, GeoRange -> "World", GeoProjection -> {"Orthographic", "Centering" -> CountryData["World", "CenterCoordinates"]}, GeoBackground -> None, ImageSize -> 700]

Orthographic projection.

Orthographic projection.

I then created an animation of the travelling salesman going around the globe.

Export["animation.gif", 
    GeoGraphics[{GeoStyling[FaceForm[White], EdgeForm[{Thin, Gray}]], Polygon[CountryData["Countries"]], GeoStyling[FaceForm[Orange]], Polygon[c[[path[[#]]]]], {Gray, GeoPath[geocen[[path[[1 ;; #]]]]]}}, 
     GeoRange -> "World", GeoProjection -> {"Orthographic", "Centering" -> geocen[[path[[#]]]]}, GeoBackground -> None, ImageSize -> 300] & /@ Range@(c+1), 
 ImageResolution -> 300, "DisplayDurations" -> 1.5]

This animation can also be found here.

As the travelling salesman moves to the next country, the centre of projection also moves to that country. The animation begins with Afghanistan because the list of countries CountryData["Countries"] returned were arranged in alphabetical order. Bear in mind that this is an attempt at finding the shortest path, going through the geographic centre of each country, which results to a distance of about 112,312 miles. This distance can be reduced in a number of ways -- taking a different route for instance, or, starting from a different country.

[1] Weisstein, Eric W. "Traveling Salesman Problem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/TravelingSalesmanProblem.html

[2] Weisstein, Eric W. "Hamiltonian Cycle." From

[3] Erica Klarreich (2013)