Select Page
Travelling Salesman Problem

Feb 29, 2020

#### Computing and IT

An algorithm may describe how a problem can be solved by a computer, but the concept of an algorithm is more general than that. In fact, algorithms as explicit problem-solving tools originated with mathematicians and long pre-date the invention of the computer.

In 1791, the French government ordered the leading mathematician Gaspard Clair Francois Marie Riche de Prony to create new mathematical tables for use in precise land surveys. The tables would be of unprecedented accuracy, being calculated to between 14 and 29 decimal places.

The process by which de Prony created his tables had a profound impact on the development of the computer. In the 19th century, on a visit to France, the British mathematician Charles Babbage saw de Prony’s work and was struck by the idea that a machine could be instructed to generate mathematical data by following an algorithm. The idea for the first computer had been born, a task that would occupy the remainder of Babbage’s life, but which would not be realised until the middle of the 20th century.

The algorithms we use in everyday life are somewhat imprecise – a recipe for a cake might tell us to ‘mix until smooth’ – but what exactly do we mean by ‘smooth’? Everyday algorithms might also omit an instruction when it is expected that the person applying the algorithm will intuitively know what to do – for example, a recipe might say ‘Bake for 45 mins at 180 degrees Celsius without giving explicit instruction to turn the oven on and off.

By contrast, algorithms for programs must be precise and self-contained – they must contain all the instructions required to solve the problem, and those instructions must be ambiguous because computers cannot deal, as humans can, with omission or imprecision. Thus we can describe an algorithm as a set of unambiguous, self-contained, step-by-step instructions guaranteed to complete a particular task in a finite amount of time.

Unfortunately, there are some problems that algorithms struggle to solve. Route finding is just to name one. What seemed to be a simple problem when first written down in 1832, has consumed enormous amounts of time, money and energy up to the present day.

Given a list of cities and the distance between each pair of cities, what is the shortest possible route that visits each city once and returns to the original city?’

This question was popularised in the 1930s, a time when companies required their sales teams to trave widely to attract business, so it became known as the travelling salesman problem (TSP).

Obviously, the TSP is relevant to route planning, navigation software and courier companies; but it also appears in unexpted areas, including genetic research, choosing the order of electrical components on a circuit board, and designing microprocessors.

The TSP doesn’t sound very difficult to solve, but as the number of cities grows, the number of possible routes grows even faster at a rate related to a value known as its factorial.

The factorial of a number is the result obtained by multiplying all the whole numbers between 1 and that number. So, 3 factorial (written as 3!) is 1 x 2 x 3 = 6 whilst 5! is 1 x 2 x 3 x4 x 5 = 120.

In the TSP, the number of possible routes can be calculated for n greater than 2, using the formula:

number of routes = (n – 1)!/2

where n is the number of cities. Finding the shortest route becomes increasingly difficult with increasing numbers of cities since factorials grow at such a fast rate. By the time, we try to find the shortest route between just ten cities, we must consider over 180000 possible routes.

We could solve the TSP using a so-called brute-force algorithm which examines every possible route between cities to find the shortest possible route. Brute-force algorithms, which examine every possible option in searching for the best one, are guaranteed to find the solution to a problem, but applying brute force to a solution can take a very long time.

For example, if it would take a computer program 0.3 milliseconds to calculate the best route between 3 cities using a brute-force approach to the TSP, it would take the program 0.9 milliseconds for 4 cities, 18 millieseconds for 6 cities and 5.34 x 10^13 milliseconds or just over 1600 years for 18 cities!!!

As you can see it is infeasible to use brute force to search for the best possible solution for anything more than a small number of cities. However, it is possible to write algorithms that produce good routes between the cities in a reasonable amount of time. These algorithms may  not generate the shortest route, but are likely to produce routes that are only slightly longer – they are said to be near-optimal. In many cases, near-optimal routes are ‘good enough’ for most purposes; the time and energy used to find such routes is far less than that required to find the elusive optimal route using brute force.

Perhaps, the simplest near-optimal route finder is called the nearest-neighbour algorithm. It is remarkably simple; so long as there are cities that have not been visited during the trip so far, the algorithm identifies the closes unvisited city as the next one to visit. When all the cities have been visited, it is time to return home and complete the trip.

The time taken for the nearest-neighbour algoritms to find a near-optimal route is proportional to the square of the number of cities. If we compare it with the brute-force algorithm, its performance is much better, because squares grow far less quickly than factorials. For 10 cities, nearest-neighbour will need about 10^2 = 100 calculations, but brute-force requires 9!/2 = 181440. With 100 cities, nearest-neighbour needs 100^2 = 10000 calculations, but brute force needs 99!/2 (about 4.7 x 10^155). The latter is an extremely big number, so big that a computer the size of the entire universe could not carry out the search.

Unlike brute force, nearest-neighbour is not guaranteed to find the best route. On average, the best routes produced by nearest-neighbour are about one quarter linger than the optimum route. In fact, for certain arrangements of cities, nearest-neighbour actually produces the worst-possible route!

More sophisticated algorithms, including those mimicking aspects of biological systems, produce better solutions than nearest-neighbour, but are much more complex. Computers work constantly on variations of the TSP as part of our everyday life – routing parcels to their destinations, keeping track of railway rolling stock and ensuring the efficient usie of cars and aircraft to reduce fuel consumption. The TSP even has roles to play in matching DNA traces retrieved at crime scenes to DNA samples of suspects, and comparing the genetic similarities between species in studies of evolution.

#### Subscribe

A multi-lingual and highly-motivated Virtual Assistant/Bookkeeper and Web Designer, specialised in Word Press, Adobe Photoshop and Illustrator, Microsoft Office Applications and Sage Accountancy Software.

## Related Articles

#### Olive bread with houmous and tzatziki

Ingredients for olive bread: 250 g bread flour1 tsp salt1/2 tsp sugar150 ml warm water1 tbsp olive oilrosemary for houmous: 400 g chickpeas1/2 lemon1 garlic clove2 tbsp olive oil2 tbsp tahini pastesun dried tomatoes/roasted red peppers/artichoke/olives (optional) and...

Ingredients : 1.5 cups oats1 cup flour1 cup desiccated coconut1 tsp baking soda1/2 tsp salt1 tsp cinnamon1 cup brown sugar1/2 cup margarine3 tbsp Agave syrup/honey2 tbsp milk170 g chocolate chips Mix all ingredients and bake in a preheated oven till crispy....

Ingredients : 1.5 cups oats1 cup flour1 cup desiccated coconut1 tsp baking soda1/2 tsp salt1 tsp cinnamon1 cup brown sugar1/2 cup margarine3 tbsp Agave syrup/honey2 tbsp milk170 g chocolate chips Mix all ingredients and bake in a preheated oven till crispy....