Der Artikel beschreibt die Umsetzung WMS-System standen wir vor der Notwendigkeit, ein nicht standardmäßiges Clustering-Problem zu lösen und welche Algorithmen wir zu seiner Lösung verwendeten. Wir erzählen Ihnen, wie wir das Problem systematisch und wissenschaftlich angegangen sind, auf welche Schwierigkeiten wir gestoßen sind und welche Erkenntnisse wir daraus gezogen haben.
Mit dieser Veröffentlichung beginnt eine Artikelserie, in der wir unsere erfolgreichen Erfahrungen bei der Implementierung von Optimierungsalgorithmen in Lagerprozessen teilen. Der Zweck der Artikelserie besteht darin, das Publikum mit den Arten von Optimierungsproblemen des Lagerbetriebs vertraut zu machen, die in fast jedem mittleren und großen Lager auftreten, sowie über unsere Erfahrungen bei der Lösung solcher Probleme und die dabei auftretenden Fallstricke zu berichten . Die Artikel werden für diejenigen nützlich sein, die in der Lagerlogistikbranche arbeiten WMS-Systeme sowie Programmierer, die sich für Anwendungen der Mathematik in der Wirtschaft und die Optimierung von Prozessen in einem Unternehmen interessieren.
Engpass in den Prozessen
Im Jahr 2018 haben wir ein Projekt zur Umsetzung abgeschlossen WMS-Systeme im Lager der Firma „Handelshaus „LD“ in Tscheljabinsk. Wir haben das Produkt „1C-Logistics: Warehouse Management 3“ für 20 Arbeitsplätze: Bediener implementiert WMS, Lagerhalter, Gabelstaplerfahrer. Das durchschnittliche Lager ist etwa 4 m2 groß, die Anzahl der Zellen beträgt 5000 und die Anzahl der Artikel beträgt 4500. Das Lager lagert Kugelhähne aus eigener Produktion in verschiedenen Größen von 1 kg bis 400 kg. Der Lagerbestand wird in Chargen gelagert, da die Warenauswahl nach FIFO erfolgen muss.
Bei der Entwicklung von Systemen zur Automatisierung von Lagerprozessen standen wir vor dem bestehenden Problem einer nicht optimalen Lagerhaltung. Die Besonderheiten von Lager- und Staukränen bestehen darin, dass eine Einheitslagerzelle nur Artikel aus einer Charge enthalten kann. Die Produkte kommen täglich im Lager an und bei jedem Eingang handelt es sich um eine separate Charge. Insgesamt entstehen in einem Monat Lagerbetrieb 1 separate Chargen, obwohl jede in einer separaten Zelle gelagert werden sollte. Produkte werden oft nicht in ganzen Paletten, sondern in Stücken ausgewählt, und als Ergebnis ist in der Stückauswahlzone in vielen Zellen das folgende Bild zu beobachten: In einer Zelle mit einem Volumen von mehr als 30 m1 gibt es mehrere Kräne, die nehmen weniger als 3-5 % des Zellvolumens ein.
Abb. 1. Foto mehrerer Warenstücke in einer Zelle
Es ist klar, dass die Lagerkapazität nicht optimal genutzt wird. Um sich das Ausmaß der Katastrophe vorzustellen, kann ich Zahlen nennen: Im Durchschnitt gibt es zwischen 1 und 3 solcher Zellen mit einem Volumen von mehr als 100 m300 mit „winzigen“ Salden während verschiedener Betriebsperioden des Lagers. Da das Lager relativ klein ist, wird dieser Faktor während der Hochsaison im Lager zu einem „Engpass“ und verlangsamt die Lagerprozesse erheblich.
Idee zur Problemlösung
Es entstand eine Idee: Chargen von Resten mit den nächstgelegenen Daten sollten auf eine einzige Charge reduziert werden, und solche Reste mit einer einheitlichen Charge sollten kompakt zusammen in einer Zelle oder in mehreren platziert werden, wenn in einer nicht genügend Platz für die Unterbringung vorhanden ist gesamte Restmenge.
Abb.2. Schema zur Komprimierung von Rückständen in Zellen
Dadurch können Sie die belegte Lagerfläche, die für die Einlagerung neuer Waren genutzt wird, deutlich reduzieren. In einer Situation, in der die Lagerkapazitäten überlastet sind, ist eine solche Maßnahme äußerst notwendig, da sonst möglicherweise nicht genügend freier Platz für die Unterbringung neuer Waren vorhanden ist, was zu einem Stopp der Lagerbestückungs- und Nachschubprozesse führt. Zuvor vor der Umsetzung WMS-Systeme führten diesen Vorgang manuell durch, was wirkungslos war, da die Suche nach geeigneten Rückständen in den Zellen recht langwierig war. Mit der Einführung eines WMS-Systems haben wir uns nun entschieden, den Prozess zu automatisieren, zu beschleunigen und intelligent zu machen.
Der Prozess zur Lösung eines solchen Problems ist in zwei Phasen unterteilt:
- In der ersten Phase finden wir Gruppen von Chargen, deren Komprimierungsdatum nahe beieinander liegt.
- Im zweiten Schritt berechnen wir für jede Chargengruppe die kompakteste Platzierung der restlichen Ware in den Zellen.
Im aktuellen Artikel konzentrieren wir uns auf die erste Stufe des Algorithmus und überlassen die Behandlung der zweiten Stufe dem nächsten Artikel.
Suchen Sie nach einem mathematischen Modell des Problems
Bevor wir uns daran machten, Code zu schreiben und unser Rad neu zu erfinden, beschlossen wir, dieses Problem wissenschaftlich anzugehen, nämlich: es mathematisch zu formulieren, es auf ein bekanntes diskretes Optimierungsproblem zu reduzieren und effektive vorhandene Algorithmen zu verwenden, um es zu lösen, oder diese vorhandenen Algorithmen zu verwenden als Grundlage und passen sie an die Besonderheiten des zu lösenden praktischen Problems an.
Da aus der betriebswirtschaftlichen Formulierung des Problems klar hervorgeht, dass es sich um Mengen handelt, werden wir ein solches Problem mengentheoretisch formulieren.
Lassen – die Menge aller Restchargen eines bestimmten Produkts in einem Lager. Lassen – gegebene Konstante von Tagen. Lassen – eine Teilmenge von Chargen, wobei der Datumsunterschied für alle Chargenpaare in der Teilmenge eine Konstante nicht überschreitet . Wir müssen die Mindestanzahl disjunkter Teilmengen finden , so dass alle Teilmengen zusammengenommen würde es viele geben .
Mit anderen Worten: Wir müssen Gruppen oder Cluster ähnlicher Parteien finden, bei denen das Ähnlichkeitskriterium durch die Konstante bestimmt wird . Diese Aufgabe erinnert uns an das bekannte Clustering-Problem. Es ist wichtig zu sagen, dass sich das betrachtete Problem vom Clustering-Problem dadurch unterscheidet, dass unser Problem eine streng definierte Bedingung für das Kriterium der Ähnlichkeit von Clusterelementen hat, die durch die Konstante bestimmt wird , aber im Clustering-Problem gibt es keine solche Bedingung. Die Erklärung des Clustering-Problems und Informationen zu diesem Problem finden Sie hier
So ist es uns gelungen, das Problem zu formulieren und ein klassisches Problem mit einer ähnlichen Formulierung zu finden. Jetzt ist es notwendig, bekannte Algorithmen zur Lösung in Betracht zu ziehen, um das Rad nicht neu zu erfinden, sondern die besten Praktiken zu übernehmen und sie anzuwenden. Um das Clustering-Problem zu lösen, haben wir die gängigsten Algorithmen in Betracht gezogen, nämlich: -bedeutet, -Mittel, Algorithmus zur Identifizierung verbundener Komponenten, Minimum-Spanning-Tree-Algorithmus. Eine Beschreibung und Analyse solcher Algorithmen finden Sie hier
Um unser Problem zu lösen, Clustering-Algorithmen -bedeutet und -Mittel sind überhaupt nicht anwendbar, da die Anzahl der Cluster nie im Voraus bekannt ist und solche Algorithmen berücksichtigen nicht die konstante Tagesbeschränkung. Solche Algorithmen wurden zunächst nicht berücksichtigt.
Um unser Problem zu lösen, sind der Algorithmus zur Identifizierung verbundener Komponenten und der Minimum-Spanning-Tree-Algorithmus besser geeignet, aber wie sich herausstellte, können sie nicht „frontal“ auf das zu lösende Problem angewendet werden und eine gute Lösung erhalten. Um dies zu erklären, betrachten wir die Funktionslogik solcher Algorithmen in Bezug auf unser Problem.
Betrachten Sie die Grafik , in dem die Eckpunkte die Menge der Parteien sind und die Kante zwischen den Eckpunkten и hat ein Gewicht, das der Differenz der Tage zwischen den Chargen entspricht и . Im Algorithmus zur Identifizierung verbundener Komponenten wird der Eingabeparameter angegeben Wo , und in der Grafik Alle Kanten, deren Gewicht größer ist, werden entfernt . Nur die engsten Objektpaare bleiben verbunden. Der Sinn des Algorithmus besteht darin, einen solchen Wert auszuwählen , bei dem der Graph in mehrere verbundene Komponenten „zerfällt“, wobei die zu diesen Komponenten gehörenden Parteien unser durch die Konstante bestimmtes Ähnlichkeitskriterium erfüllen . Die resultierenden Komponenten sind Cluster.
Der Minimum-Spanning-Tree-Algorithmus baut zunächst auf einem Diagramm auf Minimaler Spannbaum und entfernt dann nacheinander Kanten mit dem höchsten Gewicht, bis der Graph in mehrere verbundene Komponenten „zerfällt“, wobei die zu diesen Komponenten gehörenden Parteien auch unser Ähnlichkeitskriterium erfüllen. Die resultierenden Komponenten sind Cluster.
Bei der Verwendung solcher Algorithmen zur Lösung des betrachteten Problems kann eine Situation wie in Abbildung 3 auftreten.
Abb. 3. Anwendung von Clustering-Algorithmen auf das zu lösende Problem
Nehmen wir an, unsere Konstante für die Differenz zwischen Batch-Tagen beträgt 20 Tage. Graph wurde zur leichteren visuellen Wahrnehmung in räumlicher Form dargestellt. Beide Algorithmen ergaben eine 3-Cluster-Lösung, die leicht verbessert werden kann, indem die in separaten Clustern platzierten Chargen miteinander kombiniert werden! Es ist offensichtlich, dass solche Algorithmen an die Besonderheiten des zu lösenden Problems angepasst werden müssen und ihre Anwendung in reiner Form zur Lösung unseres Problems zu schlechten Ergebnissen führen wird.
Bevor wir also begannen, Code für für unsere Aufgabe modifizierte Graphalgorithmen zu schreiben und unser eigenes Fahrrad neu zu erfinden (in dessen Silhouetten wir bereits die Umrisse von quadratischen Rädern erkennen konnten), beschlossen wir erneut, ein solches Problem wissenschaftlich anzugehen, nämlich: Versuchen Sie, es auf eine weitere diskrete Problemoptimierung zu reduzieren, in der Hoffnung, dass vorhandene Algorithmen zu seiner Lösung ohne Änderungen angewendet werden können.
Eine weitere Suche nach einem ähnlichen klassischen Problem war erfolgreich! Es ist uns gelungen, ein diskretes Optimierungsproblem zu finden, dessen Formulierung eins zu eins mit der Formulierung unseres Problems übereinstimmt. Diese Aufgabe stellte sich heraus Deckungsproblem einstellen. Lassen Sie uns die Formulierung des Problems in Bezug auf unsere Besonderheiten darstellen.
Es gibt eine endliche Menge und Familie aller seiner disjunkten Teilmengen von Parteien, so dass sich die Datendifferenz für alle Parteienpaare jeder Teilmenge ergibt aus der Familie überschreitet nicht die Konstanten . Eine Hülle wird als Familie bezeichnet der geringsten Macht, deren Elemente dazu gehören , so dass die Vereinigung von Mengen aus der Familie sollte die Menge aller Parteien geben .
Eine detaillierte Analyse dieses Problems finden Sie hier и Weitere Möglichkeiten zur praktischen Anwendung des Abdeckungsproblems und seiner Modifikationen finden sich
Algorithmus zur Lösung des Problems
Wir haben uns für das mathematische Modell des zu lösenden Problems entschieden. Schauen wir uns nun den Algorithmus zur Lösung an. Teilmengen aus der Familie können mit dem folgenden Verfahren leicht gefunden werden.
- Ordnen Sie Stapel aus einem Satz an in absteigender Reihenfolge ihres Datums.
- Finden Sie die minimalen und maximalen Chargentermine.
- Für jeden Tag Finden Sie vom Mindestdatum bis zum Höchstdatum alle Chargen, deren Daten abweichen nicht mehr als (also der Wert Es ist besser, die gerade Zahl zu nehmen.
Logik des Verfahrens zur Bildung einer Mengenfamilie при Tage ist in Abbildung 4 dargestellt.
Abb.4. Bildung von Teilmengen von Parteien
Dieses Verfahren ist nicht für jeden notwendig Gehen Sie alle anderen Chargen durch und überprüfen Sie die Abweichungen in ihren Daten oder vom aktuellen Wert Bewegen Sie sich nach links oder rechts, bis Sie eine Charge finden, deren Datum sich von unterscheidet um mehr als die Hälfte des Wertes der Konstante. Alle nachfolgenden Elemente werden für uns nicht interessant sein, wenn sie sich sowohl nach rechts als auch nach links bewegen, da für sie der Unterschied in Tagen nur größer wird, da die Elemente im Array ursprünglich geordnet waren. Dieser Ansatz führt zu einer erheblichen Zeitersparnis, wenn die Anzahl der Parteien und die Verteilung ihrer Termine sehr groß ist.
Das Set-Covering-Problem ist -schwierig, was bedeutet, dass es keinen schnellen (mit einer Betriebszeit gleich einem Polynom der Eingabedaten) und genauen Algorithmus zur Lösung gibt. Um das Mengenüberdeckungsproblem zu lösen, wurde daher ein schneller Greedy-Algorithmus gewählt, der natürlich nicht genau ist, aber folgende Vorteile bietet:
- Für kleine Probleme (und das ist genau unser Fall) berechnet es Lösungen, die ziemlich nahe am Optimum liegen. Mit zunehmender Größe des Problems verschlechtert sich die Qualität der Lösung, allerdings immer noch recht langsam;
- Sehr einfach zu implementieren;
- Schnell, da die Laufzeit geschätzt wird .
Der Greedy-Algorithmus wählt Mengen nach folgender Regel aus: In jeder Phase wird eine Menge ausgewählt, die die maximale Anzahl noch nicht abgedeckter Elemente abdeckt. Eine detaillierte Beschreibung des Algorithmus und seines Pseudocodes finden Sie hier
Ein Vergleich der Genauigkeit eines solchen Greedy-Algorithmus anhand von Testdaten des zu lösenden Problems mit anderen bekannten Algorithmen, wie dem probabilistischen Greedy-Algorithmus, dem Ameisenkolonie-Algorithmus usw., wurde nicht durchgeführt. Die Ergebnisse des Vergleichs solcher Algorithmen anhand generierter Zufallsdaten können gefunden werden
Implementierung und Implementierung des Algorithmus
Dieser Algorithmus wurde in der Sprache implementiert 1S und wurde in eine externe Verarbeitung namens „Residue Compression“ einbezogen, mit der verbunden war WMS-System. Wir haben den Algorithmus nicht in der Sprache implementiert C ++ und verwenden Sie es von einer externen nativen Komponente, was korrekter wäre, da die Geschwindigkeit des Codes geringer ist C + + Mal und in einigen Beispielen sogar zehnmal schneller als die Geschwindigkeit ähnlicher Codes 1S. Auf der Zunge 1S Der Algorithmus wurde implementiert, um Entwicklungszeit zu sparen und das Debuggen in der Produktionsbasis des Kunden zu vereinfachen. Das Ergebnis des Algorithmus ist in Abbildung 5 dargestellt.
Abb.5. Verarbeitung zum „Komprimieren“ von Rückständen
Abbildung 5 zeigt, dass im angegebenen Lager die aktuellen Warenbestände in den Lagerzellen in Cluster unterteilt sind, innerhalb derer sich die Daten der Warenchargen um maximal 30 Tage voneinander unterscheiden. Da der Kunde Kugelhähne aus Metall produziert und im Lager lagert, deren Haltbarkeit in Jahren berechnet wird, kann eine solche Datumsdifferenz vernachlässigt werden. Beachten Sie, dass eine solche Verarbeitung derzeit systematisch in der Produktion und bei den Betreibern eingesetzt wird WMS bestätigen die gute Qualität der Parteienclusterung.
Schlussfolgerungen und Fortsetzung
Die wichtigste Erfahrung, die wir bei der Lösung eines solchen praktischen Problems gesammelt haben, ist eine Bestätigung der Wirksamkeit der Verwendung des Paradigmas: Mathematik. Problemstellung berühmte Matte. Modell berühmter Algorithmus Algorithmus unter Berücksichtigung der Besonderheiten des Problems. Diskrete Optimierung gibt es schon seit mehr als 300 Jahren, und in dieser Zeit ist es den Menschen gelungen, viele Probleme zu berücksichtigen und viel Erfahrung bei deren Lösung zu sammeln. Zunächst ist es sinnvoller, auf diese Erfahrung zurückzugreifen und erst dann damit zu beginnen, das Rad neu zu erfinden.
Im nächsten Artikel werden wir die Geschichte über Optimierungsalgorithmen fortsetzen und uns das interessanteste und viel komplexere vorstellen: einen Algorithmus zur optimalen „Komprimierung“ von Zellresten, der vom Batch-Clustering-Algorithmus erhaltene Daten als Eingabe verwendet.
Habe den Artikel vorbereitet
Roman Shangin, Programmierer der Projektabteilung,
Erstes BIT-Unternehmen, Tscheljabinsk
Source: habr.com