Wie Bienen helfen, Touren zu planen
Tourenplanungsprobleme bilden einen wesentlichen Schwerpunkt des Operations Research.
Dieser Umstand ist nicht zuletzt durch ihren direkten wirtschaftlichen Bezug begründet.
So bilden die Transportkosten mit einem Anteil von 21,6% im industriellen Sektor beziehungsweise
sogar 31,2% im Dienstleistungsbereich den größten Treiber der Logistikkosten und damit verbunden
einen nicht zu vernachlässigenden Einflussfaktor auf die Wirtschaftlichkeit von Unternehmen [Str08].
Der Gegenstand von Tourenplanungsproblemen ist es, Auslieferungs- oder Abholaufträge von geographisch verteilten Kunden zu effizienten Touren zusammenzufassen. Im Standardproblem der Tourenplanung werden Aufträge eines homogenen Gutes einer festen Anzahl kapazitätsbegrenzter sowie gleichartiger Transportmittel zugeordnet, welche die Auslieferung der Aufträge in einer möglichst guten Reihenfolge ausführen. Die hierbei verfolgte Zielstellung ist die Minimierung der Gesamtstrecke bei vorgegebener oder maximaler Fahrzeuganzahl. Hierbei dürfen die Aufträge nicht gesplittet und die Kapazitätsgrenzen der Transportmittel nicht verletzt werden. Das Tourenplanungsproblem beschreibt somit simultan ein Zuordnungsproblem von Kundenaufträgen zu Touren und je Tour ein Reihenfolge- bzw. Rundreiseproblem hinsichtlich der Anfahrt der einzelnen Kunden. Bienenalgorithmen sind neben Verfahren wie Ant Colony Optimization und Genetischen Algorithmen ein Vertreter der naturanalogen Metaheuristiken, die vornehmlich zur Optimierung kombinatorischer Probleme geeignet sind. Sie stellen ein noch relativ junges Verfahren dar und adaptieren im Allgemeinen das Verhalten realer Honigbienen bei der Futtersuche, wobei die Kommunikation zwischen den Bienen eine zentrale Rolle einnimmt. Nach KARL VON FRISCH [Fri93] nutzen Bienen unterschiedliche Tänze dazu, um andere Bienen über gefundene Futterquellen rund um den Bienenstock zu unterrichten. Hier ist insbesondere der Schwänzeltanz zu erwähnen, welcher sowohl die Richtung als auch die Entfernung einer Futterquelle übermittelt. Der untenstehende Beitrag stellt einen neuen Optimierungsalgorithmus für das Standardproblem der Tourenplanung mit Zeitfensterrestriktionen vor. Das Verfahren beschreibt die zweistufige Metaheuristik "Bee Colony-inspired Algorithm (BCiA)" zur Steuerung eines Konstruktionsverfahrens, welches das Verhalten von Honigbienen bei der Futtersuche adaptiert. Das in einer Diplomarbeit entwickelte Verfahren wurde erfolgreich auf Benchmark-Probleme angewendet und erzielt gute Resultate. Originalartikel & Weitere Informationen
Literatur
|