Shortening the 29th Olympic Torch Tour

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

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]

Contributed by: Frederick Wu (March 2008)
Open content licensed under CC BY-NC-SA


Snapshots


Details

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.

References

[1] F. Wu, "Chapter 9," Manipulate@Mathematica, Beijing: Tsinghua, 2010.

[2] F. Wu, "Optimizing the 2008 Beijing Olympic Torch Tour," SimWe Journal, 14, 2008 pp. 71–90.

[3] G. Reinelt, "The 3-Opt Heuristic and Variants", The Traveling Salesman Computational Solution for TSP Applications, New York: Springer–Verlag, 1994 pp. 117–123.

[4] 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.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send