3d Verpackungsalgorithmus für den Versand des Artikels

24

Ich habe die Aufgabe erhalten, einen Versandkalkulator zu erstellen, der die bestmögliche Unterbringung von Waren auf möglichst wenigen Kartons vorschlägt:

  1. Es gibt eine endliche Menge bekannter rechteckiger Kastengrößen

  2. Es gibt viele beliebige rechteckige Gegenstände, die in Schachteln verpackt werden können

  3. Die weniger Boxen sollten am besten genutzt werden. Denn der Versand von zwei Kartons 1x1x1 ist deutlich teurer als ein Karton 1x2x1. Dies sollte hier Priorität haben.

  4. Es sollte auch optimiert werden, um die kleineren Boxen als Priorität der zweiten Ebene zu verwenden. (Bsp .: Wenn eine Auswahl zwischen einer größeren und zwei kleinen Kisten vorliegt, sollte die größere Kiste ausgewählt werden.)

  5. Elemente können gedreht werden, um in die Box zu passen, aber die Drehung muss auf mindestens 45 ° -Schritte begrenzt werden (nach meinen Recherchen lassen einige Konfigurationen eine 45-Grad-Drehung zu, um Retangular-Boxen besser in eine größere Retangular-Box zu passen). wobei 90 ° -Drehungen der zu nehmende Standard sind.

  6. Boxen haben ein Gewichtslimit und Gegenstände haben ein beliebiges Gewicht (zB: ein Gegenstand mit einer Größe von 1x1x1 kann schwerer sein als andere 2x2x2 Gegenstände)

Ich habe ein bisschen recherchiert und einige abstrahierte Algorithmen zum Packen von Behältern und zum Rucksackproblem gefunden. Dabei habe ich die folgende etwas bruteforce-Variante gefunden, die dem am besten passenden Algorithmus ähnelt:

  1. Sortieren Sie die Artikel in absteigender Volumenreihenfolge (zuerst größer) in einer Liste "Zu verpackende Artikel"

  2. Für jeden Artikel auf dieser Liste:

    1. Wählen Sie die kleinere Box, die in der Liste "Verwendete Boxen" aufgeführt ist und über genügend verbleibendes Volumen und Gewichtslimit verfügt, um auf den Artikel zu passen.

    2. Wenn es keine solche Box gibt, erstellen Sie eine neue Box aus dem bekannten Satz möglicher Boxgrößen, die der kleinsten Größe entspricht, die den Abmessungen und dem Gewicht des Artikels entspricht, und fügen Sie sie der Liste der "verwendeten Boxen" hinzu.

    3. Wenn eine Box zu dem Objekt passt (unter Verwendung der unten stehenden Anpassungsfunktion), fügen Sie sie der Liste der Objekte dieser Box hinzu und entfernen Sie sie aus der Liste der anzupassenden Objekte. Markieren Sie dabei die relative 3D-Position innerhalb der Box.

    4. Wiederholen Sie diesen Vorgang ab 2.1, bis auf der Liste "Zu verpackende Artikel" kein einzupassender Artikel vorhanden ist.

Die in Schritt 2 oben verwendete Anpassungsprüffunktion:

  1. Überprüfen Sie, ob das verbleibende Volumen der Box zum Volumen des Artikels passt. Wenn nicht, geben Sie false zurück.

  2. Überprüfen Sie, ob die Summe aus dem Gewicht der Box und dem aktuellen Gewicht der Box kleiner oder gleich dem Gewichtslimit der Box ist. Wenn nicht, geben Sie false zurück.

  3. Überprüfen Sie die Liste "Elemente der Box", um die erste Boxkoordinate auszuwählen, die die kleinste Y-Komponente und genügend Platz für die Breite, Tiefe und Höhe des Elements hat, wobei die anderen Elemente als nicht verfügbarer Platz betrachtet werden.

  4. Wenn das Element nicht in die aktuelle Ausrichtung passt, drehen Sie es der Einfachheit halber um eine der 6 möglichen Umdrehungen, wobei Sie keine 45 ° -Umdrehungen annehmen. (Umdrehungen, die zu Größen führen, die bereits getestet wurden, können übersprungen werden. Beispiel: Durch Drehen einer Schachtel um 180 ° werden die gleichen Abmessungen wie in der ursprünglichen Position erzielt, da alle Schachteln und Gegenstände für gegenüberliegende Seiten die gleiche Größe haben und daher übersprungen werden können.)

  5. Wenn das Objekt nicht auf allen möglichen Wegen in seine ursprüngliche Ausrichtung gedreht wurde, versuchen Sie es ab Schritt 3 erneut.

  6. Wenn alle Rotationen ausprobiert wurden und keine Übereinstimmung gefunden wurde, wird die aktuelle Koordinate als nicht verfügbarer Raum betrachtet.

  7. Wenn kein zu überprüfender Speicherplatz verfügbar ist, geben Sie false zurück. Andernfalls versuchen Sie es ab Schritt 3 erneut.

Ich möchte wissen, ob es angesichts der vorgestellten Einschränkungen eine beste Lösung für mein Problem gibt.

Dies scheint theoretisch zu funktionieren, aber ich habe es nicht mit Code versucht. Ich möchte wissen, ob ich in die richtige Richtung gehe oder ob es bessere und performantere Möglichkeiten gibt, dies zu tun.

Referenzen wären toll.

Bearbeiten:

Ich habe einige interessante APIs von Drittanbietern gefunden, die tun, was ich will, aber diese müssen getrennt werden, sodass ich keinen Zugriff auf diese habe.

Einige Beispiele sind:

Bearbeiten 2:

Ein reales Beispiel für ein zu lösendes Problem wäre:

  • Ich habe 4 Kastengrößen BxHxT: 10x12x18, 12x16x24, 16x20x30, 24x32x40
  • Ich habe eine Bestellung von 4 Artikeln, wobei 1 Artikel die Größe 6x8x10, 2x 22x14x30 und 1x 22x4x20 hat

Wie kann ich diese Artikel in eine beliebige Anzahl von Kartons einer oder mehrerer Größen unter Verwendung der geringstmöglichen Anzahl von Kartons unter Verwendung der kleinstmöglichen Anzahl von Kartons und unter Beibehaltung des geringstmöglichen freien Platzes einpassen?

Ricardo Souza
quelle
4
Es ist kein packingzugehöriges Tag erforderlich . algorithms
Ausreichend
Ich bin gespannt, wird das eigentliche Packen von Robotern oder Menschen ausgeführt? Wenn es das letztere ist, ist die Raumoptimierung die Zeit wert, die erforderlich ist, um herauszufinden, wie jede Box gedreht werden muss, um in sie zu passen?
Foraidt
Gute Frage. Die eigentliche Verpackung wird von Menschen durchgeführt, aber die Software schlägt die Verpackungsreihenfolge und die Position jeder Schachtel vor. Es ist keine Erfahrung in der Verpackung erforderlich, um das bereitgestellte Layout zu betrachten und die Waren in die Schachtel zu legen. Zunächst wird etwas Zeit aufgewendet, um sich daran zu gewöhnen, aber es wird nicht erforderlich sein, über die beste Disposition nachzudenken.
Ricardo Souza
1
Ich denke, alles, was @msw sagt, ist, dass diese Art von Problem wahrscheinlich nicht zu einer "perfekten" Lösung passt, sondern eher zu einer akzeptablen Lösung, die in angemessener Zeit mit Heuristiken auf der Grundlage der von Ihnen festgelegten Regeln gefunden wird unter der Voraussetzung. Aus mathematischer Sicht bedeutet dies oft, dass Sie es mit einem anderen Satz von Algorithmen und Werkzeugen angehen. Ich denke, er empfiehlt das nur. Beispielsweise können genetische Algorithmen, simuliertes Tempern und andere Methoden zum Verfolgen einer Gradientenabstiegskurve, die den Lösungsraum in Bezug auf Ihre Heuristik approximiert, hier Vorteile bieten.
J Trana
1
Ich poste hier nur eine Idee. Wenn Sie nicht glauben, dass es effektiv ist, können Sie es ignorieren. Diese Lösung (es ist eher eine Optimierung) hängt wirklich davon ab, wie ähnlich die Eingabe Ihres Algorithmus sein wird. Ausnutzen der Tatsache, dass Ihre Eingabe im Laufe der Zeit einige Ähnlichkeiten aufweist. Sie können die berechneten Ergebnisse (die eine teure Berechnungskomplexität haben) speichern / zwischenspeichern und sie dann mit Ihren Eingaben vergleichen. Wenn Sie eine vollständige Übereinstimmung oder eine teilweise Übereinstimmung haben, müssen Sie nur ein paar Berechnungen durchführen, um einige kleinere Objekte neu anzuordnen. Dies führt natürlich zu neuen Problemen.
JAAAY

Antworten:

4

Das Verpacken von Behältern ist sehr rechenintensiv. Denken Sie an die Hälfte des Problems: Sie möchten das Produkt in Versandkartons verpacken, ohne dass es in den Karton verschwindet. Eine optimale Lösung hierfür würde das Durchlaufen aller möglichen Teilmengen und aller möglichen 3D-Anordnungen des Produkts erfordern, die in einem einzigen LKW versandt werden müssen. Ich gebe Ihnen die optimale Lösung dafür, weil ich einen Freund habe, der vor dem Frühstück sechs unmögliche Dinge tut.

Jetzt müssen Sie nur noch alle Kartons verschwendungsfrei auf den LKW bringen. Mein Freund macht seine zweite unmögliche Sache und gibt Ihnen die Lösung. Leider ist bei den oben ausgewählten Kistengrößen im LKW ein Leerraum vorhanden, der reduziert werden könnte, wenn Sie bei der ersten Aufgabe andere (größere oder kleinere) Kisten ausgewählt hätten. Wenn Sie die Größe einer Kiste ändern, müssen Sie den LKW bestenfalls umpacken. Im schlimmsten Fall müssen Sie möglicherweise alle Kartons neu verpacken, was genauso schwierig ist wie das Problem, mit dem wir begonnen haben. Und wie in der ersten Phase müssten Sie alle möglichen 3D-Arrangements ausprobieren.

Ich fand Skienas The Algorithm Design Manual hilfreich, um zu überlegen, welche Klasse von Algorithmen für welche Probleme geeignet ist , aber ich habe meistens gelernt, dass gute Lösungen für selbst alltägliche Probleme Sie mit Rechenschwierigkeiten konfrontieren. Das meiste, was Sie brauchen, passt in die Klasse der Müllprobleme, und dieser Artikel ist ein guter Ausgangspunkt. Es ist erwähnenswert, dass einige der besten Algorithmen dafür kommerzielle Produkte sind, da diese Aufgabe überall in der Logistik auftaucht (in welcher geringsten Anzahl von Eisenbahnwaggons kann ich meine Waren einlagern? Und dergleichen). Wenn ein Hersteller mit der richtigen Heuristik 100 Waggons pro Monat einsparen kann, ist der Verdienst beträchtlich.

Leider ist die Literatur zur Optimierung der Heuristik bei weitem nicht so umfangreich wie für Algorithmen. Wenn Sie es alleine versuchen, können Sie sicher sein, dass Sie schon in Ihrem zweiten Monat davon träumen, rechteckige Prismen zu bewegen. Ich hatte ein Problem mit dem Materialabbau, bei dem ich mich wahrscheinlich an die Experten (oder deren Software) wenden würde, wenn ich es noch einmal tun müsste.

Vielen Dank an @JTrana für die feine Erweiterung meines Kommentars.

msw
quelle
Danke für deine Rückmeldung. Wie ich bereits zu der Frage gesagt habe, habe ich mich bereits mit diesem Thema befasst und bin auf eine Mischung einiger Algorithmen gestoßen, um diese oben vorzuschlagen. Ich mache mir nur Sorgen um die Verpackung selbst. Alle diese Kisten werden per Postversand versandt. Glücklicherweise werde ich mich nicht um das Beladen von LKWs kümmern müssen.
Ricardo Souza
Das war ein guter Teil meiner Erklärung. Sie können den Algorithmus nicht von Firmen "extrahieren", die möchten, dass Sie für ihre Dienstleistung bezahlen. Die beiden von Ihnen aufgelisteten Firmen haben eine API, aber das Packen erfolgt auf ihren Servern, und Sie haben keinen Zugriff auf den Implementierungscode, außer durch Diebstahl. Und es ist gut, dass Sie die Lastwagen nicht packen müssen, jetzt ist Ihr Problem nur noch halb so schwer, weshalb Firmen Ihnen eine Lösung verkaufen möchten und die Leute bereit sind, den Service zu kaufen.
msw
1
Ich denke, wir haben hier ein Missverständnis. Ich habe mich möglicherweise nicht gut ausgedrückt (wie Sie vielleicht bemerkt haben, ist Englisch nicht meine Muttersprache). Ich bitte nicht darum, die Algorithmen zu stehlen. Ich bin hierher gekommen, um das Thema zu klären. Ich habe einige Nachforschungen angestellt und das obige Beispiel zur Analyse herangezogen. Vielleicht ist jemand auf die gleichen Probleme gestoßen, die mir bessere Anweisungen geben können. Was kann ich tun, um bessere Ergebnisse zu erzielen, wenn meine Lösung nicht anwendbar ist? Das ist meine eigentliche Frage dort oben. Ich hoffe, ich habe mich jetzt klarer ausgedrückt.
Ricardo Souza
Dein Englisch ist gut; Ich denke, das Problem ist, dass wir über verschiedene Ebenen der Aufgabe sprechen. Sie denken an die Umsetzung und ich denke an eine kombinatorische Explosion. Ich denke, das Lösen von Edit 2 wird Ihnen helfen, das Problem besser zu verstehen, wenn ich es so betrachte. Können Sie das wie angegeben lösen? Ohne Makulatur, mit einer minimalen Anzahl von Kartons der minimalen Größe? Das ist das Multioptimierungsproblem, von dem ich bereits sagte, dass es unmöglich ist, es zu tun: Sie müssen mindestens einen dieser Faktoren opfern, um einen anderen zu optimieren.
msw
Vielen Dank. Ich glaube, ich habe es jetzt verstanden. Ich habe nicht versucht, es zu codieren. Ich habe darüber nachgedacht, keine Zeit für die Programmierung zu verschwenden, bevor eine konkretere Lösung oder zumindest ein positives Feedback zu meinem Vorschlag vorliegt, da dies zunächst ein Angebot ist. Ich recherchiere noch, aber ich fürchte, ich muss eine dieser APIs besorgen und prüfen, ob die Geräte (Datenkollektoren mit Win CE 6.0) mit dem Internet verbunden sind. Die ersten Informationen, die ich vom Kunden erhielt, gaben an, dass er am Arbeitsplatz keinen Internetzugang haben wird.
Ricardo Souza
1

Wenn ich neue Algorithmen erstelle und kürzlich selbst einen Pack-Algorithmus erstellt habe (ich weiß, dass er noch Optimierungspotenzial hat), gehe ich immer am einfachsten vor:

Wie würde ich es als Mensch tun und versuchen, es in einen Algorithmus zu übersetzen? Von meinem (Robotik-) KI-Lehrer Rolf Pfeifer denke ich immer noch daran, dass offensichtliche Intelligenz manchmal mit sehr einfachen Regeln erzeugt werden kann, anstatt sie zu überarbeiten Ich versuche zu unterentwickeln

  1. Identifizieren Sie zu große Gegenstände (Gegenstände, die nicht in eine bestimmte Schachtel passen)
  2. Versuchen Sie, die bestmögliche Schachtel zu finden (indem Sie das Gesamtvolumen und die Artikelabmessungen miteinander vergleichen).
  3. Bestellen Sie Artikel von groß bis klein und Kartons (Leerzeichen) von klein bis groß
  4. Platzieren Sie den größten Gegenstand auf kleinstem Raum
  5. Wenn das größte Element nicht gefunden wird, springen Sie darüber und versuchen Sie es mit dem nächsten, bis nichts mehr passt
  6. Suchen Sie für die verbleibenden Elemente nach dem neuen besten Feld. ...

    X. Denken Sie immer an außergewöhnliche Ereignisse (übergroße Elemente, seltsame Formen, wenn eine Box nur 1 Element enthält, wäre es nicht besser, ein Element ohne Box zu senden? Usw.), aber Sie können eine Heuristik auch in Form einer Entscheidung treffen Baum.

Natürlich gibt es weitere Vorbehalte, je weiter Sie kommen, ich gebe diese Ideen nur als Ausgangspunkt an. Von dort aus gibt es viele Möglichkeiten. Eine Alternative wäre, eine Kiste in kleine Würfel zu teilen (zB 5cmx5cmx5cm) und sie als belegt / frei zu verfolgen. Ein anderer Ansatz könnte als 3D-Tetris usw. bezeichnet werden.

Mit diesem Ansatz müssen Sie sich nicht unbedingt um eine kombinatorische Explosion sorgen. Andererseits kann es zu einer kombinatorischen Explosion kommen, wenn es sich um Zugladungen handelt, aber auch: Glauben Sie wirklich, dass ein Unternehmen die Packliste Stück für Stück überprüft? Nein, sie nähern sich einer Lösung zum Teilen und Erobern: Teilen Sie die Komplexität mithilfe standardisierter Volumina (z. B. Paletten oder Boxen mit fester Größe). Denken Sie also auch aus praktischen Gründen daran, dass nicht nur Züge, sondern manchmal auch die Zeit des Mitarbeiters Geld ist. ein zug kann x paletten laden, jede palette hat ein festes volumen, also packe artikel in paletten, aber vielleicht besteht eine palette aus mehreren reihenfolgen, also benutze feste kästen für die artikel, die dann in paletten geladen werden, die dann geladen werden in Züge.

Zumindest ging ich als Mensch so mit der Aufgabe um, holte mir die beste Schachtel und passte dann den größten Gegenstand einzeln auf kleinstem Raum an (und fügte ein bisschen Vorschau hinzu).

Wie in meinem Algorithmus haben Sie am Ende wahrscheinlich nicht die beste Lösung, aber eine weitaus gute Heuristik, die Sie dann weiter verfeinern können.

Manchmal ist es einfacher, mit dem ersten Schritt zu beginnen und Probleme auf Ihrem Weg zu beseitigen. Natürlich ist dies im Idealfall kein Schritt über den Tellerrand, sondern ein bisschen klug. Manchmal sind Sie gezwungen, nach Alternativen zu suchen und zu wählen die beste oder implementieren einen "Schritt zurück".

Aber wie ich von meinem KI-Lehrer gelernt habe (Rolf Pfeifer, tut mir leid, dass ich mich wieder darum gekümmert habe): Manchmal kann man ein scheinbar intelligentes Verhalten mit einigen sehr einfachen und wenigen Regelsätzen erzeugen Sie erkennen ein Hindernis auf der rechten Seite, biegen rechts ab, wenn sich auf der linken Seite ein Hindernis befindet, und fahren geradeaus, wenn es kein Hindernis gibt oder wenn sich das Hindernis vorne befindet. Wenn 3 oder 4 Roboter in einem Quadrat von 3 x 3 m mit vielen Ping-Pong-Bällen platziert werden, scheint es erstaunlich zu sein, dass die Roboter aufräumen und die Ping-Pong-Bälle in die Ecken schieben, obwohl die Roboter es sind Nur programmiert, um Hindernissen auszuweichen.

PD: Die einzige reale Abweichung, die ich von diesem Ansatz gefunden habe, war, als ich nebenbei als Bühnenarbeiter für große Konzerte wie Metallica, Iron Maiden, Britney Spears, Paul Mc Cartney und so weiter gearbeitet habe internationale touren haben punkt für punkt genaue packlisten. Die Berechnungen werden einmal durchgeführt (ich weiß nicht, von Menschen oder Maschinen) und dann repliziert. Wenn sie das erste Mal packen, machen sie manchmal sogar Schicht für Schicht Bilder und kleben sie in den LKW, damit die örtlichen Besatzungen genau wissen, welche Kiste wann und wo aufgeladen werden muss. Dies ist jedoch auch ein spezifischer Packbedarf, da für eine Tour immer die gleichen Kisten und Lastwagen verwendet werden.

Canelo Digital
quelle
1

Die Heuristik, die Sie in Ihrem Beitrag erwähnen, scheint interessant zu sein.

Ich würde ein paar Änderungen vorschlagen, um die endgültige Lösung zu verbessern.

Versuchen Sie bei einer Lösung, bei der alle Artikel in einer Schachtel verpackt sind, den Inhalt von zwei kleinen Schachteln in einer größeren Schachtel zusammenzuführen (dies sollte dazu beitragen, die Kriterien für die Verwendung von möglichst wenigen Schachteln zu verbessern).

Alternativ können Sie jedes Mal, wenn Sie eine neue Box starten, anstatt die kleinste Box zu verwenden, die das aktuelle Objekt aufnehmen kann, die größte auswählen, die das Objekt aufnehmen kann. Wenn jedes Objekt einer Box zugewiesen ist, versuchen Sie, alle Objekte von a zuzuweisen Box zu einer kleineren Box.

Anstatt die Position Ihrer anderen Boxen als fest zu betrachten, können Sie sich auch vorstellen, in Ihrer Anpassungsfunktion die Ladereihenfolge zu ändern. Auf diese Weise können Sie auf Kosten einer längeren Laufzeit bessere Lösungen finden.

Renaud M.
quelle
Das scheint interessante Verbesserungen. Ich habe dieses Problem schon lange nicht mehr angesprochen. Vielleicht sollte ich es eines Tages versuchen. Vielen Dank.
Ricardo Souza