# Traveling on all lines of the Paris Métro **URL:** \ **Category:** Factual Questions\ **Created:** [May 5, 2012, 11:34pm UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029 "2012-05-05T23:34:49Z")\ **Posts on this page:** 14\ **Page:** 2
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [May 21, 2012, 10:29pm UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/21 "2012-05-21T22:29:43Z")
> [@ultrafilter](#): > > The metro is a graph. Stations are vertices, and the edges are the trains you can take. Each edge has a type associated with it, and you’re looking for the shortest path that contains at least one edge of each type. I asked around, and it turns out that this problem is NP-complete by reduction from the Hamiltonian path problem. So using one of the solutions upthread is likely your best option. ---
**Author:** ![Sunspace](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sunspace/32/1250_2.png) [@Sunspace](https://boards.straightdope.com/u/Sunspace)\ **Post date:** [May 22, 2012, 12:52am UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/22 "2012-05-22T00:52:26Z")
> [@Ludovic](#): > > That’s only allowed if the Marseilles Gambit is in effect, unless of course if you’re playing by the Modified Rochambeau edition. But according to Directive EC 67/202.10 originally promulgated by Lavallière and Bouton, it’s also allowed for any non-French citizen with a valid visa. This essentially holds for anyone with a Schengen visa now. ---
**Author:** ![partlycloudy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/partlycloudy/32/3114_2.png) [@partlycloudy](https://boards.straightdope.com/u/partlycloudy)\ **Post date:** [May 22, 2012, 1:59pm UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/23 "2012-05-22T13:59:32Z")
Only marginally related here, but if you’re a fan of the Paris Metro (or even if you’re not), you might enjoy this little artistic video montage: [Paris Metro as You’ve Never Seen It](http://www.thedailybeast.com/videos/2011/10/01/paris-metro-as-you-ve-never-seen-it.html). I saw it on The Daily Beast today and thought of this thread. Loves me some Paris Metro! ---
**Author:** ![RadicalPi](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/radicalpi/32/9806_2.png) [@RadicalPi](https://boards.straightdope.com/u/RadicalPi)\ **Post date:** [June 21, 2019, 9:15am UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/24 "2019-06-21T09:15:54Z")
I know that it’s been a while, but I’ve finally made my way back to Paris, and using the route below, I completed the circuit of all the lines of the métro. > [@RadicalPi](#): > > Here’s the best I’ve managed to do so far by trial and error. Many thanks to **Kobal2** for bringing up the idea of using Châtelet. You, and anyone one else who wants to, are more than welcome to come with when I do this later this year. > > Start at Porte des Lilas, one of the terminuses of Line 3bis. > > Take line 3bis south 3 stops to Gambetta. > Take line 3 west 1 stop to Père Lachaise. > Take line 2 south 4 stops to Nation. > Take line 6 southeast 5 stops to Bercy. > Take line 14 northwest 2 stops to Châtelet. > Take line 4 south 4 stops to Odéon. > Take line 10 west 4 stops to Duroc. > Take line 13 north 4 stops to Champs-Élysées–Clemenceau > Take line 1 southeast 1 stop to Concorde. > Take line 12 north 1 stop to Madeleine. > Take line 8 east 2 stops to Richelieu Drouot. > Take line 9 east 4 stops to République. > Take line 5 north 2 stops to Gare de l’Est. > Take line 7 northeast 2 stops to Louis Blanc. > Take line 7bis east 5 stops to Place des Fêtes. > Take line 11 east 2 stops to Porte des Lilas, which is the beginning spot. > > 15 transfers (best possible), 46 stops The only differences are that I started and ended at Gare de l’Est, since that was most convenient for me. Also, there are only 3 stops on line 4 between Châtelet and Odéon. The trip took 2 hours and 27 minutes from starting platform to ending platform, only 3 minutes longer than I had planned. As you might imagine, most of the time was spent waiting for the trains to arrive, at about a 60/40 ratio. A montage picture of the information panels in the stations I took is [here](https://i.imgur.com/4UJbtEp.png). I am, on the whole, prouder than I probably should be. Thanks to everyone in 2012 who helped me figure this out. ---
**Author:** ![friedo](https://avatars.discourse-cdn.com/v4/letter/f/8edcca/32.png) [@friedo](https://boards.straightdope.com/u/friedo)\ **Post date:** [June 21, 2019, 10:39am UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/25 "2019-06-21T10:39:20Z")
Now do New York City. The record is just under 24 hours. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [June 21, 2019, 11:43am UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/26 "2019-06-21T11:43:25Z")
It’s been seven years and nobody’s bothered to track down or construct a machine-readable node list for the Paris Métro graph? :rolleyes: Bah!! 😃 ---
**Author:** ![Telemark](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/telemark/32/372_2.png) [@Telemark](https://boards.straightdope.com/u/Telemark)\ **Post date:** [June 21, 2019, 12:47pm UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/27 "2019-06-21T12:47:59Z")
> [@RadicalPi](#): > > I am, on the whole, prouder than I probably should be. Nonsense. You had a dream, you took steps to make it happen, you executed it to perfection. Congrats! ---
**Author:** ![Bert\_Nobbins](https://avatars.discourse-cdn.com/v4/letter/b/aeb1de/32.png) [@Bert\_Nobbins](https://boards.straightdope.com/u/Bert_Nobbins)\ **Post date:** [June 21, 2019, 2:11pm UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/28 "2019-06-21T14:11:11Z")
It’s a good job you did it now. They’re building four more metro lines: 15, 16, 17 and 18. See: [https://www.societedugrandparis.fr/info/grand-paris-express-largest-transport-project-europe-1061](https://www.societedugrandparis.fr/info/grand-paris-express-largest-transport-project-europe-1061) I imagine that may complicate the matter somewhat. ---
**Author:** ![bob\_2](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bob_2/32/3341_2.png) [@bob\_2](https://boards.straightdope.com/u/bob_2)\ **Post date:** [June 21, 2019, 2:47pm UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/29 "2019-06-21T14:47:41Z")
If you fancy taking the London Tube Challenge here is a handy map to put you on the right track (groan). The basic rules are: 1. You don’t have to cover every stretch of track or step on every platform, but you must arrive at or depart from every Underground station by train. (Overground, National Rail and Docklands Light Railway stations not included). 2. You may take buses or run between stations (but not taxis, private cars or skateboards). If you are going for the record (currently 16 hours, 14 minutes and 10 seconds) you also need a witness with a master stopwatch. [https://secure.i.telegraph.co.uk/multimedia/archive/03078/tube-challenge\_3078591a.jpg](https://secure.i.telegraph.co.uk/multimedia/archive/03078/tube-challenge_3078591a.jpg) ---
**Author:** ![kodabar](https://avatars.discourse-cdn.com/v4/letter/k/f08c70/32.png) [@kodabar](https://boards.straightdope.com/u/kodabar)\ **Post date:** [June 28, 2019, 9:30am UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/30 "2019-06-28T09:30:29Z")
Having participated in several Tube challenges and being acquainted with most of the recent record holders, I can tell you one or two things about doing this sort of thing. It’s a variant on the travelling salesman problem and there is no easy solution. The last time we held a Tube challenge it brought competitors from around the world, many of them mathematicians. Some people used neural networks, some used various efficiency routines, some did it by dead reckoning, others relied on luck or experience of the system. There’s all kinds of extra variables such as which carriage to get on for the most direct exit or transfer, minor branches (eg Kensington Olympia) that don’t get many trains, etc. It’s quite a problem to solve. Even with the right plan, you can arrive in a station and encounter an unexpected train, meaning you have to be very adaptive. And there’s the problem of food, drink and toilets. And sometimes you need the experience of actually knowing the system as there’s some points where you’re better off travelling on foot overground or taking a car or bike between awkward spurs. Even a seemingly perfect plan can get screwed up when certain stations (eg Victoria) get closed for overcrowding, a section gets suspended for a signal failure, etc. There’s a lot to taken into account. Even a seemingly perfect route can get screwed up when a minor delay throws everything out of whack. Well done to RadicalPi for realising his dream! ---
**Author:** ![Tim\_T-Bonham.net](https://avatars.discourse-cdn.com/v4/letter/t/46a35a/32.png) [@Tim\_T-Bonham.net](https://boards.straightdope.com/u/Tim_T-Bonham.net)\ **Post date:** [June 28, 2019, 6:51pm UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/31 "2019-06-28T18:51:28Z")
Isn’t this simply a version of the [Travelling Salesman problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem), a common & well-studied problem in operations research? ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [June 29, 2019, 12:01pm UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/32 "2019-06-29T12:01:25Z")
> [@Tim\_T-Bonham.net](#): > > Isn’t this simply a version of the [Travelling Salesman problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem), a common & well-studied problem in operations research? The basic problem, just finding a route regardless of time, is like that. And the Metro is small enough that the time complexity isn’t a real problem. But if you throw in requirements regarding reducing time then it gets complicated. Add in the dynamic, everchanging aspects of trains being delayed, etc. and it gets nasty. Even trying to be “approximately optimal” only partially helps then. ---
**Author:** ![Elendil\_s\_Heir](https://avatars.discourse-cdn.com/v4/letter/e/7cd45c/32.png) [@Elendil\_s\_Heir](https://boards.straightdope.com/u/Elendil_s_Heir)\ **Post date:** [July 7, 2019, 3:54am UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/33 "2019-07-07T03:54:31Z")
> [@Telemark](#): > > Nonsense. You had a dream, you took steps to make it happen, you executed it to perfection. Congrats! Hear, hear - and thanks for giving us an update! ---
**Author:** ![wolfpup](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/wolfpup/32/10618_2.png) [@wolfpup](https://boards.straightdope.com/u/wolfpup)\ **Post date:** [July 7, 2019, 4:12am UTC](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029/34 "2019-07-07T04:12:41Z")
> [@RadicalPi](#): > > I know that it’s been a while, but I’ve finally made my way back to Paris, and using the route below, I completed the circuit of all the lines of the métro. > > The only differences are that I started and ended at Gare de l’Est, since that was most convenient for me. Also, there are only 3 stops on line 4 between Châtelet and Odéon. > > The trip took 2 hours and 27 minutes from starting platform to ending platform, only 3 minutes longer than I had planned. As you might imagine, most of the time was spent waiting for the trains to arrive, at about a 60/40 ratio. > > A montage picture of the information panels in the stations I took is [here](https://i.imgur.com/4UJbtEp.png). > > I am, on the whole, prouder than I probably should be. Thanks to everyone in 2012 who helped me figure this out. Thanks for the followup 7 years later! But I just have one question. From everything I’ve heard about the Paris Métro (and also the airports and other public places) when you finally arrived back at Gare de l’Est, **did you still have your wallet**? 😉 [Previous page](https://boards.straightdope.com/t/traveling-on-all-lines-of-the-paris-metro/621029.md?page=1)