3
$\begingroup$

When I went to London, I wondered how to visit all the London Underground stations as fast as possible.

Given

  • a randomly-chosen start station,
  • timetable of train arriving & departing of every station,
  • the time it takes to change from one to another line.

Assuming that there is no Tube strike on that day, and trains run on time, what is the best route to visit all the London Tube stations? (By visiting, just passing the station while being on the train counts.)


I've tried breaking the problem down to a smaller size and computing all possible routes, but that'd take ages to run with all 270 stations.

So, could you guys give me some ideas how to do this better? Or if this something similar to this problem, could you please show me those?

What I've tried:

  • I've Googled, and I found something like optimum road trips, but it doesn't work with train stations that have interchanges.
  • Took a look at A*, Dijkstra's but they give a tree as an answer which ignores loops.

Thanks!

$\endgroup$
  • $\begingroup$ the time it takes to change from one to another line is that a constant or a custom value? For example, it could be equal for every situation, or be a single value for every pair of lines in a station, or could be a different value for pair of lines in a station AND time and date AND direction of the pair. It looks like the timetables repeat every week. An idea: use dynamic programming. Also, if the requirement is relaxed, if we do not need to find the best route, then we can settle with using a greedy algorithm which will perform much faster. $\endgroup$ – raindrop Jan 11 '18 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.