The Tube Challenge (http://en.wikipedia.org/wiki/Tube_Challenge) is the problem of riding every stop on the London Underground. Every stop must be a stop along a train ride. To be more precise, entering a station and leaving it without riding the train to another stop does not count as "riding" a stop, and if a train passes by a stop without stopping at it (maybe it's going express), a stop doesn't count. The contestant can also go between stations on foot or using some other form of public transportation.

Without considering the time tables, and assuming a known, fixed travel time in between locations, you can think of this as an arc routing problem - a rural postman problem that doesn't have to return to its starting point. The required arcs are train lines, with parallel lines combined into a single line, and optional arcs represent walking/bus riding between train stops.

There must be some optimization happening, since the challenge has been going on in London since 1959, but I can't find anything.

I'm curious because the record for the Chicago CTA was just broken this month, with a time around 9 hours and 30 minutes.

asked 19 Feb '12, 22:22

Luis%20de%20la%20Torre's gravatar image

Luis de la T...
4231612
accept rate: 11%


You may be interested in this recent related paper

link

answered 20 Feb '12, 07:25

AndyT's gravatar image

AndyT
6788
accept rate: 7%

Great! This is exactly what I was looking for. Funny that it just appeared online less than two weeks ago.

(20 Feb '12, 10:29) Luis de la T...
1

Any longer and I probably would have forgotten that I saw it ;)

(20 Feb '12, 16:54) AndyT

Based on the Wikipedia definition, this problem seems to be a TSP with an open ending (in real world applications, we have the open vehicle routing problem similar to this notion).

Wikipedia: Participants do not have to travel along all lines to complete the challenge, merely to pass through all the stations on the system. Participants may connect between stations on foot, or by using other forms of public transport.

Also, as there are multiple modes of transportation between stations, this would be a multi-modal TSP in which you have to select order of visiting stations as well as transportation mode. This would be a highly challenging and uncertain problem as there are many complicating factor such as subway congestion or heavy traffic on the streets. In addition, some modes of transportation might make the participant tired (e.g. waling) which would make excessive use of them infeasible.

link

answered 19 Feb '12, 23:44

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

edited 20 Feb '12, 00:17

1

There is a large body of work on routing problems with time windows that should also be relevant.

(20 Feb '12, 00:02) DC Woods ♦

@Ehsan, I'm not sure that this is true. The authority would be the Guinness World Records, but their website has no details I can find - http://www.guinnessworldrecords.com/records-5000/fastest-time-to-travel-to-all-london-underground-stations/. Walking from one station to another would not count as visiting the two stations. To visit them, you must ride the train between them, or through them on a ride that stops on them. This is specifically why I was thinking of it as an RPP and not a TSP.

(20 Feb '12, 00:12) Luis de la T...

Also, it might be the case that for any two stations one train stop away from each other, the fastest way between them is to take the train. You could just assume that you must take a train between stops one hop away from each other, and for stations not one train stop away from each other, you can take an indirect path through other stations on the train, or a direct path by walking/busing/running.

(20 Feb '12, 00:17) Luis de la T...

One more comment: I believe that the Wikipedia you quoted means that you don't have to ride parallel tracks. In Chicago, you wouldn't have to ride Fullerton-Diversey-Wellington-Belmont on brown and purple, only on brown or purple.

(20 Feb '12, 00:20) Luis de la T...

@Luis: I would still consider this problem a TSP as the main constraint is to visit all the stations, not all the lanes.

@DC: I agree. Since trains run on schedule, you must be in each specific station within a specific period of time to be able to use the trains effectively.

(20 Feb '12, 00:22) Ehsan ♦

@Ehsan: Suppose that I have one train station left, and I walk to it. I'm not done. I have to enter the train station, and ride to another station. In this way, it's not a TSP. This last train ride I do must be one that I haven't ridden yet, otherwise I've contradicted needing to visit the station I just got on the train at. I believe this makes it an RPP (since I can think of it as riding train lines, modulo parallel lines, I haven't visited yet).

(20 Feb '12, 00:40) Luis de la T...

@Luis: I've not got a chance to take a look at the paper yet. However, I guess you're right. I think I neglected the fact that it might be not optimal to travel on a Hamiltonian cycle in such a network as some of the stations are dead-end and walking or using other modes of transportation worsen the objective function. Therefore, the optimal solution is not necessarily a TSP solution.

(20 Feb '12, 10:48) Ehsan ♦
showing 5 of 7 show 2 more comments
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×9
×1
×1
×1

Asked: 19 Feb '12, 22:22

Seen: 4,258 times

Last updated: 20 Feb '12, 16:54

OR-Exchange! Your site for questions, answers, and announcements about operations research.