The Travelling Salesman Problem
By Elliot Catt, The University of Newcastle
Suppose you are going on a vacation and you want to visit some cities, but you want to order the cities you are visiting in such a way as to spend the least time travelling between locations, or use the least fuel. How do you do this?
It turns out that this is one of the most well-known problems in computer science and optimisation, the travelling salesman problem. The idea is the same; there is a salesman who wishes to visit all the cities in the shortest time.
The solution? It is pretty hard. In fact, the problem itself is what is known as NP-Complete, meaning it is very hard to solve. This can be easily demonstrated. Suppose again that you were going on vacation and wished to visit 100 cities. How many possible ways can you visit all 100? Around 4.7 x 10^155. That is about 470000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.
Now there is no current computer powerful or fast enough to look at every single one of these trips to find out which is the best. However, we don’t have to have a computer.
Using some techniques, we are able to eliminate paths between cities that we know won’t be in the optimal trip. Because of these techniques, we don’t even have to stop at 100 cities; we can look at problems with up to 10000 cities! Which would normally have an amount of trips being a number with 35656 digits, too many for a blog.
Being a travelling salesman or planning a vacation are not the only applications of this problem. In fact this same problem has been applied to protein folding, vehicle routing and many other problems.
Our techniques to solve problems, such as the travelling salesman problem, are not unique to themselves. Most computational and optimisation problems are able to be related to each other, so being able to solve the travelling salesman problem well lets us solve other hard problems from timetabling to packing your bag.
Elliot Catt was one of the recipients of a 2016/17 AMSI Vacation Research Scholarship.