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.

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 = 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.

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. In passing, it is worth mentioning this text has been copied 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.

Here is a diagram of the lowest band 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 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.

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.

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.

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.