9846

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.
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.

THINGS TO TRY

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+