The Moscow Metro has 340km of track and 203 stations. Over 70 of those stations link to a station on another line, all of which represent possible route permutations. Furthermore, our Moscow Metro Challenge follows rules that also allow for the linking of stations by foot or publicly scheduled transport other than the metro, adding yet more possible routes. To highlight just how complex route planning for the Moscow Metro Challenge therefore is, there are over 180,000 possible routes between ten points of destination. For 15 points, the number of combinations tops 43.5 billion.
But it gets more complicated than that. It isn’t simply a matter of plotting the fastest theoretical route, because the timing and frequency of metros and modes of transport differs across lines and locations. This confuses planning yet further because X route might in theory be optimal, but Y route might in practice be better because it gets you to Delovoy Tsentr Metro Station at a time that means you don’t have to wait ten minutes for a metro, or to Mitino at the right time to catch a bus to Skhodninskaya. In a similar vein, certain interchanges between stations are faster than others. The link between Aleksandrovskiy Sad and Biblioteka Imena Lenina is much quicker, for example, than the interchange between Ploshchad Revolutsiy and Teatralnaya.
In essence, we are faced in our planning with a variant of the travelling salesmen problem, which has been taxing mathematicians since the 1800s. The travelling salesman problem asks, "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" But let your hopes for an easy answer be crushed: despite mathematicians and computer programmers using algorithmic, heuristic, brute-force super-computing and artificial intelligence-based methods, they have struggled to produce a definitive method that shows provable optimal routes between multiple destination points. (Below is an example of a brute force algorithm working on a mere seven points of destination.)
But it gets more complicated than that. It isn’t simply a matter of plotting the fastest theoretical route, because the timing and frequency of metros and modes of transport differs across lines and locations. This confuses planning yet further because X route might in theory be optimal, but Y route might in practice be better because it gets you to Delovoy Tsentr Metro Station at a time that means you don’t have to wait ten minutes for a metro, or to Mitino at the right time to catch a bus to Skhodninskaya. In a similar vein, certain interchanges between stations are faster than others. The link between Aleksandrovskiy Sad and Biblioteka Imena Lenina is much quicker, for example, than the interchange between Ploshchad Revolutsiy and Teatralnaya.
In essence, we are faced in our planning with a variant of the travelling salesmen problem, which has been taxing mathematicians since the 1800s. The travelling salesman problem asks, "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" But let your hopes for an easy answer be crushed: despite mathematicians and computer programmers using algorithmic, heuristic, brute-force super-computing and artificial intelligence-based methods, they have struggled to produce a definitive method that shows provable optimal routes between multiple destination points. (Below is an example of a brute force algorithm working on a mere seven points of destination.)
We have access to neither a supercomputer nor the kind of intellect needed to apply ant-colony optimization algorithms, so we decided to focus our planning on making smart choices.
First, we ranked the all of the lines extending from the circle line by the time it took from the last station to the first useable interchange station. All lines on the Moscow metro go toward, through and then away from the centre, which means each line has two sections to rank (for instance, Red Line southwest and Red Line northeast, or orange line north and orange line south.) Those sections that rank longest would be good candidates to start and finish, because that would mean they only had to be travelled once, whereas having them in the middle of the route would involve travelling all the way out and all the way back in. Below, for example, the Yandex Metro app shows that it takes 27 minutes to travel from the end of the Purple Line east to its first functional interchange, Krestyanskaya Zastava, but only 19 minutes to do likewise on the Red Line northeast.
First, we ranked the all of the lines extending from the circle line by the time it took from the last station to the first useable interchange station. All lines on the Moscow metro go toward, through and then away from the centre, which means each line has two sections to rank (for instance, Red Line southwest and Red Line northeast, or orange line north and orange line south.) Those sections that rank longest would be good candidates to start and finish, because that would mean they only had to be travelled once, whereas having them in the middle of the route would involve travelling all the way out and all the way back in. Below, for example, the Yandex Metro app shows that it takes 27 minutes to travel from the end of the Purple Line east to its first functional interchange, Krestyanskaya Zastava, but only 19 minutes to do likewise on the Red Line northeast.
Second, we searched for bus, tram, train or trolleybus routes linking end-stations, or stations close to the end, of lines that ranked badly in the above list. This could effectively improve the position of certain lines on the list by cutting the length of time to the first functional interchange. Below, for example, Google Maps suggests we could travel on the 570 bus from Mitino on the blue line to Skhodnenskaya on the blue line in 41 minutes during rush hour. We could take the MCC light rail system to link Sportivnaya to Leninskiy Prospekt in 20 minutes at the same time, should we so desire.
Finally, we looked at the system as a whole and identified sections that it made plain sense to do in a certain way. For instance, it makes sense to link the Orange, Grey, Light Green and Dark Green lines in that order, or the exact reverse, because the two green lines link at their southern ends, and Grey and Orange lines are linked by the Butovskaya Line in the South, and the Light Green and Grey lines link nearish the northern end of the latter. This leaves the Dark Green North and the Orange north as the open ends of the loop. Something else that makes sense is to have potential points of delay early in the journey. For instance, if there is a twenty minute gap between a specific bus route, having it very early in the challenge will increase your chances of getting the timing just right.
This process narrowed down the choices considerably, and made it easier to start picking out potential routes. These became more self-evident because it made clear sense to link the ends of certain lines by bus or by the MCC light rail system. The final step of route planning was to look at non-obvious route combinations, and try to assess them; however, these were a simpler form of the travelling salesman problem, with only a few points of destination, meaning we could solve them through the brute force elimination using a sheet of paper and the Yandex Metro app. For instance, the section of track west of Kievskaya, toward Moskva Citi and Kuntseva (pictured below), involving the dark blue, light blue and yellow lines, has four interchanges. The order that one traverses this section does not affect the rest of the route, as it is isolated. Therefore, it should, in theory, be possible to identify an optimal route.
This process narrowed down the choices considerably, and made it easier to start picking out potential routes. These became more self-evident because it made clear sense to link the ends of certain lines by bus or by the MCC light rail system. The final step of route planning was to look at non-obvious route combinations, and try to assess them; however, these were a simpler form of the travelling salesman problem, with only a few points of destination, meaning we could solve them through the brute force elimination using a sheet of paper and the Yandex Metro app. For instance, the section of track west of Kievskaya, toward Moskva Citi and Kuntseva (pictured below), involving the dark blue, light blue and yellow lines, has four interchanges. The order that one traverses this section does not affect the rest of the route, as it is isolated. Therefore, it should, in theory, be possible to identify an optimal route.
We’ll keep our final route secret for now, and there are bound to be improvements that folks could make (including one obvious one, which we have eschewed for poetic reasons). Indeed, we hope people do improve on our route, and beat whatever record we set, as there is no reason the London Underground Challenge and New York Subway Challenge should be popular, but something similar for the Moscow Metro not. And while we’re not going to give future challengers everything we know, we hope that this represents a start.
- More about the Moscow Metro Challenge here
- More on the post-challenge party here
- More about the rules of the challenge here
- More about the Tigrus Project here