When finding some math worksheets to occupy my six year old daughter on her day off of school, I discovered a Christmas brain teaser for elementary students (in pdf format):
Find a route [between twelve cities] for Santa to follow that is as short as possible. After you have found a route, compare it to others to see if they found a shorter route.
Of course, you will immediately recognize this as the TSP. The “solution” is amusing:
Try to view this question as open-ended, or your student(s) might be working on it for days. …And if someone figures out the best answer to this question, please let me know and I’ll add it here.
Finding the optimal solution to a twelve city TSP is indeed pretty hard. So hard, in fact, that the folks at math-drills.com couldn’t find the solution. I have confidence that my readers can find the optimal solution in less than a day. But please spend Christmas with your families enjoying holiday cheer.
Happy holidays!
Punk Rock Operations Research 
December 24th, 2010 at 3:30 pm
The optimal solution goes 30,071 miles (assuming the reindeer make it into Warsaw without being distracted by any reindeer hotties as they pass near Finland).
December 26th, 2010 at 10:33 am
You are amazing, Paul!
January 3rd, 2011 at 3:56 pm
On my first attempt I got an answer of 26,651. I started by finding the shortest distance of London to Paris, then I would pick the shortest remaining distance and repeat. The last stop was Sydney.
It may be possible to go even shorter by starting with the city that is most out of the way (probably Sydney) and then choosing the shortest route remaining route.
January 9th, 2011 at 6:26 pm
Hmmm. Maybe this isn’t a TSP after all. Looking back, the instructions do not explicitly say the loop must be closed. (Brent’s solution, by the way, adds up to 37,215 if you do in fact close the circuit.) The shortest simple path appears to have length 21,694.
Idle hands are indeed the devil’s workshop. 🙂
December 22nd, 2020 at 1:05 am
[…] Vehicle Routing Problem: However, the main problem that Santa and his associates face is the problem of route planning. Santa has to define not only the number of trips necessary to deliver all the presents but also the optimal routes for each of these trips. Santa seems to find himself in the situation of having to solve several travel salesman problems (TSPs): “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”. If you would like to try solving one of these TSPs for Christmas with your children or friends, a few years ago Professor Laura Albert reported one of them on her blog Punk Rock Operation Research. […]