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

In diesem Artikel erfahren Sie, wie Sie das Problem des Mangels an freien Zellen im Lager lösen und einen diskreten Optimierungsalgorithmus entwickeln, um dieses Problem zu lösen. Wir werden darüber sprechen, wie wir das mathematische Modell des Optimierungsproblems „erstellt“ haben und auf welche Schwierigkeiten wir bei der Verarbeitung der Eingabedaten für den Algorithmus unerwartet gestoßen sind.

Wenn Sie sich für mathematische Anwendungen in der Wirtschaft interessieren und keine Angst vor identischen Formulentransformationen in der 5. Klasse haben, dann sind Sie bei cat willkommen!

Der Artikel ist nützlich für diejenigen, die WMS- Systeme implementieren, in der Lager- oder Produktionslogistikbranche arbeiten, sowie für Programmierer, die sich für mathematische Anwendungen in der Geschäfts- und Prozessoptimierung im Unternehmen interessieren.

Einführungsteil

Diese Veröffentlichung setzt die Artikelserie fort, in der wir unsere erfolgreichen Erfahrungen bei der Implementierung von Optimierungsalgorithmen in Lagerprozessen teilen.

Im vorherigen Artikel wurden die Besonderheiten des Lagers beschrieben, in dem wir das WMS- System eingeführt haben, und es wurde auch erläutert, warum wir das Problem der Bündelung von Warenbeständen bei der Implementierung des WMS- Systems lösen mussten und wie wir dies getan haben.

Als wir mit dem Schreiben eines Artikels über Optimierungsalgorithmen fertig waren, stellte sich heraus, dass dieser sehr umfangreich war. Daher haben wir beschlossen, das angesammelte Material in zwei Teile zu unterteilen:

• Im ersten Teil (diesem Artikel) werden wir darüber sprechen, wie wir das mathematische Modell des Problems „erstellt“ haben und auf welche großen Schwierigkeiten wir plötzlich bei der Verarbeitung und Konvertierung von Eingabedaten für den Algorithmus gestoßen sind.
• Im zweiten Teil werden wir die Implementierung des Algorithmus in C ++ im Detail untersuchen, ein Computerexperiment durchführen und die Erfahrungen zusammenfassen, die wir bei der Implementierung solcher „intelligenten Technologien“ in den Geschäftsprozessen des Kunden gesammelt haben.

Wie man einen Artikel liest. Wenn Sie den vorherigen Artikel gelesen haben, können Sie sofort zum Kapitel "Überblick über vorhandene Lösungen" gehen. Wenn nicht, finden Sie die Beschreibung des zu lösenden Problems im Spoiler unten.

Übersicht bestehender Lösungen

Bevor wir mit der Beschreibung der von uns entwickelten Algorithmen fortfahren, sollten wir einen kurzen Überblick über die auf dem Markt vorhandenen WMS- Systeme geben, die ähnliche optimale Komprimierungsfunktionen implementieren.

Zunächst ist das Produkt „1C: Enterprise 8. WMS Logistics. Warehouse Management 4 ”, das 1C gehört und von ihm repliziert wird und zur vierten Generation von WMS- Systemen gehört, die von AXELOT entwickelt wurden. In diesem System wird die Komprimierungsfunktionalität deklariert, mit der unterschiedliche Produktreste in einer gemeinsamen Zelle kombiniert werden sollen. Es ist erwähnenswert, dass die Komprimierungsfunktionalität in einem solchen System auch andere Funktionen umfasst, z. B. das Korrigieren der Platzierung von Waren in Zellen gemäß ihren ABC-Klassen, aber wir werden nicht darauf eingehen.

Wenn Sie den Code des Systems "1C: Enterprise 8. WMS Logistics. Warehouse Management 4 ”(das in diesem Teil der Funktion geöffnet ist), dann können wir Folgendes schließen. Der Restkomprimierungsalgorithmus implementiert eine eher primitive lineare Logik, und von einer „optimalen“ Komprimierung kann keine Rede sein. Natürlich sieht er keine Bündelung von Parteien vor. Mehrere Kunden mit einem solchen implementierten System beschwerten sich über die Ergebnisse der Komprimierungsplanung. Beispielsweise trat in der Praxis während der Komprimierung häufig die folgende Situation auf: 100 Stk. Es ist geplant, die restlichen Waren von einer Zelle in eine andere Zelle zu bringen, in der 1 Stück liegt. Waren, obwohl es zeitlich optimal ist, das Gegenteil zu tun.

Auch die Komprimierungsfunktionalität der Restgüter in den Zellen wird in vielen fremden WMS- Systemen deklariert, aber leider haben wir kein wirkliches Feedback zur Effizienz der Algorithmen (dies ist ein Geschäftsgeheimnis) und noch mehr zur Tiefe ihrer Logik (proprietäre Software mit geschlossenem Code). Wir haben keine, daher können wir nicht beurteilen.

Suchen Sie nach einem mathematischen Modell eines Problems

Um qualitativ hochwertige Algorithmen zur Lösung eines Problems zu entwerfen, ist es zunächst erforderlich, dieses Problem mathematisch klar zu formulieren, was wir tun werden.

Es gibt viele Zellen $$$J$ in denen die Überreste einiger Waren. Ferner werden solche Zellen Spenderzellen genannt. Wir bezeichnen $$$w_j$ Warenvolumen in der Zelle $$$$ j$ $.

Es ist wichtig zu sagen, dass nur ein Produkt einer Sendung oder mehrere Sendungen, die zuvor in einem Cluster zusammengefasst waren (siehe vorherigen Artikel ), am Komprimierungsverfahren teilnehmen können, was auf die Besonderheiten der Lagerung und Verpackung von Waren zurückzuführen ist. Für verschiedene Produkte oder verschiedene Stapelcluster sollte ein separates Komprimierungsverfahren gestartet werden.

Es gibt viele Zellen $$$I$ in die möglicherweise Reste von Spenderzellen eingebracht werden können. Solche Zellen werden Containerzellen genannt. Dies können entweder freie Zellen im Lager oder Spenderzellen aus einer Vielzahl von sein $$$J$ . Immer viel $$$J$ ist eine Teilmenge von $$$I$ .

Für jede Zelle $$$i$ von vielen $$$I$ Kapazitätsgrenzen festgelegt $$$d_i$ gemessen in dm3. Ein dm3 ist ein Würfel mit einer Seitenlänge von 10 cm. Die im Lager gelagerten Produkte sind ziemlich groß, daher reicht in diesem Fall eine solche Diskretisierung aus.

Die Matrix der kürzesten Entfernungen $$$s_ {ij}$ in Metern zwischen jedem Zellenpaar $$$(i, j)$ wo $$$i$ und $$$j$ gehören zu den Sets $$$I$ und $$$J$ entsprechend.

Wir bezeichnen $$$S_ {ij}$ "Kosten" für den Transport von Waren aus der Zelle $$$i$ zu Zelle $$$j$ . Wir bezeichnen $$$D_i$ "Kosten" für die Auswahl eines Containers $$$i$ Reste aus anderen Zellen hinein zu bewegen. Wie genau und in welchen Maßeinheiten werden die Werte berechnet $$$S_ {ij}$ und $$$D_i$ Wir werden weiter darauf eingehen (siehe Abschnitt Vorbereitung der Eingabedaten). Jetzt reicht es zu sagen, dass solche Mengen direkt proportional zu den Mengen sind $$$s_ {ij}$ und $$$d_i$ entsprechend.

Bezeichnen mit $$$x_ {ij}$ eine Variable mit dem Wert 1, wenn der Rest der Zelle $$$j$ zum Container bewegen $$$i$ und sonst 0. Bezeichnen mit $$$y_i$ Variable mit dem Wert 1, wenn Container $$$i$ enthält die Reste des Produkts und sonst 0.

Die Aufgabe ist wie folgt : Es ist notwendig, so viele Container zu finden $$$I ^ *$ und somit Spenderzellen an Zellbehälter "anhängen", um die Funktion zu minimieren

$$

$$\ min {F} = \ sum _ {i \ in I, ~ j \ in J} ^ {} S_ {ij} \ cdot x_ {ij} + \ sum _ {i \ in I} ^ {} D_ { i} \ cdot y_ {i}$$

unter Einschränkungen

$$

$$\ sum _ {j \ in J} ^ {} w_ {j} \ cdot x_ {ij} \ leq d_ {i} \ cdot y_ {i}, ~ für ~ alle ~ i \ in I$$

Insgesamt suchen wir im Verlauf der Berechnung der Lösung des Problems:

• Erstens: Speichern Sie Speicherkapazität.
• Zweitens sparen Sie den Ladenbesitzern Zeit.

Die letzte Einschränkung bedeutet, dass wir keine Waren in einen Container umlagern können, den wir nicht ausgewählt haben, und daher für ihre Wahl keine „Kosten“ entstanden sind. Diese Einschränkung bedeutet auch, dass das Volumen der von den Zellen zum Container transportierten Waren die Kapazität des Containers nicht überschreiten darf. Mit der Lösung des Problems meinen wir viele Container $$$I ^ *$ und Verfahren zum Anbringen von Spenderzellen an Behältern.

Diese Formulierung des Optimierungsproblems ist nicht neu und wurde von vielen Mathematikern seit Beginn der 80er Jahre des letzten Jahrhunderts untersucht. In der ausländischen Literatur gibt es zwei Optimierungsprobleme mit einem geeigneten mathematischen Modell: das Problem des Standortes einer kapazitiven Einrichtung aus einer Quelle und das Standortproblem einer kapazitiven Einrichtung aus mehreren Quellen (wir werden die Unterschiede zwischen den folgenden Aufgaben diskutieren). Es ist anzumerken, dass in der mathematischen Literatur die Aussagen dieser beiden Optimierungsprobleme in Bezug auf die Lokalisierung von Unternehmen vor Ort formuliert sind, daher der Name „Standort der Einrichtung“. Zum größten Teil ist dies eine Hommage an die Tradition, da die Notwendigkeit zur Lösung solcher kombinatorischen Probleme zum ersten Mal aus dem Bereich der Logistik stammte, zum größten Teil aus dem militärisch-industriellen Wachstum in den 50er Jahren des letzten Jahrhunderts. In Bezug auf den Unternehmensstandort werden solche Aufgaben wie folgt formuliert:

• Es gibt eine begrenzte Anzahl von Städten, in denen es möglicherweise möglich ist, produzierende Unternehmen zu lokalisieren (im Folgenden: produzierende Städte). Für jede Fertigungsstadt werden die Kosten für die Eröffnung eines Unternehmens in ihr sowie eine Beschränkung der Produktionskapazität des darin eröffneten Unternehmens festgelegt.
• Es gibt eine begrenzte Anzahl von Städten, in denen sich Kunden tatsächlich befinden (im Folgenden als Kundenstädte bezeichnet). Für jede dieser Kundenstädte wird das Nachfragevolumen nach Produkten festgelegt. Der Einfachheit halber gehen wir davon aus, dass das Produkt, das Unternehmen produzieren und konsumieren, eines ist.
• Für jedes Paar, die Herstellerstadt und die Kundenstadt, wird der Wert der Transportkosten für die Lieferung des erforderlichen Produktvolumens vom Hersteller an den Kunden festgelegt.

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

• Die Gesamtkosten für die Eröffnung von Unternehmen und die Transportkosten waren minimal;
• Das Volumen der Kundennachfrage, das mit einem offenen Unternehmen verbunden ist, hat die Produktionskapazitäten dieses Unternehmens nicht überschritten.

Nun ist der einzige Unterschied zwischen diesen beiden klassischen Problemen zu erwähnen:

• Standortproblem einer kapazitiven Einrichtung aus einer Hand - Der Client wird nur von einem offenen Unternehmen geliefert.
• Standortproblem einer kapazitiven Einrichtung mit mehreren Quellen - Ein Kunde kann gleichzeitig von mehreren offenen Unternehmen beliefert werden.

Ein solcher Unterschied zwischen den beiden Problemen ist auf den ersten Blick unbedeutend, führt jedoch tatsächlich zu einer völlig anderen kombinatorischen Struktur solcher Probleme und infolgedessen zu völlig unterschiedlichen Algorithmen zu ihrer Lösung. Die Unterschiede zwischen den Aufgaben sind in der folgenden Abbildung dargestellt.


Abb. 3. a) Problem mit dem Standort der Anlage mit mehreren Quellen


Abb. 3. b) Problem mit dem Standort einer kapazitiven Einrichtung aus einer Hand

Beide Aufgaben $$$NP$ sind schwierig, das heißt, es gibt keinen genauen Algorithmus, der ein solches Problem in Polynomzeit aus der Größe der Eingabedaten lösen würde. Mit einfacheren Worten, alle genauen Algorithmen zur Lösung des Problems funktionieren exponentiell, obwohl sie möglicherweise schneller sind als eine vollständige Suche nach den Optionen in der Stirn. Seit der Aufgabe $$$NP$ ist schwierig, dann werden wir nur ungefähre Heuristiken betrachten, dh Algorithmen, die Lösungen sehr nahe am Optimum stabil berechnen und schnell genug arbeiten. Wenn Interesse an einer solchen Aufgabe besteht, finden Sie hier eine gute Bewertung in russischer Sprache.

Wenn wir zur Terminologie unseres Problems der optimalen Komprimierung von Waren in Zellen übergehen, dann:

• Kundenstädte sind Spenderzellen $$$J$ mit den Resten der Ware,
• Fertigungsstädte - Containerzellen $$$I$ , in dem es die Überreste anderer Zellen platzieren soll,
• Transportkosten - Zeitkosten $$$S_ {ij}$ Ladenbesitzer, um das Warenvolumen aus der Spenderzelle zu bewegen $$$j$ zur Containerzelle $$$i$ ;;
• die Kosten für die Eröffnung eines Unternehmens - die Kosten für die Auswahl eines Containers $$$D_i$ gleich dem Volumen der Containerzelle $$$i$ multipliziert mit einem bestimmten Wirtschaftlichkeitskoeffizienten der freien Volumina (der Wert des Koeffizienten ist immer> 1) (siehe Abschnitt zur Vorbereitung der Eingabedaten).

Nachdem die Analogie zu den bekannten klassischen Zustellungen des Problems gezogen wurde, muss die wichtige Frage beantwortet werden, von der die Wahl der Architektur des Lösungsalgorithmus abhängt: Die Bewegung von Resten aus der Spenderzelle ist nur in einem und nur einem Behälter (Single-Source) möglich, oder die Bewegung von Resten ist möglich in mehrere Containerzellen (Multi-Source)?

Es ist erwähnenswert, dass in der Praxis beide Formulierungen des Problems einen Platz haben. Wir geben alle Vor- und Nachteile für jede dieser Aussagen unten an:
Tabelle 1. Vor- und Nachteile der Optionen "Single Source" und "Multi Source".

Da die Anzahl der Pluspunkte für die Single-Source-Option größer ist und auch die Tatsache berücksichtigt wird, dass je kleiner die Anzahl der Reste in den Spenderzellen ist, desto geringer der Unterschied im Grad der Kompressionskompaktheit ist, der für beide Versionen des Problems berechnet wurde, fiel unsere Wahl auf die Single-Quelle. Quelle

Es ist anzumerken, dass die Lösung der Multi-Source-Option ebenfalls stattfindet. Es gibt eine große Anzahl effektiver Algorithmen zur Lösung, von denen die meisten auf die Lösung einer Reihe von Transportproblemen hinauslaufen. Hier gibt es beispielsweise nicht nur effiziente, sondern auch elegante Algorithmen .

Eingabevorbereitung

Bevor Sie mit der Analyse und Entwicklung eines Algorithmus zur Lösung des Problems fortfahren, müssen Sie festlegen, welche Daten und in welcher Form wir sie an die Eingabe senden. Es gibt keine Probleme mit dem in den Spenderzellen verbleibenden Warenvolumen und der Kapazität der Behälterzellen, da dies trivial ist - solche Werte werden in m3 gemessen, aber mit den Kosten für die Verwendung des Behälterbehälters und den Kosten für die Bewegung der Matrix ist dies nicht so einfach!

Zunächst betrachten wir die Berechnung der Kosten für den Transport von Waren von einer Spenderzelle in eine Containerzelle. Zunächst muss festgelegt werden, in welchen Maßeinheiten wir die Umzugskosten berechnen. Die zwei offensichtlichsten Optionen sind Meter und Sekunden. In "sauberen" Messgeräten sind die Umzugskosten sinnlos. Wir zeigen dies am Beispiel. Lass die Zelle $$$A$ befindet sich auf der ersten Ebene, Zelle $$$Bis$ 30 Meter entfernt und befindet sich auf der zweiten Ebene:

• Ausziehen $$$A$ in $$$B$ teurer als Umzug von $$$B$ in $$$A$ , da das Absenken von der zweiten Stufe (1,5 bis 2 Meter über dem Boden) einfacher ist als das Anheben auf die zweite Stufe, obwohl der Abstand gleich ist;
• 1 Stk. Bewegen. Waren aus der Zelle $$$A$ in $$$B$ Es ist einfacher als 10 Stück zu bewegen. des gleichen Produkts, obwohl der Abstand gleich sein wird.

Bewegungskosten werden am besten in Sekunden berücksichtigt, da Sie so den Unterschied in den Ebenen und den Unterschied in der Menge der transportierten Waren berücksichtigen können. Um die Bewegungskosten in Sekunden zu berücksichtigen, müssen wir den Bewegungsvorgang in Elementarkomponenten zerlegen und für jede Elementarkomponente Zeitmessungen durchführen.

Aus der Zelle lassen $$$j$ bewegt sich $$$N_j$ Stk Waren zum Container $$$i$ . Lass $$$S_ {run}$ - die durchschnittliche Geschwindigkeit des Mitarbeiters im Lager, gemessen in m / s. Lass $$$S_ {get}$ und $$$S_ {put}$ - Durchschnittsgeschwindigkeit einer einzelnen Ausführung von Vorgängen für das Warenvolumen von 4 dm3 (das durchschnittliche Volumen, das ein Mitarbeiter im Lager während des Vorgangs einmal benötigt). Lass $$$H_ {get}$ und $$$H_ {put}$ Die Höhe der Zellen, von denen aus die Operationen ausgeführt werden, wird entsprechend genommen und platziert. Beispielsweise beträgt die durchschnittliche Höhe der ersten Stufe (Etage) 1 m, der zweiten Stufe 2 m usw. Dann die Formel zur Berechnung der Gesamtzeit, um den Verschiebevorgang abzuschließen $$$T_ {ij}$ Folgendes:

$$

$$T_ {ij} = \ left (N_ {j} \ cdot \ frac {w_ {j}} {4} \ right) \ cdot S_ {get} \ cdot H_ {get} + s_ {ij} \ cdot S_ { run} + \ left (N_ {j} \ cdot \ frac {w_ {j}} {4} \ right) \ cdot S_ {put} \ cdot H_ {put}.$$

Tabelle 2 zeigt die Statistiken der Ausführungszeit jeder Elementaroperation, die vom Lagermitarbeiter unter Berücksichtigung der Besonderheiten der gelagerten Waren gesammelt wurden.
Tabelle 2. Die durchschnittliche Zeit für die Durchführung von Lageroperationen

Mit der Methode zur Berechnung der Umzugskosten entschieden. Jetzt müssen Sie herausfinden, wie die Kosten für die Auswahl einer Containerzelle berechnet werden. Hier ist alles viel, viel komplizierter als mit den Umzugskosten, weil:

• -, – , -, , , , . , , «» , . 4 .
• zweitens, da wir die Gesamtkosten bei der Lösung des anfänglichen Problems minimieren müssen und dies die Summe sowohl der Kosten für den Umzug als auch der Kosten für die Auswahl der Container ist, müssen die Zellvolumina in Kubikmetern irgendwie mit Sekunden verknüpft werden, was alles andere als trivial ist.

Abb. 4. Optionen zum Verschieben von Rückständen in Behälter mit unterschiedlichen Kapazitäten.

Abbildung 4 zeigt in rot das Volumen der Rückstände, die in der zweiten Phase der Platzierung nachfolgender Waren nicht mehr in den Behälter passen.

Die folgenden Anforderungen für berechnete Lösungen für das Problem helfen dabei, Kubikmeter Containerkosten mit den Sekunden Transportkosten zu verbinden:

• In jedem Fall müssen die Rückstände aus der Spenderzelle in die Behälterzelle verbracht werden, wenn dies die Gesamtzahl der Behälterzellen verringert, in denen sich die Waren befinden.
• Es ist notwendig, ein Gleichgewicht zwischen dem Volumen der Container und der für den Umzug aufgewendeten Zeit herzustellen. Wenn beispielsweise die neue Lösung des Problems mit einem großen Volumengewinn verglichen wird und der Zeitverlust gering ist, müssen Sie eine neue auswählen.

Beginnen wir mit der letzten Anforderung. Um das mehrdeutige Wort „Balance“ zu spezifizieren, haben wir eine Umfrage unter Lagermitarbeitern durchgeführt, um Folgendes herauszufinden. Es sei ein Zellcontainervolumen vorhanden$$$d_0$ , in dem die Bewegung der Warenreste aus Spenderzellen zugeordnet ist und die Gesamtzeit einer solchen Bewegung beträgt $$$T_0$ . Angenommen, es gibt mehrere alternative Optionen, um dieselbe Menge von Waren aus denselben Spenderzellen in andere Behälter zu legen, wobei jede Platzierung ihre eigenen Bewertungen hat $$$d_1$ wo $$$d_1$ < $$$d_0$ und $$$T_1$ wo $$$T_1$ > $$$T_0$ .

Die Frage ist: Was ist der minimale Lautstärkegewinn? $$$d_0-d_1$ akzeptabel für einen bestimmten Wert des Zeitverlusts $$$T_1-T_0$ ?Lassen Sie uns anhand eines Beispiels veranschaulichen. Ursprünglich sollten die Rückstände in einen Behälter mit einem Volumen von 1000 dm3 (1 m3) gegeben werden, und die Reisezeit betrug 70 Sekunden. Es besteht die Möglichkeit, Rückstände in einen anderen Behälter mit 500 dm3 und einer Zeit von 130 Sekunden zu geben. Frage: Sind wir bereit, weitere 60 Sekunden der Zeit des Ladenbesitzers für den Umzug aufzuwenden, um 500 dm3 freies Volumen zu sparen? Basierend auf einer Umfrage unter Lagermitarbeitern wurde die folgende Tabelle erstellt.


Abb. 5. Diagramm der Abhängigkeit der minimal zulässigen Volumeneinsparungen von der Zunahme der Differenz in der Betriebszeit.

Wenn die zusätzlichen Zeitkosten 40 Sekunden betragen, können wir sie nur dann ausgeben, wenn der Volumengewinn mindestens 500 dm3 beträgt. Trotz der Tatsache, dass in der Abhängigkeit eine leichte Nichtlinearität beobachtet wird, nehmen wir zur Vereinfachung weiterer Berechnungen an, dass die Abhängigkeit zwischen den Größen linear ist und durch die Ungleichung beschrieben wird

$$

$$\frac{d_{0}-d_{1}}{10} \geq T_{1}-T_{0}$$

In der folgenden Abbildung betrachten wir die folgenden Methoden zum Platzieren von Waren in Containern.


Abb. 6. Option (a): 2 Behälter, Gesamtvolumen 400 dm3, Gesamtzeit 150 s.

Abb. 6. Option (b): 2 Behälter, Gesamtvolumen 600 dm3, Gesamtzeit 190 s.

Abb. 6. Option (en): 1 Behälter, Gesamtvolumen 400 dm3, Gesamtzeit 200 s.

Option (a) der Wahl der Container ist der ursprünglichen Option vorzuziehen, da die Ungleichung gilt: (800-400) / 10> = 150-120, was 40> = 30 impliziert. Option (b) ist weniger bevorzugt als die ursprüngliche Option , da die Ungleichung nicht gilt: (800-600) / 10> = 190-150, was 20> = 40 impliziert. Aber Option (c) passt nicht in diese Logik! Betrachten Sie diese Option genauer. Einerseits ist die Ungleichung (800-400) / 10> = 200-120, was bedeutet, dass die Ungleichung 40> = 80 nicht erfüllt ist, was darauf hinweist, dass der Volumengewinn keinen so großen Zeitverlust wert ist.

Andererseits reduzieren wir mit dieser Option (c) nicht nur das gesamte belegte Volumen, sondern auch die Anzahl der belegten Zellen. Dies ist die erste von zwei wichtigen Anforderungen für die berechneten Lösungen für die oben aufgeführten Probleme. Damit diese Anforderung erfüllt werden kann, muss natürlich eine positive Konstante auf der linken Seite der Ungleichung hinzugefügt werden $$$Const$ und eine solche Konstante muss nur hinzugefügt werden, wenn die Anzahl der Container abnimmt. Erinnern Sie sich daran $$$y_i$ Ist eine Variable gleich 1, wenn der Container $$$i$ ausgewählt und 0, wenn der Container $$$i$ nicht ausgewählt. Bezeichnen $$$I_0$ - viele Behälter in der ursprünglichen Lösung und $$$I_1$ - Viele Behälter in der neuen Lösung. Im Allgemeinen wird die neue Ungleichung folgendermaßen aussehen:

$$

$$\ sum _ {i \ in I_ {0}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ in I_ {0}} ^ {} y_ {i} - \ left (\ sum _ {i \ in I_ {1}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ in I_ {1}} ^ {} y_ {i} \ right) \ geq T_ {1} -T_ {0}$$

Wenn wir die obige Ungleichung transformieren, erhalten wir

$$

$$\ sum _ {i \ in I_ {0}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ in I_ {0}} ^ {} y_ {i} + T_ {0} \ geq \ sum _ {i \ in I_ {1}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ in I_ {1}} ^ {} y_ {i} + T_ {1}$$

Basierend darauf haben wir eine Formel zur Berechnung der Gesamtkosten $$$F_k$ eine Lösung für das Problem:

$$

$$F_ {k} = \ sum _ {i \ in I_ {k}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ in I_ {k}} ^ { } y_ {i} + T_ {k}.$$

Nun stellt sich die Frage : Welchen Wert sollte eine solche Konstante haben? $$$Const$ ? Offensichtlich muss sein Wert groß genug sein, damit die erste Voraussetzung für die Lösung des Problems immer erfüllt ist. Sie können natürlich einen konstanten Wert von 10 ³ oder 10 ⁶ annehmen, aber ich möchte solche "magischen Zahlen" vermeiden. Wenn wir die Besonderheiten der Durchführung von Lageroperationen berücksichtigen, können wir mehrere fundierte numerische Schätzungen der Größe einer solchen Konstante berechnen.

Lass $$$S_ {max}$ - der maximale Abstand zwischen den Zellen des Lagers einer Zone ABC, in unserem Fall gleich 100 m $$$d_ {max}$ - das maximale Volumen des Zellencontainers im Lager, in unserem Fall 1000 dm3.

Der erste Weg, um den Wert zu berechnen $$$Const$ . Betrachten Sie die Situation, wenn sich auf der ersten Ebene zwei Container befinden, in denen sich die Waren bereits physisch befinden, dh sie selbst Spenderzellen sind und die Kosten für den Transport der Waren in dieselben Zellen natürlich 0 betragen. Es ist notwendig, einen solchen konstanten Wert zu finden $$$Const$ wobei es vorteilhaft wäre, die Rückstände immer von Behälter 1 zu Behälter 2 zu bewegen. Ersetzen der Werte $$$S_ {max}$ und $$$d_ {max}$ In die obige Ungleichung erhalten wir:

$$

$$\ frac {d_ {max}} {10} + Const \ geq S_ {max} \ cdot s_ {run} + \ frac {d_ {max}} {4} \ left (s_ {get} + s_ {put} \ rechts),$$

was folgt

$$

$$Const \ geq S_ {max} \ cdot s_ {run} + d_ {max} \ left (\ frac {s_ {get} + s_ {put}} {4} - \ frac {1} {10} \ right) .$$

Wenn wir die Werte der durchschnittlichen Ausführungszeit von Elementaroperationen in die obige Formel einsetzen, erhalten wir

$$

$$Const \ geq 100 \ cdot 1.5 + 1000 \ left (\ frac {9} {10} \ right) \ rightarrow Const \ geq 1050.$$

Der zweite Weg, um den Wert zu berechnen $$$Const$ . Stellen Sie sich eine Situation vor, in der es eine gibt $$$N$ Spenderzellen, aus denen die Waren in Container 1 transportiert werden sollen $$$S_ {1j}$ - Abstand von der Spenderzelle $$$j$ zu Container 1. Es gibt auch Container 2, in dem sich bereits Waren befinden und dessen Volumen es Ihnen ermöglicht, die verbleibenden Waren aufzunehmen $$$N$ Zellen. Der Einfachheit halber nehmen wir an, dass das Volumen der von Spenderzellen zu Behältern transportierten Waren gleich und gleich ist $$$d_ {max} / N$ . Es ist erforderlich, einen solchen konstanten Wert zu finden $$$Const$ bei dem die Platzierung aller Rückstände aus $$$N$ Zellen in Container 2 wären immer rentabler, als sie in verschiedene Container zu legen:

$$

$$2 \ cdot \ frac {d_ {max}} {10} +2 \ cdot Const + N \ left (S_ {1j} \ cdot s_ {run} + \ frac {d_ {max}} {4 \ cdot N} \ left (s_ {get} + s_ {put} \ right) \ right) \ geq \ qquad \ qquad \ qquad \ qquad \ qquad \\ \ qquad \ qquad \ qquad \ qquad \ qquad \ frac {d_ {max}} { 10} + Const + N \ cdot \ left (S_ {max} \ cdot s_ {run} + \ frac {d_ {max}} {4 \ cdot N} \ left (s_ {get} + s_ {put} \ right) ) \ right).$$

Wir transformieren die Ungleichung, die wir bekommen

$$

$$\ frac {d_ {max}} {10} + Konst + N \ cdot S_ {1j} \ cdot s_ {run} \ geq N \ cdot S_ {max} \ cdot s_ {run} \ rightarrow Const \ geq N \ cdot s_ {run} \ left (S_ {max} -S_ {1j} \ right) - \ frac {d_ {max}} {10}.$$

Um den Wert der Menge zu "stärken" $$$Const$ nehmen wir das an $$$S_ {1j}$ = 0. Die durchschnittliche Anzahl von Zellen, die normalerweise an dem Verfahren zum Komprimieren des Restmaterials beteiligt sind, beträgt 10. Wenn wir die bekannten Werte der Mengen einsetzen, haben wir den folgenden konstanten Wert

$$

$$Const \ geq 10 \ cdot 1.5 \ cdot 100- \ frac {1000} {10} \ rightarrow Const \ geq 1400.$$

Wir nehmen den größten für jede Option berechneten Wert, dies ist der Wert von $$$Const$ für gegebene Lagerparameter. Der Vollständigkeit halber schreiben wir nun die Formel zur Berechnung der Gesamtkosten $$$F_k$ für eine machbare Lösung $$$k$ ::

$$

$$F_ {k} = \ sum _ {i \ in I_ {k}} ^ {} \ frac {d_ {i}} {10} +1400 \ cdot \ sum _ {i \ in I_ {k}} ^ { } y_ {i} + T_ {k}.$$

Nach all den titanischen Bemühungen , die Eingabedaten zu konvertieren, können wir nun sagen, dass alle Eingabedaten in die gewünschte Form konvertiert wurden und für die Verwendung im Optimierungsalgorithmus bereit sind.

Fazit

Wie die Praxis zeigt, wird die Komplexität und Bedeutung der Aufbereitung und Konvertierung der Eingabedaten für den Algorithmus häufig unterschätzt. In diesem Artikel haben wir dieser Phase besondere Aufmerksamkeit geschenkt, um zu zeigen, dass nur qualitativ und mit Bedacht vorbereitete Eingabedaten die vom Algorithmus berechneten Entscheidungen für den Kunden wirklich wertvoll machen können. Ja, es gab viele Schlussfolgerungen aus den Formeln, aber wir haben Sie vor dem Kat gewarnt :)

Im nächsten Artikel werden wir endlich auf das eingehen, worüber die beiden vorherigen Veröffentlichungen nachgedacht haben - den diskreten Optimierungsalgorithmus.

Einen Artikel vorbereitet
Roman Shangin, Programmierer, Projektabteilung,
First Bit Company, Tscheljabinsk