Diskrete Mathematik für WMS: Algorithmus zur Kompression von Waren in Zellen (Teil 1)

In diesem Artikel berichten wir, wie wir das Problem der fehlenden verfügbaren Lagerplätze gelöst haben und die Entwicklung eines Algorithmus für die diskrete Optimierung zur Lösung dieser Aufgabe. Wir erklären, wie wir das mathematische Modell der Optimierungsaufgabe „gebaut“ haben und welche unerwarteten Schwierigkeiten wir bei der Verarbeitung der Eingabedaten für den Algorithmus hatten.

Wenn Sie sich für die Anwendungen der Mathematik im Geschäftsleben interessieren und vor strengen identitätswahren Umformungen von Formeln auf dem Niveau der 5. Klasse nicht zurückschrecken, dann sind Sie herzlich eingeladen, weiterzulesen!

Der Artikel wird für diejenigen von Nutzen sein, die WMS-Systeme implementieren, in der Lager- oder Produktionslogistik tätig sind und an Anwendungen der Mathematik im Geschäftsleben sowie an der Optimierung von Prozessen im Unternehmen interessiert sind.

Einleitung

Diese Veröffentlichung setzt unsere Artikeler Reihe fort, in der wir unsere erfolgreichen Erfahrungen mit der Implementierung von Optimierungsalgorithmen in Lagerprozesse teilen.

In im vorherigen Artikel Hier wird die Spezifik des Lagers beschrieben, in dem wir das WMS-System implementiert haben, sowie erläutert, warum wir die Aufgabe der Clusterbildung von Restpartien bei der Implementierung lösen mussten. WMS-Systeme und wie wir das gemacht haben.

Nachdem wir den Artikel über Optimierungsalgorithmen fertiggestellt hatten, ist er sehr umfangreich geworden, weshalb wir das gesammelte Material in zwei Teile aufteilen wollten:

• Im ersten Teil (dieser Artikel) werden wir darüber sprechen, wie wir das mathematische Modell der Aufgabe "gebaut" haben und mit welchen großen Schwierigkeiten wir unerwartet bei der Verarbeitung und Transformation der Eingabedaten für den Algorithmus konfrontiert wurden.
• Im zweiten Teil werden wir die Implementierung des Algorithmus in der Programmiersprache C++, einen rechnerischen Versuch durchführen und die Erfahrungen zusammenfassen, die wir während der Einführung solcher "intelligenten Technologien" in die Geschäftsprozesse des Auftraggebers gesammelt haben.

Wie man den Artikel liest. Wenn Sie den vorherigen Artikel gelesen haben, können Sie direkt zum Abschnitt "Überblick über bestehende Lösungen" springen. Andernfalls finden Sie die Problembeschreibung im Spoiler unten.

Beschreibung des gelösten Problems im Lager des Auftraggebers

Engpass in den Prozessen

Im Jahr 2018 haben wir ein Projekt zur Implementierung der WMS-Systeme im Lager des "Handelshauses 'LD'" in Chelyabinsk durchgeführt. Wir haben das Produkt "1C-Logistik: Lagerverwaltung 3" an 20 Arbeitsplätzen implementiert: Betreiber WMS, Lageristen, Gabelstaplerfahrer. Die Lagerfläche beträgt durchschnittlich etwa 4.000 m², mit 5.000 Fächern und 4.500 SKUs. Im Lager werden verschiedene Größen von Kugelhähnen, die in eigener Produktion hergestellt werden, von 1 kg bis 400 kg gelagert. Die Bestände im Lager werden nach Chargen verwaltet, da eine Abholung der Ware nach FIFO erforderlich ist.

Während der Planung der Automatisierungsschemata für Lagerprozesse sind wir auf das bestehende Problem der suboptimalen Lagerung von Beständen gestoßen. Die spezifischen Anforderungen für die Lagerung und Anordnung der Krane sind so, dass in einem Fach für Einzelstücke nur Artikel einer einzigen Charge gelagert werden können (siehe Abb. 1). Die Produkte treffen täglich im Lager ein, und jede Lieferung stellt eine eigene Charge dar. Insgesamt entstehen im Laufe eines Monats 30 separate Chargen, wobei jede in einem eigenen Fach gelagert werden muss. Die Ware wird häufig nicht in vollständigen Paletten, sondern einzelnen Stückzahlen entnommen, was dazu führt, dass in vielen Fächern der Zone für Einzelentnahmen folgendes Bild zu beobachten ist: In einem Fach mit einem Volumen von über 1 m³ liegen mehrere Stücke von Kranen, die weniger als 5-10 % des Fachvolumens einnehmen.

Abb. 1. Foto von mehreren Stücke in einem Fach

Es gibt eine suboptimale Nutzung der Lagerkapazitäten. Um das Ausmaß des Problems zu verdeutlichen, kann ich Zahlen nennen: Im Durchschnitt gibt es in verschiedenen Zeiträumen zwischen 100 und 300 Lagerplätze mit einem Volumen von über 1 m³, die nur „marginale“ Bestände aufweisen. Da das Lager relativ klein ist, wird dieser Faktor in den Hochsaisonzeiten zu einem „Engpass“, der die Abläufe bei Wareneingang und -ausgang erheblich verlangsamt.

Idee zur Problemlösung

Die Idee entstand: Restbestände mit den nahesten Terminen zu einer einheitlichen Partie zusammenzuführen und diese uniformen Bestände kompakt in einer oder mehreren Fächern zu lagern, falls der Platz in einem Fach nicht ausreicht, um die gesamte Menge unterzubringen. Ein Beispiel für ein solches „Verdichten“ ist in Abbildung 2 dargestellt.

Abb. 2. Schema zur Verdichtung der Bestände in Fächern

Dies ermöglicht eine erhebliche Reduzierung der benötigten Lagerflächen, die für das neue, gelagerte Produkt verwendet werden. In einer Situation, in der die Lagerkapazitäten überlastet sind, ist eine solche Maßnahme äußerst notwendig; andernfalls könnte der verfügbare Platz zur Unterbringung neuer Waren einfach nicht ausreichen, was zu einem Stillstand der Lagerprozesse führt und infolgedessen die Annahme und den Versand beeinträchtigt. Früher wurde solch eine Operation manuell durchgeführt, was ineffizient war, da der Prozess, geeignete Bestände in den Fächern zu finden, recht langwierig war. Mit der Einführung des WMS-Systems haben wir beschlossen, diesen Prozess zu automatisieren, zu beschleunigen und intelligent zu gestalten.

Der Prozess zur Lösung einer solchen Aufgabe wird in 2 Phasen unterteilt:

• In der ersten Phase identifizieren wir die nahestehenden Gruppen von Chargen zur Komprimierung (diese Aufgabe wird behandelt) der vorherige Artikel);
• In der zweiten Phase berechnen wir für jede Gruppe von Chargen die möglichst kompakte Unterbringung der Warenbestände in den Fächern.

In diesem Artikel konzentrieren wir uns auf die zweite Phase des Algorithmus.

Überblick über bestehende Lösungen

Bevor wir zu der Beschreibung der von uns entwickelten Algorithmen übergehen, ist es sinnvoll, einen kurzen Überblick über bereits bestehende Systeme auf dem Markt zu geben. WMS, die ähnliche Funktionalitäten zur optimalen Kompression bieten.

Zunächst sei das Produkt „1C:Enterprise 8. WMS Logistik. Lagerverwaltung 4“ erwähnt, das von der Firma 1C stammt und zur vierten Generation gehört. WMS-Systeme, die von der Firma AXELOT entwickelt wurden. In diesem System ist eine Kompressionsfunktionalität integriert, die darauf abzielt, verstreute Warenbestände in einem gemeinsamen Lagerplatz zu vereinen. Es ist wichtig zu betonen, dass die Kompressionsfunktion in einem solchen System auch weitere Möglichkeiten umfasst, wie z.B. die Anpassung der Platzierung von Waren in den Fächern gemäß ihren ABC-Klassen, auf die wir jedoch nicht näher eingehen werden.

Wenn man den Code des Systems „1C: Enterprise 8. WMS Logistik. Lagerverwaltung 4“ analysiert (der in diesem Funktionsbereich offen ist), kann man Folgendes zusammenfassen. Der Algorithmus zur Kompression der Bestände implementiert eine recht primitive lineare Logik, und eine „optimale“ Kompression kann nicht angestrebt werden. Natürlich sieht er keine Clusterung von Posten vor. Einige Kunden, bei denen ein solches System implementiert wurde, haben sich über die Ergebnisse der Planungsprozesse zur Kompression beschwert. Beispielsweise trat häufig folgendes Szenario auf: 100 Stück Bestände aus einem Fach sollen in ein anderes Fach verschoben werden, in dem sich 1 Stück Produkt befindet, obwohl es aus zeitlicher Sicht günstiger wäre, es umgekehrt zu machen.

Der Funktionsumfang zur Kompression von Warenbeständen in Fächern wird auch in vielen ausländischen WMS-systemen angegeben, aber leider haben wir weder tatsächliche Rückmeldungen zur Effektivität der Algorithmen (das ist ein Geschäftsgeheimnis) noch eine Vorstellung von der Tiefe ihrer Logik (proprietäre Software mit geschlossenem Code), daher können wir darüber keine Aussage treffen.

Suche nach einem mathematischen Modell der Aufgabe

Um qualitativ hochwertige Algorithmen zur Lösung der Aufgabe zu entwickeln, muss diese zunächst klar und mathematisch formuliert werden, was wir nun tun werden.

Es gibt zahlreiche Fächer , in denen Reste eines bestimmten Produkts gelagert sind. Diese Fächer werden wir künftig als Spenderfächer bezeichnen. Bezeichnen wir das Volumen des Produkts, das im Fach vorhanden ist. $.

Es ist wichtig zu erwähnen, dass bei dem Komprimierungsverfahren nur ein Produkt einer Charge oder mehrere Chargen, die zuvor zu einem Cluster zusammengefasst wurden (lesen Sie den vorherigen Artikel), beteiligt sein können. Dies ist auf die spezifische Lagerung und Anordnung der Produkte zurückzuführen. Für verschiedene Produkte oder unterschiedliche Cluster von Chargen muss ein separates Komprimierungsverfahren gestartet werden.

Es gibt zahlreiche Fächer , in die potenziell Reste aus den Spenderfächern eingefüllt werden können. Diese Fächer werden wir künftig als Containerfächer bezeichnen. Dies können sowohl freie Fächer im Lager als auch Spenderfächer aus der Vielzahl . Immer ist die Menge eine Teilmenge von .

Für jedes Fach aus der Menge sind Kapazitätsbeschränkungen festgelegt. , gemessen in dm³. Ein dm³ entspricht einem Würfel mit Kantenlängen von 10 cm. Die Produkte, die im Lager gelagert werden, sind ausreichend groß, daher ist diese Diskretisierung in diesem Fall vollkommen ausreichend.

Die Matrix der kürzesten Distanzen ist festgelegt in Metern zwischen jedem Paar von Fächern , wobei und gehören zu Mengen und entsprechend.

Bezeichnen wir die „Kosten“ für die Bewegung von Waren aus einem Fach in ein Fach . Bezeichnen wir die „Kosten“ für die Auswahl eines Containers zum Transport von Resten aus anderen Fächern. Wie genau und in welchen Maßeinheiten die Werte berechnet werden und werden weiter unten betrachtet (siehe Abschnitt Eingabedaten vorbereiten), jetzt reicht es zu sagen, dass solche Größen direkt proportional zu den Größen sein werden und entsprechend.

Bezeichnen wir durch eine Variable, die den Wert 1 annimmt, wenn Reste aus dem Fach in den Container verschoben werden , und 0 im anderen Fall. Bezeichnen wir durch eine Variable, die den Wert 1 annimmt, wenn der Container Reste von Waren enthält, und 0 im anderen Fall.

Die Aufgabe formuliert sich so: Es gilt, eine solche Menge von Containern zu finden und auf diese Weise die Quellfächer mit den Containerfächern zu „verbinden“, um die Funktion zu minimieren

unter den Einschränkungen

Insgesamt streben wir bei der Berechnung der Lösung des Problems an:

• erstens, Lagerkapazitäten zu sparen;
• zweitens, die Zeit der Lagerarbeiter zu sparen.

Die letzte Einschränkung bedeutet, dass wir Waren nicht in einen Container verschieben können, den wir nicht ausgewählt haben, und somit auch keine "Kosten" für die Auswahl dieses Containers tragen. Diese Einschränkung bedeutet ebenfalls, dass das Volumen der aus den Fächern in den Container verschobenen Waren die Kapazität des Containers nicht überschreiten darf. Unter der Lösung des Problems verstehen wir eine Menge von Containern und die Methoden zur Befestigung der Spenderfächer an den Containern.

Eine solche Formulierung des Optimierungsproblems ist nicht neu und wurde von vielen Mathematikern bereits seit den frühen 80er Jahren des letzten Jahrhunderts untersucht. In der ausländischen Literatur existieren zwei Optimierungsprobleme mit einem passenden mathematischen Modell: Single-Source Capacitated Facility Location Problem und Multi-Source Capacitated Facility Location Problem (Über die Unterschiede in den Aufgaben sprechen wir später). Es ist erwähnenswert, dass in der mathematischen Literatur die Formulierung solcher zwei Optimierungsprobleme im Kontext der Standortwahl von Unternehmen erfolgt, daher der Begriff „Facility Location“. Dies ist größtenteils eine Tradition, da das Bedürfnis nach Lösungen für solche kombinatorischen Probleme ursprünglich aus der Logistik, insbesondere der militärisch-industriellen Branche in den 1950er Jahren, entstand. In Bezug auf die Standortwahl von Unternehmen werden diese Probleme wie folgt formuliert:

• Es gibt eine endliche Menge von Städten, in denen potenziell Produktionsstätten eröffnet werden können (im Folgenden Produktionsstädte). Für jede Produktionsstadt sind die Kosten für die Eröffnung eines Unternehmens sowie die Begrenzung der Produktionskapazitäten des dort eröffneten Unternehmens angegeben.
• Es gibt eine endliche Menge von Städten, in denen sich tatsächlich die Kunden befinden (im Folgenden Kundenstädte). Für jede dieser Kundenstädte ist das Nachfragevolumen für die Produkte angegeben. Zur Vereinfachung nehmen wir an, dass das Produkt, das von den Unternehmen hergestellt und von den Kunden konsumiert wird, identisch ist.
• Für jedes Paar Stadt-Hersteller und Stadt-Kunde sind die Transportkosten für die Lieferung des erforderlichen Produktionsvolumens vom Hersteller an den Kunden angegeben.

Es muss ermittelt werden, in welchen Städten Unternehmen eröffnet werden sollen und wie Kunden an diese Unternehmen gebunden werden können, um:

• Die Gesamtkosten für die Eröffnung der Unternehmen und die Transportkosten zu minimieren;
• Das Nachfragevolumen der Kunden, die einem eröffneten Unternehmen zugeordnet sind, darf die Produktionskapazitäten dieses Unternehmens nicht überschreiten.

Jetzt sollte das einzige Unterschied zwischen diesen beiden klassischen Aufgaben angesprochen werden:

• Single-Source Capacitated Facility Location Problem – der Kunde wird nur von einem eröffneten Unternehmen beliefert;
• Multi-Source Capacitated Facility Location Problem – der Kunde kann gleichzeitig von mehreren geöffneten Unternehmen beliefert werden.

Diese Unterscheidung zwischen den Aufgaben erscheint auf den ersten Blick geringfügig, führt jedoch in Wirklichkeit zu einer völlig anderen kombinatorischen Struktur solcher Aufgaben und infolgedessen zu völlig unterschiedlichen Algorithmen für deren Lösung. Der Unterschied zwischen den Aufgaben wird im Bild unten dargestellt.

Abb. 3. a) Multi-Source Capacitated Facility Location Problem

Abb. 3. b) Problem der Standortwahl für Kapazitäten mit einer einzigen Quelle

Beide Aufgaben - sind schwierig, das heißt, es gibt keinen exakten Algorithmus, der das Problem in einer Zeit lösen könnte, die polynomiell in Bezug auf die Größe der Eingabedaten ist. Einfacher ausgedrückt, alle exakten Algorithmen zur Lösung des Problems benötigen exponentielle Zeit, auch wenn sie möglicherweise schneller sind als ein vollständiger Brute-Force-Versuch. Da die Aufgabe - schwierig ist, werden wir nur approximative Heuristiken betrachten, also Algorithmen, die stabil Lösungen berechnen, die sehr nahe am Optimum sind und ziemlich schnell arbeiten. Wenn Interesse an solchen Aufgaben besteht, kann hier eine gute Übersicht auf Russisch gefunden werden.

Wenn wir die Terminologie unserer Aufgabe der optimalen Lagerung von Waren in Zellen übertragen, dann:

• Städte-Kunden – das sind Zellen-Geber mit Restbeständen
• Städte-Produzenten – Zellen-Behälter , in die die Reste aus anderen Zellen eingefüllt werden sollen,
• Transportkosten – Zeitkosten des Lagerverwalters für die Bewegung des Warenvolumens von der Geber-Zelle in die Behälter-Zelle ;
• Kosten für die Eröffnung eines Unternehmens – Kosten für die Auswahl des Behälters , die dem Volumen der Containerzelle entsprechen , multipliziert mit einem bestimmten Einsparungsfaktor (der Wert des Faktors ist immer > 1) (siehe Abschnitt zur Vorbereitung der Eingabedaten).

Nachdem die Analogie zu den bekannten klassischen Aufgabenstellungen gezogen wurde, ist es wichtig, eine entscheidende Frage zu beantworten, die die Wahl der Architektur des Lösungalgorithmus beeinflusst: Ist es möglich, Restbestände aus der Spenderzelle nur in einen einzigen Container (Single-Source) zu verschieben, oder können Restbestände in mehrere Zellen-Container (Multi-Source) verschoben werden?

Es ist anzumerken, dass in der Praxis beide Aufgabenstellungen existieren. Im Folgenden führen wir alle „Für“ und „Wider“ für jede dieser Varianten auf:

Tabelle 1. Vor- und Nachteile der Varianten Single-Source und Multi-Source.

Da die Vorteile der Single-Source-Variante überwiegen und angesichts der Tatsache, dass je weniger Restbestände in den Quellzellen vorhanden sind, das Unterschied in der Kompaktheit der Berechnung für beide Varianten geringer wird, fiel unsere Wahl auf die Single-Source-Variante.

Es ist erwähnenswert, dass die Entscheidung für die Multi-Source-Variante ebenfalls gerechtfertigt ist. Es gibt eine Vielzahl effektiver Algorithmen zur Lösung, von denen die meisten auf die Lösung eines Satzes von Transportproblemen hinauslaufen. Zudem gibt es nicht nur effektive, sondern auch elegante Algorithmen, wie zum Beispiel. hier.

Vorbereitung der Eingabedaten

Bevor wir mit der Analyse und der Entwicklung eines Algorithmus zur Lösung des Problems beginnen, müssen wir klären, welche Daten und in welcher Form wir sie ihm als Eingabe bereitstellen. Bei den Bestandsmengen der Waren in den Stellplätzen und der Kapazität der Container gibt es keine Probleme, da dies trivial ist – solche Werte werden in m³ gemessen. Doch bei den Kosten für die Nutzung des Containerplatzes und der Kostenmatrix für den Transport sieht es komplizierter aus!

Zunächst betrachten wir die Berechnung der Transportkosten vom Stellplatz zum Containerplatz. Zunächst müssen wir klären, in welchen Maßeinheiten wir die Transportkosten berechnen werden. Die beiden naheliegendsten Optionen sind Meter und Sekunden. Es ist jedoch nicht sinnvoll, die Transportkosten in „reinen“ Metern zu betrachten. Wir zeigen dies anhand eines Beispiels. Angenommen, der Stellplatz befindet sich auf der ersten Ebene, der Stellplatz ist 30 Meter entfernt und befindet sich auf der zweiten Ebene:

• Der Transport von in ist kostenintensiver als der Transport von in , da es einfacher ist, von der zweiten Ebene (1,5-2 Meter über dem Boden) nach unten zu senken, als nach oben zu heben, auch wenn die zurückgelegte Strecke die gleiche ist.
• Einen Artikel aus dem Stellplatz transportieren in Es wird einfacher sein, als 10 Stück desselben Produkts zu bewegen, obwohl die Strecke gleich bleibt.

Die Umzugskosten sollten besser in Sekunden berücksichtigt werden, da dies auch Unterschiede in den Ebenen und in der Menge der zu transportierenden Waren erfasst. Um die Umzugskosten in Sekunden zu erfassen, müssen wir den Umzugsprozess in elementare Bestandteile zerlegen und die Zeit für die Durchführung jedes elementaren Bestandteils messen.

Nehmen wir an, aus dem Lagerfach werden Stück Waren in den Container . Nehmen wir an, ist die durchschnittliche Bewegungsgeschwindigkeit des Mitarbeiters im Lager, gemessen in m/s. Nehmen wir an, und sind die durchschnittlichen Geschwindigkeiten für die einmalige Durchführung von Ein- und Ablageoperationen für ein Warenvolumen von 4 dm³ (das durchschnittliche Volumen, das ein Mitarbeiter im Lager bei der Durchführung von Aufgaben aufnimmt). Nehmen wir an, und sind die Höhen der Fächer, aus denen die Ein- und Ablageoperationen durchgeführt werden. Zum Beispiel beträgt die durchschnittliche Höhe der ersten Ebene (Boden) 1 m, die zweite Ebene 2 m usw. Dann lautet die Formel zur Berechnung der gesamten Zeit für die Durchführung der Umzugsoperation wie folgt:

Tabelle 2 zeigt die Statistiken zur Ausführungszeit jeder grundlegenden Operation, die von den Lagermitarbeitern unter Berücksichtigung der Art der gelagerten Waren gesammelt wurden.

Bezeichnung der Operation	Kennzeichnung	Durchschnittswert
Durchschnittliche Bewegungsgeschwindigkeit des Lagerarbeiters		1,5 m/s
Durchschnittliche Zeit für die Ausführung einer Operation zum Einlagern (für ein Volumen von 4 dm³)		2,4 Sek.

Tabelle 2. Durchschnittliche Zeit für Lageroperationen

Wir haben uns auf die Berechnung der Kosten für den Transport geeinigt. Jetzt müssen wir herausfinden, wie wir die Kosten für die Auswahl des Fachcontainers berechnen. Hier ist alles viel, viel komplizierter als bei den Transportkosten, da:

• Erstens sollten die Kosten direkt vom Volumen der Behälter abhängen – das gleiche Volumen an Beständen, das aus den Spenderzellen verschoben wird, sollte besser in einen kleineren Behälter gelegt werden als in einen großen, vorausgesetzt, dass dieses Volumen vollständig in beide Behälter passt. Indem wir die Gesamtkosten für die Auswahl der Behälter minimieren, versuchen wir, die 'knappen' freien Lagerkapazitäten im Kommissionierbereich zu sparen, um die anschließenden Platzierungsoperationen der Waren in den Zellen durchzuführen. Abbildung 4 zeigt die Optionen für den Transfer von Beständen in große und kleine Behälter sowie die Folgen solcher Transfers bei der Durchführung nachfolgender Lageroperationen.
• Zweitens, da wir bei der Lösung des ursprünglichen Problems die Gesamtkosten minimieren müssen, die sowohl die Kosten für den Transfer als auch die Kosten für die Auswahl der Behälter umfassen, müssen die Volumina der Zellen in Kubikmetern irgendwie mit den Sekunden in Verbindung gebracht werden, was alles andere als trivial ist.

Abb. 4. Optionen zum Transfer von Beständen in Behälter mit unterschiedlichem Volumen.

In Abbildung 4 ist der verbleibende Volumen in Rot dargestellt, der im Container während der zweiten Phase der Platzierung weiterer Waren nicht mehr untergebracht werden kann.

Es hilft, die Kubikmeter der Kosten für die Auswahl des Containers mit den Zeitkosten für den Transport zu verknüpfen, die folgenden Anforderungen an die berechneten Lösungen des Problems:

• Es ist notwendig, dass die Bestände aus der Spenderzelle in jedem Fall in die Containerzelle verschoben werden, wenn dies die Gesamtzahl der Containerzellen, in denen sich die Ware befindet, reduziert.
• Es muss ein Gleichgewicht zwischen dem Volumen der Container und den Zeitkosten für den Transport gewahrt werden: Wenn im neuen Lösungsansatz im Vergleich zur vorherigen Lösung der Gewinn im Volumen groß und der Verlust an Zeitkosten gering ist, sollte die neue Lösung gewählt werden.

Beginnen wir mit der letzten Anforderung. Um das mehrdeutige Wort „Gleichgewicht“ zu konkretisieren, haben wir eine Umfrage unter den Lagerangestellten durchgeführt, um Folgendes zu klären. Angenommen, es gibt eine Containerzelle mit einem Volumen , in die die Bestände von Waren aus Spenderzellen verschoben werden sollen und die Gesamtdauer dieses Transfers beträgt . Lassen Sie uns einige alternative Optionen für die Platzierung derselben Menge an Ware aus denselben Quellzellen in andere Container betrachten, wobei jede Platzierung ihre eigenen Bewertungen hat. , wobei < und , wobei >.

Die Frage stellt sich: Was ist der minimal akzeptable Gewinn an Volumen? bei einem festgelegten Zeitverlust. ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Abb. 5. Diagramm, das die Abhängigkeit des minimalen akzeptablen Volumenvergünstigung von der erhöhten Zeitdifferenz der Durchführung zeigt.

Das heißt, wenn die zusätzlichen Zeitkosten 40 Sekunden betragen, sind wir bereit, diese auszugeben, wenn der Gewinn an Volumen mindestens 500 dm3 beträgt. Trotz einer leichten Nichtlinearität in der Abhängigkeit nehmen wir der Einfachheit halber an, dass die Beziehung zwischen den Größen linear und durch eine Ungleichung beschrieben wird.

Im folgenden Bild betrachten wir verschiedene Möglichkeiten zur Lagerung von Waren in Containern.

Abb. 6. Option (a): 2 Container, Gesamtvolumen 400 dm3, Gesamtzeit 150 Sek.

Abb. 6. Option (b): 2 Container, Gesamtvolumen 600 dm3, Gesamtzeit 190 Sek.

Abb. 6. Option (c): 1 Container, Gesamtvolumen 400 dm3, Gesamtzeit 200 Sek.

Option (a) for selecting containers is more preferable than the initial option, as the inequality (800-400) / 10 >= 150-120 holds, leading to 40 >= 30. Option (b) is less preferable than the initial option because this inequality does not hold: (800-600) / 10 >= 190-150, resulting in 20 >= 40. However, option (c) does not fit this logic! Let’s consider this option in more detail. On one hand, the inequality (800-400) / 10 >= 200-120 implies that the inequality 40 >= 80 does not hold, indicating that the gain in volume does not justify such a significant loss in time.

On the other hand, in this option (c), we not only reduce the total occupied volume but also decrease the number of occupied bins, which is the first of two important requirements for computed problem solutions listed above. Clearly, to meet this requirement, some positive constant must be added to the left side of the inequality. , and this constant should only be added when the number of containers decreases. Let’s remember that — ist eine Variable, die 1 ist, wenn der Container ausgewählt ist, und 0, wenn der Container nicht ausgewählt ist. Bezeichnen wir als die Menge der Container in der ursprünglichen Lösung und als die Menge der Container in der neuen Lösung. Allgemein wird die neue Ungleichung folgendermaßen aussehen:

Durch Umformung der obigen Ungleichung erhalten wir

Auf dieser Grundlage haben wir die Formel zur Berechnung der Gesamtkosten einer bestimmten Lösung des Problems:

Jetzt stellt sich aber die Frage: welchen Wert sollte eine solche Konstante haben? ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Sei — die maximale Distanz zwischen den Lagereinheiten in einer Zone ABC, die in unserem Fall 100 m beträgt. Sei — das maximale Volumen einer Lagerzelle, das in unserem Fall 1000 dm³ beträgt.

Der erste Weg zur Berechnung der Größe . Betrachten wir die Situation, in der es 2 Container auf der ersten Ebene gibt, die bereits physisch Waren enthalten, das heißt, sie selbst sind die Spendereinheiten, und die Kosten für den Transport der Waren zu denselben Einheiten betragen natürlich 0. Es ist notwendig, einen Wert für die Konstante zu finden , bei dem es immer vorteilhaft wäre, die Restbestände aus Container 1 in Container 2 zu bewegen. Durch Einsetzen der Werte und in die obige Ungleichung erhalten wir:

woraus folgt

Wenn wir die Werte der durchschnittlichen Ausführungszeit einfacher Operationen in die obige Formel einsetzen, erhalten wir

Die zweite Methode zur Berechnung der Größe . Betrachten wir die Situation, in der es Spenderzellen gibt, aus denen die Waren in Container 1 verschoben werden sollen. Wir bezeichnen – die Entfernung von der Spenderzelle zu Container 1. Es gibt auch Container 2, der bereits Waren enthält, und dessen Volumen es ermöglicht, Reste aus allen Spenderzellen zu fassen. Zur Vereinfachung nehmen wir an, dass das Volumen der Waren, die aus den Spenderzellen in die Container verschoben werden, gleich ist und beträgt. Es ist erforderlich, einen Wert für die Konstante zu finden, bei dem die Platzierung aller Reste aus den Zellen in Container 2 immer vorteilhafter wäre als die Platzierung in verschiedene Container:

Durch Umformung der Ungleichung erhalten wir

Um den Wert der Größe zu „verstärken“, nehmen wir an, dass = 0. Die durchschnittliche Anzahl der Zellen, die normalerweise am Verfahren zur Verdichtung der Reste im Lager beteiligt sind, beträgt 10. Wenn wir die bekannten Werte einsetzen, haben wir den folgenden Wert der Konstante: = 0. Die durchschnittliche Anzahl der Zellen, die normalerweise am Verfahren zur Komprimierung von Lagerbeständen beteiligt sind, beträgt 10. Setzt man die bekannten Werte ein, so ergibt sich der folgende Wert der Konstante.

Wir nehmen den größten Wert, der für jede Variante berechnet wurde, dieser wird der Wert der Größe sein. für die vorgegebenen Lagerparameter. Um abschließend zu sein, notieren wir die Formel zur Berechnung der Gesamtkosten. für eine zulässige Lösung. :

Jetzt, nach all den titanischen Anstrengungen, die Eingabedaten umzuformen, können wir sagen, dass alle Eingabedaten in die benötigte Form umgewandelt wurden und bereit für den Einsatz im Optimierungsalgorithmus sind.

Fazit

Wie die Praxis zeigt, wird der Aufwand und die Bedeutung der Phase der Vorbereitung und Umwandlung der Eingabedaten für den Algorithmus oft unterschätzt. In diesem Artikel haben wir dieser Phase viel Aufmerksamkeit geschenkt, um zu zeigen, dass nur qualitativ und sinnvoll aufbereitete Eingabedaten die durch den Algorithmus berechneten Lösungen tatsächlich wertvoll für den Kunden machen können. Ja, es wurden viele Formeln abgeleitet, aber wir haben Sie schon vor dem katastrophalen Ereignis gewarnt 🙂

Im nächsten Artikel werden wir schließlich zu dem kommen, wofür die letzten beiden Veröffentlichungen gedacht waren – zum Algorithmus der diskreten Optimierung.

Der Artikel wurde verfasst von
Roman Shangin, Programmierer der Projektabteilung,
Unternehmen Erster Bit, Stadt Tscheljabinsk.

Quelle: habr.com