Gelbe Engel lernen rechnen

	Bild: ADAC

Rund 10.000 Pannen werden dem ADAC an einem ganz normalen Tag gemeldet. Um hier die Pannenhelfer möglichst effektiv zu koordinieren ist nicht trivial und bereitet auch Mathematikern Kopfzerbrechen.

Andreas Loos

Die Zahlenkolonnen, die über den Bildschirm laufen, wollen nicht enden. „Ein ganz normaler Urlaubstag für ADAC-Helfer“, sagt Jörg Rambau mit Blick auf seinen Monitor. Hinter jeder neuen Zeile verbergen sich liegengebliebe Fahrzeuge, kaputte Anlasser, leere Batterien, oder verrußte Zündkerzen: Die Zahlen verschlüsseln, wann und wo bei den „Gelben Engeln“ des ADAC Hilferufe seiner Mitglieder eingehen. Mathematiker wie Jörg Rambau haben damit am Berliner Zuse-Institut Algorithmen gebastelt, die die Pannenhelfer schneller zu den Pannen bringen.

Rund 10.000 Pannen werden dem ADAC an einem ganz normalen Tag gemeldet. „Zu Urlaubszeiten oder bei Wintereinbruch können es leicht doppelt so viele werden“, weiß Dietmar Flügel, Leiter des Pro-„Helfen“ beim ADAC. Alle Pannenmeldungen laufen in den fünf Pannenhelferzentralen  des ADAC auf. Bislang lief die anschließende Verteilung der Aufgaben dann von Hand: Mitarbeiter, so genannte Disponenten, wiesen jeder Panne einen der 1.700 „Gelben Engel“ bzw. eines der 5.000 Fahrzeuge der ADAC-Service-Vertragspartner zu.

Dabei wählten sie eine einfache Strategie: Jeweils der Pannenhelfer, der der Panne am nächsten ist, wird alarmiert – nach Augenmaß und einem Blick auf eine digitale Landkarte, ähnlich wie der Bildschirm eines Navigationssystems. „Das kann aber bedeuten, dass andere Pannenopfer anschließend länger warten müssen“, sagt Jörg Rambau. „Gute Entscheidungen sind bei der Zahl der Pannen und Helfer mit bloßem Auge kaum noch möglich.“

Der Informatiker Flügel vergleicht das Disponieren sogar mit Schachspielen: „Der Tag beginnt mit einer Ausgangssituation und entwickelt dann eine Eigendynamik. Und genau 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 daher vor drei Jahren mit dem ZIB zusammengetan.“

Die Arbeit der „Gelben Engel“ sollte künftig der Computer erledigen – „ein technisch triviales Problem“, so Flügel. Doch in Wirklichkeit entpuppte sich die Angelegenheit als ziemlich komplex. Denn die Disponenten schlagen sich täglich mit zwei der schwierigsten mathematischen Probleme überhaupt herum, dem Problem des Hand-lungsreisenden und dem Problem der Mengenpartitionierung.

Seit über 200 Jahren spukt der Handlungsreisende durch mathematische Hirne; 1932 brachte ihn der Wiener Algebraiker Karl Menger dann mathematisch auf Papier. Seine Aufgabe ist schnell formuliert: Wie sieht der kürzeste Pfad aus, der einen Handlungsreisenden durch vorgegebene Orten führt, ohne dass er einen Ort mehrmals besucht? So einfach das klingt, die Lösung ist keineswegs „trivial“. Denn ein „traveling salesman“, der alle möglichen Wege durchprobieren will, hat sich einiges vorgenommen: Schon bei 10 Städten muss er sich zwischen 10!, also 3.628.800 verschiedenen Wegen entscheiden. Und einen Algorithmus, der wesentlich besser funktioniert als alle Wege einfach auszuprobieren, kennen Mathematiker nicht.

Das „TSP“, wie das „traveling salesman problem“ unter Graphen-theoretikern heißt, 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 – auf jeden Fall rasant. Immerhin sind heute schon Probleme mit einigen Tausend Städten lösbar, was Computer jedoch einige Stunden beschäftigt. Der Weltrekord liegt derzeit bei einer Tour durch 15.112 deutsche Städte, deren Länge Mathematiker an der texanischen Rice University und in Princeton auf knapp 66.000 km Länge bestimmten – in umgerechnet 22,6 Jahren Rechenzeit.

Und 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 auch zum Beispiel im australischen Melbourne eingesetzt werden“, weiß Dietmar 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. Hier machen die Netze mit unterschiedlicher Maschengröße die Situation komplexer.“

Aus mathematischer Sicht ist die Schwierigkeit ohnehin klar: „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“, fasst Jörg Rambau die Ausgangslage zusammen. Ein paar Jahre können sich die Pannenhelfer auch nicht Zeit für die Rechnung 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 also vergleichsweise einfach. Doch Jörg Rambau und seine Kollegen ließen sich nicht entmutigen; schließlich wurden in den vergangenen zwanzig Jahren unter Mathematikern eine ganze Reihe Tricks entwickelt, mit denen man solchen „Dispatching-Problemen“ zu Leibe rücken kann.

Die Mathematiker durchsieben daher gar nicht die ganze Sahara – sie lesen eine ziemlich gute Lösung quasi aus einer Handvoll Sand. Das Gold interessiert sie auch nicht, ihnen genügt etwas, das so ähnlich glänzt – schließlich reicht für den Alltag der ADAC-Helfer schon eine ziemlich gute Zusammenstellung von Routen. Die Routen der einzelnen Pannenhelfer sollen nur recht kurz sein und wenige Verspätungen erzeugen. Findet der Computer eine solche Zusammenstellung guter Touren 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 dem Algorithmus ZIBDIP, dem 'Zuse-Institut Berlin Dispatching via Integer Programming', können wir so in zehn Sekunden 200 Pannen auf 100 Pannenhelfer verteilen – und sind danach weniger als ein Prozent vom Optimum entfernt“, sagt Jörg Rambau.

Nicht nur die Mathematiker sind stolz auf diesen Erfolg: Die Pan-nenhelfer des ADAC testen das Tool in Genshagen bei Berlin bereits seit über einem Jahr, und sind ebenfalls recht zufrieden. Auch in der Pannenhelferzentrale Dormagen werden inzwischen die Fahrten der „Gelben Engel“ automatisch mit ZIBDIP geplant. „Zwar kontrollieren die Disponenten nach wie vor jeden einzelnen Auftrag und kümmern sich um Spezialfälle wie eine Mütter mit Kindern besonders, doch 85 Prozent aller Fälle können wir inzwischen automatisch disponieren, also ohne nochmals einzugreifen“, so Dietmar Flügel.

Und so sei damit zu rechnen, dass das Tool nach dem Urlaub im dritten Quartal dieses Jahres in allen Pannenhilfezentralen eingeführt wird. Die „Gelben Engel“ fliegen dann mit mathematischer Unterstützung.