It’s no secret (but I suppose it’s not well known either) that I’ve always loved the Paris Métro. One of the things that I’ve always wanted to do is to ride on every single line. Since I’ve lived in Paris before, I’ve covered most of them, but not in a systematic way, and I’m pretty sure I’ve never been on line 9.
So, I’m thinking about going to Paris in the fall, and I would very much like to correct this situation by traveling on every single line all at once, just to get it over with. Being the kind of person that I am, I eventually got curious as to what would be the most efficient way (defined as being the way with the fewest stations) to cover all the lines, including the 3 and 7 bis, but not the tram lines or the RER. And now that’s what I want to do. Also, for elegance, I’d like the route to start and end at the same station.
The problem is that I have no idea how to figure this out or even if it is feasible for a computer non specialist to do for myself. So, I would greatly appreciate any help you may offer to help me through figuring this out. In return, when I actually do this, I will provide you with photographs of me traveling, perhaps in various comical poses.
Here’s a map of the Paris Métro in case you need one: http://mapsof.net/map/paris-metro
(I apologize if this is the wrong place for this thread. I could be soliciting facts or opinions I guess.)
On an unrelated note, I’ve a friend who’s gig is to go to a city and bike to all the metro stops. He says it’s a great way to see the whole city, tourist and non-, ugly and beautiful. I think he’s done it in Paris, I know he’s done Berlin.
Are you determined to get to all the stops only via the metro, or can we get off the map?
I’m thinking it might be more efficient to travel to the end of one line, then take surface transport to the terminus of the next adjacent line, travel its entire length, then take alternative transport to the terminus of the next line, etc. That way each line could be transited from end to end only once, with limited need for retracing your path.
Here’s a map of the metro with streets, so a non-London-Underground projection. Assuming we can leave the metro, you could start off with missing Line 9 at Pont de Sèvres, travel the whole line to Mairie de Montreuil, then walk 20 minutes or get a cab to Parc de Bagnolet / Gallieni and transit the #3 line to Pont de Levallois — Bécon. You’d still have some bits to sort out.
That’s why I want the constraints defined. I don’t want to spend 20 minutes with a map of the metro if what we really need is some outside-the-metro thinking.
There are certainly overlaps - for example lines 8 and 9 run parallel and hit the same stations from Richelieu Drouot all the way to République. Judging by the spirit of the OP, I would say it only counts for the one you’re currently riding (although I suppose you could go half of the way in one, then change and finish on the other).
Anyway, for rive gauche lines I figure the most efficient way to use all lines would be to start at Denfert, 6 to Raspail, 4 to Montparnasse, 13 to Duroc, 10 to Sevre-Babylone, 12 to Concorde, 8 to Madeleine, 14 to St. Lazare. That’s 7 lines in 13 stations, not too bad. That leaves only 7 untouched, and you can easily hook up with it on rive droite.
The problem is that you then have to go all the way back east to get a spot on the short 3bis and 7bis lines (I didn’t even know those existed till now ! :o) ; and using the 1 at all will be tricky efficiency-wise.
Maybe a loop NW could take care of that ? The Most Useless Line* to Villiers, 2 to Charles de Gaulle, 1 to Palais Royal, 7 to Chaussée d’Antin, 9 to République, 5 to Gare de l’Est, 7 once more to Louis Blanc, 7bis to Place des Fêtes, 11 to Porte des Lilas, 3bis to Gambetta.
And then you’re fucking nowhere :p, but you did use all 16 lines in a mere 47 stops ! Can anyone top that ?
That’s 3. Goes from nowhere to nowhere, and stops at only one major hub leading to somewhere. Yes, it’s the one I live on, why do you ask ?
Wait, I missed the “end at the start” condition. Hmm. Then add a ride on the 3 to Gambetta, then 4 to Denfert, adding 18 stops (fewer if you switch to the RER B at Châtelet).
With that condition in play, it might be more worthwile to start in Châtelet, since more or less everything goes there, meaning the trip back from anywhere you end up once you’ve travelled on all lines would be shorter. And then you declare Mornington Crescent, easy peasy.
I would prefer metro-only transportation. The basic idea is that I get on the metro, and later get off, and in between, I’ve traveled on every line for at least one stop.
So, just to clarify things, the problem is more of an intellectual one than a practical one, except that I do intend to travel the route. So the absolute geography of my itinerary is of no particular importance. I’m pretty sure this is an application of graph theory, but I don’t really know how. Anyway, here are all the details of my idea that I can think of.
Travel on each of the 16 lines (that is lines 1–14 and 3 and 7 bis) of the Paris Métro from one stop until at the least the next stop.
Not leave the métro system until the very end, which means staying within the parts of the métro system where having a valid ticket is required. No other form of transportation, except foot, and only then to get from one platform to another, can be used.
Transfer from one line to another at stations that have transfers marked on the map. This means, in terms of planning my itinerary, that stations without transfers might as well not exist, except for the first and last stops.
The itinerary can begin and end at any stop of the system (and if anyone cares, I will most likely travel to the beginning stop by bus, but the bus travel doesn’t count as part of the official itinerary).
I can only be on one line at any given moment. (So, even though lines 8 and 9 follow the same trajectory for a bit, that doesn’t cover both lines. I would have to transfer.)
My optimization concerns have changes a bit since I’ve had time to sleep on it. But here they are.
Minimize the number of transfers to complete the route. The absolute minimum is 15, and it would be nice to hit every line exactly once, but if it’s not possible, it’s not possible.
It’s no longer necessary to end up where I start, but it would still be nice. This would mean that I would have to start the trip at a transfer station, leaving on one line and coming back on another.
Finally, I wonder what the shortest itinerary (by number of stops, including stops that aren’t transfer stations) that fulfills these constraints would be.
An example of an acceptable route, albeit one that doesn’t start and stop in the same place, is as follows:
Start at the Gare de Lyon (which is about a third of the way from the right edge and a third of the way from the bottom of the map).
Take line 14 southeast 1 stop to Bercy.
Take line 6 southwest 11 stops to Montparnasse–Bienvenüe.
Take line 13 northwest 7 stops to Saint-Lazare.
Take line 12 south 6 stops to Sèvres–Babylone.
Take line 10 east 2 stops to Odéon.
Take line 4 north 7 stops to Strasbourg–Saint-Denis.
Take line 8 east 8 stops to Reuilly–Diderot.
Take line 1 northeast 1 stop to Nation.
Take line 2 north 4 stops to Père Lachaise.
Take line 3 east 1 stop to Gambetta.
Take line 3bis north 3 stops to Porte des Lilas.
Take line 11 west 2 stops to Place des Fêtes.
Take line 7bis around the curve 7 stops to Louis Blanc.
Take line 7 southwest 2 stops to Gare de l’Est.
Take line 5 south 2 stops to République.
Take line 9 southeast 1 stop to Oberkampf.
So, that’s my first attempt, driven by trial-and error. 15 transfers (which is good), 65 stops (which I don’t know if it’s good or not), and it doesn’t start where it ends (which is undesirable). I admit there isn’t likely to be too much that is going to be better to deal with the 3bis and 7bis, but the rest, especially the line 6 bit, seems open for modification.
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.
One possibility is to look at a related graph, where the edges in the metro system are the vertices, and the edges of the new graph correspond to adjacent edges in the original. Then you’re looking at a shortest path problem on vertices, which may be easier to solve.
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 (which is 1 worse than Kobal2’s), but the itinerary does start where it ends.
No. If there are two lines that take the same path, each line is on separate tracks. So, even though the 8 and the 9 follow each other in the center of the city, line 8 is actually on top of line 9. A leg on one line only counts for that one line.
This is correct, as far as I’ve been able to tell. The problem is that I’ve never taken a class about graph theory ever in my life, so, even with the transformation you suggest, I don’t know what to do with it. Hopefully, you could point me to somewhere that explains all this more clearly. I have a few months, after all, to work on this.
Now, after spending most of the afternoon doing planning routes, I have to get back to work.
Oh, OK, I was thinking of a situation in my home town where two of the lines were identical until they diverged: Going from downtown to Shaker Square (or anywhere in between), the Blue Line and Green Line were interchangeable (in fact, the Red Line also overlapped for three stations, but that one used different cars and different platforms).
