Shortening the 29th Olympic Torch Tour
The Olympic games were held in Beijing, China. According to Olympic tradition, the torch is lit at Olympia and then handed over to the city holding the games, in this case Beijing. The torch was carried from Beijing and went around the world, then traveled through the major cities of China, making a tour of about 90,000 kilometers.[more]
This Demonstration, using algorithms for the traveling salesman problem, optimizes the international and China torch's tour to about 78,191 kilometers, which is shorter than the official tour by 11,721 kilometers (about 15%). It includes all 54 cities (19 international, 33 China and Beijing), starting and finishing in Beijing.[less]
Snapshot 1: the optimal international tour (excluding China) of 63,033 km on a 2D world map
Snapshot 2: the complete optimal tour of 78,191 km on a 2D China map
Snapshot 3: the official tour of 89,912 km on a 3D world map (Source: Torch Relay Beijing 2008)
The source data comes from Mathematica's CountryData and CityData collections. The distance between two cities is calculated by the great circle arc function. The algorithms used are the ThreeOpt and FindShortestTour methods. The Demonstration uses random seeds to improve the ThreeOpt algorithm.
 F. Wu, "Chapter 9," Manipulate@Mathematica, Beijing: Tsinghua, 2010.
 F. Wu, "Optimizing the 2008 Beijing Olympic Torch Tour," SimWe Journal, 14, 2008 pp. 71–90.
 G. Reinelt, "The 3-Opt Heuristic and Variants", The Traveling Salesman Computational Solution for TSP Applications, New York: Springer–Verlag, 1994 pp. 117–123.
 D. S. Johnson and L. A. McGeoch, "Experimental Analysis of Heuristics for the STSP," The Traveling Salesman Problem and Its Variations (G. Gutin and A. P. Punnen, eds.), Dordrecht: Kluwer Academic Publishers, 2002 pp. 407–450.