Publikation

Ein Multiagentenansatz zum Lösen von Fleet-Scheduling-Problemen

Klaus Fischer; Darius Schier

DFKI, DFKI Documents (D), Vol. 96-01, 1996.

Zusammenfassung

Verteilte Systeme werden in der Informatik immer wichtiger. Mit der Zunahme an Informationsbedürfnissen in der Gesellschaft steigt auch der Bedarf, schnell auf (möglicherweise physikalisch getrennte) Datenmengen zugreifen zu können. Mit der Notwendigkeit einer ständigen Verfügbarkeit von Systemen werden Fragen der Zuverlässigkeit und Sicherheit immer dringlicher. Der Effizienzzuwachs wird teilweise dadurch erreicht, bestehende Systeme durch modernere und schnellere zu ersetzen. Der eigentliche Gewinn resultiert aber aus der Zuweisung einzelner Teilaufgaben auf verschiedene Komponenten, um so durch nebenläufige Ausführung Zeit zu sparen. Durch entsprechende Organisation solch eines verteilten Systems kann auch erreicht werden, daß bei Ausfall einzelner Komponenten deren Aufgaben durch andere übernommen werden können und so der Grad der Verfügbarkeit des Gesamtsystems erhöht wird. In der Künstlichen Intelligenz (KI) spielt in diesem Zusammenhang vor allem der Aspekt der realitätsbezogenen Modellierung eine Rolle, d.h. die 'intelligente' Anpassung an eine sich ändernde Umwelt. An der DFKI GmbH wird seit 1991 Forschung im Bereich der Multiagentensysteme betrieben. Aspekte dieser Forschungsarbeit umfassen Fragestellungen, wie sich Probleme auf verschiedene Komponenten (Agenten) aufteilen lassen (Organisation), wie diese Agenten zusammen an der Lösung mitwirken können (Interaktion/Kommunikation) und mit welchen Fähigkeiten und Wissen einzelne Agenten ausgestattet sein müssen, um die Lösungsfindung vorantreiben zu können (interne Strukturen). In diesem Bericht wird vor allem der zweite Punkt näher untersucht: wie lassen sich Kooperationsstrukturen zwischen Agenten modellieren und welche Vorteile bietet die Verteiltheit gegenüber konventionellen Architekturen. Als Anwendung wurde die Domäne der Fleet-Scheduling-Probleme gewählt. Das Vehicle-Routing-Problem (VRP) als Standardvertreter einer fast unüberschaubaren Klasse von Fleet-Scheduling-Problemen ist einfach zu formulieren, jedoch schwierig zu lösen. Gegeben ist eine Liste von Kunden mit festen Forderungen, die von einer Fahrzeugflotte mit Kapazitätsbeschränkungen in möglichst optimaler Reihenfolge zu bedienen sind. An der Lösung des Problems sind eine Reihe von unterschiedlichen Sparten interessiert: Operations Research, Mathematik, Informatik und nicht zuletzt unter dem Gesichtspunkt der Wirtschaftlichkeit der 'Verursacher' selbst: die Logistik. Die Aufarbeitung der in der Literatur bekannten Verfahrensweisen zur Lösung von Fleet-Scheduling-Problemen war ein weiterer Schwerpunkt der Arbeit. Die Modellierung als Multiagentensystem, in dem autonom agierende und reagierende Agenten (Fuhrunternehmen, Fahrzeuge) durch Kooperation (Verteilen und Austauschen von Aufträgen) versuchen, ein gemeinsames Ziel (möglichst optimale Lösung des Problems) zu verwirklichen, eröffnet neue Perspektiven. Speziell die Reaktionsfähigkeit auf eine sich ständig ändernde Umwelt ist eine Anforderung, für die in dieser Form bisher in der Literatur kaum Lösungen zu finden sind. Konventionelle Scheduler, die in der Realität zur Anwendung kommen, liefern in aller Regel auf eine Eingabe (sprich Auftragsliste) eine statische Ausgabe (Tourplan). Ändert sich die Auftragslage (beispielsweise durch Forderungen eines neuen Kunden, Staumeldungen oder Belieferungsprobleme) müssen alle bisher geplanten Touren verworfen und vollständig neu berechnet werden. Ist dies nicht möglich, da die Belieferung z.B. schon begonnen hat, muß 'von Hand' weiter geplant werden. Mit dem hier vorgestellten System besteht die Möglichkeit, an bestehenden Plänen festzuhalten und diese, soweit es Zeitrestriktionen und Ladekapazitäten zulassen, zu modifizieren. Es können prinzipiell sogar Kunden zwischen einzelnen Fahrzeugen während der Ausführung des Tourplans ausgetauscht werden, um so die Gesamtqualität erheblich zu verbessern und letztendlich aus betriebswirschaftlicher Sicht Kosten zu minimieren. Vergleiche mit bekannten Lösungen aus der Literatur werden ebenso angestellt wie Perspektiven aufgezeigt, inwiefern das System erweiterbar ist. So erlaubt beispielsweise die Strukturierung des Multiagentensystems eine physikalische Verteilung der einzelnen Agenten auf verschiedene Systeme. Auch dies ist ein weiterer Schritt in Richtung realitätsbezogene Modellierung, wobei jedes Fahrzeug als lokale Planungseinheit angesehen werden kann. Innerhalb dieser Einheit lassen sich wiederum aus der KI bekannte Standardverfahren einsetzen, um jede einzelne Tour und somit den Gesamtplan aller Agenten zu verbessern. Gliederung In Kapitel 2 werden theoretische Vorüberlegungen angestellt und Grundlagen geschaffen, die zum Verständnis der Gesamtproblematik und Einordnung des Problems in größerem Kontext notwendig sind. Das Problem selbst wird in Kapitel 3 charakterisiert und aus der Literatur bekannte Lösungsansätze in Kapitel 4 aufgezeigt. Der Hauptteil der Arbeit ist in den Kapiteln 5 und 6 zu finden. Hier wird das Speditionsszenario und dessen Arbeitsweise vorgestellt, sowie Vergleiche der Qualität der Lösungen mit aus der Literatur bekannten Verfahren angestellt. In Kapitel 7 wird aufgezeigt, inwieweit das System erweiterbar ist und wo Ansätze zur Verbesserung bestehen. Im Anhang wird detailliert auf die Implementierung in der Programmiersprache Oz eingegangen.