Über Umwege zum Ziel der optimalen Route

15. November 2011, 18:46
posten

Transportlogistik ohne Computerunterstützung ist heute nicht mehr denkbar - Damit der Tourenplaner aber nicht am Menschen vorbeiführt, werden immer komplexere Ableitungen aus der Mathematik nötig

Im Zeitalter des Computers stirbt jeder Handlungsreisende tausend logistische Tode. Denn schon ein nicht vorgesehener Umweg für die ganz gewöhnliche Leberkässemmel kann eine softwaregestützte Tourenplanung derart aus dem Konzept bringen, dass die Neuberechnung der nächsten Ziele mehrere Tage benötigt. Damit menschliche Abweichungen von der computergeplanten "Idealroute" in der Praxis dennoch nicht zum Totalabsturz der Logistik-IT führen, müssen sich Informatiker bereits sehr ausgefallener Methoden der Mathematik bedienen.

"Nehmen wir das Beispiel einer Vetretertour mit 22 Kunden", erklärt Robert Keber, Logistikinformatiker der Hagenberger Software-Schmiede Risc. "Schon in diesem Fall bedeutet eine Änderung der berechneten Route eine Herausforderung für die Software: Kommen nur zwei neue Orte hinzu, würde die Zeit für die Neuberechnung normalerweise auf 23 Tage ansteigen, vorausgesetzt natürlich, wir benutzen zu simple mathematische Gleichungen."

Freilich werden sich nun nicht nur Staubsaugervertreter fragen, warum Computer dann überhaupt zur Tourenplanung eingesetzt werden, wenn denkende Menschen Umwege offensichtlich intelligenter kompensieren. Die Antwort darauf ist dennoch recht einfach: Softwaregestützte Transportlogistik bringt auch enorme Wettbewerbsvorteile. Die Fahrzeuge in einem Fuhrpark sind besser ausgelastet, insgesamt werden die gefahrenen Kilometer, der Spritverbrauch sowie die Emissionen reduziert, und im Normalfall ist ein Fahrer dadurch tatsächlich früher beim Kunden. Allerdings verlagert sich die logistische Problemlösungskompetenz so eben vom Disponenten zum Informatiker.

Keine Tipps gegen Tippfehler

Die Probleme beginnen bereits beim Pflegen der Kundenkartei. So können vorhandene Adresseinträge heute zwar schon weitgehend automatisiert geocodiert, also mit geografischen Koordinaten versehen werden. Aber gegen Tippfehler in einer Kartei mit oftmals mehreren tausend Positionen haben natürlich auch sehr engagierte Informatiker kein Rezept.

In einem zweiten Schritt müssen die ortsbezogenen Daten dann miteinander verknüpft werden. "Bei einer Liste mit 10.000 Kunden ergeben sich insgesamt 100 Millionen Einträge", rechnet Keber vor. Denn anders als bei einem Navigationsgerät wollen Tourenplaner nicht nur eine Route von A nach B wissen, sondern sie müssen jeden Zielort mit jedem anderen verbinden. Erstellt wird daher eine Distanzmatrix, die eben nicht auf einfachen Gleichungen beruht. Bereits in dieser Phase lösen komplexere Algorithmen das Problem zu langer Rechenzeiten.

Erst im dritten Schritt der Optimierung kommen dann aber jene Variablen ins Spiel, die Keber als die "klassischen Probleme des Handlungsreisenden" bezeichnet: In welchem Zeitfenster überhaupt geliefert werden darf, muss dabei ebenso berücksichtigt werden wie vermeintlich simpel zu erfüllende Kundenwünsche: etwa dass immer nur ein ganz bestimmter Fahrer kommen soll. "Diese Aspekte sind es, die das Gestalten eines maßgeschneiderten Tourenplaners aus mathematischer Sicht kompliziert machen", sagt Keber.

Aus Fehlern klug werden

Hat die Software also erst einmal registriert, dass etwa Kunde A nur eine Verspätung von maximal fünf Minuten akzeptiert, während Kunde B jederzeit vormittags angesteuert werden darf, bedeutet das wiederum zusätzliche Arbeit für den Informatiker.

Gelöst hat das Team um Keber auch dieses Problem absurd langer Rechenzeiten mit einem mathematischen Kunstgriff - der Methode des sogenannten "simulated annealing". Die Idee dahinter ist, einen Abkühlungsprozess wie er etwa nach dem Erhitzen von Stahl stattfindet, nachzubilden. Im Verlauf dieses Prozesses haben die Atome nämlich relativ viel Zeit sich neu anzuordnen - und sie probieren dabei auch "falsche Lösungen" aus. Umgelegt auf die Mathematik wird mit diesem heuristischen Verfahren in einer Software nun fast dasselbe erreicht: Diese führt also auch nichtzielführende Berechnungen aus, um letztlich deutlich schneller über "Fehler" zu einem besseren Ergebnis zu kommen.

Zusätzlich zu diesem Verfahren entwickeln die Informatiker des Risc aber derzeit noch eine weitere Methode, die sich "agiles Tourenmanagement" nennt. Dabei werden in der Realität gefahrene Routen aufgezeichnet und mit der vom Computer berechneten Tour verglichen. Ziel ist es, auf diese Weise eine "lernende Distanzmatrix" zu erstellen, in die auch notwendige Korrekturen eingearbeitet werden können. Diese relevanten Parameter aus dem Leben eines Handlungsreisenden - sei es nun die Leberkässemmel oder ein besonders schwieriger Kunde - bekommen dann in weiterer Folge bei der Berechnung von Touren die höchste Priorität.

"Benchmark ist für uns noch immer der Mensch, gesteht Keber. "Wirklich gute Disponenten mit automatisierter Planung zu toppen ist nämlich äußerst schwer." Demnach sei die Software letztlich nur eine Hilfe für die mittelmäßigen, besser zu werden. (DER STANDARD, Printausgabe, 16.11.2011)

=> Wissen: Alltag optimieren


Wissen Alltag optimieren

Die Hagenberger Risc Software GmbH wurde 1992 vom österreichischen Mathematiker Bruno Buchberger gegründet. Ihre Wissenschafter verfolgen seitdem das Ziel, Alltagsprobleme aus der Wirtschaft mit zum Teil sehr komplexen Methoden des symbolischen Rechnens und der Informatik zu lösen.

Die Abteilung Logistische Informatik befasst sich dabei mit der Frage, wie die Bereiche Produktion und Transport durch Software unterstützt werden können. Die Entwicklung der automatisierten Tourenplanung wurde bereits vor 15 Jahren begonnen und stellt einen laufenden Prozess dar.

Überdies zählen Entwicklungen für die Verkehrsentlastung, für die verbesserte Verkehrsinformation und für die Computerunterstützung von Warenwirtschaftssystemen zu diesem angewandten Forschungsbereich. Das Ziel ist in allen Fällen ein Ausschöpfen von Optimierungspotenzialen. (saum)

 


Share if you care.