Der Zufall gehört zum Programm

Von Vasco A. Schmidt

Flugpläne werden heute immer noch von sehr erfahrenen Spezialisten meist per Hand erstellt - wenn auch mit Unterstützung durch Computer. Die Flugplanoptimierung gehört zu jenen Problemen, die sich, wenn überhaupt, mathematisch exakt nur mit enormem Aufwand berechnen lassen. Selbst die schnellsten Rechner würden dazu außerordentlich viel Zeit benötigen, mehr Zeit, als die Sonne und womöglich auch das gesamte Universum existieren werden, schätzen Experten. Ein Informatiker der Berliner Humboldt-Universität hat nun einen Weg gefunden, die Flugplanoptimierung weitgehend dem Computer zu überlassen.

Um zu zeigen, was er in zwei Jahren harter Arbeit erreicht hat, braucht Thomas Emden-Weinert nur kurz auf die Maustaste zu drücken. Wenige Minuten später erscheinen blaue und rote Balken am Bildschirm, angeordnet wie in einem Stundenplan. Sie zeigen an, wie eine mittelgroße Fluglinie an einem Arbeitstag Piloten, Stewards und Stewardessen auf ihre Flüge verteilen sollte, um möglichst kostengünstig zu arbeiten.

Die blauen Balken stehen für bereits zufriedenstellend organisierte "Rundreisen" des Personals, Reisen also, die in der Heimatstadt beginnen und auch dort enden. Die roten Balken weisen auf Schwachstellen hin, die noch, vom Rechner oder per Hand, nachgebessert werden müssen.

Oft müssen Tausende Flüge mit mehreren hundert Flugzeugen gemanagt werden. Die Planer wollen erreichen, daß die Arbeitszeit der Piloten und Stewardessen ein Minimum an unfreiwilligen Pausen enthält. Und das Ziel heißt immer "Rundreise", selbst wenn dazu die Besatzung mitunter mehrmals das Flugzeug wechseln muß.

Komplizierte Arbeits- und Pausenregelungen für die Flugbegleiter erschweren die Arbeit der Planer. "In der Praxis ist man oft schon froh, wenn man überhaupt eine Zuweisung des Personals findet, die den gesetzlichen und tarifrechtlichen Bestimmungen genügt", sagt Emden-Weinert, der wissenschaftlicher Mitarbeiter am Lehrstuhl von Hans-Jürgen Prömel am Institut für Informatik ist.

Die Mathematik bietet das nötige Handwerkszeug, um komplexe Aufgaben wie die Berechnung von Flugplänen, das Management von Busnetzen oder Arbeitsabläufe in einer Automobilfabrik in einer akzeptablen Zeit wenigstens näherungsweise per Rechner zu simulieren und zu optimieren. "Operation Research" heißt die Wissenschaft, die sich dafür herausgebildet hat. Die Informatiker gehen dabei Wege, die an die Evolutionsprinzipien der Natur erinnern.

Ganz zu Anfang erstellt der Computer - mit Hilfe des Zufalls - eine "erste Lösung". Die kann schon ganz gut, aber auch furchtbar schlecht sein. Später wird diese Lösung dann Schritt für Schritt verbessert. Falls möglich, werden dabei zwei kleine Rundreisen zu einer größeren Strekke zusammengefaßt, oder aber eine allzu lange Strecke auf zwei Routen verteilt.

Am naheliegendsten wäre es, von der ersten Lösung aus immer zur nächst günstigeren zu gehen. Mathematiker nennen ein solches Optimierungsverfahren "gierig" (engl. greedy), weil es mit jedem Schritt eine Verbesserung erreichen möchte. Es ist einfach zu programmieren, findet aber fast nie eine kostengünstige Lösung. "So ein Algorithmus verrennt sich", beschreibt Emden-Weinert das Dilemma.

Aussichtsreicher ist es, nicht von Anfang an nach immer besseren Lösungen zu suchen, sondern auch Verschlechterungen zuzulassen. Dafür zieht das Programm nicht mehr, wie der "gierige Algorithmus", alle Lösungen in der Nähe der Startlösung zum Vergleich heran, sondern nur eine einzige, die es erneut mit Hilfe des Zufalls sucht. Ist diese besser als die bisherige Lösung, und unter "besser" verstehen die Auftraggeber der Berliner Informatiker "wirtschaftlicher", wird damit weitergearbeitet. Ist sie schlechter, dann "würfelt" der Computer, ob er mit der bisherigen oder der schlechteren Lösung weiterprobiert. Wie er vorgeht, wird vor Aufruf des Programms festgelegt; dabei spielen Zeit und Qualität eine ausschlaggebende Rolle.

Da die Crewpläne in der Regel bereits Monate im voraus erstellt werden, kann man meist verhältnismäßig langsam vorgehen, viele Lösungen analysieren und die Chance erhöhen, eine sehr gute zu finden. Muß aber wegen kurzfristiger Stornierung von Flügen der Plan in wenigen Minuten umgestellt werden, so muß gröber vorgegangen werden. Es kann, je nach gewünschter Qualität, wenige Minuten oder über anderthalb Stunden dauern, bis nach dem Mausklick die blauen oder roten Balken des Tagesplans erscheinen.

"Damit das Programm nicht zu komplex und damit zu langsam wird, können wir nur die wichtigsten Größen simulieren", erklärt Thomas Emden-Weinert. So muß der Computer zwar strikt die Kosten minimieren, darf aber gelegentlich einige tarifliche Bedingungen überschreiten. "Deshalb ist es in der Praxis oft noch nötig, per Hand nachzubessern."

Das nachträgliche Korrigieren ist nach Meinung der Praktiker vorteilhaft. "Man kann verschiedene Szenarien austesten und unterschiedliche Lösungen vergleichen", sagt Bernd Voigt, Geschäftsführer der Lufthansa Systems Berlin GmbH. Man könne anhand solcher Tests und Vergleiche eine höhere Planungsqualität erreichen.

Lufthansa Systems zollte der Software aus der Humboldt-Universität großes Lob. Die Lufthansa-Tochter hat kalkuliert, daß die Fluggesellschaften mit Hilfe des Programms bis zu 20 Prozent der Ausgaben für das Bordpersonal - nach dem Treibstoff der zweitgrößte Kostenfaktor - sparen können. Von Ende des Jahres an soll die neue Software nicht nur auf den Rechnern der Muttergesellschaft laufen. Auch mittlere und große Fluggesellschaften in Europa und Südamerika - es handelt sich dabei um Kunden von Lufthansa Systems - wollen künftig mit dem Programm kostengünstiger fliegen.