Travelling Salesman Maths Investigation
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.
Roscof
Morlai
Lannio
St. Brc
Brest
Carhai
Pontiv
Quimp.
Conc.
Lorient
Roscof
?
??
?
?
??
?
?
???
?
?
Morlai
??
?
??
???
??
??
???
??
???
?
Lannio
?
??
?
??
?
??
??
???
?
???
St. Brc
?
???
??
?
...
This is a preview of the whole essay
Roscof
Morlai
Lannio
St. Brc
Brest
Carhai
Pontiv
Quimp.
Conc.
Lorient
Roscof
?
??
?
?
??
?
?
???
?
?
Morlai
??
?
??
???
??
??
???
??
???
?
Lannio
?
??
?
??
?
??
??
???
?
???
St. Brc
?
???
??
?
???
??
??
?
???
???
Brest
??
??
?
???
?
??
?
???
???
???
Carhai
?
??
??
??
??
?
??
??
??
??
Pontiv
?
???
??
??
?
??
?
??
??
??
Quimp.
???
??
???
?
???
??
??
?
??
??
Conc.
?
???
?
???
???
??
??
??
?
??
Lorient
?
?
???
???
???
??
??
??
??
?
I proceeded to omit each node in turn to find the minimum connector, the minimum connector rule. I apply Prim's algorithm, as it is far more suitable for computerisation compared with Kruskal's algorithm. Each node that was left out was later joined by an arc to and from the node. If a tour is formed than, it is the best solution. Normally the solution is less than this number and the highest minimum connector is taken to be the lower bound for where the solution may lie.
Omitted Node
Min Conn
Minus
Total
Roscoff
473
70
543
Morlaix
387
09
496
Lannion
373
29
507
St. Brieuc
368
29
497
Brest
401
04
505
Carhaix
403
04
507
Pontivy
408
85
494
Quimper
405
86
494
Concarneau
382
14
496
Here is a diagram of the upper bound value, the minimum spanning-tree, therefore the solution must be less than 2 ? 432 = 864km. It is important to find the boundaries where the solution will lie, as this is the only way to judge if the solution can be improved or if it is adequate in the given situation. The solution must be more than the highest lower bound, 494km. The range of the solution:
Minimum spanning tree < solution ? minimum connector ? 2 = 494 < Upper bound ? 864
I will proceed to make shortcuts along the minimum connector * 2, to avoid travelling along the same route twice. The solution would be better if it is closer to 494km, rather than 864km.
Minimum connector - travelling twice along the same routes. 864km
Minimum connector with shortcuts, avoiding travelling along the same routes to reduce distance and boredom. 559km
Roscoff ? Morlaix ? Lannion ? Pontivy ? Lorient ? Concarneau ? Quimper ? Brest ? St. Brieuc ? Morlaix ? Rocoff
Here is the tour, starting from Roscoff, and travelling to closest unvisited town. The distances between nodes get larger, with this example, as nodes left unvisited near the end of the tour are far apart. This results in a very large distance travelled.
Starting Node
Route
Distance
Roscoff
R? M? L? C? P? Lo? Co? Q? B? S? M? R
724
Morlaix
M? B? C? P? Lo? Co? Q? L? S? M? R? M
667
Lannion
L? M? R? B? C? P? Lo? Co? Q? C? S? L
629
St. Brieuc
S? P? Lo? Co? Q? C? M? R? B? M? L? S
577
Brest
B? R? M? L? C? P? Lo? Co? Q? C? S? B
673
Carhaix
C? M? R? B? M? L? S? P? Lo? Co? Q? C
577
Pontivy
P? Lo? Co? Q? C? M? R? B? M? L? S? P
577
Quimper
Q? C? M? R? B? M? L? S? P? Lo? Co? Q
580
Concarneau
Co? Q? C? M? R? B? M? L? S? P? Lo? Co
577
Lorient
Lo? P? C? M? B? R? M? L? S? Co? Q? Lo
626
The solution lies between 864km and 494km at 559km. It is closer to the minimum connector, which means the result is satisfactory considering the large distances involved. The minimum connecting route has many dead ends and therefore resulted in a rather large difference between the highest minimum connector and the shortest route. Quite a few shortcuts were made, added to the distance of the tour.
If we were to cycle the route in 10 days, staying in each town overnight, we would cycle a mean-average of 55.9km a day. This is the normal distance covered by a person, cycling for a day. The route does not travel along the same arcs twice; this will make the cycling holiday more enjoyable. As we will be cycling during the summer holidays, the weather will be very hot.
The route is good due to the fact that much of it lies near the coast, where the temperature is slightly cooler. In the planning of the cycling tour of Brittany, I did not include other variables such as gradient and quality of roads, the sites of interest along the routes and whether we will stay the night at each town we visit.
Carhaix is located on a hill in the centre of Finistere. This would mean that the journey towards the town would be more difficult to cycle and the average speed would lower, meaning a longer time spent per kilometre than on other arcs. In departing from the town, the opposite scenario would occur, more frequent downhill cycling, less time needed per kilometre and a higher average speed.
Roads near the coast are often over many small hills and valleys, but these are not so difficult, as uphill riding is often brief. The longer the route the greater the chance of loosing our way, so with longer routes away from towns or recognisable natural features, estimated times should be increased to allow for any delays occurring. This said, all alterations will be minimal and will not affect the final tour, so I will not redo the tour building.
Our average speed would be 10km/h; this includes short breaks along the route. Here is a timetable of our tour of Brittany.
Time and Day
Distance
Planned Activities
6.30 Monday
Arrive off passenger ferry in Roscoff
Monday Night
Stay at my friend's house in Roscoff
Tuesday
Go sailing during the day around the harbour ion Roscoff
Tuesday Night
Stay a second night at my friend's house
1.00 - 13.00 Wednesday
25km
Cycle to Morlaix
Wednesday Night
Wonder around the Wednesday market, book a night at Youth Hostel
0.30 - 13.00 Thursday
45km
Cycle to Lannion
9.30 - 21.30 Thursday
Watch a movie at the cinema, stay for the night at a Youth Hostel
0.00 - 17.00 Friday
70km
Cycle to St. Brieuc and then along the East coastal road
8.00 - 19.00 Friday
Visit the sites of the town, including historic town centre and castle
Friday Night
Stay at a Youth Hostel by the river
0.30 - 16.30 Saturday
59km
Cycle to Pontivy and stay over night in a B&B
1.00 - 16.00 Sunday
50km
Cycle to Lorient
8.00 - 23.00 Sunday
Leave baggage at Youth Hostel and have a night in the city
1.00 - 17.30 Monday
64km
Cycle to Concarneau
8.30 - 20.30 Monday
Walk along seafront and go to a restaurant or order a takeaway
Monday Night
Stay the night at the Youth Hostel by the sea
0.00 - 12.30 Tuesday
24km
Travel to Quimper
3.30 - 15.00 Wednesday
Leave baggage in Youth Hostel, have lunch, then explore the town.
5.30 - 18.30 Wednesday
Visit the leisure centre and go for a swim, ice-skating, or bowling
Wednesday Night
Stay at Youth Hostel in Quimper
0.00 - 17.30 Thursday
61km
Cycle to Carhaix in the highland of Brittany, stay at a B&B.
9.30 - 18.30 Friday
97km
Longest cycle, downhill the city of Brest
Friday Night
Stay in Youth Hostel near "Sea World"
0.00 - 16.30 Saturday
64km
Return to small town of Roscoff
8.00 - 18.00 Sunday
Travel by ferry back to Plymouth
9.30 Sunday
Catch train back to Penzance (if the train is on time)
1-Apr-07
Page 1 of 7