1. Introduction
The Tube Challenge is a Guinness World Records challenge that tests both the physical and mental abilities of the person trying to break it. The main components needed in order to break this record are planning, physical stamina but also luck.
1.1 Project Aims and Objectives
In this project I am required to primarily choose a programming language and use it to create a program that will find the most efficient route to pass through all of the underground stations while following specific rules. Secondly once I have achieved in finding this route I must then test my result by attempting the tube challenge practically. The objective of this project is not only to test the theoretical and practical differences there are but mainly to be able to find a way to translate my way of thinking of solving this challenge into programming.
2. Background
2.1 Challenge Rules 6 In order to explain the objective of the project, the rules of the tube challenge must first be made clear. In order to complete the challenge I must visit all of the 270 stations of the London underground service in the shortest period of time. It is not required to pass through all of the lines connecting the stations as long as every station has been visited at least once. In addition it is not required to visit the Docklands Light Railway & National Railway stations. The following rules must apply in order for the challenge to be valid.
a. Arrive and/or leave an underground station by normal service underground train. If a train line is shared by a National Rail train line then it is allowed to use National rail trains. The only available means other than the underground trains permitted is public transport such as buses, trams and walking as long as I arrive or leave the station by an underground train. All other transportation such as taxis, private car and bicycle etc. are not permitted.
b. Attempts are only allowed during week days due to station closures on the weekends. A train must stop at the station in order for the station to count but it is not necessary to get out. Stations temporarily closed or have closed because of an emergency must not be counted.
c. Stations that are not under one location such as Hammersmith for example, both sides must be visited. Therefore it is obligatory to change at that station in order to visit the other part of it as well. This is true for all stations like Hammersmith.
d. The arrival and departure times must be recorded in a logbook for proof at the end of the challenge. Also a stopwatch must be carried by another person in order to record the starting and finishing time for both personal and public reference. In the course of the challenge more proof must be assembled such as signatures from witnesses, photographic material, tickets from public transportation etc.
2.2 Tube Challenge history
The Tube Challenge was first initiated in 1959 and since then the record has been broken many times. Even if stations have been added or removed through all this years the record has been broken in numerous occasions. The current record holders are Martin Hazel, Andi James and Steve Wilson with record time of 16 hours, 44 minutes and 16 seconds in December 2009.
2.3 Research
This project is an optimisation problem. In order to find the optimal route an algorithm that will provide me with a suitable way to get an answer must be found. The first algorithm that I researched to see its feasibility on the challenge was the travelling salesman problem. The travelling salesman problem (TSP) is not applicable in the challenge because it states that it finds the fastest route between the given states, in this case stations starting from one station and passing only once from each other station and resulting back to the initial station. The reason the TSP cannot be used is because the way the underground network is there will be a case where a station may be revisited due to closed loops inside zone 1 and the extended zone 6 underground lines. In addition the mathematics of the TSP removes the possibility of having a solution with closed loops or moving back to the station u arrived. Finally the TSP applies if the desired answer returns you to the initial station making it a totally different challenge if applied. 1, 2 Secondly I researched the genetic algorithm. The genetic algorithm (GA) uses random progression and each route is given a fitness value. This allows for the progression to be more efficient when a new route is chosen. It also adds a series of 0's and 1's in order to create chromosomes that will show the path that was chosen in order to appoint it its fitness level. Due to the fact that there are so many constrains in the Tube Challenge this algorithm cannot be used in its original form. It is though a very good starting place and I have used a similar algorithm inspired by the GA. 3
2.4 Programming language
I will be making my project in Matlab. The reason I have chosen Matlab is because all of the ideas for implementing my algorithm can be done in Matlab and I will be able to translate my thinking to programming. Matlab will help me make my program more efficient due to my background knowledge of its uses from years 2 and
3. Specification
Algorithm structure
The algorithm I will use was inspired by genetic algorithms. I have chosen to apply this algorithm because it will lead me to find the optimal solution but also solve the challenge in my own way of thinking. In order for the program to work the following steps and functions must be followed.
1. Collect data for all of the stations and the time it takes between them. This will be done using the transport for London website. Also collect opening and closing times of stations.
2. Remove any station that does not have 2 lines intersecting with it because this means it can only travel on one line. Stations are reduced to only the ones intersecting and time between them is calculated.
3. In the central London do not include bus time because it takes too long compared with the underground trains.
4. Store this data in a 2 dimensional matrix in Matlab which will show the time between stations.
5. Each station of the matrix will have an id. This id will show which lines pass through it and also have a specific station number in order to note when the program has passed through that station. The lines are included in order to add delays when changing from one line to another due to the walking distance.
6. I will then enforce a random progression from one station to the next by brute force.
7. Each time the program goes to the next station it will add the time taken to go there to the total time until then, store the id of the station it has visited in order to know it has passed through it and finally test for line changing in order to add or not a delay.
8. When all the ids of the matrix have been visited then the random progression will stop.
9. In order for the solution to be valid it must satisfy a lot of restrictions. All of them are tested. The solution must contain all lines that have stations between them from step 2, change at the specific stations that are geographically different. Finally test if the first station and last station have enough time between their opening and closing time. If all of the restrictions are satisfied then the route and final answer is stored or else it is not accepted as a solution.
10. Then it will randomly progress again. The same process is carried out but in order to make it more efficient when the route chosen has exceeded the total time of the valid route until that time then it will not continue further and start again.
11. When a new valid route is found it replaces the previous route and time if it is faster.
12. After a number of generations that no other more efficient route can be found the stored route is our optimal solution. Its route and time are displayed.
13. In order to make the program more realistic an option will be added to change the time between the stations to simulate a delay of failure in order for a new route to be found.
14. Create a friendly user interface.