Tour of Great Britain

Finding the shortest route between cities is known as the Travelling Salesman Problem and is a famously difficult problems to solve.

We could check every possible route, but this becomes very big, very fast. For example, with just 15 cities there are over 87 billion possible routes.

One solution is to always travel to the next closest city. Unfortunately, this method will not always find the shortest possible route.

Other computational methods can get close to the best possible route without having to check every possibly.

Ants searching for food deposit pheromones that can be followed by other ants. Short paths get marched over more frequently, reinforcing the pheromones, and creating a natural solution to the problem.

Calculating the shortest path between cities began to be studied by mathematicians in the 1930s. Austrian-American mathematician, Karl Menger, noted early on that travelling to the nearest neighbour does not necessarily give the shortest route.

In 1976, Cypriot mathematician Nicos Christofides, and Russian mathematician Anatoliy Serdyukov independently found an algorithm that gives a solution that is never more than 50% longer than the optimal solution. However, most solutions can usually be found within 3% of the optimal solution.

In 2020, researchers at the University of Washington were able to improve this algorithm by a (very) small amount, so solutions are never more that 49.9999999999999999999999999999999999% longer than the optimal solution.

The Travelling Salesman Problem is also known as the Vehicle Routing Problem.

For delivery services, it is important to find efficient routes of travel. These routes save time and fuel, increasing profitability and reducing greenhouse gases.

Finding the best solution is hard, but computer algorithms can be used to approximate the best solution.

Other factors may need to be considered, such as avoiding roads that are too narrow, or necessarily visiting some locations before others. These are all special cases of the Vehicle Routing Problem.

The Travelling Salesman Problem also has applications in printing circuit boards.

The Icosian game was invented in 1856 by Irish mathematician William Hamilton. The challenge is to visit each point exactly once, without using any line twice, and returning to the starting position.

The icosian game has 30 solutions, but all solutions are equivalent if you allow rotations and reflections.

A much harder game to solve is this network. Can you visit each point once, without using any line twice, and returning to the starting position?

In fact, this game is impossible! Try to convince yourself that it can’t be done.