It’s Saturday morning and you’ve got a few things to get sorted. You need to go to the post office to pick up a parcel, to the bank to pay in a cheque and to the supermarket to get something for dinner. You also need to pick up a DVD from a friend and go to a bookshop to buy a relative a present. The trouble is, you’ve not got much time. In which order do you go about your tasks? Where do you head first? You have yourself what mathematicians call a Travelling Salesperson Problem (TSP), named after the idea of a salesperson needing to travel between a series of destinations, visiting each potential client only once, and returning home in the shortest possible time.
You may think that this sounds easy, after all it is a really easy problem to explain. It turns out it is a much more difficult problem to solve. You could try working out all the possible routes, calculating their length and comparing the time it would take (“brute force method”). However, even for the five stops on your Saturday trip there are 12 possible routes. By the time you get up to 10 stops that rises to 181,440 possibilities.
In 2004, mathematicians managed to find the optimum route to travel between all 24,978 places in Sweden – a record at the time. However, if they had used the brute force method to find the solution, checking one route every millionth of second, it would have taken them 10140 centuries! Instead, the mathematicians used a method known as the “branch and cut” process which falls under a part of Operational Research known as heuristics. In general, heuristic techniques enable researchers to look for a “good” answer rather than “the best” answer. The most successful heuristic techniques can get within 2-3% of the optimum answer in a much shorter, and therefore much more practical, time.
The simplest heuristic method is known as the Nearest Neighbour algorithm. In this case you would travel to the nearest stop to you and then the nearest stop to that and so on. This provides a rough and quick answer that is generally within 25% of the best possible solution. However, imagine that the situation is lorries delivering goods to customers – the difference between 25% and 2-3% makes a massive difference to the company’s profits. Effective solving of TSP problems also has uses in computer wiring and genome sequencing. So other methods have been developed such as the Held-Karp algorithm which gets much closer to the answer. The record for an exact solution to a TSP currently stands at 85,900 “cities” calculated using the Concord algorithm.
However, no general algorithm has been found that can solve any TSP problem. In fact, if one could be found, it would settle one of the biggest outstanding problems in mathematics: the P vs NP problem. Such is the desire for a solution that the Clay Mathematics Institute have offered a $1 million prize for an answer. So the TSP isn’t just about getting from A to B, it has applications far beyond a Saturday trip to the shops and it could even make you a millionaire.
