Manuskipt zum Vortag auf den Dortmunder Gesprächen  1991

Künstliche Neuronale Netze zur Optimierung der Tourplanung in der Kommissionierung

R. Jünemann+, M. Wölker*

+   Leiter des Fraunhofer-Instituts für Materialfluß und Logistik IML
Emil-Figge-Str. 75, 4600 Dortmund 50, FRG und
Inhaber des Lehrstuhls für Förder- und Lagerwesen, Universität Dortmund

*   Universität Dortmund, Lehrstuhl für Förder- und Lagerwesen
Emil-Figge-Str. 73, 4600 Dortmund 50, FRG

Abstract

Ausgehend von einer Betrachtung der technischen und wirtschaftlichen Entwicklung soll im fol­genden Beitrag gezeigt werden, daß zur Bewältigung logistischer Aufgabenstellungen traditio­nelle Lösungskonzepte nicht mehr ausreichend sind. Aus zunehmend notwendiger holistischer Systemsicht folgen Methoden, die nicht mehr deterministische, sondern heuristische Konzepte zur Problemlösung einsetzen. Am Beispiel der Tourenplanung von Kommissionierfahrten in einer Regallagergasse mittels Künstlicher Neuronaler Netze wird die Realisierbarkeit solcher Konzepte demonstriert.

Einleitung

Tour, dynamisch berechnet mit einer
eindimensionalen Kohonenkarte

Automatische Materialflußsysteme bilden das Rückgrat heutiger logistischer Konzepte. Eine stetig wachsende Zahl von Systemen wird in immer komplexere Umgebungen und Zusammen­hänge eingebunden, weil der Wandel der Marktstrukturen weg vom Verkäufermarkt hin zum Käufermarkt dies notwendig machen. Logistische Konzepte erhalten somit ein immer größeres Gewicht, da mit steigender Komplexität das System (Bild 1) zum einen eine größere Breite und zum anderen auch eine größere Tiefe aufweist. D.h. die Systeme werden weitreichender und erfassen sowohl innerbetrieblich als auch außerbetrieblich mehr Bereiche. Zudem werden detail­liertere Strukturen berücksichtigt und beeinflußt. Jedes System entwickelt sich auch ohne direk­ten Eingriff weiter, da es eine Eigendynamik beinhaltet. Weil zusätzlich auch nichttechnische Faktoren berücksichtigt werden müssen, ist i. allg. nicht jede Beziehung bekannt oder läßt sich als kausale Verknüpfung darstellen.

Experten stoßen schnell an ihre Grenzen, da die hohe Zahl der Eingangsvariablen, Ausgangs­werte und deren Verflechtung eine Gesamtsicht des Systems nicht mehr zuläßt (kombinatorische Explosion). Ferner muß der Subjektivität eines menschlichen Experten Rechnung getragen wer­den [Dör 89]. Für jede Modellbildung und die daraus folgende Konzeptionierung in allen Ebenen [Jün 89] muß dieser hohe Komplexitätsgrad berücksichtigt werden (Bild 2) Da somit die verschiedenen Systemparameter nicht unabhängig voneinander existieren sondern sich gegen­seitig beeinflussen, müssen nicht konventionelle Lösungswege gesucht werden. Von einer mechanistischen gelangt man so zu einer holistischen Systemsicht. Es ist daher notwendig, computergestütze Datenverarbeitungssysteme einzusetzen.

Logistische Aufgabenstellungen (bei vollständiger Information über das System) können im wesentlichen in drei Problemklassen eingeteilt werden [Jün 89,Dom 90]:                 

• Tourenplanung- (TPP),
• Handlungsreisenden- (Travelling Salesman Problem, TSP),
• Distribution mit Standort, Stufen, Anzahl, Zuordnung .

Solche Probleme können mit verschiedenen Methoden berechnet werden. Klassisch sind deterministische Verfahren, bei denen das Problem zerlegt (top down) und die einzel­nen Schritte in einem Computerprogramm algorithmisiert werden. Die oben beschrie­benen Standardprobleme gehören zur Klasse der schwer lösbaren Probleme (d.h. NP-vollständig) und sind daher nur für kleine Instanzen deterministisch exakt lös­bar. Man kann die Leistungen von bekann­ten Algorithmen stark verbessern, wenn heuristische (Textkasten) Eröffnungs- bzw. Verbesserungs­verfahren eingeführt werden. Dabei nimmt man allerdings in Kauf, daß anstatt die optimale Lösung zu berechnen ein Suboptimum möglichst nahe am Optimum gefunden wird.

Heuristik

bedeutet etwa die "Kunst des Entdeckens". Die Heuristik macht Gebrauch von unscharfem Wissen (Daumenregeln, Faustformeln), das im allgemeinen die Effizienz eines Systems bei Problemlösungen verbessert. Problem- oder domänenspezifisches heuristisches Wissen fließt dann in Systeme ein, wenn exakte (algorithmische) Verfahren nicht bekannt oder zu aufwendig sind. Heuristik wird zur Problem­lösung wesentlich in wissensbasierten und neuronalen Systemen eingesetzt [Kai 89].

Außer diesem klassischen Ansatz werden in zunehmendem Maß Konzepte aus der KI-Forschung eingesetzt, deren Vorgehen sich an men­schlichen Aspekten intelligenten Verhaltens orientiert. Dieses Vorgehen ist wegen der Schwere der Problemklasse (NP-schwer) notwendig. Auch für Probleme mit unvollständiger Information (Tabelle 1). Heuristische Verfahren gehen von zwei unterschiedlichen Standpunkten aus. Einerseits werden wissensbasierte Systeme geschaffen, die nicht die Inhalte von bedeutungsfreien Variablen verarbeiten, sondern Symbole mit semantischer Bedeutung manipulieren. Sie verwenden dazu Wissen, das in einer Datenbasis vorher angelegt wird.

Andererseits wird die Beziehung einzelner einfacher Komponenten untereinander betont, so daß das Wissen implizit in den Relationen bzw. Verbindungen der einzelnen Komponenten untereinander vorhanden ist. Diese beiden Sichtweisen spiegeln den unterschiedlichen Zugang zur Informationsverarbeitung "Symbolismus vs. Konnektionismus" wieder.

Mit allen drei Konzepten (klassisch, symbolistisch, konnektionistisch) wurden und werden Softwaremaschinen entwickelt. Für jeden Einzel­fall ist ein bestimmtes Verfahren unterschiedlich gut geeignet. Weil die Entwicklungzeiten ein­zelner Softwareprojekte schon bei kleinen Problemen mehrere Mannjahre umfassen, muß eine sorgfältige Wahl getroffen werden, weil spätere Korrekturen nicht möglich oder immens auf­wendig sind. Die größten Zukunftsaussichten haben Hybridsysteme, die die Stärken der verschiedenen Konzepte nutzen und deren Schwächen umgehen (Synergie).

Beispiel Kommissionierung

In diesem Artikel können die ein­zelnen Aspekte der unterschiedlichen Ansätze nur unvollständig herausgearbeitet werden, insbesondere unter Berücksichtigung, daß dies Gegenstand aktueller Informatikforschung ist. Daher soll der Einsatz eines "intelligenten" Systems an einem Beispiel demonstriert werden.

In einem Hochregallagersystem müssen bei der Kommissionierung mit einem RFZ unter­schiedliche Positionen angefahren werden. Ziel einer Optimierung muß es sein, die optimale d.h. kürzeste Tour zu berechnen. Bei wenigen Posi­tionen kann die optimale Tour determi­nistisch berechnet werden. Aber schon Größenordnungen von 10 Positionen führen zu Rechenzeiten, die einen praktischen Einsatz verhindern. Im Folgenden wird die Größe des Problems, hier die Anzahl der anzufahrenden Positionen, mit Instanz bezeichnet.

Da in heutigen realen Lagern oftmals bis zu 50 Posi­tionen angefahren werden müssen (Kleinteile­lager), ist am FLW ein heuristi­scher Ansatz basierend auf Künstlichen Neu­ronalen Netzen (Artificial Neuronal Networks ANN, siehe folgende Seite) im Hinblick auf seine Praxi­stauglichkeit unter­sucht worden [Sch 91].

Just-In-Time und Tour-Optimierung

Die käuferorientierte Entwicklung des Marktes führt zum Just In Time (JIT) Konzept. JIT bewirkt ein verändertes Dispositionsverhalten der Käufer aufgrund einer neuen Lagerstruk­tur. Bei größerer Liefertreue und kürzerer Reaktion­szeit werden geringere Mengen mit größerer Sortenvielfalt geordert. Dies erzwingt eine Optimierung der Kommissionierverfahren (Bild 4) des Zulieferers. Diese Optimierung kann durch eine Verbesserung der Tourenplanung im Lagersystem realisiert werden.

Künstliche neuronale Netze (ANN)

Eine Nervenzelle (Neuron) kann als ein elemen­tarer Logikbaustein eines abstrakten Computers verstanden werden, der zu einer Schwellwertoperation fähig ist. Es mag erstaunen, daß die ersten Forschungsansätze schon 1943 von McCulloch und Pitts in ihrer Arbeit "A logical calculus of the ideas immanent in nervous activity" ver­öf­fentlicht wurden.

Über die stark verästelten Den­dri­ten empfängt das Neu­ron Signale, die es unterschied­lich stark erre­gen. Die meisten neurona­len Modelle unter­scheiden dabei exitato­ri­sche (erregende) und inhibitori­sche (hemmende) Kopplungen. Überschreitet die Erre­gungsstärke einen Schwellenwert, so geht das Neu­ron in den aktiven Zu­stand über, es "feuert". Im neu­ronalen Modell wird dies durch Summation der Wich­tungsfaktoren aller Verbindun­gen mit folgen­dem Schwellwertschalter realisiert. Jedes Neuron übermittelt über das Axon seinen Zustand allen anderen mit ihm ver­bun­denen Neuro­nen [Pal 88, Gei 89, Law 90].

Orientiert an die­sem biologischen Vorbild werden mehrere Elemen­tarbausteine miteinander ver­bunden. Im neuro­na­len Modell werden dann in Zeitschritten die aktuellen Zustände der Neuro­nen aus den jewei­ligen Ein­gangssignalen berech­net.

Das ANN muß für seine Aufgabe trainiert werden. D.h. die Wichtungsfaktoren der einzel­nen Verbin­dun­gen müssen so angepaßt werden, daß bei defi­nier­ten Eingangssignalen die richtigen Ausgangs­signale erzielt werden. ANN werden nach kon­trolliertem Lernen, was nur mög­lich ist, wenn die "richtige" Lösung eines Problems bereits bekannt ist, und nach selbsständigem Lernen unterschieden. Das Modell formaler Neuronen ent­spricht somit nicht exakt menschli­chen Neuronen, son­dern bildet Teil­funktionen nach. Aus diesen all­gemeinen Über­legungen lassen sich eine Vielzahl von ANNs ablei­ten, die sich in Topologie, Lern­strategie und Akti­vierungsfunk­tion stark unter­scheiden. Allen ANN ist gemeinsam, daß sie nach Ein­gabe eines Musters nach einiger Zeit in einem stabilen Zustand enden, der das Ergebnis darstellt.

Einordnung des Travelling Salesman Problems

Das allgemeine TSP gehört zu Klasse der NP-schweren Probleme. Wir betrachten hier die Ein­schrän­kung auf ein ebenes, euklidisches, symmetri­sches TSP, trotz­ der Einschränkung bleibt das TSP NP-schweer. Die reale Kosten­matrix kann hier als Entfernungsmatrix genä­hert werden, da bei den Fahrten zwischen den Haltepositionen in der Regel beide Achsen gleichzeitig bewegt werden kön­nen, daß die Kosten unabhängig von der Fahrtrichtung sind und die Beschleunigung so groß ist, daß eine lange Zeit mit gleichblei­bender Geschwindig­keit gefahren werden kann.

Inhalt der Arbeit ist es, ein Ver­fahren zu schaffen, das eine gute sub­optimale Tour (Bild 4) für ein spezielles TSP berechnet. Dabei sollen die einer Praxistauglichkeit entge­genste­henden Probleme wie Konvergenz, Qualität, Streuung, Rechenzeit bei ANNs überwunden werden, so daß man in annehmba­ren Zeiten (ca. 19 min) sicher ein gleichbleibend gutes Ergebnis er­zielt. Das Interesse liegt nicht in der Funktionsweise des ANNs selbst - womit sich die Grundla­genforschung in diesem Sektor beschäftigt - sondern in der konkreten Anwen­dung.

Im vorliegenden Fall wird auf Workstations SICOMP WS-30 ein ANN als Kohonen Typ einer selbstorganisierenden, ringför­migen Karte implementiert (Bezeichnung: RANDOM). Die Leistungsfähigkeit von RANDOM wird anschließend im Vergleich mit bekannten deter­mini­stischen (NEAREST, ALLNEAREST, HAMILTON) und heuristischen (SELFORG, TWOOLOOP) Ver­fahren untersucht. Aufgrund der z. T. heuristischen Natur der Verfahren ist eine Beurteilung nur statistisch möglich. Von den Instanzen 10, 30, 50, 100 wurden hierfür jeweils 1000 Probleme auf einer 100x20 Lagermatrix erzeugt und mit den genannten Verfah­ren berechnet.

Hier werden die mittleren Tour­län­gen L und die mittleren Standardabwei­chungen s relativ zum neuen Verfahren RANDOM verglichen. Die Qualität des heuri­sti­schen Ansatzes wird offensichtlich. Bei sehr kleinen Instanzen liegt RANDOM, ebenso wie sein Vorgänger SELFORG nur 2,6% schlech­ter als die opti­male Lösung (HAMILTON). 

Für höhere Instanzen sind beide selbstorganisie­ren­den Heuristiken (SELFORG, RANDOM) deut­lich besser als die anderen Verfahren, wobei HAMILTON aufgrund der Rechenzeit nicht angewendet werden kann. Das Vorgänger-Modell SELFORG erzeugt etwas längere Tou­ren als RANDOM. 

Zur Beurteilung der Güte muß die Standardabweichung bei der Tourbe­rechnung herangezogen werden. Offen­sichtlich sind hier signifikante Verbesse­run­gen feststell­bar. RANDOM liefert nicht nur kürzere Touren, sondern diese zusätzlich mit einer geringeren Streuung auch gegenüber dem Vor­gänger SELFORG. 

Mit der Stich­probe von 1000 Problemen wurde ein c2-Test für eine Gaußverteilung der heuristisch berechneten Tourlängen vorgenommen (TWOLOOP, SELFORG, RANDOM), der die Verbesserun­gen durch das neue Verfahren bestätigt. Dies wurde nun auf das von Padberg und Rinaldi gelöste 532 Städte-Problem ange­wendet, bei dem die optimale Tour durch 532 Städte der USA mit einer Länge von 27.686 arbitrary units berechnet wurde.

 Der Algorithmus RANDOM erarbeitet eine 3,9% ungünstigere Tour. Somit zeigt sich, daß die be­rechneten suboptimalen Lösungen im Mittel über alle Instanzen um ca. 3% vom Optimum abwei­chen. Dies ist ein sehr gutes Ergebnis, da für die optimale 532 Städte Lösung ca. 6 h auf einem Supercomputer vom Typ CYBER 205 angegeben wurden, wohinge­gen RANDOM auf SICOMP WS-30 nur ca. 2,25 h benötigt.

Die hier eingeführte Heuristik berechnet somit sehr gute Ergebnisse in einem großen Instanzenbereich. Für eine technische Anwendung ist außerdem eine geringe Streuung der Ergebnisse von Bedeutung. Daraus läßt sich schließen, daß berechnete Touren fast nie sehr schlecht sind. Ein weiterer Hindernisgrund für den Einsatz von heuristischen Verfa­hren bildet die schlechte Vorhersehbarkeit der Rechenzeit aufgrund des heuristischen Konzepts. 

RANDOM behebt dieses Problem, da es sowohl schneller als auch sicher konvergiert im Ver­gleich zum guten Vorgänger SELFORG, der bei einigen Problemen sogar zu Oszillationen neigt. Somit wer­den in RANDOM die Vorteile eines heuristischen Verfahrens gewonnen und die damit sonst einhergehenden Nachteile weitestgehend vermieden.

Zusammenfassung und Ausblick

Rückblickend gesehen wurde auf die stetige Komplexitätssteigerung bisher mit immer aufwen­digeren und somit fehlerhaften Softwaremaschinen reagiert. Viele der heutigen Problemklassen können so nicht mehr gelöst werden, was zu neuen heuristischen Konzepten zwingt. Man ver­zichtet dabei auf eine exakte Lösung, um in kurzer Zeit eine (sehr) gute Lösung zu erreichen. Expertensysteme und Neuronale Netze werden in Zukunft einen immer breiteren Raum der Softwareerstellung ein­nehmen. Damit sind die traditionellen Systeme aber nicht überholt, son­dern werden in Gesamt­systeme integriert werden müssen. Ein Beispiel dafür mag dies illustrie­ren: In Expertensystemen werden bereits ansatzweise ANNs integriert, die mit ihrer Stärke zur Assoziation aus Beispielfällen neue Regeln extrahieren. Außerdem sind die Wissensbasen vieler Expertensysteme so umfangreich geworden, daß die Verwaltung dieses Wissen von unterlager­ten traditionellen Datenbanksyste­men übernommen wird.

Am konkreten Beispiel der Kommissionierfahrten in Hochregallagergassen konnte gezeigt wer­den, daß die Schwächen eines neuronalen Netzes beseitigt werden können. Es wurde ein Netz geschaf­fen, das sehr gute Lösungen in kurzer Zeit für einen großen Instanzenbereich berechnet. Da zusätzlich eine geringe Streuung erreicht wurde, ist die Praxistauglichkeit solcher selbstorgani­sie­renden Netze evident. Als weiteres Vorgehen sollte hier die Kostenmatrix weiterentwickelt werden (z.B. Einbeziehung von Massen, Beschleunigungszeiten).

Es ist absehbar, daß für die Zukunft Applikationen unterschiedlicher Netztypen realisierbar wer­den. Dies gilt um so mehr, da ANNs im hohen Grade parallele Verarbeitung erlauben. Weit verbreitet sind daher zur Zeit Transputernetzwerke in der ANN-Simulation. Einen relevanten praktischen Vorteil dieser Lösungen bildet die Verfügbarkeit von Datenerfassungskarten, die großen Datendurchsatz (Real-Time-Videoprozessing) in das Transputernetz haben. Da auf dem Markt auch bereits spezielle Neuro‑Prozessoren vorhanden sind, können in Zukunft nicht nur Geschwindigkeitsvor­teile son­dern auch reduzierte Kosten und höhere Zuverlässigkeit erwartet werden.

Zur Zeit wird am FLW für einen neuen automatischen Kran ein neuartiges Steuerungskonzept erarbei­tet, bei dem das Pendeln der Last mit einem selbstlernenden Neuronalen Netz kontrolliert werden soll. Dieses Projekt soll in Zusammenarbeit mit Dr. Sitte von der Queensland University of Technology/ Faculty of Information Technology in Bris­bane/Australien realisiert werden, der am inversen Problem (Balancieren eine Besenstiels) mittels neuronaler Steuerung eines Roboter­arms bereits aktiv forscht. In diesem Projekt sehen wir überdies wissenschaftlich interessante Zusammenhänge mit aktuellen Fuzzy-Logic-Steuerungs­konzepten.

Die Vielzahl nichtklassischer Konzepte ist aus dem reinen (Grundlagen-)Forschungsbereich her­aus in die ersten Anwendungen getreten. Stellen heutige Applikationen auch nur in eng definier­ten Umgebungen ihre Leistungen unter Beweis, so ist doch abzusehen, daß diese Methoden immer breiteren Eingang finden werden. Schon heute sind die Synergie-Effekte bei hybriden Systemen offensichtlich.

Quellen

IAO-Forum         Expertensysteme in Produktion und Engineering
Springer, Berlin, T 23, April, 1991

Schäfer, G.          Beitrag zur Optimierung von Kommissionierfahrten in Hochregallager-gassen mittels neuronaler Netze,  Universität Dortmund, MB - FLW, 1991

Geiger, H.            Neuronale Netze
Elektronik, 21/23/25, 1990; 2, 1991

Domschke, W.     Logistik: Rundreisen und Touren
Oldenbourg, München, 3. Auflage, 1990

Lawrence, J.        Untangling, Neuronal Nets
Dr. Dobb´s Journal, April, 1990

Jünemann, R.       Materialfluß und Logistik
Springer, Berlin, 1989

Dörner, H.           Die Logik des Misslingens
Rowohlt, Hamburg, 1989

Kaindl, H.            Problemlösen durch heuristische Suche in der Artificial Intelligence
Springer Wien, 1989

Palm, G.              Assoziatives Gedächtnis und Gehirntheorie
Spektrum der Wissenschaft, Juni, 1988