I've been asked to help calculate a minimal route for a mini (personal) challenge in London. I'm struggling and while not exactly The Tube Challenge I think it's relevant enough that I may be able to draw on your collective experience!
So, the challenge:
I've been asked to calculate a route to visit all Premier League, Championship, League One and League Two (plus, as a bonus, Wembley) football stadiums within the M25. The idea is to visit each (in any order) take a photograph there (and possibly a quick pint) and then move on to the next. As the mention of the pint suggests, this is not a race but optimising the route would be a massive help. Originally the hope was that this could all be completed in one day but I'm not sure how reasonable this is - Two days would be equally acceptable... Either way, I'm sure the route would be by-and-large the same.
My start/endpoint would be Ruislip or West Ruislip - whichever is most appropriate. Note that I am not limited to the tube but would prefer to restrict myself to public transport, thus buses and trains would also be fine.
So far I have drawn a blank - I thought it would be easy to look at the tube lines that each stadium is on (or nearest to). This is a reasonable starting point but I've struggled to optimise much beyond this. Not a surprise given this is the travelling salesman problem (or close to it) which N=NP hard. Ouch! I'd considered writing a computer program but I feel this is the sort of challenge which is best solved using real human experience.
My attempt to plan this route so far:
I have found numerous websites that, given a start/end point and a set of addresses, will optimise the route between them all. Unfortunately this only considers driving routes. The best websites appeared to be Map Quest and RouteXL. Both of these arrived at the same result. I then took the optimal driving route and used TfL Journey Planner to see how long it would take to get between each point using public transport. As you might expect, many of the routes that may be optimal by car (20 min drive) can be significantly worse by public transport (up to 80 min). This has a total time from start to end of 14 hours and twenty minutes assuming perfect changes and no allocated time for taking any photographs (or that important beer!). The route can be found here: http://www.routexl.com/f=E501pZ04
The list of stadiums and post codes is pasted at the end of this post. Also pasted are the TfL Journey Planner times for each leg of the route in the order suggested by Map Quest/RouteXL.
I am sure that given the optimisation that you guys do over the entire tube network this is much simpler. I'd really appreciate it if you could take a moment to look over the stadium locations and give any suggestions on a route.
Thank you!
Code: Select all
List of Stops
-------------
Wembley International HA9 0WS
Chelsea Premier League SW6 1HS
Arsenal Premier League N7 7AJ
Tottenham Premier League N17 0AP
West Ham Premier League E13 9AZ
Crystal Palace Premier League SE25 6PU
QPR Premier League W12 7PJ
Watford Championship WD18 0ER
Brentford Championship TW8 0NT
Charlton Championship SE7 8BL
Fulham Championship SW6 6HH
Milwall Championship SE16 3LN
Leyton Orient League One E10 5NF
Wimbledon League Two KT1 3PB
Dag & Red League Two RM10 7XLCode: Select all
Map Quest/RouteXL Route Journey Times
-------------------------------------
Ruislip
Watford 1h 09m
Arsenal 1h 10m
Tottenham 0h 38m
Leyton Orient 0h 56m
West Ham 0h 44m
Dag & Red 0h 38m
Charlton 1h 11m
Milwall 0h 55m
Crystal Palace 0h 47m
Wimledon 1h 11m
Fulham 1h 05m
Chelsea 0h 33m
QPR 0h 44m
Brentford 0h 52m
Wembley 1h 10m
Ruislip 0h 37m
TOTAL 14h 20m
Watford High Street 
