There is a list of famous mathematical problems. One of these is the Travelling Salesman Problem. CQM managed to find an answer to this mathematical problem in collaboration with professors William Cook and Keld. The fact that a company from the Dutch city of Eindhoven contributed to this breakthrough was reason for Innovation Origins to talk to Arjen Vestjens (managing partner) and Peter Hulsens (partner) of CQM about this particular problem.
Travelling Salesman Problem
Arjen, can you first of all explain to us once again what exactly the Travelling Salesman Problem is all about?
“In the Travelling Salesman Problem, you are looking to figure out the shortest route between any number of locations, arriving back at the starting point. On the face of it, that may not sound very complicated. Yet it takes a computer almost a thousand years of computing time to calculate the shortest route past twenty destinations. It is consequently one of the most intensively studied problems in mathematics.”
And you all thought: ‘We’ll step it up a gear and go for just under sixty thousand destinations?’
Peter: “Haha, if we wanted to solve a mathematical problem of this caliber, we wanted to do it with complete conviction. There are 57,912 national monuments in the Netherlands, so we thought that would be a fun challenge.”
Route planning software: 1.8 billion distance ranges
Arjen, what exactly was CQM’s contribution?
” In order to choose between all of the possible routes, you first of all need to know the distances between all of the locations. CQM has its own route planning service that can calculate the distances between a large number of addresses with lightning speed. Thanks to this software, we can calculate the 1.8 billion distances between the national monuments in the Netherlands within two hours. We are now able to make this calculation on a simple computer.”
Next, William Cook and Keld Heisgaun set to work with those 1.8 billion distances…
Arjen: “Using our distance matrix, Cook and Heisgaun developed a simpler and faster algorithm. They then successfully linked the algorithm to an enormous amount of computational power. The algorithm has now been rolled out across 320 computer processors. The processors are spread over ten server clusters with one server per cluster. For the sake of illustration, the 320 computers add up to ninety years of computation time. That computational power did its job: The shortest route along all 57,912 national monuments turned out to be 20,253,062 meters.”
What was different now from before that enabled you to solve the problem?
”Arjen: “A complete distance matrix was available. Cook had previously calculated the shortest route past all the pubs in the United Kingdom. However, at that time he did not have access to a matrix with all of the separate distances between the pubs. This time, with CQM’s distance matrix, the professors had direct access to all possible distances between the 57,912 national monuments that were needed to develop the algorithm.”
“There are 57,912 national monuments in the Netherlands, we thought that would be a fun challenge.”
Speed has priority in practice
How often are you working on these issues in practice?
Peter: “For our clients, we calculate on an almost daily basis how they can get from A to B as efficiently as possible. That is also why we have in-house software. So we solve variants of this problem every day, but we do not guarantee that we have the best solution. Our customers don’t ask that of us either. They want in the shortest possible time, the best possible solution that meets all the conditions.”
Arjen: “Scientists often figure one thing out to the last detail. We, on the other hand, often have to make a quick calculation. It doesn’t have to be done to the last detail, it mainly has to be done very well. A big difference, but that doesn’t take away from the fact that it’s very important for us to follow the science and stay up to date.”
Opportunities for route optimization
What does this breakthrough mean for you?
Peter: “It opens up a lot of opportunities for route optimization, but for us the Travelling Salesman Problem is part of something bigger. Take, for example, a cab company that wants to know how to drive their cabs along a route in the most efficient way. Then you want to know the shortest route past all the pick-up points – the TSP. But it’s also important that all customers are picked up on time. Or that they won’t have to wait too long and that there won’t be too many people in the cab at the same time. So the TSP is a subcomponent of route planning.”
Arjen: “In addition, the breakthrough shows that it’s not just computers that are getting faster and smarter. Sure, faster and stronger processors are extremely important, but so are the mathematical techniques associated with them. The two do have to be able to keep up with each other, or they won’t be of any use to us in practice.”
Peter, is a twenty thousand kilometer bike ride past national monuments on the agenda for CQM’s next company outing?
“Ha ha, no. We like challenges, but 20,000 kilometers is just too far for us, too.”
Also interesting: How to weigh a turkey – and other mathematical problems in industry
Electrically stimulating the math wiz
