|
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. |
|
You may be interested in this recent related paper Great! This is exactly what I was looking for. Funny that it just appeared online less than two weeks ago.
(Feb 20 at 10:29)
Luis de la Torre
|
|
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).
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. 1
There is a large body of work on routing problems with time windows that should also be relevant.
(Feb 20 at 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.
(Feb 20 at 00:12)
Luis de la Torre
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.
(Feb 20 at 00:17)
Luis de la Torre
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.
(Feb 20 at 00:20)
Luis de la Torre
@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.
(Feb 20 at 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).
(Feb 20 at 00:40)
Luis de la Torre
@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.
(Feb 20 at 10:48)
Ehsan ♦
showing 5 of 7
show all
|
