Sie haben Ihr Ziel erreicht! Wie Mathematik den Verkehr beeinflusst

„Die nächste U-Bahn fährt in zwei Minuten“, ist auf der Anzeigetafel am Bahnsteig zu lesen. Im Radio meldet der Verkehrsfunk einen Stau. Kurz darauf tönt es aus dem Navigationsgerät im Auto: „Die Route wird aufgrund der aktuellen Verkehrslage neu berechnet.“

In beiden Fällen sorgt Mathematik dafür, dass wir auf dem schnellsten Weg zum Ziel kommen. Im Idealfall ohne Stau, ohne Verspätungen und in kürzester Zeit. Wie Mathematik das schafft, darüber diskutierten Experten auf dem 36. Treffpunkt WissensWerte im Haus des Rundfunks in Berlin. Die Aufzeichnung der Podiumsdiskussion wird am 30. März 2008 um 09:22 Uhr auf Inforadio (rbb) ausgestrahlt.

Mathe ist überall. In Kinofilmen, im Wetterbericht und beim Einparken, in Computerspielen, im MP3-Player und im Busfahrplan. Ohne den diskreten Charme der Mathematik läuft nichts, hat man das Gefühl. Bestes Beispiel: der Busfahrplan, sagt Prof. Martin Grötschel. Er ist Mathematiker und Vizepräsident des Konrad-Zuse-Zentrums für Informationstechnik Berlin (ZIB). Grötschels Spezialdisziplinen sind Optimierung und Diskrete Mathematik. Das hat nichts mit Diskretion zu tun, sondern bezeichnet einen Zweig, der sich mit mathematischen Strukturen befasst, die endlich oder abzählbar sind.

Fahrpläne für 1.300 Busse erstellen

Grötschel gilt als Experte für die Lösung logistischer Probleme. Im Auftrag der Berliner Verkehrsbetriebe (BVG) berechnet er die Einsätze von Bussen und Bahnen. Und zwar so, dass sie so effizient wie möglich unterwegs sind. „Bis vor ein paar Jahren waren Fahrpläne noch reine Handarbeit“, so Grötschel. Mit Bleistift wurden die Zeiten in große Listen eingetragen. Ohne Radiergummi lief nichts, denn ehe der Plan fertig war, wurden die Zeiten etliche Male ausradiert und wieder neu eingetragen. Acht Wochen dauerte das mitunter.

„Mittlerweile sind es bei der BVG aber 1.300 Busse, die zusammen jeden Tag über 300.000 Kilometer fahren. Dafür Fahrpläne im Kopf zu berechnen, das schafft kein Mensch“, sagt der Mathematikprofessor. Aber Computer und Algorithmen: Grötschel macht mit ihrer Hilfe aus dem unternehmerischen Problem ein mathematisches und sucht dann nach der Methode, die das Problem am besten lösen kann.

Ein Problem – unendlich viele Lösungsmöglichkeiten

Meistens ist die billigste oder komfortabelste Lösung die beste. Aber es gibt schier unendlich viele Lösungsmöglichkeiten für ein Problem. Wie die beste finden? „Es ist wie die Suche nach der Stecknadel im Heuhaufen“, sagt Prof. Martin Skutella. Er lehrt und forscht am Institut für Mathematik der Technischen Universität Berlin. Seine Fachgebiete: Kombinatorische Optimierung und Graphenalgorithmen.

„Bei der Suche nach der berühmten Stecknadel ist es unmöglich, jeden einzelnen Halm anzufassen. Vielmehr braucht man eine intelligente Möglichkeit, um die Stecknadel zu finden und das in einer vertretbaren Zeit“, so Skutella. Mathematik hilft, genau solche Probleme zu lösen. Und genau solche Probleme lieben Mathematiker, meint man, wenn man der Experten-Runde zuhört: „Mathematik ist eine spielerische Herausforderung. Man hat ein Problem, dass man lösen muss. Man sucht die beste Lösung. Man kann sogar beweisen, dass sie die optimale Lösung ist. Und die Faszination der Mathematik treibt einen dazu regelrecht an“, sagt Skutella.

Mathe hilft Autofahrern durch den Verkehr

Viele Mathematiker lassen sich noch mehr antreiben, wenn ihre Problemlösung nicht nur bloße Rechnerei ist, wie die Berechnung der millionsten Dezimalstelle der Zahl pi, sondern auch praktischen Nutzen hat. Die Lösungen von Dr. Heiko Schilling helfen zum Beispiel Tag für Tag Millionen von Autofahrern. Schilling arbeitet für TomTom, einem holländischen Unternehmen, das Navigationsgeräte entwickelt. Und in ihnen steckt ebenfalls Mathematik.

„Nehmen wir den Berliner Stadtplan als Beispiel: Die Straßen sind für uns Kanten, die Kreuzungen Knoten. So entsteht ein schematisches Modell des Stadtplans, ein Netzwerk“, erklärt Schilling. Vergleichen kann man das ungefähr mit dem Liniennetz der S- und U-Bahn.

Computer ermittelt kürzeste Kantenfolge

Aber wie weiß das Navigationsgerät, welcher Weg zwischen A und B der beste ist? Der Weg von A nach B ist eine Abfolge von Knoten und Kanten. Mögliche Wege gibt es etliche. „Der Computer kann aber mit Hilfe eines Algorithmus berechnen, welche Kantenfolge die kürzeste und damit auch, welcher Weg der kürzeste ist“, erläutert der Mathematiker. Das Navigationsgerät überträgt die Lösung dann zum einen als Markierung auf das Display und zum anderen als Stimmanweisung auf die Lautsprecher.

Und warum landet man dann manchmal doch auf einem Feldweg? „Das liegt keinesfalls am Algorithmus“, so Schilling, „sondern dann fehlen Karteninformationen. Und wenn keine Informationen da sind, kann auch nichts berechnet werden.

Bei Stau funktioniert auch Mathe nicht

Und bei Stau? Warum funktioniert Mathe dort nicht? „Wenn zu viele Autos auf der Straße sind, sind zu viele Autos auf der Straße. Da kann auch Mathe nix machen“, sagt Grötschel. Je mehr Autos auf den Straßen unterwegs sind, umso langsamer geht es voran. Man könnte natürlich für einen Ausfall, also für einen Stau vorsorgen. „In den Telekommunikations-Netzen wird das bereits gemacht“, so der Mathematikprofessor. „Dort wird der Ausfall einzelner Komponenten mit einkalkuliert, so dass bei Störungen 95 Prozent der Daten durch das restliche Netz durchgeschleust werden können. Und das klappt ganz gut.“

Für einen Verkehrsstau ist diese Methode jedoch ungeeignet. Denn Autofahrer lassen sich nicht so ohne weiteres auf das restliche Straßennetz verteilen. „Man müsste schon eine zweite, parallele Straße bauen, um den Verkehr im Falle eines Staus zu verteilen. Aber das wäre viel zu teuer“, meint Grötschel. „Allein im Telekommunikations-Netz kostet eine Absicherung bei einem einzigen Ausfall schon 20 bis 30 Prozent mehr. Bei zwei Ausfällen entstehen 60 Prozent mehr Kosten.“ Sicherheit koste eben, so Grötschel.

Für Stauprognose fehlen Daten

Und ein Stau lässt sich nicht vermeiden. Auch dann nicht, wenn das Navigationsgerät die Hinweise aus dem Verkehrsfunk mit verarbeitet. „Wenn auf der Strecke vor mir ein Stau ist, dann kann das Navigationsgerät die Information mit verwenden und die Route neu berechnen.

Wenn ich aber erst in 20 Minuten an der Stelle sein werde, dann kann sich der Stau entweder aufgelöst haben oder aber doppelt so lang sein“, erklärt Schilling das Problem. Es fehlen einfach Daten an dieser Stelle. Und welcher Fall eintritt, kann auch kein Computer oder Algorithmus vorhersehen. „Letztendlich gibt das Navigationsgerät nur Instruktionen, entscheiden muss der Fahrer aber selber“, so der Mathematiker.

„Das Problem sitzt hinterm Steuer“

Und damit spricht Schilling noch eine unberechenbare Variable an. „Das Problem sitzt hinterm Steuer“, sagt er. Die Zuhörer lachen. Ganz Unrecht hat Schilling nicht. Denn die meisten Autofahrer wollen so schnell wie möglich ans Ziel. „Man muss mit egoistischen Nutzern rechnen“, sagt auch Martin Skutella. Die Mathematik hat dafür einen Begriff: das Nash-Gleichgewicht.

Der Berufsverkehr ist ein typisches Beispiel dafür. Jeder Autofahrer wählt die für sich optimale, also schnellste Strecke. Verbessern kann er sich nicht, auch dann nicht, wenn er seine Strategie ändert. Die Autofahrer blockieren sich damit gegenseitig. Eine Verbesserung des Verkehrsflusses wäre nur dann möglich, wenn sich alle Autofahrer ihre Strecke vorgeben ließen und damit auch längere Fahrzeiten in Kauf nähmen. „Man müsste praktisch die Leute zwingen, neue, weitere Weg zu fahren. Aber wer will schon eine halbe Stunde länger unterwegs sein, nur damit andere drei Minuten schneller sind“, meint Grötschel.

„Regeln machen einen fast wahnsinnig“

Einen Individualfahrplan für das Straßennetz zu berechnen ist also extrem schwierig. Aber ein ganz normaler Busfahrplan hat es auch in sich. Es wird umso komplizierter, je komplexer die logistischen Probleme sind, sagt Martin Grötschel. „Es sind ja nicht nur allein die 1.300 Busse zu koordinieren, sondern auch Reichweiten, Pannenstatistiken, Wartungsarbeiten und Umsteigezeiten, dazu Dienstzeiten der Busfahrer, Pausenvorgaben und ihre Dienstplanwünsche. Es gibt nämlich Fahrer, die wollen immer die gleiche Strecke fahren und andere, die wollen das eben nicht. Und all diese Regeln machen einen fast wahnsinnig.“

Ziel aller Mühe: den Fahrplan zu optimieren und vielleicht einen Bus einzusparen. Und damit Geld. Das mag bei einem Bus weniger nach Peanuts klingen, aber bei Flugzeugen geht das in die Millionen. „Die Flugzeugflotten waren die ersten, die damit begonnen haben. Denn Flüge sind relativ teuer und Flugzeuge richtig auszulasten ist daher Millionen wert“, sagt Grötschel. Im Flugverkehr ist daher diese Art der Planung mit am weitesten fortgeschritten.

Fortschritt durch bessere Algorithmen und Computer

Und die Fortschritte sind zum Teil unglaublich. „Vor allem in den letzten zehn Jahren hat sich viel getan“, sagt Martin Grötschel. „Um Faktor 1000 sind die Prozesse schneller geworden. Und das liegt weniger an den Computern, sondern vor allem am Fortschritt innerhalb der Mathematik. Wir versuchen einfach, die Dinge zu verstehen und die Algorithmen ständig zu verbessern“, so der Mathematik-Professor.

„Wir wollen die Rolle der Computer aber nicht herunterspielen“, führt sein Kollege Martin Skutella weiter aus. „Ohne Computer wäre das alles nicht möglich.“ Aber man braucht eben nicht nur schnelle Computer, sondern vor allem kluge Köpfe, die sie bedienen können.

Kristin Krüger

Podium
· Prof. Dr. Dr. h.c. mult. Martin Grötschel, Vizepräsident des Konrad-Zuse-Zentrums für Informationstechnik Berlin (ZIB) und Sprecher des DFG-Forschungszentrums MATHEON
· Dr. Heiko Schilling, Team-Leitung Routen Planung, TomTom International BV
· Prof. Dr. Martin Skutella, Institut für Mathematik, Technische Universität Berlin
Moderation
Thomas Prinzler, Wissenschaftsredaktion rbb Inforadio
Der Treffpunkt WissensWerte ist eine Veranstaltung der TSB Technologiestiftung Berlin, rbb Inforadio und der Technologie Stiftung Brandenburg im Jahr der Mathematik. Sie wird mitgeschnitten und im Programm von Inforadio (rbb) 93,1 am 30. März 2008 um 09.22 Uhr gesendet.