Deep-Dive: Markov-Ketten – Modellierung Sortieranlagen

Sortieranlagen finden in zahlreichen Wirtschaftszweigen Anwendung. Versandunternehmen setzen Sortieranlagen ein, um Pakete nach Zielorten oder Versandmethoden zu klassifizieren. Im Tagebau ermöglichen sie die Trennung des geförderten Rohstoffs vom Rest. In der Lebensmittelindustrie dienen sie dazu, die Ernte separieren oder einzelne Produkte nach Größe, Gewicht und weiteren Kriterien zu kategorisieren. Auch im Recycling spielen Sortieranlage eine zentrale Rolle bei der Trennung von Stoffströmen in verschiedene Materialien.

In den zuvor genannten Szenarien wird die Sortierung automatisiert, um im Vergleich zur manuellen Sortierung den Ertrag in mindestens einer der folgenden Dimensionen zu steigern:

1. Zeit: Die automatische Sortierung ist schneller als die manuelle Sortierung, da die Maschinen die zu sortierenden Teile schneller erfassen können,
2. Qualität: Die automatische Sortierung ist genauer als die manuelle Sortierung, da die Maschinen die zu sortierenden Teile mit höherer Genauigkeit erfassen können,
3. Kosten: Die automatische Sortierung ist günstiger als die manuelle Sortierung, da die Maschinen im laufenden Betrieb weniger Kosten verursachen als menschliche Arbeitskräfte,
4. Gesundheit: Maschinen sind unempfindlicher gegenüber giftigen oder gesundheitsschädlichen Stoffen, während bei menschlichem Kontakt teils strenge Auflagen zu erfüllen sind,
5. Wiederholbarkeit: Maschinen operieren auf Basis eines fest definierten Regelsatzes und treffen unter gleichen Bedingungen stets identische Entscheidungen, während menschliches Handeln variabel ist; unterschiedliche Personen sowie dieselbe Person können in verschiedenen Situationen unterschiedliche Entscheidungen treffen.

Trotz des Aspekts der Wiederholbarkeit stellt sich bei der Verkettung von Sortiermaschinen die Frage, wie diese zusammenspielen und welchen Einfluss die voran geschaltete Sortierung auf einzelne Sortiermaschinen hat. Daher braucht es Modelle, mit denen sich die Funktionsweise kaskadierend angeordneter Sortiermaschinen abbilden lässt und mit deren Hilfe man in Echtzeit überwachen kann, ob die Anlage die vorgeschriebene Wirkungsweise einhält.

Eine Möglichkeit zur Modellierung von Stoffströmen in Sortieranlagen besteht in der Anwendung sogenannter Markov-Ketten. Diese Ketten setzen sich aus einer Menge an Zuständen – in diesem Kontext die Sortierer – und einer Menge von Übergängen – den Förderbändern, die Sortierer verbinden – zusammen. Die für Markov-Ketten grundlegende Markov-Eigenschaft besagt, dass für die Verteilung eines Zustandes lediglich die Verteilung des direkten vorangehenden Zustandes von Interesse ist, alle anderen Zustände davor können unberücksichtigt bleiben. Intuitiverweise ist diese Eigenschaft auf Sortieranlagen anwendbar, da im jeweiligen Sortierer ausschließlich Material aus dem direkt vorangegangenen Sortierer verarbeitet wird. Der Begriff „Kette“ in „Markov-Kette“ unterstreicht die Markov-Eigenschaft zusätzlich, da wie bei der Herstellung einer Kette stets nur das vorangegangene Kettenglied von Bedeutung ist; was davor kommt, spielt keine Rolle (außer beim Verschließen der Kette).

Für die nachfolgenden Erläuterungen ist es wichtig zu verstehen, dass Markov-Ketten zwar als Grundlage dienen, jedoch in abgewandelter Form verwendet werden. Auf Unterschiede zum klassischen Ansatz wird an gegebener Stelle hingewiesen.

Um Markov-Ketten mathematisch auszudrücken, wird eine Übergangsmatrix verwendet. Jede Zeile und jede Spalte repräsentiert einen Zustand, sodass die Matrix von der Dimension Anzahl der Zustände x Anzahl der Zustände ist. Die Zeilen drücken den „Von-Zustand“ aus, also den Zustand, von dem das Material kommt und die Spalten drücken den „Nach-Zustand“ aus, also den Zustand, zu dem das Material fließt. In klassischen Markov-Ketten drücken die Einträge der Matrix die Wahrscheinlichkeiten aus, mit denen das Material von Zustand A nach Zustand B fließt; dieser Prozess erfolgt vollständig oder gar nicht. In der hier betrachteten Modellierungsform stellend die Einträge jedoch Anteile dar, mit denen das Material von Zustand A zu allen verbundenen Zuständen übergeht. Die für Markov-Ketten geltende Eigenschaft, dass sich die Wahrscheinlichkeiten in jeder Zeile zu 1 (also 100 %) aufsummieren, überträgt sich auf die Anteile, da sich das Material von Zustand A zu 100 % auf alle verbundenen Zustände aufteilt.

Abbildung 1 zeigt eine beispielhafte Markov-Kette, die vier Sortierer A, B, C und D (in Blau) und fünf Endzustände, bspw. Material-Bunker, 1, 2, 3, 4 und 5 (in Orange) umfasst. Die Endzustände unterscheiden sich von den Sortierern dadurch, dass alle Materialien, die Endzustände gelangen, dort verbleiben, schließlich weisen diese keine ausgehenden Kanten auf. Im Gegensatz dazu fließt das Material in jedem Schritt durch die Sortierer hindurch, ohne darin zu verweilen. In der Übergangsmatrix drückt sich dies folgendermaßen aus:

Die resultierende Matrix ist eine obere Dreiecksmatrix, wobei für Sortierer Nullen auf der Diagonalen stehen, da das Material durch sie hindurchfließt, während für Endzustände Einsen auf der Diagonalen stehen, da diese das Material speichern. Die Variablen  und  repräsentieren hierbei die Anteile zwischen 0 und 1 für den Übergang von Zustand A, B, C oder D zum Zustand der durch die entsprechende Spalte in der Matrix dargestellt ist. Die Eigenschaft der Zeilensumme von 1 ist hierbei direkt ersichtlich. Zwei weitere Eigenschaften obiger Übergangsmatrix sind (1) es gibt stets maximal zwei Einträge ungleich Null pro Zeile und (2) für Sortierer existiert höchstens ein Eintrag ungleich Null pro Spalte, für Endzustände existieren zwei Einträge ungleich Null pro Spalte. Diese Eigenschaften ergeben sich dadurch, dass in dem angegebenen Fall jeder Zustand nur einen Eingang und zwei Ausgänge hat. Dies ist in der Praxis durchaus häufig anzutreffen, da viele Sortierer darauf ausgelegt sind nach bestimmten Materialien oder Eigenschaften zu selektieren. Alles, was das Kriterium erfüllt, wird auf ein Förderband sortiert, während der Rest auf ein anderes Förderband geleitet wird. Theoretisch lässt sich eine Sortierung nach mehr als zwei Materialien oder Eigenschaften mathematisch so umformen, dass sie wieder auf eine binäre Sortierung reduziert wird. Praktisch würde diese Situation aber durch mehr als zwei Einträge ungleich Null pro Zeile in der Übergangsmatrix aufgelöst werden.

Mittels der Übergangsmatrix, diese sei im Folgenden als  definiert, kann für gegebene Menge ermittelt werden, mit welchem Anteil dieser Mengen im nächsten Schritt an den Folgezuständen zu rechnen ist. Hierzu wird ein Zeilenvektor  mit je einem Eintrag für jeden Zustand (gleiche Reihenfolge der Zustände wie in ) erstellt, welcher die Menge des Materials zum Zeitpunkt  an den Zuständen angibt, und  gebildet. Hierbei gibt  die geschätzte Aufteilung des Materials von Zeitpunkt  zum Zeitpunkt  an. Soll die Menge für mehr als einen Schritt vorhergesagt werden, erfolgt eine Potenzierung von  entsprechend der Anzahl an Schritten. Möchte man also beispielsweise wissen, wie viel Menge drei Schritte später in den Zuständen noch verbleibt, so bildet man . Im angegebenen Beispiel wird die Menge komplett auf die Endzustände aufgeteilt sein, da alle Materialien nach spätestens drei Schritten in den Endzuständen angekommen sind.

Um nicht nur einen Querschnitt des Materials über die Zeit zu betrachten sondern auch das Verhalten der Menge an den verschiedenen Zuständen der Anlage zeitlich zu modellieren, muss  durch die zum Zeitpunkt  hinzugekommene Menge an Zustand A erweitert werden. Dies ist durch  zu bewerkstelligen, wobei  den Vektor angibt, welcher an der Stelle für Zustand A die hinzugekommene Menge an Zustand A zum Zeitpunkt  und sonst Nullen enthält. Der Vektor  wird dann erneut mit  multipliziert und  auf das Ergebnis addiert. Dieses Vorgehen kann nun iterativ durchgeführt werden. Somit wird stets die hinzugekommene Menge berücksichtigt.

Um obige Berechnungen konkret ausführen zu können, müssen vorher die Anteile  und  bestimmt werden. Wie für andere Modelle, stellen die Anteile Parameter dar und können daher beispielsweise mit einer Gittersuche optimiert werden. Dafür wird ein Gitter aus äquidistant Punkten im Intervall  erstellt. Für jeden Punkt dieses Gitters erfolgt dann eine Multiplikation des Punktes mit der Zeitreihe von Zustand X. Die erhaltene, skalierte Zeitreihe wird dann in einer zuvor definierten Metrik (z.B. Root Mean Square Error) mit der Zeitreihe des darauffolgenden Zustands Y verglichen. In der Berechnung von  aus Abbildung 1 entspräche Zustand A dem vorangehenden Zustand X und Zustand B dem nachfolgenden Zustand Y. Der optimale Anteil ist der Punkt des Gitters mit dem niedrigsten Wert der Vergleichsmetrik. Bei dem vorliegenden Anwendungsfall handelt es sich um ein auf  beschränktes, konvexes Optimierungsproblem, welches folglich ein eindeutiges, globales Minimum besitzt. Dieses Minimum lässt sich durch ein hinreichend feines Gitter ausreichend genau abschätzen, wenngleich natürlich auch andere Optimierungstechniken verwendet werden können.

Die Anwendung von Markov-Ketten liefert eine intuitive Darstellung einer Sortieranlage, die zugleich eine hohe Interpretierbarkeit ermöglicht. Trotz ihrer relativ einfachen Struktur, kann die Anwendung der Methode eine Verbesserung darstellen, insbesondere, wenn bislang keine Modellierung der Anlage stattgefunden hat. Durch Multiplikation der entsprechenden Anteile lassen sich bereits bei Befüllung des Materials in die Anlage Vorhersagen machen, wie sich dieses Material auf die verschiedenen Endzustände aufteilt. Außerdem lässt sich so untersuchen, ob bestimmte Pfade der Anlage besonders gut oder schlecht funktionieren und durch Vergleich mit dem Ist-Zustand der Anlage wird eine Anomalieerkennung ermöglicht.

Auf der anderen Seite bringt die simple Struktur der Methode einige Limitationen mit sich. Erstens funktioniert die Methode nur dann robust, wenn die Zeitreihen an den verschiedenen Sortierern ähnliche Muster aufweisen. Andernfalls sind sehr häufige Neuschätzungen der Anteile notwendig. Außerdem dürfen die Anteile selbst nicht zu volatil sein, da die Schätzungen nicht für den Zeitraum verwendet werden können auf dem sie berechnet wurden, schließlich muss der Berechnungszeitraum bereits abgeschlossen sein, damit die Werte für die Berechnungen verfügbar sind. Für die Vorhersagen müssen also stets Proportionen auf vergangenen Zeiträumen verwendet werden. Darüber hinaus müssen sich die Proportionen in einer Ebene des Diagramms stets zu 1 aufsummieren (oder zumindest sehr nahe daran liegen), ansonsten gibt es systematische Fehler im Modell die schwerwiegender werden je größer die Differenz zwischen der echten Summe und 1 ist. Sind die Unterschiede jedoch tatsächlich systematisch, lässt sich das Modell erweitern, um die Funktionsweise wiederherzustellen.

Insgesamt lässt sich also sagen, dass, sofern die Einschränkungen berücksichtigt werden, die Modellierung einer Sortieranlage mit Markov-Ketten einen durchaus vielversprechenden Ansatz liefert.

---