Rubriken

Aktuelles - Mai 2008

Duftende Ameisenspuren wiesen den Weg zu effizienter Logistik-Entwicklung

Prämiertes Projekt folgt der Natur – Kraftstoffverbrauch wichtiger Aspekt

„Besonders viel mit Ameisen habe ich nicht am Hut, aber sie können uns helfen, Probleme in der Wirtschaftswissenschaft zu lösen.“ Für Prof. Dr. Hermann Gehring, Leiter des Lehrgebiets Wirtschaftsinformatik in der Fakultät für Wirtschaftswissenschaft, FernUniversität in Hagen, sind die Krabbler „Träger eines von der Natur vorgegebenen Problemlösungskonzeptes“. Von diesem Optimierungssystem der Ameisen ließen sich der Hagener Wissenschaftler und sein ehemaliger Schüler Prof. Dr. Jörg Homberger (Stuttgart) inspirieren, um mit zwei Unternehmen eine Logistik-Software für die Kfz-Tourenplanung zu entwickeln. Zusammen mit Oliver Becker, arvato sytems GmbH, Gütersloh, und Markus Feldmann, Digital Request GmbH, Bielefeld, erhielten sie hierfür den „do it.software-award 2007“. Gehring und Homberger hatten die Schwerpunktaufgaben Methodik, Parallelisierung und Algorithmisierung. Die Praxis floss durch die beiden Unternehmensvertreter ein.

Das grundlegende Lebensproblem jedes Ameisenvolkes ist die Futtersuche: Die Tiere schwärmen von einem Punkt, ihrem Nest, aus, finden zufällig eine Nahrungsquelle. Bei der Suche nach einer ergiebigen und nahegelegenen Futterquelle legt jedes eine Spur aus Duft-Lockstoffen (Pheromonen). Wenn eines eine gute Futterquelle gefunden hat läuft es sofort auf seiner eigenen Spur zurück in den Ameisenhaufen. In dieser Kommunikationszentrale informiert die Ameise ihre Artgenossinnen. Je kürzer der Weg ist, desto mehr Informationen können gegeben werden. Nun setzt eine Ameisenwanderung zu der günstigen Quelle ein – die Pheromonenspur duftet immer stärker. „Als Kollektiv führen die Ameisen also eine Wegoptimierung durch“, erläutert Prof. Gehring. Ihr Grundkonzept basiert auf dem Evolutionsprinzip und wird als „genetischer Algorithmus“ bezeichnet. Von diesem Optimierungssystem der Ameisen ließen sich auch die beiden Hagener Wissenschaftler inspirieren.

Optimale Lösung nicht das Ziel

An diesem Modell orientiert sich die Wissenschaft schon seit einigen Jahren bei der effizienten Lösung von Problemen. Dabei geht es nicht darum, die optimale Lösung zu finden. Vielmehr reicht es, mit einem vertretbaren Aufwand und möglichst schnell eine sehr gute oder gute Lösung zu finden. Wichtig hierfür ist – analog zur Duftverstärkung – auf mathematischem Weg die Wahrscheinlichkeit zu erhöhen, eine gute Lösung zu finden.

Die Lösungsfindung stellt man sich am besten dreidimensional vor: In einem abgegrenzten (Problem-)Bereich befindet sich ein Gebirge. Jeder Berg stellt eine der möglichen Problemlösungen dar, je höher ein Gipfel ist desto besser ist die Lösung. Auf einen Unterschied zwischen virtueller Realität und Berechnung weist Prof. Gehring hin: „In einem tatsächlichen Gebirge sieht ein Mensch ja, welcher Gipfel der höchste ist – in der Mathematik nicht.“

Auf der Suche nach dem Optimum generiert ein Rechenprogramm zufällige Lösungen – z. B. 1.000 – und berechnet mögliche (Lösungs-)Wege zu immer höheren Gipfeln. Je mehr zu einem bestimmten Gipfel führen, desto größer ist die Wahrscheinlichkeit, dass dies eine sehr gute Lösung ist, wenn auch nicht unbedingt die Beste. Für eine bestimmte Zahl, vielleicht 100, wird dann die jeweilige Lösungsgüte – die Wegelänge – berechnet. In der anschließenden „Phase der laufenden Verbesserungen“ erhalten die „guten Routen“ eine höhere Wahrscheinlichkeit, gewählt zu werden. Je mehr Lösungswege berechnet werden desto größer ist die Chance, der optimalen nahe zu kommen. Lernt man so die „Wege“ kennen, kann man ihre Qualitätsfaktoren besser einschätzen, z. B. ihre Kosten. Je besser die Qualität ist, desto stärker fließen die positiven und negativen Faktoren in die Bewertung ein. Genau wie die Ameisen – die zumindest eine Futterquelle ansteuern, mit der sie (über-)leben können – erhält man so eine wenigstens zufriedenstellende Lösung.

Ob sie gut genug ist muss im Einzelfall bewertet werden. „Die Gipfelhöhe – die Problemlösung – im mathematischen Modell entspricht dabei der Futterquellen-Qualität der Ameisen, die Zahl der Optimierungsläufe des Rechenprogramms ihren Wegen, die Wahrscheinlichkeitsverteilungen den Pheromonen", erläutert Prof. Homberger. Dafür muss der Rechner allerdings lange genug arbeiten.

Das Projektteam kam daher auf die Idee, für eine entsprechende Rechnerkapazität verschiedene Computer zu einem leistungsstarken Parallelrechner zu vernetzen. In diesem Rechnernetz fließen – wie im Ameisenhaufen – Informationen darüber, wie die Wege zu bewerten sind: Wie lang sind sie? Welche Kosten für Transporte entstehen? Je günstiger ein Weg ist, desto stärker „duftet“ die rechnerische Pheromenenspur.

Besonders stolz ist das Team darauf, dass erstmals der ökologische Aspekt berücksichtig werden kann. Üblicherweise geht es bei Entwicklungen zur Tourenoptimierung darum, die Fahrzeugzahl zu verringern oder die Wegstreckensumme aller eingesetzten Kfz zu vermindern. Mit der neuen Software kann man aber auch die Umweltverträglichkeit der Touren optimieren. Um den Kraftstoffverbrauch und den C02-Ausstoß zu minimieren werden Strecken ausgewählt, die z. B. gleichmäßige Geschwindigkeiten ermöglichen. Dabei werden Qualitätsfaktoren wie Entfernungen oder Fahrzeuganzahl berücksichtigt. Ein Einzelhandelsunternehmen, das bei der Entwicklung kooperierte, konnte bis zu 20 Prozent C02-Emissionen verhindern.

Die Professoren Gehring und Homberger hatten in dem Projekt die Schwerpunkte Methodik, Parallelisierung und Algorithmisierung. Die Grundlagen für die im Sinne des Wortes „richtungweisende Arbeit“ legte vor allem Prof. Dr. Jörg Homberger in seiner Zeit als wissenschaftlicher Mitarbeiter an der FernUniversität. Die Fäden des Projektes liefen auch jetzt wieder bei ihm zusammen, ist Prof. Gehring stolz auf seinen früheren Promovenden. Der heutige Professor an der Fachhochschule für Technik, Stuttgart, will sich in nicht all zu ferner Zeit bei ihm auch noch habilitieren.

Gerd Dapprich | 19.05.2008
FernUni-Logo FernUniversität in Hagen, 58084 Hagen, Telefon: +49 2331 987-01, E-Mail: fernuni@fernuni-hagen.de