In diesem Artikel erzählen wir, wie wir das Problem des fehlenden Lagerraums gelöst haben und über die Entwicklung eines Algorithmus zur diskreten Optimierung für diese Aufgabe. Wir werden erläutern, wie wir das mathematische Modell der Optimierungsaufgabe "gebaut" haben und auf welche unerwarteten Schwierigkeiten wir bei der Verarbeitung der Eingangsdaten für den Algorithmus gestoßen sind.
Wenn Sie sich für die Anwendungen der Mathematik im Geschäftsleben interessieren und keine Angst vor komplexen gleichwertigen Umstellungen auf dem Niveau der 5. Klasse haben, heißen wir Sie herzlich willkommen!
Der Artikel wird für diejenigen nützlich sein, die WMS-Systeme implementieren, in der Lager- oder Produktionslogistik tätig sind oder Programmierer, die sich für die Anwendungen der Mathematik im Geschäftsleben und die Optimierung von Prozessen im Unternehmen interessieren.
Einführungsteil
Diese Veröffentlichung setzt die Reihe von Artikeln fort, in denen wir unsere erfolgreichen Erfahrungen mit der Implementierung von Optimierungsalgorithmen in Lagerprozesse teilen.
Im es wird die Spezifik des Lagers beschrieben, in dem wir das WMS-System implementiert haben, und es wird erklärt, warum wir die Aufgabe der Clusterbildung von Restpartien von Waren bei der Implementierung des WMS-Systems lösen mussten und wie wir das getan haben.
Als wir mit dem Schreiben des Artikels über Optimierungsalgorithmen fertig waren, wurde er sehr umfangreich, weshalb wir das gesammelte Material auf 2 Teile aufteilen wollten:
- Im ersten Teil (dieser Artikel) erzählen wir, wie wir das mathematische Modell der Aufgabe "gebaut" haben und auf welche großen Schwierigkeiten wir unerwartet bei der Verarbeitung und Umwandlung der Eingangsdaten für den Algorithmus gestoßen sind.
- Im zweiten Teil werden wir die Implementierung des Algorithmus im C++-Sprache detailliert betrachten, einen computergestützten Versuch durchführen und die Erfahrungen zusammenfassen, die wir bei der Implementierung solcher "intelligenten Technologien" in die Geschäftsprozesse des Kunden gemacht haben.
Wie man den Artikel liest. Wenn Sie den vorherigen Artikel gelesen haben, können Sie direkt zum Kapitel "Überblick über bestehende Lösungen" übergehen. Wenn nicht, finden Sie die Beschreibung des zu lösenden Problems im Spoiler unten.
Beschreibung des zu lösenden Problems im Lager des Kunden
Engpass in den Prozessen
Im Jahr 2018 haben wir ein Projekt zur Implementierung des WMS-Systems im Lager des "Handels Hauses LD" in Chelyabinsk durchgeführt. Wir haben das Produkt "1C-Logistik: Lagerverwaltung 3" an 20 Arbeitsplätzen implementiert: Bediener WMS, Lageristen, Gabelstaplerfahrer. Das Lager hat eine mittlere Fläche von etwa 4.000 m2, mit 5.000 Fächern und 4.500 SKUs. Im Lager werden Kugelhähne eigener Produktion in verschiedenen Größen von 1 kg bis 400 kg gelagert. Die Bestände im Lager werden nach Partien aufgeteilt, da eine Auswahl der Ware nach FIFO erforderlich ist.
Bei der Planung von Automatisierungsschemata für Lagerprozesse sind wir auf das bestehende Problem der suboptimalen Lagerung von Beständen gestoßen. Die Spezifika der Lagerung und Ablage der Kräne sind so, dass in einem Fach für Einzelartikel nur Artikel einer einzigen Partie gelagert werden können (siehe Abb. 1). Die Produkte treffen täglich im Lager ein, und jede Anlieferung stellt eine separate Partie dar. Insgesamt entstehen im Verlauf eines Monats 30 separate Parteien, wobei jede in einem eigenen Fach gelagert werden muss. Die Ware wird häufig nicht ganze Paletten, sondern Einzelstücke entnommen, und in vielen Fächern der Bereich für die Einzelentnahme sehen wir folgendes Bild: In einem Fach mit mehr als 1 m3 Volumen liegen mehrere Stücke von Kränen, die weniger als 5-10 % des Volumens des Faches ausmachen.
Abb. 1. Foto von mehreren Stücke in einem Fach
Es liegt eine suboptimale Nutzung der Lagerkapazitäten vor. Um das Ausmaß des Problems darzustellen, kann ich Zahlen anführen: Im Durchschnitt gibt es in verschiedenen Perioden des Lagerbetriebs zwischen 100 und 300 solcher Fächer mit einem Volumen von über 1 m3 und „marginalen“ Beständen. Da das Lager relativ klein ist, wird dieser Faktor in den Stoßzeiten zu einem „Engpass“, der die Lagerprozesse bei der Annahme und Auslieferung stark verlangsamt.
Die Idee zur Lösung des Problems
Die Idee entstand, die Restpartien mit den nächstgelegenen Daten zu einer einheitlichen Partie zusammenzuführen und solche Restbestände mit der einheitlichen Partie kompakt in einem Fach oder in mehreren, falls der Platz in einem nicht ausreicht, unterzubringen. Ein Beispiel für ein solches „Verdichten“ ist in Abbildung 2 dargestellt.
Abb. 2. Schema zur Verdichtung der Restbestände in den Fächern
Dies ermöglicht eine signifikante Reduzierung der benötigten Lagerfläche, die für neue Produkte verwendet wird. In einer Situation mit Überlastung der Lagerkapazitäten ist diese Maßnahme äußerst notwendig, da sonst der verfügbare Platz für die Unterbringung neuer Waren einfach nicht ausreicht, was zu einem Stillstand der Lagerprozesse und somit zu einem Ausbleiben von Wareneingang und -ausgang führen kann. Vor der Einführung des WMS-Systems wurde ein solcher Vorgang manuell durchgeführt, was ineffizient war, da der Prozess der Suche nach geeigneten Beständen in den Lagerplätzen ziemlich langwierig war. Jetzt, mit der Einführung des WMS-Systems, haben wir beschlossen, den Prozess zu automatisieren, zu beschleunigen und ihn intelligenter zu gestalten.
Der Prozess zur Lösung dieser Aufgabe wird in 2 Phasen unterteilt:
- In der ersten Phase finden wir zeitlich nahe Gruppen von Partien zur Verdichtung (diese Aufgabe wird gewidmet) );
- In der zweiten Phase berechnen wir für jede Gruppe von Partien die maximal kompakte Anordnung der Warenbestände in den Lagerplätzen.
In diesem Artikel werden wir uns auf die zweite Phase des Algorithmus konzentrieren.
Überblick über bestehende Lösungen
Bevor wir zur Beschreibung der von uns entwickelten Algorithmen übergehen, ist es sinnvoll, einen kurzen Überblick über die bereits bestehenden Systeme auf dem Markt zu geben, WMSin denen eine solche Funktionalität zur optimalen Verdichtung realisiert wurde.
Zunächst ist das Produkt „1C: Unternehmen 8. WMS Logistik. Lagerverwaltung 4“ zu erwähnen, das der Firma 1C gehört und dorthin gehört, und das zur vierten Generation WMS-Systemen gehört, die von der Firma AXELOT entwickelt wurden. In diesem System ist die Funktionalität zur Verdichtung angegeben, die darauf abzielt, verstreute Warenbestände in einem gemeinsamen Lagerplatz zusammenzuführen. Es sei darauf hingewiesen, dass die Funktionalität der Verdichtung in einem solchen System auch weitere Möglichkeiten umfasst, wie z.B. die Korrektur der Anordnung von Waren in den Lagerplätzen gemäß ihren ABC-Klassen, aber darauf werden wir nicht eingehen.
Analysiert man den Code des Systems „1C: Enterprise 8. WMS Logistik. Lagerverwaltung 4“ (der in diesem Teil der Funktionalität offen ist), kann man folgendes abschließen. Der Algorithmus zur Kompression von Beständen implementiert eine recht primitive lineare Logik, und von einer „optimalen“ Kompression kann nicht die Rede sein. Natürlich berücksichtigt er keine Clusterung von Chargen. Einige Kunden, die ein solches System implementiert haben, haben über die Ergebnisse der Planung der Kompression geklagt. Zum Beispiel kam es in der Praxis oft zu folgender Situation bei der Kompression: 100 Stück Bestände aus einem Lagerort sollten in einen anderen Lagerort, wo 1 Stück Ware liegt, verschoben werden, obwohl es aus Sicht des Zeitaufwands optimaler wäre, das Gegenteil zu tun.
Auch die Funktionalität zur Kompression von Warenbeständen in Lagerplätzen wurde in vielen ausländischen WMS-Systemen angekündigt, aber leider haben wir weder reale Rückmeldungen zur Effizienz der Algorithmen (das ist Geschäftsgeheimnis) noch Vorstellungen über die Tiefe ihrer Logik (proprietäre Software mit geschlossenem Quellcode), daher können wir kein Urteil fällen.
Suche nach einem mathematischen Modell des Problems
Um qualitativ hochwertige Algorithmen für die Lösung des Problems zu entwerfen, ist es zunächst notwendig, dieses Problem klar mathematisch zu formulieren, was wir auch tun werden.
Es gibt viele Lagerplätze 
, in denen sich Bestände bestimmter Waren befinden. Diese Lagerplätze werden wir als Spender-Lagerplätze bezeichnen. Wir bezeichnen 
das Volumen der Ware, die sich im Lagerplatz befindet 
$.
Es ist wichtig zu sagen, dass in dem Kompressionsverfahren nur eine Ware einer Charge oder mehrere Chargen, die vorher in einem Cluster zusammengefasst wurden (lies ), beteiligt sein können, was aufgrund der Spezifik der Lagerung und Anordnung von Waren bedingt ist. Für verschiedene Waren oder verschiedene Cluster von Chargen muss ein eigener separater Kompressionsprozess gestartet werden.
Es gibt viele Lagerplätze 
, in die potenziell Bestände aus Spender-Lagerplätzen eingelegt werden können. Diese Lagerplätze werden wir als Container-Lagerplätze bezeichnen. Es können sowohl freie Lagerplätze im Lager als auch Spender-Lagerplätze aus einer Vielzahl 
. Immer ist die Menge 
eine Teilmenge von 
.
Für jeden Lagerplatz 
aus der Menge 
gibt es Einschränkungen für die Kapazität 
, gemessen in dm3. Ein dm3 ist ein Würfel mit Seitenlängen von 10 cm. Die Produkte, die im Lager aufbewahrt werden, sind ziemlich groß, daher reicht in diesem Fall eine solche Diskretisierung vollkommen aus.
Die Matrix der kürzesten Entfernungen ist festgelegt 
in Metern zwischen jedem Paar von Fächern 
und 
gehören zu Mengen 
und 
entsprechend.
Bezeichnen wir 
die „Kosten“ für den Transport von Waren von einem Fach
in ein Fach 
. Bezeichnen wir 
die „Kosten“ für die Auswahl eines Containers 
für den Transport von Restbeständen aus anderen Fächern. Wie genau und in welchen Maßeinheiten die Werte berechnet werden 
und 
wird im Folgenden erörtert (siehe Abschnitt Vorbereitung der Eingangsdaten), jetzt reicht es zu sagen, dass solche Größen direkt proportional zu den Größen sein werden 
und 
entsprechend.
Bezeichnen wir mit 
eine Variable, die den Wert 1 annimmt, wenn Restbestände aus dem Fach 
in den Container transportiert werden 
, und 0 andernfalls. Bezeichnen wir mit 
eine Variable, die den Wert 1 annimmt, wenn der Container 
Restbestände an Waren enthält, und 0 andernfalls.
Die Aufgabe wird so gestellt: Es ist erforderlich, eine solche Menge von Containern zu finden 
und die Fächer-Spender auf Fächer-Container so „anzubringen“, dass die Funktion minimiert wird
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 transportieren können, den wir nicht ausgewählt haben, und entsprechend keine „Kosten“ für dessen Auswahl entstanden sind. Diese Einschränkung bedeutet auch, dass das Volumen der transportierten Waren von den Fächern in den Container die Kapazität des Containers nicht überschreiten darf. Als Lösung des Problems verstehen wir die Menge von Containern 
und die Möglichkeiten, die Fächer-Spender mit Containern zu verbinden.
Diese Formulierung des Optimierungsproblems ist nicht neu und wurde von vielen Mathematikern bereits seit Anfang der 80er Jahre des letzten Jahrhunderts untersucht. In der ausländischen Literatur gibt es zwei Optimierungsprobleme mit einem entsprechenden mathematischen Modell: und (Über die Unterschiede der Aufgaben sprechen wir später). Es sollte gesagt werden, dass in der mathematischen Literatur die Formulierung dieser beiden Optimierungsprobleme in den Begriffen der Standortwahl von Unternehmen erfolgt, daher auch der Name „Facility Location“. Dies ist größtenteils eine Hommage an die Tradition, da der Bedarf an der Lösung solcher kombinatorischer Probleme erstmals in den 50er Jahren des letzten Jahrhunderts aus der Logistik, hauptsächlich aus der militärisch-industriellen Branche, entstand. Im Kontext der Standortwahl von Unternehmen werden solche Probleme folgendermaßen formuliert:
- Es gibt eine endliche Menge von Städten, in denen potenziell Produktionsunternehmen angesiedelt werden können (folgend Städte-Produzenten genannt). Für jede Stadt-Produzent sind die Kosten für die Eröffnung eines Unternehmens sowie die Beschränkung der Produktionskapazitäten des zu eröffnenden Unternehmens gegeben.
- Es gibt eine endliche Menge von Städten, in denen sich tatsächlich Kunden befinden (folgend Städte-Kunden genannt). Für jede solche Stadt-Kunde ist das Volumen der Nachfrage nach dem Produkt angegeben. Zur Vereinfachung nehmen wir an, dass das Produkt, das die Unternehmen herstellen und die Kunden konsumieren, identisch ist.
- Für jedes Paar Stadt-Produzent und Stadt-Kunde sind die Transportkosten für die Lieferung des erforderlichen Produktvolumens vom Produzenten zum Kunden festgelegt.
Es muss herausgefunden werden, in welchen Städten Unternehmen eröffnet werden sollen und wie Kunden diesen Unternehmen zugeteilt werden sollen, um:
- Die Gesamtkosten für die Eröffnung von Unternehmen und die Transportkosten zu minimieren;
- Das Volumen der Nachfrage der an ein eröffnetes Unternehmen angeschlossenen Kunden darf die Produktionskapazitäten dieses Unternehmens nicht überschreiten.
Jetzt sollte über den einzigen Unterschied zwischen diesen beiden klassischen Aufgaben gesprochen 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 eröffneten Unternehmen beliefert werden.
Diese Unterscheidung zwischen den beiden Aufgaben erscheint auf den ersten Blick unbedeutend, führt jedoch tatsächlich zu einer völlig anderen kombinatorischen Struktur solcher Aufgaben und somit zu ganz unterschiedlichen Algorithmen zu deren Lösung. Der Unterschied zwischen den Aufgaben wird im Bild unten demonstriert.
Abb. 3. a) Multi-Source Capacitated Facility Location Problem
Abb. 3. b) Single-Source Capacitated Facility Location Problem
Beide Aufgaben 
-schwierig, das heißt, es gibt keinen genauen Algorithmus, der ein solches Problem in polynomialer Zeit in Bezug auf die Größe der Eingabedaten lösen könnte. Einfacher ausgedrückt, werden alle genauen Algorithmen zur Lösung dieses Problems exponentielle Zeit benötigen, obwohl sie möglicherweise schneller sind als ein vollständiger Erschöpfungsansatz. Da das Problem 
-schwierig ist, werden wir nur annähernde Heuristiken betrachten, das heißt, Algorithmen, die stabil Lösungen berechnen, die sehr nahe am Optimalen liegen, und die schnell genug arbeiten. Wenn Interesse an solchen Problemen besteht, kann hier eine gute Übersicht auf Russisch gefunden werden.
Wenn wir die Terminologie unseres Problems des optimalen Komprimierens von Waren in Zellen verwenden, dann:
- Städte-Kunden sind Zellen-Donoren
mit Warenrückständen, - Städte-Produzenten sind Zellen-Container , in die die Rückstände aus anderen Zellen platziert werden sollen,
- Transportkosten sind Zeitkosten des Lageristen für den Transport des Warenvolumens aus der Zelle-Donor in die Zelle-Container ;
- Kosten für die Gründung des Unternehmens sind die Kosten für die Auswahl des Containers , die dem Volumen der Zelle-Container entsprechen , multipliziert mit einem bestimmten Faktor zur Einsparung von freien Kapazitäten (der Wert des Faktors ist immer > 1) (siehe Abschnitt zur Vorbereitung der Eingangsdaten).
mit Warenrückständen, 
, in die die Rückstände aus anderen Zellen platziert werden sollen,
des Lageristen für den Transport des Warenvolumens aus der Zelle-Donor 
in die Zelle-Container 
; 
, die dem Volumen der Zelle-Container entsprechen 
, multipliziert mit einem bestimmten Faktor zur Einsparung von freien Kapazitäten (der Wert des Faktors ist immer > 1) (siehe Abschnitt zur Vorbereitung der Eingangsdaten).Nachdem die Analogie zu den bekannten klassischen Lieferproblemen gezogen wurde, muss eine wichtige Frage beantwortet werden, die die Wahl der Architektur des Lösungsalgorithmus beeinflusst: Ist der Transport der Rückstände aus der Zelle-Donor nur in einen und nur einen Container (Single-Source) möglich, oder kann der Transport der Rückstände in mehrere Zellen-Container (Multi-Source) erfolgen?
Es ist zu beachten, dass in der Praxis beide Problemstellungen auftreten können. Im Folgenden werden die „Pro“ und „Contra“ für jede dieser Problemstellungen aufgeführt:
| Varianten des Problems | Vorteile der Variante | Nachteile der Variante |
|---|---|---|
| Single-Source | Die Warentransportoperationen, die nach dieser Variante des Problems berechnet werden:
| |
| Multi-Source | Die Kompressionen, die für diese Aufgabenstellung berechnet wurden, sind in der Regel um 10-15% kompakter im Vergleich zu den Kompressionen, die nach der Option «Single-Source» berechnet wurden. Es sei jedoch auch erwähnt, dass je geringer die Anzahl der Bestände in den Spender-Fächern ist, desto geringer ist der Unterschied in der Kompaktheit. | Die Warentransportoperationen, die nach dieser Variante des Problems berechnet werden:
|
Tabelle 1. Vor- und Nachteile der Optionen Single-Source und Multi-Source.
Da die Anzahl der Vorteile bei der Option Single-Source höher ist und auch unter Berücksichtigung der Tatsache, dass je geringer die Anzahl der Bestände in den Spender-Fächern ist, der Unterschied in der Kompaktheit der Kompression, die für beide Optionen berechnet wurde, geringer ist, fiel unsere Wahl auf die Option Single-Source.
Es sei erwähnt, dass die Entscheidung für die Option Multi-Source ebenfalls legitim ist. Es gibt viele effektive Algorithmen zur Lösung, von denen die meisten darin bestehen, eine Reihe von Transportproblemen zu lösen. Darüber hinaus gibt es nicht nur effektive, sondern auch elegante Algorithmen, beispielsweise:
Vorbereitung der Eingabedaten.
Bevor wir mit der Analyse und Entwicklung des Algorithmus zur Lösung des Problems beginnen, müssen wir festlegen, welche Daten und in welcher Form wir sie ihm zur Eingabe bereitstellen. Bei den Beständen der Waren in den Spender-Fächern und dem Volumen der Container-Fächer gibt es keine Probleme, da dies trivial ist – solche Größen werden in m3 gemessen, aber bei den Kosten für die Nutzung des Container-Fachs und der Kostenmatrix für den Transport ist es nicht so einfach!
Beginnen wir mit der Berechnung Kosten für die Warenverlagerung von der Regalezelle zum Container. Zunächst müssen wir klären, in welchen Maßeinheiten wir die Kosten für die Verlagerung berechnen wollen. Zwei naheliegende Optionen sind Meter und Sekunden. Es ist sinnlos, die Kosten für die Verlagerung in „reinen“ Metern zu berechnen. Dies zeigen wir am Beispiel. Angenommen, die Regalezelle 
befindet sich auf der ersten Ebene, die Regalezelle 
ist 30 Meter entfernt und befindet sich auf der zweiten Ebene:
- Die Verlagerung von in ist kostenintensiver als die Verlagerung von in , da es einfacher ist, von der zweiten Ebene (1,5-2 Meter über dem Boden) nach unten zu senken, als auf die zweite Ebene zu heben, obwohl die zurückgelegte Strecke gleich ist.
- Es ist einfacher, 1 Stück Ware aus der Regalezelle in zu verlagern, als 10 Stück derselben Ware, obwohl die zurückgelegte Strecke gleich sein wird.
in 
ist kostenintensiver als die Verlagerung von 
in 
, da es einfacher ist, von der zweiten Ebene (1,5-2 Meter über dem Boden) nach unten zu senken, als auf die zweite Ebene zu heben, obwohl die zurückgelegte Strecke gleich ist.
in 
zu verlagern, als 10 Stück derselben Ware, obwohl die zurückgelegte Strecke gleich sein wird.Die Kosten für die Verlagerung sollten besser in Sekunden erfasst werden, da dies sowohl Unterschiede in den Ebenen als auch Unterschiede in der verlagerten Warenmenge berücksichtigt. Um die Kosten für die Verlagerung in Sekunden zu berechnen, müssen wir den Verlagerungsprozess in elementare Bestandteile zerlegen und die Zeit für die Durchführung jedes einzelnen Elements messen.
Angenommen, aus der Regalezelle 
werden 
Stück Ware in den Container 
verlagert. Angenommen, 
ist die durchschnittliche Bewegungsgeschwindigkeit des Mitarbeiters im Lager, gemessen in m/s. Angenommen, 
und 
sind die durchschnittlichen Geschwindigkeiten für das einmalige Ausführen der Aktionen 'nehmen' und 'abladen' entsprechend für ein Warenvolumen von 4 dm³ (das durchschnittliche Volumen, das ein Mitarbeiter im Lager bei der Ausführung von Aktionen aufnimmt). Angenommen, 
und 
sind die Höhen der Regalen, aus denen die Aktionen 'nehmen' und 'abladen' durchgeführt werden. Zum Beispiel ist die durchschnittliche Höhe der ersten Ebene (Boden) 1 m, die zweite Ebene 2 m usw. Daher lautet die Formel zur Berechnung der Gesamtzeit für die Durchführung des Verlagerungsprozesses 
wie folgt:
In Tabelle 2 sind die Statistiken für die Durchführung jeder elementaren Operation aufgeführt, die von den Lagermitarbeitern unter Berücksichtigung der Spezifik des gelagerten Gutes gesammelt wurden.
| Bezeichnung der Operation | Bezeichnung | Durchschnittswert |
|---|---|---|
| Durchschnittliche Bewegungsgeschwindigkeit des Mitarbeiters im Lager |  | 1,5 m/s |
| Durchschnittsgeschwindigkeit für die Ausführung einer Aktion 'abladen' (für ein Warenvolumen von 4 dm³) |  | 2,4 s |
Tabelle 2. Durchschnittliche Zeit für die Durchführung von Lageroperationen
Wir haben uns für die Methode zur Berechnung der Kosten für die Verlagerung entschieden. Jetzt müssen wir herausfinden, wie man die Kosten für die Auswahl der Regalezelle berechnet. Hier ist alles viel, viel komplizierter als bei den Umzugskosten, da:
- Erstens müssen die Kosten in direkter Abhängigkeit vom Volumen des Containers stehen – das gleiche Volumen an Restbeständen, das aus den Spenderboxen bewegt wird, sollte besser in einen kleineren Container als in einen großen Container gelegt werden, vorausgesetzt, dass dieses Volumen in beide Container vollständig passt. So streben wir, indem wir die Gesamtkosten für die Wahl der Container minimieren, an, die "knappen" freien Lagerkapazitäten im Bereich der Kommissionierung zu sparen, um die anschließenden Produktplatzierungsoperationen in den Boxen durchzuführen. Abbildung 4 zeigt Varianten der Bewegung von Restbeständen in große und kleine Container sowie die Folgen solcher Bewegungen bei der Durchführung nachfolgender Lageroperationen.
- Zweitens, da wir in der Lösung der ursprünglichen Aufgabe gerade die Gesamtkosten minimieren müssen, die sich aus den Umzugskosten und den Kosten für die Wahl der Container zusammensetzen, müssen die Volumina der Boxen in Kubikmetern irgendwie mit Sekunden in Verbindung gebracht werden, was alles andere als trivial ist.
Abb. 4. Varianten der Bewegung von Restbeständen in Container unterschiedlicher Kapazität.
In Abbildung 4 ist das Volumen der Restbestände, das bereits nicht mehr in den Container beim zweiten Platzierungsbereich passt, in roter Farbe dargestellt.
Um die Kubikmeter der Kosten für die Wahl des Containers mit den Sekunden der Umzugskosten zu verknüpfen, gelten folgende Anforderungen an die zu berechnenden Lösungen der Aufgabe:
- Es ist erforderlich, dass die Restbestände aus der Spenderbox in jeden Fall in die Containerbox bewegt werden, wenn dies die Gesamtzahl der Containerboxen, in denen sich die Ware befindet, verringert.
- Es muss ein Gleichgewicht zwischen den Volumen der Container und den Zeitkosten für Umzüge gewahrt bleiben: Wenn beispielsweise in einer neuen Lösungsvariante im Vergleich zur vorherigen Lösung der Gewinn im Volumen groß ist und der Verlust an Zeitkosten gering ist, sollte die neue Variante 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 herauszufinden. Angenommen, es gibt eine Containerbox mit einem Volumen 
, in die die Restbestände von Produkten aus den Spenderboxen zugewiesen sind, und die Gesamtzeit für diese Bewegung beträgt 
. Lassen Sie uns auch einige alternative Optionen zur Platzierung derselben Menge an Waren aus denselben Spenderzellen in andere Container berücksichtigen, wobei jede Platzierung ihre eigenen Bewertungen hat. 
<
und 
>
.
Die Frage ist: Was ist der minimale Gewinn an Volumen, 
der akzeptabel ist, bei einem vorgegebenen Zeitverlust. 
? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.
Abb. 5. Diagramm der Abhängigkeit der minimalen akzeptablen Volumeneinsparung von der erhöhten Zeitdifferenz für die Durchführung der Operation.
Das heißt, wenn die zusätzlichen Kosten in der Zeit 40 Sekunden betragen, sind wir bereit, diese nur auszugeben, wenn der Gewinn an Volumen mindestens 500 dm³ beträgt. Trotz der gewissen Nichtlinearität in der Abhängigkeit nehmen wir zur Vereinfachung weiterer Berechnungen an, dass die Beziehung zwischen den Größen linear ist und durch eine Ungleichung beschrieben wird.
Im folgenden Bild betrachten wir die folgenden Methoden zur Platzierung von Waren in Containern.
Abb. 6. Variante (a): 2 Container, Gesamtvolumen 400 dm³, Gesamtzeit 150 Sek.
Abb. 6. Variante (b): 2 Container, Gesamtvolumen 600 dm³, Gesamtzeit 190 Sek.
Abb. 6. Variante (c): 1 Container, Gesamtvolumen 400 dm³, Gesamtzeit 200 Sek.
Variante (a) der Containerwahl ist bevorzugter als die ursprüngliche Variante, da die Ungleichung erfüllt ist: (800-400)/10 >= 150-120, woraus folgt, dass 40 >= 30. Variante (b) ist weniger bevorzugt als die ursprüngliche Variante, da die Ungleichung nicht erfüllt ist: (800-600)/10 >= 190-150, woraus folgt, dass 20 >= 40. Aber Variante (c) passt nicht in diese Logik! Lassen Sie uns diese Variante genauer betrachten. Auf der einen Seite ist die Ungleichung (800-400)/10 >= 200-120, was bedeutet, dass die Ungleichung 40 >= 80 nicht erfüllt ist, was darauf hinweist, dass der Gewinn an Volumen einen solchen großen Zeitverlust nicht wert ist.
Auf der anderen Seite reduzieren wir in dieser Variante (c) nicht nur das gesamte beanspruchte Volumen, sondern verringern auch die Anzahl der belegten Zellen, was eines der zwei wichtigen Anforderungen an die berechneten Lösungen für die oben genannten Aufgaben darstellt. Offensichtlich muss eine bestimmte positive Konstante zur linken Seite der Ungleichung hinzugefügt werden, damit diese Anforderung erfüllt wird. 
, und zwar nur dann, wenn die Anzahl der Container verringert wird. Lassen Sie uns erinnern, dass 
— dies eine Variable ist, die 1 ist, wenn der Container 
ausgewählt ist, und 0, wenn der Container. 
nicht ausgewählt. Bezeichnen wir 
– eine Menge von Containern in der ursprünglichen Lösung und 
– eine Menge von Containern in der neuen Lösung. Im Allgemeinen wird die neue Ungleichung folgendermaßen aussehen:
Indem wir die obenstehende Ungleichung umformen, erhalten wir
Aus diesem ergibt sich die Formel zur Berechnung der Gesamtkosten 
einer bestimmten Variante der Problemstellung:
Aber jetzt stellt sich die Frage: welchen Wert sollte eine solche Konstante haben 
? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.
Seien 
– der maximale Abstand zwischen den Lagerzellen einer Zone ABC, der in unserem Fall 100 m beträgt. Seien 
– das maximale Volumen einer Lagerzelle-Container, das in unserem Fall 1000 dm3 beträgt.
Die erste Methode zur Berechnung der Größe 
. Betrachten wir eine Situation, in der es 2 Container auf der ersten Ebene gibt, in denen bereits physisch Waren vorhanden sind, das heißt, sie sind selbst die Zellenspender, und die Kosten für die Bewegung der Waren in dieselben Zellen betragen natürlich 0. Es ist notwendig, einen solchen Wert der Konstante zu finden 
, bei dem es immer vorteilhaft wäre, die Restbestände von Container 1 in Container 2 zu verschieben. Indem wir die Werte einsetzen 
und 
in die oben angegebene Ungleichung, erhalten wir:
woraus folgt
Indem wir die Werte der durchschnittlichen Zeit für die Durchführung elementarer Operationen in die obenstehende Formel einsetzen, erhalten wir
Die zweite Methode zur Berechnung der Größe 
. Betrachten wir eine Situation, in der es gibt 
Zellenspender, aus denen geplant ist, die Waren in Container 1 zu verschieben. Bezeichnen wir 
– den Abstand von der Zellenspender 
zum Container 1. Es gibt auch Container 2, in dem bereits Waren vorhanden sind und dessen Volumen es ermöglicht, die Restbestände aus allen 
Zellen unterzubringen. Zur Vereinfachung nehmen wir an, dass das Volumen der Waren, die aus den Zellenspendern in die Container verschoben werden, gleich und beträgt 
. Es ist erforderlich, einen solchen Wert der Konstante zu finden 
, bei dem die Platzierung aller Restbestände aus 
Zellen in Container 2 immer vorteilhafter wäre, als ihre Platzierung in verschiedene Container:
Indem wir die Ungleichung umformen, 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 der Verdichtung von Restbeständen im Lager beteiligt sind, beträgt 10. Indem wir die bekannten Werte einsetzen, erhalten wir den folgenden Wert der Konstante
Wir nehmen den größten Wert, der nach jeder Variante berechnet wurde, und das wird der Wert der Größe 
für die gegebenen Parameter des Lagers sein. Jetzt, um die Vollständigkeit abzuschließen, schreiben wir die Formel zur Berechnung der Gesamtkosten 
für eine bestimmte zulässige Lösung 
:
Jetzt, nach all den titanischen Anstrengungen zur Umwandlung der Eingabedaten, können wir sagen, dass alle Eingabedaten in die gewünschte Form umgewandelt und bereit sind, im Optimierungsalgorithmus verwendet zu werden.
Fazit
Die Praxis zeigt, dass der Aufwand und die Bedeutung der Phase der Vorbereitung und Umwandlung der Eingabedaten für den Algorithmus oft unterschätzt wird. In diesem Artikel haben wir speziell viel Aufmerksamkeit auf diese Phase gerichtet, um zu zeigen, dass nur qualitativ hochwertige und klug vorbereitete Eingabedaten die Entscheidungen, die der Algorithmus berechnet, für den Kunden tatsächlich wertvoll machen können. Ja, es gab viele Ableitungen von Formeln, aber wir haben Sie noch vor dem Wettkampf gewarnt 🙂
Im nächsten Artikel werden wir endlich zu dem Punkt kommen, warum die letzten zwei Veröffentlichungen gedacht wurden – zum Algorithmus der diskreten Optimierung.
Der Artikel wurde erstellt von
Roman Schangin, Programmierer in der Abteilung Projekte,
Unternehmen Erster Bit, Stadt Tscheljabinsk
Quelle: habr.com
