Wenn das Lager ein Nest und die Lastwagen Ameisen sind

(as) «Transportplanung mit Ameisenlogik» heisst das vom Migros-Genossenschaftsbund und dem Softwareunternehmen Cantaluppi & Hug AG aus Zürich vorgestellte Siegerprojekt des Swiss Logistics Award 2012. Ziel war es, das bei der Migros täglich zu bewältigende Transportvolumen effizienter zu disponieren. Es handelt sich dabei um eine Menge von 23 000 Tonnen Gütern, die auf 400 Bahnwagen und mehr als 500 Nutzfahrzeugen durchs Land reisen. Täglich fallen über 2000 Transportaufträge mit rund 70 000 Paletten an, wobei 600 Standorte angefahren werden. Angesichts der Komplexität der Disposition stellte man bei der Migros fest, dass das menschliche Hirn zunehmend an seine Grenzen stiess. Besonders unter Zeitdruck war es schwierig, eine optimale und kilometeroptimierte Tourenplanung zu erstellen.
In der Folge wurden technische Hilfsmittel evaluiert, welche trotz der Komplexität der Transportplanung mit allen möglichen Restriktionen und Rahmenbedingungen in kurzer Zeit optimale Touren in guter Qualität liefern sollten. Cantaluppi & Hug hat bereits die heute eingesetzte Transportsoftware CADIS für die Migros entwickelt. Die neue systemunterstützte Tourenplanung setzt auf den Einsatz eines Optimierungsmodells. Dieses berücksichtigt Daten über das Strassennetz und Kilometerkosten ebenso wie Restriktionen, die sich aus Zeitfenstern, Fahrzeugtypen, Ladekapazitäten und anderen Parametern ergeben.
In der IT befasst sich das Fachgebiet Operations Research mit solchen Problemen. Doch die Rechenzeit heute gängiger Optimierungsmodelle steigt mit der Zahl der Kunden stark an. Während ein Modell für 40 Kunden in einer Sekunde bereitsteht, braucht der Computer bei 52 Kunden schon einen Tag und bei 70 sogar tausend Jahre.

Die richtige Route duftet stark

Ameisen arbeiten anders. In den 90er- Jahren stellten Forscher fest, dass sich Ameisenstrassen zwischen Futterquelle und Nest immer auf dem kürzesten Weg etablieren. Hindernisse werden stets auf der kürzeren Seite umgangen. Der Mechanismus dahinter ist einfach. Ameisen markieren ihre Wege mit flüchtigen Duftstoffen. Hat eine Ameise eine Futterquelle entdeckt, geht sie den Weg zurück zum Nest und verstärkt die Duftspur auf dem Weg. Andere Ameisen werden davon angelockt, und es bildet sich eine Ameisenstrasse. Entstehen zufällig zwei Ameisenstrassen zur selben Futterquelle, duftet die kürzere stärker und lockt die Tiere stärker an. Für den Computer ist nun das Verteilzentrum das Nest, die Lastwagen sind die Ameisen und die Futterquellen die Filialen. Das Futter sind die Transportaufträge zwischen Filiale und Nest.
Der Computer errechnet den besten Weg in zwei Schritten. In einem ersten werden Tausende von Lösungen erzeugt und die besten Streckenabschnitte mit einer virtuellen Duftspur versehen. Im zweiten Schritt werden Ameisen beziehungsweise Lastwagen in der Nähe einer Strecke mit Duftspur auf diese geroutet. Dann wird erneut die beste Strecke ermittelt und die Duftspur dort verstärkt. Alle anderen früher markierten Strecken verlieren etwas von ihrer Duftstärke. Dieser Prozess läuft so lange, bis es keine Verbesserungsmöglichkeiten mehr gibt oder er von aussen abgebrochen wird. Die Migros integrierte das so entwickelte Optimierungswerkzeug in die normale CADIS-Dispositionsoberfläche. Für die Optimierung kann der Disponent jetzt Aufträge markieren und die Optimierung für diese starten. Eine manuelle Anpassung ist stets möglich. Aus technischer Sicht ist das Tool ein separates C#-Programm, welches vom Dispoprogramm CADIS aufgerufen wird. Die Daten werden über eine XML-Schnittstelle ausgetauscht. Die Chauffeure erhalten die errechneten Tourendaten schliesslich über ihre mobilen Endgeräte. Auch die Filialen können in Echtzeit über ihre Anlieferungen informiert werden.

Ameisenlogik liefert fast immer pünktlich

Die Software liefert sehr gute Ergebnisse. In einem direkten Vergleich erhielten ein erfahrener Disponent auf der einen und das Programm auf der anderen Seite die gleiche Aufgabe. Dabei ging es darum, 200 Filialen mit insgesamt 1736 Paletten Nachschubmenge für einen Transporttag zu beliefern. Das Zeitfenster für die Warenanlieferung bei den Filialen betrug plus/minus 30 Minuten. Der erfahrene Disponent brauchte vier Stunden für die Planung, das Programm fünf Minuten Rechenzeit. Der Disponent kam dabei auf 60 Touren mit 10 400 Kilometern, die Software schlug 58 Touren mit 10 600 Kilometern vor. Allerdings hatte der Disponent bei der Pünktlichkeit keine Chance. Er verzeichnete total 130 Stunden Abweichung von den Anliefer-Zeitfenstern. Seine Lieferungen kamen maximal 90 Stunden zu spät und 40 Stunden zu früh an. Die Software lieferte hingegen nie zu spät, an einigen Orten aber insgesamt zehn Stunden zu früh. Zudem hielt der Disponent, ob bewusst oder unbewusst, einige Restriktionen nicht ein. Im praktischen Einsatz zeigte sich jedoch, dass der Disponent in rund 20 Prozent aller Touren unabkömmlich war und sich insgesamt erst aus der Kombination von Software und Mensch die gewünschte optimale Distributionsleistung erzielen liess.
Testreihen im Migros-Verteilzentrum Suhr verliefen sehr erfolgreich. Seit 2012 wird deshalb das gesamte Saisongeschäft (Ostern, Weihnachten, grossvolumige Aktionen) mit dem Ameisentool disponiert. Statt wie bisher fünf Manntage braucht die Disposition aller Touren nun noch einen halben Tag. Die Weg-Zeit-Optimierung ist durch die Abrechnung auf Basis von Tonne/Kilometer direkt kostenwirksam. Die Investitionskosten für die Software, die als Modul der CADISApplikation läuft, waren einmalige Kosten, die Betriebskosten sind bescheiden. Die Migros erzielt mit dem Einsatz des Tools im Vergleich zur manuellen Disposition ein Optimierungspotenzial von bis zu zehn Prozent. Bei Tourenplanungen mit relativ starren Gebietszuteilungen und fixen Fahrplänen sind sogar 15 bis 30 Prozent erreichbar.
Über die Kosteneinsparungen hinaus ist auch die erzielte Reduktion der CO2-Emissionen für die Migros ein erklärtes Ziel. Das Tool kommt derzeit auch bei der Transportsimulation und dem Offertwesen zum Einsatz. Im Endausbau ist vorgesehen, dass es die tägliche Distributionsplanung ab den grossen Verteilzentren unterstützt. Bisher erfolgte die Transportplanung nach auf Erfahrungswerten gebildeten und relativ starren Rahmentouren, welche in etwa immer gleich gefahren wurden. Mithilfe der Ameisenlogik und des Optimizers sollen die Touren täglich von Grund auf neu berechnet werden. Laut Guido Federspiel, Leiter Operations, wird eine Umstellung aber erst nach einem längeren Parallelbetrieb und mit hoher Planungsqualität erfolgen. Eine wichtige Basis für die computerunterstützte Tourenplanung ist nämlich die saubere Erfassung und Pflege der Einflussfaktoren und geltenden Rahmenbedingungen. Einschränkungen kann die Ameisenlogik nur berücksichtigen, wenn diese als Regeln hinterlegt sind. Die konsequente Datenpflege hat deshalb an Wichtigkeit zugenommen, betont Federspiel.

Grundsätzlich überall nutzbare Innovation

Die Jury des Swiss Logistics Award beurteilte das Projekt als zukunftsweisend. Es erlaube die optimale Auslastung der Verkehrsinfrastruktur. Planungen könnten innerhalb kürzester Zeit abgeschlossen werden. Die Anwendung des Verfahrens der Metaheuristik (Ameisenlogik) stelle in der Transportlogistik eine Innovation dar. Einmalig und wegweisend für die Entwicklung von weiteren Optimierungsprogrammen sei die Geschwindigkeit, mit welcher die komplexe Aufgabe bewältigt wurde. Dank dem Algorithmus würden Tourkilometer minimiert und die Auslastung der Fahrzeuge optimiert.
Laut Ruedi Hug eignet sich die Software für Werkverkehrs- und Transportdienstleister, die nicht zwingend an fixe Tourenpläne gebunden sind. Ob sich der Einsatz lohne, hänge weniger von der Zahl der Touren insgesamt, sondern eher von der individuellen Auftragsstruktur ab. Je nach Situation erreiche das Sparpotenzial zwischen fünf und 30 Prozent. Grundsätzlich könne jeder Betrieb das Ameisentool nutzen. Es wird über eine XML-Schnittstelle an die verwendete Transportsoftware angebunden. Zudem bietet Cantaluppi & Hug die Transportsoftware CADIS ausserhalb der Migros unter dem Namen «Transit» an.

Alexander Saheb