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.
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!
This article first appeared in Dutch on nemokennislink.nl.