The Netherlands is a small country, it has a total area of 33,893 square kilometers and is divided into twelve provinces. The Netherlands, with its beautiful cities and culture, attracts a lot of tourists every year. On a yearly basis it is chosen by 17 million foreign tourists, making it the 20th most visited country in the world (source: Wikipedia). Suppose you are coming to the Netherlands for the first time, you want to enjoy your time in the country in the best possible way and probably visit and see as much as possible. So you rend a car and you decide to travel around. But now the challenge begins, planning such a trip!
Probably this is also the worse part of your trip; thankfully a group of mathematicians organized a contest to solve this problem. Let's see what they did and what kind of results they obtained. Next time you can amaze your travel partners using some mathematics to construct the best plan to travel around the country you will visit!
Contest: the traveling mathematicians problem
Two times per year, all scientists involved in NETWORKS (a mathematics research program) come together to discuss their newest inventions. This year a contest was held, to see which of them is the most ingenious. They had to solve a problem called the Traveling Salesman Problem! This problem goes as follows: suppose for a minute you have to deliver packages in some cities in the Netherlands, then you want to visit all these cities once and finally also return home, where you started from. The question is not just to find any route, but the route with the shortest travel time. Essentially this route is the same route as the one a traveler needs in order to travel around the country with a mini-bus! But delivering packages is a little bit boring so we formulated the problem in the contest a little bit differently, the contestants were asked to figure out how mathematicians should be brought home.
In the figure below you can see all capitals of the provinces of the Netherlands. (Did you know all of them?)
The numbers represent the time it takes in minutes to go from one capital to the other. Now let’s go to the problem. In Utrecht, 11 mathematicians are waiting, and they each live in one of the 11 provinces besides Utrecht. You have one bus ready in which you can bring the mathematicians to their houses.
Your goal: bring all the mathematicians home and go back to Utrecht as fast as possible!
Have you ever been in a bus with a mathematician? They won’t stop talking about how interesting their work is, which makes the bus driver a little bit drowsy. For every mathematician in the bus, the bus will take 10% longer to reach their destination! If you are bringing 11 mathematicians, you take 1.85 times longer to reach the next city!
(The problem seems a bit weird, but of course it’s not really about bringing mathematicians home. This problem originates from a delivery problem, where packages have to be delivered to a number of places, and deliveries take longer when more packages are taken along. A similar problem is one where passengers have to be taken along on a train, but the more passengers you take along, the more train parts you will need and the slower the train goes. It is more fun however to think about bringing mathematicians home, and math is supposed to be fun!)
Now let’s look at a possible solution, which is shown in the figure on the left. This is the plan: first take seven mathematicians with you in the bus, and bring them to the northern capitals of the Netherlands. The first part of the trip, from Utrecht to Haarlem will be quite tough for the bus driver, since there will be seven mathematicians, but luckily one of them exits at Haarlem and six will remain. Five mathematicians will remain after Lelystad, four after Leeuwarden, etc.
After this tour, the final four mathematicians are brought home. First the one living in The Hague, after which only the mathematicians with a ``zachte G’’ are left.
Question: Can you compute how much time it took to bring all mathematicians home following this route? Remember, for every mathematicians on board the travel time increases by 10%.
Mathematicians like challenges, so we made the problem even harder: we now have a map, consisting of the 100 biggest cities in the Netherlands. We were able to find one mathematician living in each of these cities.
For this experiment, we brought all these mathematicians to Utrecht, and asked ourselves what is the best way to bring them home. In this experiment, the bus driver takes 1% longer for every mathematician in the bus.
Question: for the problem with 100 cities, do you know how many different solutions exist to this problem? (you should restrict to sensible solutions, so no solutions where you purposely take longer routes than necessary)
Since every city has to be visited once, except for Utrecht, you already have 99! (read the `!’ as factorial, that is 5! = 5*4*3*2*1=120) possible orders. Then, between every two adjacent deliveries, you have to decide whether you return to the depot or not, giving you another 2^(100-2) options.
The total number of options: 99! * 2^98 (Which is a lot!)
It is time to see what our contestants came up with, and what methods they used!
The contestants solutions
Our first contestant tried to generate semi-random solutions to find a good solution, which goes as follows.
First you say how many groups there should be, say N. Then you throw an N-sided fair coin 100 times to decide to which group each city belongs. After this, for each group you go from Utrecht to the nearest city in the group. From this city you go the nearest again, and so on, until every city has been finished. This is called the nearest-neighbor algorithm.
This experiment is repeated 100000 times, after which the best solution is chosen. The solution that is shown was the best one, in which all mathematicians are home after 5334 minutes, which is about 89 hours. At some point in the solution, there are more than 90 mathematicians in the bus. Poor bus driver…
If you want to solve a problem, it is always good to have a baseline to compare against. Otherwise, how can you say how good your solution is?
For example, suppose you are making a multiple-choice exam, where you can choose A, B, C or D for each answer. By randomly choosing an answer to each question, you a 25% chance to get it right. If the exam has 20 questions, you’ll get 5 questions right, just by randomly choosing. Therefore, only if you get more than 5 questions right, you should be awarded a higher grade than 1.0.
When you read the solutions from the next contestants, try and see how much better that is than randomly choosing.
Our next two contestants, did things a little bit smarter. First, they looked which cities were close to each other. One did this using a smart algorithm, the other did it by hand (the one by hand was actually better!). They both found three so called clusters. Then, they used a genetic algorithm to find the best route for each of the clusters.
A genetic algorithm is an algorithm that, from two solutions, can create a better solution by taking the best of both. For example: suppose Sophie solves the problem, and she has a very efficient route through the northern part of the Netherlands, but her solution is slow in the south. For Benjamin it is the other way around: his route through the south is excellent, but his northern tour is not so good. If Sophie and Benjamin would join forces and pick the best of both worlds, they surely will find a great solution. A genetic algorithm combines parts of thousands of solutions, to make even better solutions.
The solutions would bring all mathematicians home after 3866 and 3738 minutes, which correspond to 64 hours and 26 minutes and 62 hours and 18 minutes respectively, the latter being worthy of a second place!
Choosing this route will take 62 hours and 18 minutes to bring all mathematicians home!
Only two contestants left, let’s talk about another way to solve this problem, called local search.
First, we start with a random solution, so perhaps the one that our first contestant found! Then, we make a very small change, for example we swap the order in which we visit two cities, or we move a city from the blue to the red tour. If this new solution is better, then we stick with that one. And again, we’ll try to improve the solution. We repeat this until we cannot get any better. You then find a solution like the one that is shown, which takes 3823 minutes, which is equal to 63 hours and 43 minutes, well-worthy of a third place!
The winner of the competition found the solution that is shown below. The conclusion is, split the mathematicians into three groups, then do a big city tour through the northern part, south-western part and south-eastern part of the Netherlands.
The method that was used is called simulated annealing. It is similar to local search, but there is a small twist. Sometimes, you are happy to make a change that makes your solution worse! The longer you run the algorithm, the more critical you become in accepting worse solutions.
Because you sometimes accept a bad solution, you are able to find a very good solution if you make another change.
The best solution takes 3531 minutes, which is 59 hours and 29 minutes. So it seems like it is a good idea to use multiple buses, or hire bus drivers that do not get bored by mathematicians that easily!
Finishing up
After all mathematicians were brought home (in the optimal way of course), and the contest was officially over. Even for a problem that can be explained pretty easily, there are many possible solutions. Especially algorithms like local search or simulated annealing work very well. Did you know that the time table for trains, or the refilling of supermarkets can be computed using these methods?
Hence if you travel to the Netherlands use Utrecht as a central point and make three journeys to the north, to the south-east and to the south-west side of the country. And probably it will take much less time than just choosing the next destination at random.
Oh and the bus driver? He is happy he doesn’t have to deal with all these mathematicians anymore, but he did subscribe to the Network Pages, because some of the stories he heard in the bus seemed quite interesting.
Recently there has been a breakthrough in the field of algorithms for geometric network problems, concerning the complexity of the Euclidean Travelling Salesman Problem.
Are you one of those people who always seems to pack just a bit too much for your car to handle when packing for a vacation? Then you should have a look at this article!
On Friday 24th of September Professor Ton Koonen received a royal distinction “Ridder in the Orde van de Nederlandse Leeuw” during the symposium “Optical Networks – communication fabric of our society”, preceding his valedictory lecture “Light work(s)”.
