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.
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.
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. I saw it on The Daily Beast today and thought of this thread.
Loves me some Paris Metro!
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.
I am, on the whole, prouder than I probably should be. Thanks to everyone in 2012 who helped me figure this out.
Now do New York City. The record is just under 24 hours.
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!! 
Nonsense. You had a dream, you took steps to make it happen, you executed it to perfection. Congrats!
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
I imagine that may complicate the matter somewhat.
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:
-
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).
-
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
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!
Isn’t this simply a version of the 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.
Hear, hear - and thanks for giving us an update!
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? 