Mathematics: Optimal Cycle Tour Network

The travelling salesman algorithm and other algorithms tried to find the most efficient network for a cycling holiday in Brittany, France.

Collage of Brittany towns in road maps

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.

Brittany Map with Cycling Destinations
Map of Brittany (Bretagne) with my cycling destinations

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 = 181,440. This would be far too many to individually analyse. Some of the possible arcs will be left as the routes between the towns either 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.

I will use Prim’s algorithm to join all the nodes on the network together, leaving out some routes which are not on the map. Afterwards, certain nodes will be methodically omitted to obtain a list of minimum connectors, out of which I find he the highest minimum connector.

Cycling distances between towns and villages in Brittany
Cycling distances between towns and villages in Brittany
 RoscoffMorlaixLannionSt. BrcBrestCarhaixPontivyQuimperConc.Lorient
Roscoff2564103
Morlaix2545105655011982102
Lannion45706492114134
St. Brc105701478459112100
Brest646514797121141162
Carhaix5064849754616275
Pontivy119925954948750
Quimper1038211412161942467
Conc.10211214162872464
Lorient13410016275506764
Distance table between each point

I proceeded to omit each node in turn to find the minimum connector, the minimum connector rule. Each node that was left out was later joined by an arc to and from the node. If a tour is formed then it is the best solution. Consequently, not all is what it seems as this text has been ripped from Nahoo at nahoo.net. Normally the solution is more than this number and the highest minimum connector is taken to be the lower bound for where the solution may lie.

Omitted nodeMin conn.MinusTotal
Roscoff47370543
Morlaix387109496
Lannion373129507
St. Brieuc368129497
Brest401104505
Carhaix403104507
Pontivy40885494
Quimper40586494
Concarneau382114496
List of minimum connectors with ommitted nodes

Here is a diagram of the lowest band value, the minimum spanning-tree, therefore the solution must be less than 2 × 432 = 864km.

Minimum spanning tree connecting all points in the network
Minimum spanning tree connecting all points in the network

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 minimum connector, 494km.

The range of the solution:
Highest minimum connector < Solution ≤ Minimum connector × 2
= 494 < Solution ≤ 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, maximum distance
Minimum connector – travelling twice along the same routes. 864km
Minimum connector, different routes
Minimum connector with shortcuts, avoiding travelling along the same routes to reduce distance and boredom. 559km

Here is the tour, starting from Roscoff, and travelling to closest unvisited town: Roscoff → Morlaix → Lannion → Pontivy → Lorient → Concarneau → Quimper → Brest → St. Brieuc → Morlaix → Roscoff.

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.

My actual cycling tour based on interest along each route
Starting at Roscoff, travelling to the next closest unvisited town.
Starting NodeRouteDistance
RoscoffR → M → L → C → P → Lo → Co → Q → B → S → M → R724
MorlaixM → B → C → P → Lo → Co → Q → L → S → M → R → M667
LannionL → M → R → B → C → P → Lo → Co → Q → C → S → L629
St. BrieucS → P → Lo → Co → Q → C → M → R → B → M → L → S577
BrestB → R → M → L → C → P → Lo → Co → Q → C → S → B673
CarhaixC → M → R → B → M → L → S → P → Lo → Co → Q → C577
PontivyP → Lo → Co → Q → C → M → R → B → M → L → S → P577
QuimperQ → C → M → R → B → M → L → S → P → Lo → Co → Q580
ConcarneauCo → Q → C → M → R → B → M → L → S → P → Lo → Co577
LorientLo → P → C → M → B → R → M → L → S → Co → Q → Lo626
Starting at other locations, the total distance varies using this technique.

The solution lies between 864km and 494km at 559km. It is closer to the highest 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 quite 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 Finistère. 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 losing 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 DayDistancePlanned Activities
16.30 MondayArrive off passenger ferry in Roscoff
Monday NightStay at my friend’s house in Roscoff
TuesdayGo sailing during the day around the harbour ion Roscoff
Tuesday NightStay a second night at my friend’s house
11.00 – 13.00 Wednesday25kmCycle to Morlaix
Wednesday NightWonder around the Wednesday market, book a night at Youth Hostel
10.30 – 13.00 Thursday45kmCycle to Lannion
19.30 – 21.30 ThursdayWatch a movie at the cinema, stay for the night at a Youth Hostel
10.00 – 17.00 Friday70kmCycle to St. Brieuc and then along the East coastal road
18.00 – 19.00 FridayVisit the sites of the town, including historic town centre and castle
Friday NightStay at a Youth Hostel by the river
10.30 – 16.30 Saturday59kmCycle to Pontivy and stay over night in a B&B
11.00 – 16.00 Sunday50kmCycle to Lorient
18.00 – 23.00 SundayLeave baggage at Youth Hostel and have a night in the city
11.00 – 17.30 Monday64kmCycle to Concarneau
18.30 – 20.30 MondayWalk along seafront and go to a restaurant or order a takeaway
Monday NightStay the night at the Youth Hostel by the sea
10.00 – 12.30 Tuesday24kmTravel to Quimper
13.30 – 15.00 WednesdayLeave baggage in Youth Hostel, have lunch, then explore the town.
15.30 – 18.30 WednesdayVisit the leisure centre and go for a swim, ice-skating, or bowling
Wednesday NightStay at Youth Hostel in Quimper
10.00 – 17.30 Thursday61kmCycle to Carhaix in the highland of Brittany, stay at a B&B.
9.30 – 18.30 Friday97kmLongest cycle, downhill the city of Brest
Friday NightStay in Youth Hostel near “Sea World”
10.00 – 16.30 Saturday64kmReturn to small town of Roscoff
8.00 – 18.00 SundayTravel by ferry back to Plymouth
19.30 SundayCatch train back to Penzance (if the train is on time)
Travel plan with details of points of interest and accommodation.

Comments

This is an A-Level Mathematics project from around 1999. The diagrams have been remade as vectors to replaces the hard-to-view original images. Any comments are still welcome.