Does any work exist on optimizing the tube/subway challenge?

 7 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 de la T... 423●1●6●12 accept rate: 11%

 6 You may be interested in this recent related paper answered 20 Feb '12, 07:25 AndyT 678●8 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
 1 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. answered 19 Feb '12, 23:44 Ehsan ♦ 4.8k●3●12●24 accept rate: 16% 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
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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: