In March 2021 the largest roadmap instance of the traveling salesman problem ever was solved. Frans de Ruiter, consultant at the Dutch company CQM, together with Bill Cook, professor of applied mathematics at the John Hopkins University, and Keld Helsgaun, associate professor emeritus in computer science at Roskilde University in Denmark, managed to determine the shortest cycling route for a route past all 57,912 locations with National Monuments in the Netherlands.
This is a new record for the Travelling Salesman Problem. Although it is not very likely that you will take your bike and start cycling through the Netherlands this results shows how large instances of problems having a very high complexity, like the Travelling Salesman Problem, can be solved when optimization techniques are used. On Thursday 9 September we interviewed Frans who explained to us how this astonishing result was made possible.
"The inspiration to work on this problem came from an online talk I watched by Bill Cook. In the talk Bill was explaining how they managed to find the optimal walking route between 40.603 historic sites in the US and 49,687 pubs in the UK. During the talk he mentioned that a major challenge in such problems is to get a matrix with all the distances of the edges connecting the points. We are talking about a matrix with almost 1.6 billion entries, which is a huge amount of entries to just download from Google Maps. But creating such large distance matrices was exactly what our algorithms at CQM can do. In our projects we create matrices of similar size on a daily basis. The key in speeding up the computations is by efficiently preprocessing the map. In our case, we use natural boundaries that show up in road maps. For instance, rivers and lakes divide the Netherlands in several components connected by a limited number of bridges and ferries as shown on the map. When I realized that providing such a large distance matrix is possible I decided to contact Bill. And we started working on finding the optimal cycling tour to 57,912 Dutch monuments."
Almost in one shot
After creating the matrix of the cycling distances between the 57,912 Dutch monuments the quest for the optimal cycling tour started. This quest lasted almost seven months from which the three were just waiting for the computations to be complete!
"The first step of the analysis was to use heuristic methods to find an initial tour which would be close to optimal. Keld Helsgaun took over and used the LKH code to find an initial tour. The LKH code is an effective implementation of the Lin-Kernighan heuristic for solving the traveling salesman problem. The initial tour the heuristic gave had length equal to 20,253,564 meters. That is an astonishingly good result given that the optimal route, as it turned out in the end, is just 502 meters shorter than this one. A couple of weeks later we managed to improve the tour length by 186 meters, using a parallel version of LKH. What I found really astonishing in the LKH heuristic is that for the case of the UK pub tour it gave the optimal tour in one shot!"
Figure 2: The shortest possible tour to nearly every pub in the United Kingdom was computed in one shot using the LKH heuristic. Taken from the Travelling Salesman Problem website.
"We found no further improvements over the following weeks, hence Bill started working on the computations to show whether this route was the optimal one. This computation was carried out between September 2020 and March 2021 at the University of Waterloo. The full computation for this problem used a total of 96.9 years of computer time (if run on a single processor core of one of our Linux servers). During the process Bill and Keld managed to improve the initial route a couple of times and in the end obtain a cycling tour they couldn’t improve any more. Then Bill showed that this tour was indeed optimal!”
Figure 3: Frans de Ruiter set to bike the Dutch tour!
CQM
CQM is a Dutch consultancy company with a leading role in data analysis and quantitative methods. They use advanced algorithms to tackle highly complex problems from logistics, route and production planning, and data analysis. Frans explains in his talk “Analytics to improve mobility for elderly and disabled citizens” in the Analtyics for a Better World seminar series how these techniques are used in practice by CQM:
"A problem that I work on at CQM concerns the daily planning of a Dutch taxi company. CQM offers a route planning service for the fast calculation of the distances between large numbers of addresses, thus enabling automatic route planning. In the Netherlands almost 75% of the taxi market consists of contracted rides, which are meant for specific groups of people. Think of health insurers that organize the transport of people that need to go or leave from the hospital but also of elderly who cannot arrange regular transport on their own. From all contracted taxi rides we focus on the so-called Valys contracts. These are interregional relatively long-distance rides subsidized by the Dutch government for recreational and social purposes. Almost 200.000 people per year make use of such contracts and almost 90% of the contracts are made at least one day in advance. We compute every day the most efficient way to combine the taxi rides that all the customers need. These are about 2,500 rides on quiet days, up to 15,000 rides on Christmas day. Using our optimization techniques we can make this daily planning once we receive the bookings sparing up to thousands of kilometers for the taxi drivers!"
Further reading
Have a look at the website of Professor Bill Cook for more optimal routes and information on the Travelling Salesman Problem. You can also watch this talk of Bill Cook where he explains the methods used to solve so large instances of the Travelling Salesman Problem. For a major theoretical breakthrough in the Euclidean Travelling Salesman Problem you can have a look at this article published a couple of weeks ago. The featured image is also taken from the website of Bill Cook on the Travelling Salesman Problem.
Recently there has been a breakthrough in the field of algorithms for geometric network problems, concerning the complexity of the Euclidean Travelling Salesman Problem.
. 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!
Nowadays we have route planners such as TomTom and Google Maps to make driving to a holiday destination a lot simpler. In this article we explain the science behind these route planners.
A lot of services that we enjoy every day, for example commuting by train or ordering some product from a web-shop, give rise to very complex problems, like making the daily train schedule or deciding how all the products that have been ordered should be delivered. How can we efficiently solve such problems? In this article I will explain how a method called preprocessing works.
