Travelling Salesman Maths Investigation

Authors Avatar
Travelling Salesman Maths Investigation

During the summer holidays last year, I went on a cycling holiday. I arrived in Roscoff, by ferry from Plymouth, and stayed at a friend's house for a few days and then set off around Brittany on my bicycle. I found the cycling hard work at the beginning, but after a few days, my legs were no longer sore, even after five hours of continuous cycling. At the end of three weeks, I had visited many of the towns and villages in Brittany and had nicely tanned legs.

This year I am planning to go cycling with a friend. To avoid cycling along a route which is repetitive and contains long stretches of road to cycle in a day? I will draw a network to plan my route. I have linked up the main towns in west Brittany and distances between them along roads shown in the Michelin road map. I intend to cycle from one town to another during the day, and then stay the night in the destination town. I will start and finish the trip in the small town of Roscoff, where my friend and I will stay at my French friend's house in the town centre.

I will try to cycle along the shortest possible route between towns. I can only look at a few of the routes between the 10 nodes out a possible (10-1)! /2 = 181440. This would be far too many to individually analyse. Some of the possible arcs will be left as either the routes between the towns do not exist or the route passes directly through another node. I feel my network is adequately sophisticated as there are 10 nodes and many of the nodes are joined to each other. Distances between nodes are calculated by adding up the distances of sections of road on the map. All the distances on my network are in kilometres, avoiding main roads with large visitors and fast cars.
Join now!


Roscof

Morlai

Lannio

St. Brc

Brest

Carhai

Pontiv

Quimp.

Conc.

Lorient

Roscof

?

??

?

?

??

?

?

???

?

?

Morlai

??

?

??

???

??

??

???

??

???

?

Lannio

?

??

?

??

?

??

??

???

?

???

St. Brc

?

???

??

?

...

This is a preview of the whole essay