Hybrider Ansatz zur Lösung realer

Wissenschaftliche Berichte Band 13, Artikelnummer: 11777 (2023) Diesen Artikel zitieren

418 Zugriffe

2 Altmetrisch

Details zu den Metriken

Das effiziente Verpacken von Gegenständen in Behälter ist eine alltägliche Aufgabe. Das als „Bin Packing Problem“ bekannte Problem wurde dank des großen Interesses aus Industrie und Logistik im Bereich der künstlichen Intelligenz intensiv untersucht. Seit Jahrzehnten wurden viele Varianten vorgeschlagen, wobei das dreidimensionale Bin-Packing-Problem den realen Anwendungsfällen am nächsten kommt. Wir stellen ein hybrides quantenklassisches Framework zur Lösung realer dreidimensionaler Bin-Packing-Probleme (Q4RealBPP) vor, das verschiedene realistische Merkmale berücksichtigt, wie zum Beispiel: (1) Paket- und Bin-Abmessungen, (2) Übergewichtsbeschränkungen, (3) Affinitäten zwischen Artikelkategorien und (4) Präferenzen für die Artikelbestellung. Q4RealBPP ermöglicht die Lösung realitätsnaher Fälle von 3 dBPP unter Berücksichtigung von Einschränkungen, die in der Industrie- und Logistikbranche sehr beliebt sind.

Die Optimierung der Verpackung von Produkten in eine endliche Anzahl von Behältern ist eine entscheidende tägliche Aufgabe im Bereich Produktion und Vertrieb. Abhängig von den Eigenschaften sowohl der Verpackungen als auch der Behälter können mehrere Verpackungsprobleme formuliert werden, die allgemein als Bin Packing Problems (BPP)1 bekannt sind. Innerhalb dieser Kategorie gilt die eindimensionale BPP (1 dBPP) als die einfachste Variante2, deren Ziel es ist, alle Artikel in möglichst wenige Behälter zu packen. Für den Umgang mit realen Situationen in Logistik und Industrie wurden viele Varianten mit einer variablen Anzahl von Einschränkungen vorgeschlagen3. Das dreidimensionale BPP (3 dBPP)4, bei dem jedes Paket drei Dimensionen hat: Höhe, Breite und Tiefe, ist die bekannteste und anspruchsvollste Variante. In mehreren Studien5,6,7 wurde hervorgehoben, dass 3 dBPP in vielen industriellen Umgebungen von praktischem Interesse ist. In den letzten Jahren wurde es so formuliert, dass es vielfältige und praktische Anwendungen wie Palettenbeladung8, Straßentransport9, Luftfracht10 usw. ermöglicht. Aufgrund seiner Komplexität wird 3 dBPP auch immer wieder als Benchmark zum Testen neu entwickelter Methoden und Mechanismen verwendet11,12 .

An einer anderen Front befindet sich das Quantencomputing noch in einem frühen Stadium, hat jedoch in der wissenschaftlichen Gemeinschaft große Aufmerksamkeit erregt, da es Forschern und Praktikern ein revolutionäres Paradigma für die Bewältigung verschiedener Arten praktischer Optimierungsprobleme bietet13,14,15,16. Insbesondere Quanten-Annealer wurden in jüngster Zeit auf eine Vielzahl von Optimierungsproblemen angewendet, die von den Bereichen Industrie17, Logistik18 und Wirtschaft19 inspiriert waren. Die in der Quantengemeinschaft durchgeführte Forschung zu BPP ist jedoch noch spärlich, obwohl BPP klassischerweise umfassend als Optimierungsproblem untersucht wurde.

Die bahnbrechende Arbeit zu BPP auf dem Gebiet des Quantencomputings präsentiert eine hybride quantenklassische Methode zur Lösung des 1 dBPP20, deren Löser aus zwei Modulen besteht: (1) einer Quantensubroutine, mit der eine Menge möglicher Konfigurationen gesucht wird, um eine zu füllen Single Bin und (2) eine klassische rechnerische Heuristik, die vollständige Lösungen unter Verwendung der durch die Quantensubroutine gegebenen Teilmengen erstellt. Um die Leistung der entwickelten Quantensubroutine zu vertiefen, wurden weitere Tests anhand einer Zufallsstichprobe und einer auf Zufallsbewegungen basierenden Heuristik21 durchgeführt. Neben diesen beiden Arbeiten formuliert eine zusätzliche Studie ein Problem im Zusammenhang mit der Atomenergieindustrie als 1 dBPP und löst es mithilfe des D-Wave-Quantenannealers22. Eine weitere Arbeit zeigt quanteninspirierte evolutionäre Berechnungstechniken als Alternative zur Lösung von BPP-bezogenen Problemen23,24,25. Quanteninspirierte Techniken sind eine spezielle Klasse evolutionärer Algorithmen, die sich zur Definition ihrer Operationen die Quantenphysik zunutze machen und für die Ausführung auf einem klassischen Computer konzipiert sind26. Somit können sie auf keiner Quantenmaschine ausgeführt werden.

Im Gegensatz zu 1 dBPP ist die Bewältigung von 3 dBPP im Quantenbereich aus zwei verwandten Gründen viel anspruchsvoller: (1) seiner Komplexität, die zunimmt, wenn Einschränkungen aus der realen Welt berücksichtigt werden, und (2) dem beginnenden Zustand von Entwicklung der aktuellen kommerziellen Quantencomputer, deren Kapazitäten immer noch durch Dekohärenz und Fehler begrenzt sind, was ein Hindernis für die Lösung stark eingeschränkter Probleme darstellen könnte. In diesem Artikel stellen wir ein hybrides quantenklassisches Computer-Framework für das realitätsorientierte 3 dBPP vor, das als Quantum for Real Bin Packing Problem (Q4RealBPP) bezeichnet wird. Das vorgeschlagene Framework greift auf den Leap Constrained Quadratic Model (CQM) Hybrid Solver (LeapCQMHybrid27) von D-Wave zurück. Gleichzeitig baut Q4RealBPP auf einem bestehenden Code28 auf. Dieser Referenzcode ist ein ausgezeichneter Ausgangspunkt, der den Weg für die beiden Hauptbeiträge ebnete, die in dieser Arbeit entwickelt wurden:

Effizienz des Codes: Im Referenzcode ist das Problem so formuliert, dass viele Variablen (also Qubits) benötigt werden. Dieses Problem befasst sich mit dem Problem der Machbarkeit im Kontext der Quantenhardware im Zeitalter der verrauschten Quanten im mittleren Maßstab (NISQ)29. Daher ist die Optimierung des Codes für die Bewältigung komplexer Probleme von entscheidender Bedeutung. Q4RealBPP bietet in dieser Hinsicht einen Fortschritt, indem es untersucht, wie die als intrinsische Einschränkungen bezeichneten Einschränkungen verfeinert werden können. Diese Einschränkungen sind diejenigen, die für die BPP-Definition erforderlich sind (z. B. Fälle nicht außerhalb eines Behälters ablegen) und wurden zuvor im Referenzcode eingeführt. Daher umfasste die neuartige Arbeit, die zu diesem speziellen Aspekt durchgeführt wurde, unter anderem die Neudefinition einiger mathematischer Formeln, die diese intrinsischen Einschränkungen definieren, und die Eliminierung eines redundanten Optimierungsziels. Dank dieser Vorgehensweise können Probleme mit weniger Variablen formuliert werden, was sich direkt auf die Fähigkeit des Frameworks auswirkt, größere Instanzen zu adressieren.

Anwendbarkeit des Tools: Der Referenzcode ist darauf ausgerichtet, die grundlegendste Variante des 3 dBPP zu lösen, indem nur die Dimensionen von Paketen und Behältern berücksichtigt werden. Diese Einstellung ist weit entfernt von echten Kundenanforderungen, bei denen wahrscheinlich andere Funktionen wie Gewichtungen, Lastausgleich oder Inkompatibilitäten eine Rolle spielen. Wir haben diese Richtung weiter ausgearbeitet, indem wir eine Reihe von Einschränkungen namens Real-World BPP Restrictions implementiert haben. Alle diese Einschränkungen stellen einen Mehrwert für Q4RealBPP dar, da sie eine erhebliche Erweiterung der mathematischen Formulierung des Problems erforderten. Wir vertiefen diesen Aspekt in den folgenden Abschnitten.

Unter Berücksichtigung dieser Faktoren ist Q4RealBPP auf Industrie- und Logistikbereiche ausgerichtet und befasst sich unter anderem mit Problemen wie der Organisation von Hafencontainern, der Einführung von Paketen in Lieferwagen und LKWs oder der Platzierung von Lebensmitteln auf Verteilerpaletten. Mit Hilfe einer hybriden quantenklassischen Methode stellt Q4RealBPP einen soliden Schritt vorwärts zur Lösung von 3 dBPP dar, mit dem klaren Ziel, realitätsbezogene Probleme anzugehen, die von Endbenutzern und Unternehmen geschätzt werden. Zu den von Q4RealBPP in Betracht gezogenen Funktionen gehören (1) Abmessungen von Paketen und Behältern, (2) maximal zulässiges Gewicht pro Behälter, (3) positive und negative Affinitäten zwischen Artikelkategorien und (4) Präferenzen für die Paketbestellung (in Bezug auf Lastaufnahme und Lastausgleich). ). Um seine Anwendung zu demonstrieren, haben wir ein Experiment durchgeführt, das aus 12 verschiedenen Fällen bestand, die als veranschaulichende Beispiele dienten. Darüber hinaus ermöglicht Q4RealBPP Benutzern die einfache Erstellung flexibler und klar definierter Instanzen, um eine Vielzahl realer Situationen anzupassen, die im Quantencomputer gelöst werden sollen.

Der Rest des Artikels ist wie folgt aufgebaut: Unter „Mathematische Formulierung“ werden die 3-dBPP-Formulierung und die entsprechende Notation vorgestellt. Darüber hinaus wird eine detaillierte Untersuchung der benötigten Rechenressourcen für beliebige Instanzen durchgeführt. In „Experimentelle Ergebnisse“ wird die Anwendbarkeit dieses Tools anhand einer Reihe realistischer Instanzen als Eingabe getestet. Die Schlussfolgerungen aus den präsentierten Ergebnissen und unsere Zukunftspläne finden Sie abschließend im Abschnitt „Schlussfolgerungen und zukünftige Arbeiten“.

In diesem Abschnitt beschreiben wir ausführlich die mathematische Formulierung der 3-dBPP-Variante, die in dieser Forschung behandelt wird. Zunächst sind in Tabelle 1 die Eingabeparameter und Variablen aufgeführt, aus denen sich das Problem zusammensetzt.

Das 3 dBPP kann als Optimierungsproblem gelöst werden, bei dem eine geeignete Kostenfunktion zur Minimierung definiert werden muss. In unserem Fall wird diese Kostenfunktion als Summe dreier Ziele dargestellt. Die jedem Ziel zugewiesene Stärke, d. h. die für jedes einzelne berücksichtigte Relevanz, hängt von den Benutzerpräferenzen ab, indem einfach jedes Ziel mit einem geeigneten Gewicht multipliziert wird. Somit kann das Problem als \(\min \text { }\sum _{i=1}^3\omega _io_i\) mit \(\omega _i\) den Gewichten jedes Ziels \(o_i\) angegeben werden. In unserer Studie werden wir diese Verzerrung nicht berücksichtigen, also \(\omega _i=1\text { }\forall i\).

Das erste und wichtigste Ziel ist die Minimierung der Gesamtzahl der Behälter, die zum Auffinden der Pakete verwendet werden. Dies kann durch Minimierung erreicht werden

Um sicherzustellen, dass die Artikel vom Boden bis zur Oberseite des Behälters verpackt werden und Lösungen mit schwebenden Paketen vermieden werden, wird außerdem ein zweites Ziel definiert, indem die durchschnittliche Höhe der Artikel für alle Behälter minimiert wird

Neben diesen beiden aus dem Referenzcode28 neu formulierten Zielen fügen wir außerdem ein drittes optionales Ziel \(o_3\) hinzu, um die Lastausgleichsfunktion zu berücksichtigen. Diese Sorge ist besonders wichtig, wenn beispielsweise Luftfrachtflugzeuge und Überfahrten als Transportmittel ausgewählt werden30,31. In solchen Situationen sollten Pakete gleichmäßig um eine bestimmte xy-Koordinate innerhalb des Behälters verteilt werden. Wir können dem entgegenwirken, indem wir den sogenannten Taxi- oder Manhattan-Abstand zwischen den Gegenständen und den gewünschten Massenschwerpunkt für jeden Behälter berechnen. Dadurch verringern sich auch die Lücken zwischen den Artikeln. Diesbezüglich ist das dritte zu minimierende Ziel

mit

wobei \(0\le x_i< nL\) (horizontal gestapelte Behälter) und \(0\le y_i< W\) \(\forall i\in I\). Dieser objektive Term minimiert für jedes Element den Abstand zwischen der Schwerpunktprojektion in der xy-Ebene und der \(({\tilde{L}},{\tilde{W}})\)-Koordinate jedes Abschnitts.

Die oben definierten Ziele unterliegen gewissen Einschränkungen, die für die Ableitung realistischer Lösungen unerlässlich sind. Der gesamte Pool an Einschränkungen ist in zwei Kategorien unterteilt: diejenigen, die der BPP-Definition innewohnen (intrinsische Einschränkungen) und diejenigen, die aus einer realen Perspektive relevant sind (reale BPP-Einschränkungen).

Artikelausrichtungen: Die Tatsache, dass jeder Artikel innerhalb eines Behälters nur eine Ausrichtung haben darf, kann mithilfe von implementiert werden

Satz möglicher Orientierungen \(k\in K_i\) für ein gegebenes Element i der Dimensionen \((l_i,w_i,h_i)\). (a) \(k = 1\), (b) \(k = 2\), (c) \(k = 3\), (d) \(k = 4\), (e) \(k = 5\), (f) \(k = 6\). Siehe Tabelle 2.

Ausrichtungen ergeben die effektive Länge, Breite und Höhe der Elemente entlang der X-, Y- und Z-Achse

und aufgrund (5) ist in jeder Gleichung nur ein Term \(r_{i,k}\) ungleich Null.

Es sollte berücksichtigt werden, dass es Elemente mit geometrischen Symmetrien geben kann, wie z. B. kubische Elemente, bei denen keine Drehungen angewendet werden können. Redundante und nicht-redundante Ausrichtungen werden im Referenzcode28 berücksichtigt. In unserer Formulierung prüfen wir zuvor, ob diese Symmetrien existieren, um \(K_i\) für jedes Element zu definieren. Dadurch werden (6)–(8) vereinfacht, indem redundante Ausrichtungen herausgefiltert werden und zu einer Formulierung führen, die weniger Variablen (also Qubits) verwendet, um dasselbe Problem darzustellen, wobei \(\kappa =\sum _{i=1} ^m|K_i|\le 6m\) Variablen \(r_{i,k}\) benötigt. Für \(i\in I_\text {c}\) mit \(I_\text {c}{:}{=}\{i\in I\,|\,l_i=w_i=h_i\}\) ( kubische Elemente), können wir \(r_{i,1}=1\) und ansonsten 0 setzen und so (5) im Voraus erfüllen. In Tabelle 2 sehen wir die nicht-redundanten Orientierungssätze für ein Element i abhängig von seinen Abmessungen. Dieser einfache Mechanismus reduziert die Komplexität des Problems und begünstigt die Implementierung der Quantenhardware.

Nicht überlappende Einschränkungen: Da es sich um starre Pakete handelt, die sich also nicht überlappen können, müssen eine Reihe von Einschränkungen definiert werden, um diese Konfigurationen zu überwinden. Hierzu muss mindestens eine dieser Situationen eintreten (siehe Abb. 2)

Wie mit der Orientierungsvariablen \(r_{i,k}\) in (5) besprochen, muss die relative Position zwischen den Elementen i und k eindeutig sein, also

Darstellung von \(b_{i,k,q}\) aktiviert für alle relativen Positionen \(q\in Q\) zwischen den Elementen i und k. Siehe (9)–(14). Beide stehen in Kontakt, dies ist jedoch nicht verpflichtend. (a) \(b_{{i},{k},1}=1\), (b) \(b_{{i},{k},2}=1\), (c) \(b_ {{i},{k},3}=1\), (d) \(b_{{i},{k},4}=1\), (e) \(b_{{i},{ k},5}=1\), (f) \(b_{{i},{k},6}=1\).

Einschränkungen bei der Artikel- und Behälterzuordnung: Die folgenden Einschränkungen gewährleisten ein angemessenes Verhalten bei der Artikel- und Behälterzuordnung. Um zu vermeiden, dass Duplikate desselben Artikels verpackt werden, muss jeder Artikel in genau einen Behälter gelangen, wo

Mit der folgenden Formel wird überprüft, ob Artikel in Behältern verpackt werden, die bereits verwendet werden

Daher wird \(v_j\) bei Bedarf während des Packens aktiviert. Um dies zu gewährleisten, können Behälter nacheinander aktiviert werden, um doppelte Lösungen zu vermeiden

Einschränkungen für Bin-Grenzen: Um Bin-Grenzen berücksichtigen zu können, müssen die folgenden Einschränkungen erfüllt sein

Dabei stellt (19) sicher, dass sich die im Behälter j platzierten Elemente i nicht außerhalb des letzten Behälters (n-ten Behälters) entlang der x-Achse befinden. (20) stellt sicher, dass sich der Artikel i innerhalb des entsprechenden Behälters j entlang der x-Achse befindet (aktiviert, wenn \(n>1\)), (21) bestätigt, dass sich das in den Behälter j gelegte Element i nicht außerhalb entlang der y-Achse befindet, während (22) sicherstellt, dass der innerhalb des Behälters j zugewiesene Gegenstand i nicht außerhalb entlang der y-Achse liegt Z-Achse.

In diesem Unterabschnitt stellen wir diejenigen Einschränkungen vor, die mit der operativen Perspektive des Problems zusammenhängen, dh diejenigen, die reale industrielle Situationen berücksichtigen. Alle folgenden Einschränkungen sind in unserer Formulierung optional.

Übergewichtsbeschränkung: Das Gewicht jedes Pakets und die maximale Kapazität der Behälter sind allgemeine Kontextdaten, um eine Überschreitung der maximalen Gewichtskapazität der Behälter zu vermeiden. Vermeiden Sie daher überladene Behälter. Wir können diese Einschränkung als einführen

Diese Einschränkung wird aktiviert, wenn die maximale Kapazität M gegeben ist.

Affinitäten zwischen Paketkategorien: Es gibt häufig Präferenzen dafür, einige Pakete in verschiedene Behälter aufzuteilen (negative Affinitäten oder Inkompatibilitäten) oder sie im Gegenteil in demselben Behälter zu sammeln (positive Affinitäten). Betrachten wir \(I_\alpha {:}{=}\{i\in I\text { }|\text { }{} \texttt {id}\text { von }i\text { ist gleich }\ alpha \}\), dh \(I_\alpha \subset I\) ist eine Teilmenge aller Elemente, deren ID gleich \(\alpha\) ist. Gegeben sei eine Menge von p negativen Affinitäten \(A^\text {neg}{:}{=}\{(\alpha _1,\beta _1),\dots ,(\alpha _p,\beta _p)\}\) , dann wird die Einschränkung sein

Um diese Einschränkung zu aktivieren, muss eine Reihe von Inkompatibilitäten angegeben werden. Darüber hinaus können wir im Voraus \(\nu {:}{=}6n\sum _{(\alpha ,\beta )\in A^\text {neg}}|I_\alpha ||I_\beta |\ erfüllen ) nicht überlappende Einschränkungen (siehe (9)–(14)), was zu einer einfacheren Formulierung führt. Umgekehrt wird bei gegebener Menge positiver Affinitäten \(A^\text {pos}\), wie mit \(A^\text {neg}\) angegeben, die Einschränkung so gestellt

Diese Einschränkung wird aktiviert, wenn eine Reihe positiver Affinitäten gegeben ist. Wenn \(A^\text {pos}\) und \(A^\text {neg}\) gegeben sind, dann können beide Einschränkungen eingeführt werden, indem man nur eine Formel verwendet, indem man (24) und (25) addiert.

Präferenzen bei der relativen Positionierung: Die relative Positionierung von Elementen erfordert, dass einige von ihnen in einer bestimmten Position in Bezug auf andere vorhandene Elemente platziert werden müssen. Diese Präferenz ermöglicht die Einführung der Reihenfolge einer Reihe von Paketen entsprechend ihrer Position in Bezug auf die Achsen. Somit hilft diese Präferenz bei der Bestellung in vielen realen Fällen, wie zum Beispiel: Paketzustellung (ein Artikel i, der vor Artikel k geliefert werden muss, wird vorzugsweise näher an der Kofferraumtür platziert) oder Lastaufnahme (kein schweres Paket sollte über dünnen Paketen liegen). ), unter anderen.

In Bezug auf diese Präferenz können wir zwei verschiedene Perspektiven definieren, um die relative Positionierung zu behandeln:

Zu vermeidende Positionierung (\(P_q^{-}\)): Die Liste der Elemente (i, k) sollte sich nicht an der angegebenen relativen Position \(q\in Q\) befinden. Daher wird \(b_{i,k,q}=0\) erwartet, was Konfigurationen bevorzugt, bei denen der Löser \(q'\in Q\) mit \(q'\ne q\) für die relative Positionierung von Elementen auswählt (ich k).

Positionierung zugunsten (\(P_q^{+}\)): Die Liste der Elemente (i, k) sollte sich in einer bestimmten relativen Position q befinden. Bei Aktivierung dieser Präferenz sollte \(b_{i,k,q}=1\) gelten und folglich \(b_{i,k,q'}=0 \ \forall q'\ne q\).

Formal werden diese Präferenzen geschrieben als

Diese Präferenzen könnten auch als obligatorische Vorauswahlen behandelt werden. In einem solchen Fall würde die Anzahl der benötigten Variablen reduziert, ebenso der Suchraum. Wenn wir \(\smash [t]{p^{-}=\sum _{q\in Q}|P_q^{-}|}\) und \(\smash [t]{p^{+} =\sum _{q\in Q}|P_q^{+}|}\) mit \(\smash [t]{P^{-}_q\cap P^{+}_{q'}=\varnothing }\), basierend auf (15), wäre die Menge der reduzierten Variablen gegeben durch \(\smash [t]{p^{-}+6p^{+}}\). Darüber hinaus werden \(\smash [t]{n(p^{-}+5p^{+})}\) nicht überlappende Einschränkungen (siehe (9)–(14)) direkt erfüllt und können daher ignoriert werden Vereinfachung des Problems. Aus Gründen der Klarheit wurden diese Präferenzen in diesem Dokument für tragende Zwecke als harte Einschränkungen (HC) angewendet, wie in den kommenden „Experimentellen Ergebnissen“ erläutert.

Lastausgleich: Um diese Einschränkung zu aktivieren, muss ein Zielschwerpunkt angegeben werden. Globale Positionen in Bezug auf den Behälter als Ganzes (wie in Ziel \(o_3\) in (3) beschrieben) werden unter Verwendung der folgenden Einschränkungen festgelegt

Dieses Merkmal ist in Abb. 3 für \(({\tilde{L}},{\tilde{W}})=(L/2,W/2)\ dargestellt, dessen rote Linie die verfügbaren \({ \tilde{x}}_i\) und \({\tilde{y}}_i\)-Werte (siehe (4)).

Darstellung der verfügbaren \({\tilde{x}}_i\)- und \({\tilde{y}}_i\)-Werte, die durch die in (27) angegebenen Einschränkungen für \(({\tilde{L}}, {\tilde{W}}) = (L/2,W/2)\).

In Bezug auf die Komplexität des in dieser Untersuchung vorgeschlagenen 3 dBPP ist die Gesamtzahl der Variablen, die zur Bewältigung einer beliebigen Instanz erforderlich sind, in Tabelle 3 angegeben, wobei unsere Formulierung wie folgt skaliert wird: \({\mathscr {O}}[m^2+nm] \) in Bezug auf Variablen. Darüber hinaus ist die Gesamtmenge der erforderlichen Einschränkungen in Tabelle 4 angegeben, deren Menge quadratisch wächst als \({\mathscr {O}}[m^2+nm]\).

In diesem Abschnitt führen wir ein Experiment durch, um die Anwendbarkeit von Q4RealBPP zu demonstrieren, wobei das Problem als CQM modelliert und dann durch den von D-Wave27 bereitgestellten LeapCQMHybrid gelöst wurde. Zunächst sollte klargestellt werden, dass sich CQM auf das mathematische Modell bezieht, das quadratische Zielfunktionen und quadratische Einschränkungen für binäre und ganzzahlige Variablen verwendet. Als dieses Konzept von D-Wave Systems eingeführt wurde, entwickelte dieses Unternehmen den Hybridlöser LeapCQMHybrid, der auch die Definition von Gleichheits- und Ungleichheitsanforderungen unterstützt. Diese Funktion bietet einen Vorteil im Vergleich zur Quadratic Unconstrained Binary Optimization (QUBO), der nativen Formulierung für die QPUs. Das CQM-Modell und das LeapCQMHybrid führen einige interessante Abkürzungen für eine benutzerfreundlichere Verwendung ein, die es dem Benutzer ermöglichen, ein Problem intuitiver und beschreibender darzustellen und die Übersetzung in eine mathematische Formulierung in Form einer QUBO-Matrix zu vermeiden.

Genauer gesagt sieht der LeapCQMHybrid-Workflow wie folgt aus: Zunächst erhält ein klassisches Frontend die CQM-Formulierung des Problems als Eingabe. Anschließend werden mehrere parallele Berechnungsthreads ausgeführt, die jeweils aus zwei Teilen bestehen: einem heuristischen Modul (HM) und einem Quantenmodul (QM). Einerseits versucht HM, das Problem durch den Einsatz eines hochmodernen heuristischen Lösers zu lösen. Andererseits unterstützt QM diese Lösung, indem es verschiedene Quantenabfragen formuliert, die darauf abzielen, den HM zu vielversprechenden Regionen des Suchraums zu führen oder Verbesserungen an bereits vorhandenen Lösungen zu finden. Dieses QM führt seine Operationen durch, indem es auf den neuesten verfügbaren Quantencomputer von D-Wave zugreift. Zum Zeitpunkt des Verfassens dieses Artikels ist die aktuellste Architektur das Advantage_system, das aus 5616 Qubits besteht, die in einer Pegasus-Topologie organisiert sind. Hybridlöser von D-Wave Systems sind proprietär, daher sind zusätzliche Details zu den Quantenunterprogrammen und der Anzahl der zur Lösung eines Problems verwendeten Qubits nicht öffentlich verfügbar. Weitere Informationen finden interessierte Leser im entsprechenden Bericht von D-Wave32.

Um die Anwendbarkeit von Q4RealBPP zu demonstrieren, haben wir jedoch einen Ad-hoc-Benchmark erstellt, der aus 12 verschiedenen Instanzen des 3 dBPP besteht. Um die Auswirkungen jeder Einschränkung zu analysieren, widmet sich jede Instanz der Bewertung eines bestimmten Merkmals des Problems. Außerdem haben wir zwei spezifische Instanzen generiert, die alle Einschränkungen unseres modellierten 3 dBPP vereinen. In Tabelle 5 beschreiben wir die Hauptmerkmale der 12 verwendeten Instanzen.

Der gesamte Datensatz wurde mithilfe eines selbst entwickelten Python-Skripts (geprägt als Q4RealBPP-DataGen) generiert. Damit dieses Dokument möglichst in sich geschlossen ist, erläutern wir kurz die Funktionsweise von Q4RealBPP-DataGen. Dieses Skript führt zwei Schritte aus, um Q4RealBPP-kompatible Instanzen zu generieren: Erstens generiert Q4RealBPP-DataGen zufällig eine definierte Anzahl von Elementen und folgt dabei der in Ref.8 festgelegten Paketverteilung und den Abmessungen. Anschließend werden die Attribute hinsichtlich Übergewichtsbeschränkung, Affinitäten zwischen Artikelkategorien, Tragfähigkeit und Lastverteilung mithilfe von Q4RealBPP-DataGen vervollständigt. Diese Einschränkungen werden vom Generator zufällig konfiguriert, mit Ausnahme der letzten beiden (Lastaufnahme und Lastausgleich). Diese letzten Merkmale sowie die Behälterabmessungen wurden auf der Suche nach einem realistischen Szenario empirisch festgelegt. Es sollte klargestellt werden, dass Q4RealBPP ein flexibles Framework ist, das es Benutzern ermöglicht, ihre eigenen Einstellungen zu erstellen, indem sie nicht nur die Instanz des Problems konfigurieren, sondern auch die realitätsorientierten Einschränkungen aktivieren oder deaktivieren. Für weitere Informationen sind der vollständige Benchmark der Instanzen und Q4RealBPP-DataGen offen verfügbar in33. Darüber hinaus wird in34 ausführlich erläutert, wie der Datensatz generiert wurde und welches Format die einzelnen Instanzen haben.

In unserem speziellen Anwendungsfall werden die Präferenzen bei der relativen Positionierung (siehe reale BPP-Einschränkungen) als HC für die Lastaufnahme getestet. Unter Berücksichtigung von Fragilitätsproblemen könnte man die Regel anwenden, Paare von Paketen auszuwählen, um auf der Grundlage eines Massenverhältnisses \(\eta\) zu entscheiden, welche Höhe jedes einzelne davon platzieren soll (unter der Annahme, dass das Gewicht mit der Fragilität zusammenhängt). Definieren wir also \(P_3^{-}=\{(i,k)\in I^2\text { }|\text { }i\eta \}\) (also \(b_{i,k,3}=0\text { }\forall (i,k)\in P_3^{-}\)) und \(P^{-}_6=\ {(i,k)\in I^2\text { }|\text { }i\eta \}\) (also \(b_{i ,k,6}=0\text { }\forall (i,k)\in P_6^{-}\)), diese Instanziierung vermeidet Konfigurationen, bei denen Elemente, deren Masse mehr als das \(\eta\)-fache der Masse von beträgt andere sind darüber platziert.

Abbildung 4 stellt die von Q4RealBPP bereitgestellten Ergebnisse für jede der in Tabelle 5 beschriebenen Instanzen dar. Bezüglich der Laufzeit haben wir empirisch ermittelt, wie lange es dauert, bis LeapCQMHybrid diese Instanzen auflöst, und zwar auf \({30}\,{\textrm {s}}\), was einer maximalen Quantum Processing Unit (QPU)-Zugriffszeit von \({0,032}\,{\textrm{s}}\) pro Ausführung entspricht. Schließlich sind für interessierte Leser alle erzielten Ergebnisse frei verfügbar33.

(a) Farbpalette, die in den gelösten Fällen verwendet wurde. (b)–(m) Kurze Beschreibung der in Tabelle 5 aufgeführten Fälle und der von Q4RealBPP bereitgestellten Lösungen. Rote Linien zeigen die Behältergrenzen. Die aktivierten Einschränkungen funktionieren wie erwartet.

Darüber hinaus haben wir zusätzliche Experimente durchgeführt, um die Leistung von Q4RealBPP besser zu verstehen. Zu diesem Zweck haben wir alle in Tabelle 5 beschriebenen Fälle unter unterschiedlichen Zeitvorgaben gelöst. Daher wurden 10 Kopien jeder Instanz unabhängig voneinander ausgeführt, wobei die Zeitlimits auf 5, 10, 30 und 60 Sekunden festgelegt waren. Oben in Abb. 5 sind die erhaltenen Ergebnisse unter Verwendung des Mittelwerts \(\mu\) und der Standardabweichung \(\sigma\) des Energiewerts \(\{e_i\}_{i=1}^{ dargestellt. 10}\) (wobei Energie die Summe der zu optimierenden Zielwerte darstellt), wobei \(e_i\) die i-te Energie ist, die vom Löser nach dem zugewiesenen Zeitlimit für jede Instanz zurückgegeben wird. Darüber hinaus ist auch die mittlere QPU-Zugriffszeit in Nanosekunden angegeben. Als ergänzende Analyse haben wir im unteren Teil von Abb. 5 die Abweichung um die mittleren Energien in Bezug auf berechnet, da die zurückgegebenen Energien je nach Art des Vorfalls erheblich variieren

um die Stabilität der Lösung deutlicher zu veranschaulichen. Diese zusätzliche Analyse ist im unteren Teil von Abb. 5 dargestellt.

Aus Abb. 5 lassen sich drei Hauptschlussfolgerungen ziehen: (1) Im Allgemeinen gilt: Je länger die vorgegebene Zeitspanne, desto geringer ist die zurückgegebene Energie (und damit die bessere Lösungsqualität); (2) die Abweichung um die Mittelwerte der Zielfunktion bleibt über die verschiedenen vorgegebenen Zeitgrenzen hinweg stabil und zeigt keine bemerkenswerte Abhängigkeit von der Art des untersuchten Falles; und (3) obwohl dem Löser unterschiedliche Zeitlimits zugewiesen wurden, schwankte die QPU-Zugriffszeit nicht wesentlich für jeden einzelnen, was darauf hindeutet, dass der Optimierungsprozess im LeapCQMHybrid-Workflow hauptsächlich auf dem heuristischen Modul des Lösers beruht. Trotz des klaren Verhaltens, das unsere Ergebnisse zeigen, sollten weitere Arbeiten durchgeführt werden, um ein tieferes Verständnis der Leistung des vorgestellten Frameworks zu erlangen.

Oben: mittlere Energiewerte mit ihrer entsprechenden Standardabweichung für die 10 Läufe, die zu jeder Instanz gehören. Von links nach rechts betragen die dem Löser gegebenen Zeitlimits für jede Instanz \({5}\,{\textrm{s}}\), \({10}\,{\textrm{s}}\), \({30}\,{\textrm{s}}\) und \({60}\,{\textrm{s}}\). Die über und unter den schattierten Bereichen platzierten Zahlen zeigen die mittlere QPU-Zugriffszeit für jedes Zeitlimit innerhalb jeder Instanz (in Einheiten von Nanosekunden). Unten: unter Verwendung von (28), Abweichung um die mittlere Energie der oben dargestellten Ergebnisse. Für beide Diagramme zeigt der schattierte Bereich den Bereich an, in dem die Minimal- und Maximalwerte während der Studie lagen.

In dieser Arbeit haben wir Q4RealBPP vorgestellt, ein quantenklassisches Framework zur Lösung realer Instanzen des 3 dBPP. Diese Software kann sowohl von Endbenutzern als auch von Praktikern problemlos für den Umgang mit 3-dBPP-Instanzen unter Berücksichtigung von Einschränkungen wie Gewicht, Tragfähigkeit, Paketkategorien und Lastausgleich verwendet werden.

Um die Anwendbarkeit von Q4RealBPP zu beweisen, haben wir es an 12 Instanzen unterschiedlicher Art getestet, mit der Hauptabsicht, die Fähigkeit der Methode zu demonstrieren, reale Einschränkungen zu berücksichtigen. Wie in Abb. 4 dargestellt, hat Q4RealBPP alle generierten Instanzen erfolgreich bewältigt und dabei verschiedene reale Situationen berücksichtigt. Besonders hervorzuheben sind die letzten beiden Instanzen, 3dBPP_11 und 3dBPP_12 (Abb. 4l, m), in denen alle Einschränkungen aktiviert sind.

Die zukünftige Arbeit umfasst die folgenden Interessen: Erstens haben wir geplant, eine fortgeschrittenere Version des Q4RealBPP zu entwickeln, um das Framework auf andere BPP-Varianten zu verallgemeinern und weitere Funktionen wie die Kategorisierung von Elementen in mehreren Klassen zu berücksichtigen. Darüber hinaus beabsichtigen wir, dieses Framework in Verbindung mit ergänzenden Algorithmen der künstlichen Intelligenz zu nutzen, um seine potenziellen Anwendungen in der realen Welt zu verbessern. Schließlich würde ein gründlicher Vergleich zwischen Q4RealBPP und jeder herkömmlichen Methode der künstlichen Intelligenz zu einer tiefergehenden Analyse unseres Frameworks im Hinblick auf die Robustheit der Ergebnisse und Ausführungszeiten beitragen. Auf jeden Fall würde dieser wertvolle Vergleich unweigerlich die Implementierung einer klassischen Technik erfordern, die vollständig an das in diesem Artikel beschriebene 3-dBPP-Problem angepasst ist. Aus diesem Grund haben wir diese Aktion als zukünftige Arbeit festgelegt. Abschließend sind die Autoren der Ansicht, dass in dieser Hinsicht weitere Arbeiten erforderlich sind. Daher ermutigen wir Forscher auf diesem Gebiet, unsere Benchmarking-Instanzen33 zu nutzen und anzupassen, um bereits bestehende und neuartige Frameworks zu testen und zu vergleichen.

Der Code ist auf begründete Anfrage beim entsprechenden Autor (EO) erhältlich. Die verwendeten Daten sowie Q4RealBPP-DataGen und alle in dieser Arbeit diskutierten Ergebnisse sind unter http://dx.doi.org/10.17632/y258s6d939.1 verfügbar.

Garey, MR & Johnson, DS Approximationsalgorithmen für Bin-Packing-Probleme: Eine Umfrage. In Analysis and Design of Algorithms in Combinatorial Optimization 147–172 (Springer, 1981).

Kapitel Google Scholar

Munien, C. & Ezugwu, AE Metaheuristische Algorithmen für eindimensionale Bin-Packing-Probleme: Ein Überblick über aktuelle Fortschritte und Anwendungen. J. Intell. Syst. 30, 636–663 (2021).

Google Scholar

Delorme, M., Iori, M. & Martello, S. Bin Pack- und Schneidstoffprobleme: Mathematische Modelle und exakte Algorithmen. EUR. J. Oper. Res. 255, 1–20 (2016).

Artikel MathSciNet MATH Google Scholar

Martello, S., Pisinger, D. & Vigo, D. Das dreidimensionale Bin-Packing-Problem. Oper. Res. 48, 256–267 (2000).

Artikel MathSciNet MATH Google Scholar

Lodi, A., Martello, S. & Vigo, D. Heuristische Algorithmen für das dreidimensionale Bin-Packing-Problem. EUR. J. Oper. Res. 141, 410–420 (2002).

Artikel MathSciNet MATH Google Scholar

Yang, H. & Shi, J. Ein hybrider CD/VND-Algorithmus für dreidimensionales Bin-Packing. Im Jahr 2010 Zweite Internationale Konferenz über Computermodellierung und Simulation, vol. 3, 430–434 (IEEE, 2010).

Parreño, F., Alvarez-Valdés, R., Oliveira, JF & Tamarit, JM Ein hybrider Greif-/VND-Algorithmus für zwei- und dreidimensionales Bin-Packing. Ann. Oper. Res. 179, 203–220 (2010).

Artikel MathSciNet MATH Google Scholar

Elhedhli, S., Gzara, F. & Yildiz, B. Dreidimensionale Behälterverpackung und gemischte Palettierung. Informiert J. Optim. 1, 323–352 (2019).

Artikel MathSciNet Google Scholar

Ramos, AG, Silva, E. & Oliveira, JF Eine neue Lastausgleichsmethode für Containerladeprobleme im Straßentransport. EUR. J. Oper. Res. 266, 1140–1152 (2018).

Artikel MathSciNet MATH Google Scholar

Paquay, C., Schyns, M. & Limbourg, S. Eine gemischte ganzzahlige Programmierformulierung für das dreidimensionale Bin-Packing-Problem, das sich aus einer Luftfrachtanwendung ergibt. Int. Trans. Oper. Res. 23, 187–213 (2016).

Artikel MathSciNet MATH Google Scholar

Paquay, C., Limbourg, S., Schyns, M. & Oliveira, JF Mip-basierte konstruktive Heuristik für das dreidimensionale Bin-Packing-Problem mit Transportbeschränkungen. Int. J. Prod. Res. 56, 1581–1592 (2018).

Artikel MATH Google Scholar

Silva, EF, Machado Toffolo, TA & Wauters, T. Exakte Methoden zum dreidimensionalen Schneiden und Verpacken: Eine vergleichende Studie zu Einzelbehälterproblemen. Berechnen. Oper. Res. 109, 12–27 (2019).

Artikel MathSciNet MATH Google Scholar

Lucas, A. Ising Formulierungen vieler NP-Probleme. Vorderseite. Physik. 2, 25 (2014).

Artikel Google Scholar

Gill, SS et al. Quantencomputing: Eine Taxonomie, systematische Überprüfung und zukünftige Richtungen. Softw. Üben. Exp. 52, 66–114 (2022).

Artikel Google Scholar

Chandarana, P. et al. Meta-Learning digitalisierte-konterdiabatische Quantenoptimierung. arXiv:2206.09966 (arXiv-Vorabdruck) (2022).

Huang, T. et al. Zeitoptimales Quantenfahren durch Variationsschaltungslernen. arXiv:2211.00405 (arXiv-Vorabdruck) (2022).

Luckow, A., Klepsch, J. & Pichlmeier, J. Quantencomputing: Auf dem Weg zu Branchenreferenzproblemen. Digitale Welt 5, 38–45 (2021).

Artikel Google Scholar

Osaba, E., Villar-Rodriguez, E. & Oregi, I. Eine systematische Literaturübersicht zum Quantencomputing für Routing-Probleme. IEEE Access 20, 20 (2022).

Google Scholar

Orús, R., Mugel, S. & Lizaso, E. Quantencomputing für das Finanzwesen: Überblick und Aussichten. Rev. Phys. 4, 100028 (2019).

Artikel Google Scholar

Garcia-de Andoin, M., Osaba, E., Oregi, I., Villar-Rodriguez, E. & Sanz, M. Hybride quantenklassische Heuristik für das Bin-Packing-Problem. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2214–2222 (Association for Computing Machinery, 2022).

De Andoin, MG, Oregi, I., Villar-Rodriguez, E., Osaba, E. & Sanz, M. Vergleichender Benchmark eines Quantenalgorithmus für das Bin-Packing-Problem. Im Jahr 2022 IEEE Symposium Series on Computational Intelligence (SSCI), 930–937 (2022).

Bozhedarov, A. et al. Quanten- und quanteninspirierte Optimierung zur Lösung des Minimum-Bin-Packing-Problems. arXiv:2301.11265 (arXiv-Vorabdruck) (2023).

Layeb, A. & Boussalia, SR Ein neuartiger quanteninspirierter Kuckuckssuchalgorithmus für das Bin-Packing-Problem. Int. J. Inf. Technol. Berechnen. Wissenschaft. 4, 58–67 (2012).

Google Scholar

Zendaoui, Z. & Layeb, A. Adaptiver Kuckuckssuchalgorithmus für das Bin-Packing-Problem. In Modellierung und Implementierung komplexer Systeme 107–120 (Springer, 2016).

Kapitel Google Scholar

Layeb, A. & Boussalia, SR Ein neuartiger, von gierigen Quanten inspirierter Kuckuckssuchalgorithmus für Bin-Packing-Probleme variabler Größe. Int. J. Mathe. Oper. Res. 6, 732–751 (2014).

Artikel MathSciNet Google Scholar

Zhang, G. Quanteninspirierte evolutionäre Algorithmen: Eine Umfrage und empirische Studie. J. Heurist. 17, 303–351 (2011).

Artikel MATH Google Scholar

D-Wave-Entwickler. Messung der Leistung des Leap Constrained Quadratic Model Solver. Technik. Rep. 14-1065A-A, D-Wave Systems Inc. (2022).

D-Wave Ocean-Entwicklerteam. 3d-bin-packing (GitHub-Repository) (2022). Zuletzt abgerufen am 27.02.2023.

Preskill, J. Quantencomputing in der NISQ-Ära und darüber hinaus. Quantum 2, 79 (2018).

Artikel Google Scholar

Dahmani, N. & Krichen, S. Lösung eines Lastausgleichsproblems mit einem Ansatz zur Partikelschwarmoptimierung mit mehreren Zielen: Anwendung auf den Flugzeugfrachttransport. Int. J. Oper. Res. 27, 62–84 (2016).

Artikel MathSciNet MATH Google Scholar

Zhu, R. & Wang, L. Forschung zur Echtzeit-Kanaloptimierung von Schiffen basierend auf einem Lastausgleichsalgorithmus. In der 29. Internationalen Ozean- und Polartechnikkonferenz (OnePetro, 2019).

D-Wave-Entwickler. Hybridlöser für eingeschränkte quadratische Modelle. Technik. Rep. 14-1055A-A, D-Wave Systems Inc. (2021).

Osaba, E., Villar, E. & V. Romero, S. Benchmark-Datensatz und Instanzgenerator für reale 3dbpp. https://doi.org/10.17632/y258s6d939.1 (2023). Online bei Mendeley Data.

Osaba, E., Villar-Rodriguez, E. & Romero, VS Benchmark-Datensatz und Instanzgenerator für reale dreidimensionale Bin-Packing-Probleme. Datenbrief 20, 109309 (2023).

Artikel Google Scholar

Referenzen herunterladen

Diese Arbeit wurde von der baskischen Regierung durch das HAZITEK-Programm (Q4_Real-Projekt, ZE-2022/00033) und vom spanischen CDTI durch das R&D Projects Brewer 2021-Programm (QOptimiza-Projekt, 095359) und das Missions Science and Innovation Program (CUCO) unterstützt ). unter Grant MIG-20211005.

TECNALIA, Baskische Forschungs- und Technologieallianz (BRTA), 48160, Derio, Spanien

Sebastian V. Rosemary, Eneko Osaba, Esther Villar-Rodriguez, Izaskun Oregi und Yue Ban

EUNEIZ, 01013, Vitoria-Gasteiz, Spanien

Izaskun Oregi

Sie können diesen Autor auch in PubMed Google Scholar suchen

Sie können diesen Autor auch in PubMed Google Scholar suchen

Sie können diesen Autor auch in PubMed Google Scholar suchen

Sie können diesen Autor auch in PubMed Google Scholar suchen

Sie können diesen Autor auch in PubMed Google Scholar suchen

Alle Autoren haben die Forschung konzipiert. SVR formulierte das Problem und entwickelte den Code. EVR hat den Instanzgenerator formuliert und entwickelt. SVR und EO konzipierten und führten die Experimente durch. Alle Autoren haben das Manuskript verfasst. Alle Autoren haben das Manuskript überprüft.

Korrespondenz mit Eneko Osaba.

Die Autoren geben an, dass keine Interessenkonflikte bestehen.

Springer Nature bleibt neutral hinsichtlich der Zuständigkeitsansprüche in veröffentlichten Karten und institutionellen Zugehörigkeiten.

Open Access Dieser Artikel ist unter einer Creative Commons Attribution 4.0 International License lizenziert, die die Nutzung, Weitergabe, Anpassung, Verbreitung und Reproduktion in jedem Medium oder Format erlaubt, sofern Sie den/die ursprünglichen Autor(en) und die Quelle angemessen angeben. Geben Sie einen Link zur Creative Commons-Lizenz an und geben Sie an, ob Änderungen vorgenommen wurden. Die Bilder oder anderes Material Dritter in diesem Artikel sind in der Creative Commons-Lizenz des Artikels enthalten, sofern in der Quellenangabe für das Material nichts anderes angegeben ist. Wenn Material nicht in der Creative-Commons-Lizenz des Artikels enthalten ist und Ihre beabsichtigte Nutzung nicht gesetzlich zulässig ist oder über die zulässige Nutzung hinausgeht, müssen Sie die Genehmigung direkt vom Urheberrechtsinhaber einholen. Um eine Kopie dieser Lizenz anzuzeigen, besuchen Sie http://creativecommons.org/licenses/by/4.0/.

Nachdrucke und Genehmigungen

V. Romero, S., Osaba, E., Villar-Rodriguez, E. et al. Hybrider Ansatz zur Lösung realer Bin-Packing-Problemfälle mithilfe von Quanten-Annealern. Sci Rep 13, 11777 (2023). https://doi.org/10.1038/s41598-023-39013-9

Zitat herunterladen

Eingegangen: 06. März 2023

Angenommen: 18. Juli 2023

Veröffentlicht: 21. Juli 2023

DOI: https://doi.org/10.1038/s41598-023-39013-9

Jeder, mit dem Sie den folgenden Link teilen, kann diesen Inhalt lesen:

Leider ist für diesen Artikel derzeit kein gemeinsam nutzbarer Link verfügbar.

Bereitgestellt von der Content-Sharing-Initiative Springer Nature SharedIt

Durch das Absenden eines Kommentars erklären Sie sich damit einverstanden, unsere Nutzungsbedingungen und Community-Richtlinien einzuhalten. Wenn Sie etwas als missbräuchlich empfinden oder etwas nicht unseren Bedingungen oder Richtlinien entspricht, kennzeichnen Sie es bitte als unangemessen.