Graph Theory Subway Trains

U-Bahn.svgBeen to Berlin recently? Noticed how everything seems to flow particularly smoothly when you navigate the subway system (the U-bahn) there? But that’s just because it’s Germany, right? I mean, seemingly in exchange for exhibiting certain, shall we say, strict and humorless character-traits, and sustaining themselves on Sauerkraut and other tasteless food (at least according to popular imagination outside of the country), Germans can at least be sure that their trains run on time.

Actually, not really. I don’t mean that the subway-trains don’t run on time in Berlin, it’s quite likely that they do. Rather, it seems that they have recently addressed the entire issue of U-bahn efficiency – especially the problem of minimizing transfer times between one line and another – with a bit of higher mathematics, as Holger Dambeck recounts for us in Der Spiegel (Waiting faster).

Consider: you pull into a transfer-station in your one subway train and cast an anxious eye across the platform to where you rather hope the other subway-line to which you want to transfer has a train already waiting there for you. Of course, it’s rare that you’re so lucky; usually you’ll need to get out and wait for some period of time before that follow-on train ever arrives. And sometimes – oh, the frustration! – you do see the train there across the platform as your first train pulls into the station, yet the other train-driver can’t even wait a minute and instead pulls out of the station just as you are arriving!

Surely there must be some way to schedule all the arrivals and departures in some better fashion – not to ensure that there’s always a transfer-train there waiting for you as your first train arrives, that’s certainly asking for too much – but at least to ensure minimal transfer-times for all. Certainly there is: it turns out that that is simply a problem in Graph Theory! A complicated problem, to be sure, but it can be broken down to fairly simple fundamentals, as Dambeck does here by presenting the straightforward case of two lines running in one direction with only four stations and with a new train setting out every four minutes, for which you want to minimize the transfer times from one to another. The solution (it’s on the second page of this two-page piece, although the same diagram is on both) is that having the second train set off on its journey two minutes after the first does ensures minimal transfer times, namely two minutes whether you’re transferring from line 1 to 2 or vice-versa.

On the other hand, Berlin’s subway system is somewhat more complex, with nine lines (actually maybe 9-and-a-half, since a mini-line, the “U55” or “Chancellor’s Line,” just opened on 8 August) and 170 stations, with special rules for the transfer-possibilities (if any) at each. Getting that right in Graph Theory requires some computer-power, in the hands of mathematicians who know what they are doing, in this case a team from the Technical University Berlin headed by one Christian Liebchen. (This guy’s last name, by the way, means “darling” or “sweetheart” – chouchou for those of you who are French.) Sure enough, Liebchen and his cohort have come up with a train-schedule for Berlin’s U-bahn about which they can claim “there is none better,” and it’s one that the subway authorities have put into practice. In the meantime, the public transport authorities in Potsdam (not far away; just to Berlin’s southwest) and the Netherlands Railroads (rather further away) have expressed an interest in availing themselves of this group’s expertise, while Liebchen himself has left academia for a well-paid job at the German Railways.

Such Graph Theory, by the way, according to the article can also be applied to solving Sudoku puzzles. But you should also be aware that Holger Dambeck is not any regular Spiegel journalist, but rather an author who likes to write about mathematics and who has a book he wants to sell you (if you read German): Numerator: Mathematics for everyone. A steal at only €7.95, with free delivery within Germany, Austria, and other neighboring countries, under certain multiple conditions which, even if you can handle the German, may take graph theory again to understand.

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

Comments are closed.