Poor Santa has to travel all across the country to deliver all his presents. How does he do this?
A network of presents
Christmas time is approaching. For most people this is a time to enjoy good food, and to relax. For old Santa on the other hand, it is probably the most stressful time of the year. It is quite a challenge for him to deliver gifts to children all across the country in one night. Therefore, Santa prefers to take the shortest route possible. You can think of this as a problem on a network: the nodes are the locations of the gifts, and edges between two nodes show the travel time between the locations of the two presents. Below you see an example of such a network, where Santa has to deliver four presents at different locations, and returns home afterwards.
A network of four presents. The red lines show the shortest route to deliver all four presents.
Many possible routes
Suppose that Santa has to deliver n gifts in different cities. In how many possible orderings can he deliver those gifts? As a starting point, Santa can choose all n different cities. After that, he can choose one of the n-1 remaining cities to deliver the second present. Continuing like this, you can argue that there are n*(n-1)*(n-2)*...*1=n! different ways to deliver all gifts. Out of all these n! different routes, Santa would like to take the shortest one. If he has to deliver 20 presents for example, this means that there are 2.432.902.008.176.640.000 different possible routes to deliver all presents!
Million dollar prize
Calculating the lengths of all these possible different routes is therefore not an option. Mathematicians have been trying for years to find an easier solution to find the shortest travel route, and call this problem the travelling salesman problem. This problem is much younger than Santa Claus himself, it was first studied around 1800. Since then, many mathematical tricks have been developed so that you do not have to calculate the length of all those possible routes. Still, nobody has found an efficient way to calculate the best route to deliver presents for a large number of presents. In fact, we do not even know if such an efficient method even exists. The person who finds an efficient method to deliver presents, or the person who shows that no such method exists, will be awarded a million dollar prize!
Advice for Santa
Below, you see the shortest route for Santa to deliver 20 presents across The Netherlands. We see that Santa does not have to take the causeway across the sea to deliver his presents in the north of the country, but instead he takes an inland route. He sometimes also has to turn around and take the same route again after delivering a present. Hopefully this helps Santa to deliver as many presents as fast as possible!
Shortest route for Santa to deliver these 20 presents.
You have a job interview in 20 minutes and you are in a hurry to arrive at your application in time. To make matters even more stressful, there are many routes to your destination, but you have no idea which one to select. Luckily, you have access to a navigation system that can help you in your route selection process.
Elisabeth already has an idea in mind: she would like to find the fastest possible route that goes to each address exactly once before finally returning to the station. This task is a well-known mathematical problem, namely the Traveling Salesman Problem (TSP)! How can she solve it?
Say you are living in Eindhoven and would like to spend a day in Amsterdam: what better way to get there than taking the train? Before your train departs, a whole logistic operation has taken place in the headquarters of the railway company to make this trip possible.
