The Travelling Salesman Problem, or TSP, was first defined
around 150 years ago. The problem then was to find the shortest possible route
for salesmen to visit each of their customers once and finish back where they
started.
In the 21st century, this same problem now applies to a multitude
of activities - delivering fresh stock to supermarkets, supplying manufacturing
lines, air traffic control, and even DNA sequencing. Complex and sophisticated
computer programmes using optimisation - where algorithms produce the best
possible result from multiple choices - now form the basis of solutions to
these modern-day problems. The time required to find an optimal solution is
vital for practical application of the TSP. How long can lorry drivers wait for
their route to be finalised when the salads they hope to deliver will only be
fresh for another 24 hours? How long can air traffic control keep an airliner
flying in circles around Heathrow Airport?