Eine große Speditionsfirma hat an einem Tag etliche hundert Transportaufträge zu erledigen. Gesucht ist die kostengünstigste Aufteilung aller Fuhren auf die verfügbaren Lastwagen. Dabei geht es nicht nur darum, die Gesamtfahrstrecken und -zeiten möglichst kurz zu halten, sondern es sind auch zahlreiche Nebenbedingungen zu erfüllen: Die Lastwagen dürfen nicht überladen werden, die Fahrer müssen die Arbeitszeitbegrenzung einhalten, Kunde A öffnet erst um 10 Uhr, aber man kann nicht statt dessen frühmorgens gleich den Kunden B beliefern, denn der Auftrag besteht gerade darin, Ware von A zu B zu schaffen.

Das ist der typische Fall eines Optimierungsproblems aus der industriellen Praxis. Im Prinzip sind solche Probleme einfach: Es gibt nur endlich viele Möglichkeiten, die Aufträge den Lastwagen zuzuweisen; man probiere sie alle durch und nehme unter den zulässigen, das heißt mit den Nebenbedingungen vereinbaren Lösungen die kostengünstigste. Nur gibt es mehr denkbare Möglichkeiten, als alle Computer der Welt in erträglicher Zeit durchprobieren könnten.

Aufgaben dieser Art gehören zur selben Klasse wie das Problem des Handlungsreisenden (travelling salesman problems, TSPs): Dabei ist die kürzeste Tour durch eine vorgegebene Anzahl von Städten gesucht. Mit großem theoretischen und Rechenaufwand gelingt es immer häufiger, auch zu sehr komplexen Aufgabenstellungen die optimale, nicht mehr verbesserbare Lösung zu finden (siehe "Die optimierte Odyssee", Spektrum der Wissenschaft, 4/99, S. 76). In der Praxis dominieren jedoch nach wie vor die heuristischen Verfahren: Man nehme – und sei es blindlings – irgendeine Reihenfolge, Lastwagenbeladung und so weiter und versuche sie durch kleine Veränderungen nachzubessern.

Blinde Suche nach dem Gipfel

Es ist wie Umherirren in einer imaginären Landschaft. Die guten Lösungen entsprechen hohen Gipfeln, die schlechten tiefen Löchern, die Landschaft ist stark zerklüftet, und das kleine Männchen, das man sich als das personifizierte Optimierungsverfahren vorstellt, ist blind und macht nur kleine Schritte: Mehr als die unmittelbare Umgebung seines derzeitigen Standortes kann es nicht erfassen. Um diese Behinderung zu kompensieren, muss es sehr viele Schritte tun und darf dabei keineswegs immer nur aufwärts gehen, sonst bleibt es bald auf dem nächsten Maulwurfshügel stecken. Gunter Dueck und seine Kollegen vom Wissenschaftlichen Zentrum der IBM in Heidelberg haben in dieser Zeitschrift (3/93, S. 42) mehrere Prinzipien für das Akzeptieren von Fehltritten vorgestellt.

Nun ist es Gerhard Schrimpf und Hermann Stamm-Wilbrandt aus Duecks Arbeitsgruppe sowie dem Regensburger Physiker Johannes Schneider gelungen, die Leistung dieser heuristischen Verfahren dramatisch zu verbessern (Journal of Computational Physics, Bd. 159, S. 139–171, April 2000).

Die erste Idee ist: Man mache große Schritte statt kleine. Beim Problem des Handlungsreisenden läuft das auf große Änderungen der Städtefolge hinaus. Wenn man diese Folge einfach auswürfelt, ergibt sich ein wildes Wegegewirr kreuz und quer über die Landschaft (linkes Bild im Kasten). Man stelle sich die Wege von Stadt zu Stadt als Gummifädchen vor – eigentlich wollen sie sich ja verkürzen. Um eine große Änderung dieses Fadenmusters zu erreichen, greifen Schrimpf und seine Kollegen zu einer brutalen Methode: Sie löschen – wie durch Abwerfen einer Bombe – vorübergehend alle Städte in einem bestimmten, zum Beispiel kreisförmigen Teilgebiet aus, wodurch die freigewordenen Fädchen zusammenschnurren.

Nach dem Bombardement wird eine zerstörte Stadt nach der anderen wieder in die Tour aufgenommen, und zwar von dem Fädchen, das sich zu diesem Zweck am wenigsten dehnen muss. Die Stadt wird also an der günstigsten Stelle eingesetzt, was dem Verfahren den Namen best insertion eingetragen hat. Offensichtlich beruht der Erfolg der Kombination aus Zerstörung und Wiederaufbau ("R & R" wie ruin and recreate) darauf, dass die Zerstörung gewachsener Strukturen dem Neuen, Besseren den Weg freimacht (Bild Mitte und rechts im Kasten).

Man kann mit der Methode der best insertion auch bei null anfangen und die Städte, die man eine nach der anderen aus einer gedachten Urne zieht, entsprechend in die anwachsende Tour einsetzen. Das bringt bereits eine ziemlich gute Lösung. So ergibt sich bei den 442 Städten des TSP im Kasten im Durchschnitt eine Tour, die nur 15 Prozent länger ist als die optimale. Wer dagegen die Städte einfach in der zufallsbestimmten Reihenfolge aufsucht, ist im Durchschnitt 15-mal so lange unterwegs wie im optimalen Fall.

Der segensreiche Effekt von Zerstörung und Wiederaufbau

Wenn man nun in einer durch best insertion gewonnenen, also schon ziemlich guten Lösung nicht Städte in einem bestimmten Kreis, sondern zufällig ausgewählte löscht – eine Streubombe gewissermaßen – und abermals durch best insertion einen Weg rekonstruiert, ergibt sich in den meisten Fällen eine deutliche Verbesserung. Der Effekt ist um so ausgeprägter, je größer die Bombenwirkung ist, jedenfalls bis zu einem Zerstörungsgrad von 50 Prozent. Kreisförmige Bomben sind dagegen nur bis zu einer Größe von etwa 30 Prozent hilfreich.

Große Schritte bringen also mehr ein als kleine, erfordern allerdings auch mehr Rechenaufwand. Beim TSP halten sich diese beiden Effekte noch annähernd die Waage. Erst bei zusätzlichen Komplikationen kommen die Vorteile des Bombenverfahrens voll zum Tragen.

Typische Komplikationen sind zum Beispiel die Einhaltung von Gewichtsgrenzen und Terminen beim Lastwagenproblem. Kleine Änderungen an einer bestehenden Tour laufen stets Gefahr, die Lösung unzulässig zu machen: Wenn man irgendwie Pakete von einem Lastwagen in den anderen umpackt, ist mit großer Wahrscheinlichkeit hinterher mindestens ein Fahrzeug überladen. Da trifft es sich günstig, dass es ein Wiederaufbauverfahren gibt, das garantiert zulässige Lösungen liefert. Zu allem Überfluss liegt es auch noch im allgemeinen Trend, denn es hat gewisse Ähnlichkeiten mit Outsourcing. Das ist die zweite Idee von Ruin & Recreate.

Nehmen wir an, die Spedition ist in Frankfurt am Main ansässig. Jeder Lastwagen wird zu einer selbstständigen Geschäftseinheit erklärt. Sowie ein Auftrag hereinkommt ("ein 100-Kilo-Paket von Frankfurt nach Stuttgart, Lieferung bis 13 Uhr"), gibt jeder Lastwagen ein Gebot ab, und zwar zu den präzisen Selbstkosten. Der günstigste bekommt den Zuschlag. Wenn der im Beispiel genannte Auftrag der erste ist, der überhaupt eingeht, bieten alle Lastwagen den vollen Kilometerpreis Frankfurt – Stuttgart und zurück, und einer von ihnen erhält den Zuschlag. (Es kommt nicht darauf an, dass dieser Preis für ein einzelnes Paket aberwitzig hoch wäre.) Wenn als nächstes eine Ladung nach Würzburg zu schaffen ist, gewinnt der Lastwagen, der schon den Auftrag nach Stuttgart hat, die Ausschreibung, weil er nur noch die Mehrkosten für den Umweg in Rechnung stellt. Für eine Fuhre nach Düsseldorf kommt wahrscheinlich ein anderer zum Zuge. Für einen Auftrag, den ein Lastwagen aus Termin- oder Kapazitätsgründen nicht annehmen kann, gibt er erst gar kein Gebot ab.

Nachdem so alle Aufträge verteilt sind, bietet sich vielleicht ein etwas merkwürdiges Bild: Drei verschiedene Lastwagen fahren Stuttgart an, denn der Gewinner des ersten Stuttgart-Auftrags konnte die beiden anderen wegen eines Termins in Schweinfurt nicht annehmen, der zweite Lastwagen in die Schwabenhauptstadt war schon ausgelastet, als der dritte Auftrag hereinkam, und jeder ist an einmal angenommene Aufträge gebunden. Aber sämtliche Nebenbedingungen werden eingehalten, weil das Verfahren so konstruiert ist: Die so gefundene Lösung ist in jedem Fall zulässig.

Wie lässt sich diese halb-optimale Lösung weiter verbessern? Ganz einfach: Man werfe eine Bombe auf Stuttgart und Umgebung. Alle Aufträge für dieses Zielgebiet werden gelöscht; die Lastwagen planen daraufhin ihre restlichen Touren neu, manche bleiben vielleicht ganz zu Hause. Im nächsten Moment sind alle gelöschten Aufträge wieder da und werden nach dem geschilderten Verfahren verteilt. Nun werden die Lastwagen, die vorher für die Aufträge nach Stuttgart abenteuerliche Zickzackkurse fuhren, mit Leichtigkeit von einem unterboten, der ohnehin Kisten nach Rottweil zu bringen hat. Das Geflecht der Routen entzerrt sich merklich – jedenfalls in Stuttgart und Umgebung.

Die Region Oberfranken wird noch ungeschickt bedient? Eine Bombe auf Nürnberg und Umgebung schafft Erleichterung. Der Zwang, den Termin 12 Uhr einzuhalten, hat bei vielen Aufträgen Fuhrunternehmer am Mitbieten gehindert und dadurch eine schlechte Verteilung verursacht? Man werfe statt einer Orts- eine Zeitbombe: Alle Aufträge mit Terminen um ungefähr 12 Uhr werden gelöscht und neu ausgeschrieben. Selbst Streubomben können hilfreich sein.

Aber das ist noch nicht alles. Einmal Zerstören und Wiederaufbauen lässt sich als ein – großer – Schritt in dem oben geschilderten imaginären Gebirge interpretieren. Bei der Suche nach dem Optimum kann man viele solche Schritte hintereinander ausführen und wie bei den kleinen Schritten nach verschiedenen Strategien auch Verschlechterungen akzeptieren. Aber selbst wenn man das nicht tut, erzielen alle R&R-Verfahren dramatische Gewinne. Bei der Anwendung auf Lastwagenprobleme fanden geeignet angepasste R&R-Verfahren bereits im Durchschnitt Lösungen einer Qualität, welche die bisher besten Verfahren nur im günstigsten Fall erreicht hatten.

Welches sind die Gründe für diesen überraschenden Erfolg? An den Bomben allein liegt es offensichtlich nicht. Ihre Größe und Bauart hat zwar einen gewissen, aber doch beschränkten Einfluss auf die Leistung des Verfahrens. Eher ist es schon die Wiederaufbau-Heuristik: Im Gegensatz zu den kleinen Schritten der klassischen Optimierungsverfahren, die mit ungefähr gleicher Wahrscheinlichkeit auf- wie abwärts führen, sind die großen Schritte von best insertion und seinen Varianten in der Tendenz nach oben gerichtet. Deswegen bringt schon zielloses Umherirren etwas ein.

Andererseits sind die Wiederaufbau-Verfahren keine Wundermittel. Auch mit ihrer Hilfe findet man nicht von null an auf Anhieb eine optimale oder auch nur fast optimale Lösung. Sie sind gut für kleine Teilprobleme, für das Gesamtproblem aber weniger geeignet – oder gar nicht durchführbar: In manchen Anwendungen erzeugt eine wohldosierte Bombe ein Teilproblem, das mit anderen Techniken exakt lösbar ist. Das Gesamtproblem dagegen wäre für diese Verfahren viel zu umfangreich.

Die Bomben sind also ein Mittel, um Verfahren, die sehr gut bei mittelgroßen Problemen funktionieren, auf große anwendbar zu machen: Sie schaffen ein mittelgroßes Problem, während die klassischen Heuristiken das große Problem durch Lösen sehr vieler sehr kleiner Teilprobleme angehen.

Es trifft sich gut, dass der Recreate-Teil von Ruin & Recreate aus lauter unabhängigen Preisberechnungen verschiedener Lastwagen, Teilstrecken und so weiter besteht. Wegen dieser Unabhängigkeit lässt sich nämlich dieser Teil des Verfahrens, der ungefähr 90 Prozent der Gesamt-Rechenzeit in Anspruch nimmt, an die vielen Prozessoren eines Parallelrechners delegieren.

Bei allem Erfolg: Das Verfahren R&R ist heuristisch und sein Funktionieren mathematisch nicht beweisbar. Es gibt auch keine Anleitung, wie man die Parameter – Bombensorte und -größe, Akzeptierungsstrategie für Fehltritte – im Einzelfall wählen soll. Man muss einfach probieren. Dabei ist es hilfreich, sich die Arbeitsweise des Verfahrens mit einer geschickten Visualisierung am Bildschirm vorspielen zu lassen.

So entdeckt man zum Beispiel, dass abweichend von dem oben geschilderten Ausschreibungsverfahren Dumping-Angebote sinnvoll sein können. Gesetzt den Fall, ein Lastwagen muss für seine zweite Kiste so viel Zusatzaufwand treiben, dass er die anderen nicht unterbieten kann, fährt aber mit drei Kisten konkurrenzlos günstig. Dann kommt er, wenn alles mit rechten Dingen zugeht, nie dazu, dieses günstige Angebot für die dritte Kiste abzugeben – es sei denn, er bietet die Fuhre für die zweite Kiste unter Preis an. Was bei Lastwagen kaum vorstellbar ist, kommt bei der Auslegung von Kommunikationsnetzen regelmäßig vor.

Kleine Änderungen der Nebenbedingungen erfordern zuweilen große Änderungen der Verfahrensparameter. Es empfiehlt sich also, das Problem zuerst sehr realitätsnah in die mathematische Formulierung umzusetzen und dafür engen Kontakt zum Kunden zu halten: der Firma, deren Betriebsabläufe man optimieren soll.

Am besten lässt sich optimieren, bemerkt Schrimpf mit leichtem Grinsen, wenn der von den Einsparungen Betroffene nicht mit am Tisch sitzt. Läuft die Optimierung darauf hinaus, den Lagerbestand einer Firma auf ein Drittel zu reduzieren, könnte das die Kooperationsbereitschaft des Lagerleiters mindern, weil dessen firmeninterner Rang an der Größe des Lagers hängt. Wenn aber das Kommunikationsnetz einer auf viele Standorte verteilten Organisation möglichst kostengünstig zu gestalten ist, leidet unter dem Erfolg nur der Netzbetreiber – und der wird vorher nicht gefragt. <


Aus: Spektrum der Wissenschaft 5 / 2000, Seite 8
© Spektrum der Wissenschaft Verlagsgesellschaft mbH