How do you successively visit a large number of different locations with as few kilometers as possible? This may seem like a simple question, but it is actually one of the most difficult mathematical problems and known as the Travelling Salesman Problem. Yet CQM – together with Professor Bill Cook and Professor Keld Helsgaun – succeeded in solving the largest Travelling Salesman Problem on a map ever and determined the shortest cycling route for a tour of all 57,912 locations with national monuments in the Netherlands. The possibilities for similar problems is endless,
The Travelling Salesman Problem can be formulated as follows: Find the shortest route that passes each location exactly once and ends back at the first location. You could, of course, calculate all possible routes and then compare them. But to find the optimal route this way would take a computer at least 1,000 years of computing time with just 22 locations, or so the Washington Post reported in 2018.
Pub crawl
Bill Cook, who himself calculated the shortest pub crawl across England in 2016, used 320 computer processors in 10 server clusters, for a combined 90 years of computing time. And yep, the shortest cycling route – or optimal distance – was proven: It takes 20,253,062 meters of cycling to visit all the National Monuments in the Netherlands. And with this, the largest ever mathematical problem of its kind (on a real route map) was solved!
Route optimization
No matter how athletic enthusiasts of Dutch landmarks are, no one is likely to cycle over 20 thousand kilometers to cover the entire route, even if it is thus guaranteed to be the shortest. In this case it is not about practicality, but rather about proving that the Travelling Salesmen Problem with more than 25 objects is not computationally impossible.
Frans de Ruiter: “Together with Bill Cook and Keld Helsgaun, CQM succeeded in solving the largest commercial traveller problem on a map ever (with almost 60,000 objects). This breakthrough means a lot for the possibilities in route optimization for the business market. Consider, for example, the planning of (professional) transport, such as cab rides, and intermodal transports.”
Also interesting:: Barcelona puts pedestrians in the shade with app
Selected for you!
Innovation Origins is the European platform for innovation news. In addition to the many reports from our own editors in 15 European countries, we select the most important press releases from reliable sources. This way you can stay up to date on what is happening in the world of innovation. Are you or do you know an organization that should not be missing from our list of selected sources? Then report to our editorial team.