The shortest way to visit all metro lines in a city
This addresses a recreational or theoretical optimization problem for tourists or enthusiasts, with incremental application of mathematical programming to specific metro networks.
The paper tackles the problem of visiting all metro lines in a city with the minimum number of steps, finding that 16 Parisian lines can be visited in 26 steps and 13 Tokyo lines in 15 steps, with no increase when adding RER lines in Paris.
What if $\{$a tourist, a train addict, Dr. Sheldon Cooper, somebody who likes to waste time$\}$ wants to visit all metro lines or carriages in a given network in a minimum number of steps? We study this problem with an application to the metro network of Paris and Tokyo, proposing optimal solutions thanks to mathematical programming tools. Quite surprisingly, it appears that you can visit all 16 Parisian metro lines in only 26 steps (we denote by a step the act of taking the metro from one station to an adjacent one). Perhaps even more surprisingly, adding the 5 RER lines to these 16 lines does not increase the size of the best solution. It is also possible to visit the 13 lines of (the dense network of) Tokyo with only 15 steps.