Gesundheit: Mathematiker beflügeln „Gelbe Engel“

Eine schier endlose Liste von Zahlen flimmert über den Bildschirm. Hinter jeder neuen Zeile verbergen sich ausgelaufene Batterien, Luft im Benzin oder verrußte Zündkerzen. Die Zahlen verschlüsseln, wann und wo den „Gelben Engeln“ des ADAC Autopannen gemeldet wurden.

„Ein ganz normaler Urlaubstag für ADAC-Helfer“, sagt Jörg Rambau, Mathematiker am Konrad-Zuse-Zentrum in Berlin. Er und seine Kollegen haben ein Verfahren entwickelt, um die Helfer schneller zu den Pannen zu bringen. 10000 Pannen werden dem ADAC an einem normalen Tag gemeldet. „Zur Urlaubszeit oder bei Wintereinbruch können es doppelt so viele werden“, sagt Dietmar Flügel, Informatiker beim ADAC.

In den fünf Pannenhelferzentralen des ADAC managte man die Verteilung der Aufgaben bislang von Hand: Mitarbeiter, die „Disponenten“, wiesen jeder Panne einen der 1700 „Gelben Engel“, beziehungsweise eines der 5000 Fahrzeuge der ADAC-Service-Vertragspartner zu. Dabei wählten sie eine einfache Strategie: Der Pannenhelfer, der der Panne am nächsten ist, wird alarmiert – nach Augenmaß und einem Blick auf eine digitale Landkarte, ähnlich dem Bildschirm eines Navigationssystems.

„Das kann aber bedeuten, dass andere Pannenopfer anschließend länger warten müssen“, sagt Rambau. „Gute Entscheidungen sind bei der großen Zahl der Pannen und Helfer mit bloßem Auge kaum noch möglich.“

Der Informatiker Flügel vergleicht die Aufgabe mit dem Schachspiel: „Der Tag beginnt mit einer Ausgangssituation und entwickelt dann eine Eigendynamik. Und genauso wie ein guter Schachspieler hat jeder Disponent seinen eigenen Stil. In Genshagen bei Berlin zum Beispiel sitzen 30 Disponenten: 30 Köpfe, 30 verschiedene Planungsstrategien. Vor allem, um die Servicequalität zu harmonisieren, haben wir uns vor drei Jahren mit dem Zuse-Zentrum zusammengetan.“ Die Arbeit der „Gelben Engel“ soll künftig der Computer erledigen.

Doch die Angelegenheit entpuppte sich als komplex. Die Disponenten schlagen sich täglich mit zwei der schwierigsten mathematischen Probleme herum: dem Problem des Handlungsreisenden und dem der Mengenpartitionierung.

Seit über 200 Jahren spukt der Handlungsreisende durch Mathematikerhirne. 1932 brachte ihn der Wiener Algebraiker Karl Menger dann zu Papier. Die Aufgabe ist schnell formuliert: Wie sieht der kürzeste Pfad aus, der einen Handlungsreisenden durch vorgegebene Orte führt, ohne dass er einen Ort mehrmals besucht? So einfach das klingt – die Lösung ist keineswegs trivial. Denn wer alle möglichen Wege durchprobieren wollte, hätte einiges vor: Schon bei 10 Städten müsste er sich zwischen 3628800 verschiedenen Wegen entscheiden. Und einen Algorithmus, der wesentlich besser funktioniert als alle Wege einfach auszuprobieren, kennen Mathematiker nicht.

Die Aufgabe gehört daher zu den besonders komplexen „NP-harten Problemen“. Das heißt: Ist n die Anzahl der Städte, dann wächst die Rechenzeit (egal auf welchem Computer) vermutlich schneller als jedes Polynom in n – und das heißt übersetzt: Sie wächst rasant.

Immerhin sind schon Probleme mit einigen tausend Städten lösbar. Was Computer jedoch Stunden beschäftigt. Der Weltrekord liegt derzeit bei einer Tour durch 15112 deutsche Orte. Das Problem der Mengenpartitionierung ist kaum weniger aufwändig: Wie teilt man die Menge der Pannenhelfer am günstigsten auf die Menge der Motorschäden auf?

Dazu kommt, dass in Deutschland die Planung schwieriger als andernorts ist. „Für die Software, die wir einsetzen, sind auch automatische Disponierungs-Tools erhältlich, die zum Beispiel im australischen Melbourne eingesetzt werden“, sagt Flügel. „Dort sind aber viele Straßenzüge rechtwinklig angeordnet. Und es muss nicht das weitläufige flache Land versorgt werden wie in Deutschland.“

Aus mathematischer Sicht ist die Schwierigkeit rasch erkennbar: „Schon bei 60 Unfällen haben die Pannenhelfer viel mehr Touren zur Auswahl, als es Atome im Universum gibt – und das sind eine ganze Menge“, sagt Rambau. Ein paar Jahre Zeit können sich die Pannenhelfer für die Rechnung auch nicht nehmen: Die Hilfe muss binnen Sekunden auf den Weg gebracht werden.

Wollte man in wenigen Sekunden den gesamten Sand der Sahara nach einem einzelnen Goldkorn durchsieben, dann hätte man es vergleichsweise einfach. Doch Rambau ließ sich nicht entmutigen; schließlich haben Mathematiker in den vergangenen 20 Jahren einige Tricks entwickelt, mit denen man solchen Problemen zu Leibe rücken kann.

Für den Alltag der ADAC-Helfer sollten die Touren kurz sein und wenige Verspätungen erzeugen. Um sie zu finden, durchsieben die Mathematiker nicht die ganze Sahara. Findet der Computer eine geeignete Zusammenstellung der Routen nicht in der ersten Handvoll Sand, dann fügt er weiteren Sand hinzu und siebt erneut. Wie nahe er dabei schon dem Optimum ist, kann er dabei aus der Struktur des Problems abschätzen, ohne das Optimum selbst zu kennen.

„Mit unserem Algorithmus können wir in zehn Sekunden 200 Pannen auf 100 Pannenhelfer verteilen – und sind danach weniger als ein Prozent vom Optimum entfernt", sagt Rambau. Die Mathematiker sind stolz auf diesen Erfolg. Und die Pannenhelfer des ADAC testen das Tool in Genshagen bei Berlin bereits seit über einem Jahr, und sind ebenfalls zufrieden. Auch in der Pannenhelferzentrale Dormagen werden inzwischen die Fahrten der „Gelben Engel“ mit Hilfe des Zuse-Zentrums geplant.

„Zwar kontrollieren die Disponenten nach wie vor jeden einzelnen Auftrag und kümmern sich um Spezialfälle, etwa eine Mutter mit Kindern“, sagt Flügel. „Aber 85 Prozent aller Fälle können wir inzwischen automatisch disponieren, ohne nochmals einzugreifen.“ Und so sei damit zu rechnen, dass das Programm nach dem Urlaub, im dritten Quartal dieses Jahres, in allen Pannenhilfezentralen eingeführt wird. Die „Gelben Engel“ fliegen dann mit mathematischer Unterstützung.

Andreas Loos