Travelling Salesman Problem

The Travelling Salesman Problem is a wellknown NP-hard problem in combinatorial optimization. The goal is to find the shortest possible route that visits each city and returns to the origin city.

Material

• Acrylic sheet
• Laser cutting
• Blu-Tack of different colors
• String

DIY

1. Cut the map in an acrylic sheet
2. Cut tokens
3. Tie the string to a token

1. Fix the tokens to the map using the Blu-Tack

1. Using the notes, mark the string where the solution is

Activity description

1. Tell the participants that they are big stars with their own jet, and that they want to visit all of their friends living in the cities in green, but they do not want to spend to much time in their jet eventhough it is a very comfy jet
2. Let them play, and try to find the optimal route
3. If they did not find the optimal guide them towards the optimal route (cf. note)
4. When the optimal route is found, repeat adding the blue cities, then the red ones, and finally the black ones

Sources

• a vectoriel image for the map of France
• notes in english (green, blue, red, black and complete route) and in french (green, blue, red, black and complete route)
• you can add your cities to the map and generate the corresponding LaTeX file for the notes using java -jar "svg2tikz.jar" france.svg (jar available here)

Other Activities

• Lights out
• N-queens