Enfoque híbrido para resolver problemas reales.

Scientific Reports volumen 13, número de artículo: 11777 (2023) Citar este artículo

418 Accesos

2 altmétrico

Detalles de métricas

El embalaje eficiente de artículos en contenedores es una tarea diaria común. Conocido como Bin Packing Problem, ha sido intensamente estudiado en el campo de la inteligencia artificial, gracias al gran interés de la industria y la logística. Desde hace décadas, se han propuesto muchas variantes, siendo el problema del embalaje de contenedores tridimensional el más cercano a los casos de uso del mundo real. Introducimos un marco híbrido cuántico-clásico para resolver problemas de empaque de contenedores tridimensionales del mundo real (Q4RealBPP), considerando diferentes características realistas, tales como: (1) dimensiones del paquete y del contenedor, (2) restricciones de sobrepeso, (3) afinidades entre categorías de artículos y (4) preferencias para el pedido de artículos. Q4RealBPP permite resolver instancias de 3 dBPP orientadas al mundo real, contemplando restricciones muy apreciadas por los sectores industrial y logístico.

La optimización del envasado de productos en un número finito de contenedores es una tarea diaria crucial en el ámbito de la producción y la distribución. Dependiendo de las características tanto de los paquetes como de los contenedores, se pueden formular múltiples problemas de embalaje, generalmente conocidos como Bin Packing Problems (BPP)1. Dentro de esta categoría, el BPP unidimensional (1 dBPP) se considera el más simple2, cuyo objetivo es empaquetar todos los artículos en el menor número de contenedores posible. Se han propuesto muchas variantes con un número variable de limitaciones para hacer frente a situaciones reales en la logística y la industria3. El BPP tridimensional (3 dBPP)4, en el que cada paquete tiene tres dimensiones: alto, ancho y profundidad, es la variante más conocida y más desafiante. Destacado en varios estudios5,6,7, 3 dBPP tiene un interés práctico en muchos entornos industriales. En los últimos años, se ha formulado para poseer aplicaciones diversas y prácticas, como carga de palés8, transporte por carretera9, carga aérea10, etc. Debido a su complejidad, 3 dBPP también se emplea de forma recurrente como punto de referencia para probar métodos y mecanismos recientemente desarrollados11,12. .

En otro frente, la computación cuántica aún se encuentra en su etapa inicial, pero ha atraído mucha atención de la comunidad científica, ya que ofrece a investigadores y profesionales un paradigma revolucionario para abordar diferentes tipos de problemas prácticos de optimización13,14,15,16. En particular, los recocidos cuánticos se han aplicado recientemente a una amplia variedad de problemas de optimización inspirados en los campos de la industria17, la logística18 y la economía19. Sin embargo, la investigación sobre BPP llevada a cabo en la comunidad cuántica aún es escasa, a pesar de que BPP ha sido ampliamente estudiado clásicamente como un problema de optimización.

El trabajo pionero sobre BPP en el campo de la computación cuántica presenta un método híbrido cuántico-clásico para resolver el 1 dBPP20, cuyo solucionador se compone de dos módulos: (1) una subrutina cuántica con la que buscar un conjunto de configuraciones factibles para llenar una contenedor único y (2) una heurística computacional clásica que construye soluciones completas empleando los subconjuntos dados por la subrutina cuántica. Para profundizar el rendimiento de la subrutina cuántica desarrollada, se realizaron pruebas adicionales con un muestreo aleatorio y una heurística basada en paseos aleatorios21. Además de esos dos artículos, un estudio adicional formula un problema relacionado con la industria de la energía atómica como 1 dBPP, resolviéndolo utilizando el recocido cuántico D-Wave22. Otros trabajos muestran técnicas de computación evolutiva de inspiración cuántica como una alternativa para abordar problemas relacionados con BPP23,24,25. Las técnicas de inspiración cuántica son una clase específica de algoritmos evolutivos que utilizan la física cuántica para definir sus operaciones y están diseñadas para ejecutarse en una computadora clásica26. Por tanto, no se pueden ejecutar en ninguna máquina cuántica.

En contraste con 1 dBPP, abordar 3 dBPP en el dominio cuántico es mucho más desafiante debido a dos motivos relacionados: (1) su complejidad, que aumenta a medida que se tienen en cuenta las limitaciones del mundo real y (2) el estado incipiente de desarrollo de los actuales ordenadores cuánticos comerciales con capacidades aún limitadas por la decoherencia y los errores, lo que podría suponer un obstáculo para resolver problemas muy restringidos. En este artículo, presentamos un marco de computación híbrido cuántico-clásico para 3 dBPP orientado al mundo real, que se denomina Quantum for Real Bin Packing Problem (Q4RealBPP). El marco propuesto recurre al solucionador híbrido del modelo cuadrático restringido por salto (CQM) (LeapCQMHybrid27) de D-Wave. Al mismo tiempo, Q4RealBPP se basa en un código existente28. Este código de referencia es un excelente punto de partida, que allanó el camino para estas dos contribuciones principales desarrolladas en este trabajo:

Eficiencia del código: en el código de referencia, el problema está formulado de tal manera que se necesitan muchas variables (por lo tanto, qubits). Esta cuestión aborda el problema de la viabilidad en el contexto del hardware cuántico en la ruidosa era cuántica de escala intermedia (NISQ)29. Por tanto, la optimización del código es crucial para afrontar problemas complejos. Q4RealBPP proporciona un paso adelante en este aspecto al explorar cómo se pueden pulir las restricciones acuñadas como restricciones intrínsecas. Estas restricciones son las necesarias para la definición de BPP (por ejemplo, no colocar cajas fuera de un contenedor) y fueron introducidas previamente en el código de referencia. Así, el novedoso trabajo realizado en esta faceta concreta ha implicado, entre otros, la redefinición de algunas fórmulas matemáticas que definen estas restricciones intrínsecas, y la eliminación de un objetivo de optimización redundante. Gracias a este procedimiento, se pueden formular problemas utilizando menos variables, lo que impacta directamente en la capacidad del framework para abordar instancias más grandes.

Aplicabilidad de la herramienta: el código de referencia está orientado a resolver la variante más básica del 3 dBPP considerando únicamente la dimensión tanto de los bultos como de los contenedores. Esta configuración dista mucho de las exigencias reales del cliente, donde probablemente intervengan otras características como pesos, balanceo de carga o incompatibilidades, entre otras. Hemos profundizado en esta dirección mediante la implementación de un conjunto de restricciones denominadas Restricciones de BPP del mundo real. Todas estas restricciones representan un valor agregado para Q4RealBPP, habiendo requerido una extensión significativa de la formulación matemática del problema. Profundizamos en este aspecto en siguientes apartados.

Teniendo en cuenta estos factores, Q4RealBPP se orienta a campos relacionados con la industria y la logística, contemplando problemas como la organización de contenedores portuarios, la introducción de paquetes en furgonetas y camiones de reparto o la colocación de productos alimenticios en palets de distribución, entre otros. Con la ayuda de un método híbrido cuántico-clásico, Q4RealBPP representa un sólido paso adelante para resolver 3 dBPP con el claro propósito de afrontar problemas centrados en el mundo real y apreciados por los usuarios finales y las empresas. Las características contempladas por Q4RealBPP involucran (1) dimensiones de paquetes y contenedores, (2) peso máximo permitido por contenedor, (3) afinidades positivas y negativas entre categorías de artículos y (4) preferencias para ordenar paquetes (en términos de soporte de carga y equilibrio de carga). ). Para demostrar su aplicación, hemos realizado una experimentación compuesta por 12 instancias diferentes que sirven como ejemplos ilustrativos. Además, Q4RealBPP permite a los usuarios crear fácilmente instancias flexibles y bien definidas para adaptar una gran cantidad de situaciones del mundo real para resolverlas en la computadora cuántica.

El resto del artículo está organizado de la siguiente manera: en “Formulación matemática” se presenta la formulación de 3 dBPP y su correspondiente notación. Además, se realiza un estudio detallado de los recursos computacionales necesarios para instancias arbitrarias. En “Resultados experimentales”, se prueba la aplicabilidad de esta herramienta utilizando un conjunto de casos realistas como entrada. Finalmente, las conclusiones derivadas de los resultados presentados y nuestros planes futuros se dan en “Conclusiones y trabajo futuro”.

En esta sección, describimos en detalle la formulación matemática de la variante de 3 dBPP abordada en esta investigación. Primero, los parámetros de entrada y las variables que componen el problema se muestran en la Tabla 1.

Los 3 dBPP se pueden resolver como un problema de optimización donde se debe definir una función de costos adecuada a minimizar. En nuestro caso, esta función de costos se representa como la suma de tres objetivos. La fuerza otorgada a cada objetivo, es decir, la relevancia que tiene cada uno, depende de las preferencias del usuario simplemente multiplicando cada objetivo por un peso adecuado. Por lo tanto, el problema se puede plantear como \(\min \text { }\sum _{i=1}^3\omega _io_i\) con \(\omega _i\) los pesos de cada objetivo \(o_i\). En nuestro estudio, no consideraremos este sesgo, es decir, \(\omega _i=1\text { }\forall i\).

El primer y principal objetivo minimiza la cantidad total de contenedores utilizados para localizar los paquetes. Esto se puede lograr minimizando

Además, para garantizar que los artículos se empaquetan desde el suelo hasta la parte superior del contenedor, evitando soluciones con paquetes flotantes, se define un segundo objetivo minimizando la altura promedio de los artículos para todos los contenedores.

Además de estos dos objetivos reformulados a partir del código de referencia28, agregamos un tercer objetivo opcional \(o_3\) para tener en cuenta la función de equilibrio de carga. Esta preocupación es particularmente importante cuando el medio de transporte elegido son los aviones de carga y los viajes en barco30,31, por ejemplo. En esas situaciones, los paquetes deben distribuirse uniformemente alrededor de una coordenada xy determinada dentro del contenedor. Podemos abordar esto calculando la llamada distancia de taxi o Manhattan entre artículos y el centro de masa deseado para cada contenedor. Como resultado, también se reducen las brechas entre artículos. En este sentido, el tercer objetivo a minimizar es

con

donde \(0\le x_i< nL\) (contenedores apilados horizontalmente) y \(0\le y_i< W\) \(\forall i\in I\). Este término objetivo minimiza para cada elemento la distancia entre el centro de proyección de masa en el plano xy y la coordenada \(({\tilde{L}},{\tilde{W}})\) de cada contenedor.

Los objetivos definidos anteriormente están sujetos a ciertas restricciones, que son esenciales para derivar soluciones realistas. Todo el conjunto de restricciones se divide en dos categorías: las intrínsecas a la definición de las AFF (restricciones intrínsecas) y las relevantes desde una perspectiva del mundo real (restricciones de las AFF del mundo real).

Orientaciones de artículos: el hecho de que dentro de un contenedor cada artículo debe tener solo una orientación se puede implementar usando

Conjunto de posibles orientaciones \(k\in K_i\) para un elemento dado i de dimensiones \((l_i,w_i,h_i)\). (a) \(k = 1\), (b) \(k = 2\), (c) \(k = 3\), (d) \(k = 4\), (e) \(k = 5\), (f) \(k = 6\). Ver Tabla 2.

Las orientaciones dan lugar a la longitud, el ancho y la altura efectivos de los elementos a lo largo de los ejes x, y y z.

y debido a (5), solo un término \(r_{i,k}\) es distinto de cero en cada ecuación.

Se debe considerar que podrían existir elementos con simetrías geométricas, como los cúbicos donde no aplican rotaciones. En el código de referencia28 se consideran orientaciones redundantes y no redundantes. En nuestra formulación, previamente verificamos si existen estas simetrías para definir \(K_i\) para cada elemento. Gracias a esto, (6)–(8) se simplifican filtrando orientaciones redundantes y dando lugar a una formulación que utiliza menos variables (por lo tanto, qubits) para representar el mismo problema, donde \(\kappa =\sum _{i=1} ^m|K_i|\le 6m\) se necesitan variables \(r_{i,k}\). Para \(i\in I_\text {c}\) con \(I_\text {c}{:}{=}\{i\in I\,|\,l_i=w_i=h_i\}\) ( elementos cúbicos), podemos establecer \(r_{i,1}=1\) y 0 en caso contrario, satisfaciendo así (5) de antemano. En la Tabla 2 podemos ver los conjuntos de orientación no redundantes para un elemento i en función de sus dimensiones. Este mecanismo simple reduce la complejidad del problema, siendo favorable para que el hardware cuántico lo implemente.

Restricciones que no se superponen: dado que estamos considerando paquetes rígidos, es decir, no se pueden superponer, es necesario definir un conjunto de restricciones para superar estas configuraciones. Para ello debe ocurrir al menos una de estas situaciones (ver Fig. 2)

Como se analizó con la variable de orientación \(r_{i,k}\) en (5), la posición relativa entre los elementos i y k debe ser única, por lo que

Representación de \(b_{i,k,q}\) activada para todas las posiciones relativas \(q\in Q\) entre los elementos i y k. Ver (9)-(14). Ambos están en contacto pero no es obligatorio. (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\).

Restricciones de asignación de artículos y contenedores: el siguiente conjunto de restricciones garantiza un comportamiento adecuado durante la asignación de artículos y contenedores. Para evitar empacar duplicados del mismo artículo, cada artículo debe ir exactamente a un contenedor, donde

La siguiente fórmula verifica si los artículos se empaquetan dentro de contenedores que ya están en uso.

por lo que activa \(v_j\) si es necesario durante el empaquetado. Los contenedores se pueden activar secuencialmente para evitar soluciones duplicadas, asegurando que

Restricciones de límites de bin: para contemplar los límites de bin, se debe cumplir el siguiente conjunto de restricciones

donde (19) garantiza que los artículos i colocados dentro del contenedor j no estén fuera del último contenedor (n-ésimo contenedor) a lo largo del eje x, (20) asegura que el artículo i esté ubicado dentro de su contenedor j correspondiente a lo largo del eje x (activado si \(n>1\)), (21) confirma que el artículo i colocado dentro del contenedor j no está afuera a lo largo del eje y, mientras que (22) asegura que el artículo i asignado dentro del contenedor j no está afuera a lo largo del eje y eje Z.

En esta subsección introducimos aquellas restricciones relacionadas con la perspectiva operativa del problema, es decir, aquellas que consideran situaciones industriales del mundo real. Todas las siguientes restricciones son opcionales en nuestra formulación.

Restricción de sobrepeso: el peso de cada paquete y la capacidad máxima de los contenedores son datos contextuales habituales para evitar superar la capacidad máxima de peso de los contenedores, así que evite los contenedores sobrecargados. Podemos introducir esta restricción como

Esta restricción se activa si se da la capacidad máxima M.

Afinidades entre categorías de paquetes: comúnmente existen preferencias por separar algunos paquetes en diferentes bins (afinidades negativas o incompatibilidades) o, por el contrario, agruparlos en un mismo contenedor (afinidades positivas). Consideremos \(I_\alpha {:}{=}\{i\in I\text { }|\text { }{} \texttt {id}\text { de }i\text { es igual a }\ alpha \}\), es decir, \(I_\alpha \subset I\) es un subconjunto de todos los elementos etiquetados con id igual a \(\alpha\). Dado un conjunto de p afinidades negativas \(A^\text {neg}{:}{=}\{(\alpha _1,\beta _1),\dots ,(\alpha _p,\beta _p)\}\) , entonces la restricción será

Para activar esta restricción se debe dar un conjunto de incompatibilidades. Además, podemos satisfacer de antemano \(\nu {:}{=}6n\sum _{(\alpha ,\beta )\in A^\text {neg}}|I_\alpha ||I_\beta |\ ) restricciones que no se superponen (ver (9) – (14)), lo que lleva a una formulación más simple. Por el contrario, dado un conjunto de afinidades positivas \(A^\text {pos}\) como se indica con \(A^\text {neg}\), entonces la restricción se planteará de manera que

Esta restricción se activa si se da un conjunto de afinidades positivas. Si se dan \(A^\text {pos}\) y \(A^\text {neg}\), entonces ambas restricciones se pueden introducir usando una sola fórmula sumando (24) y (25).

Preferencias en posicionamiento relativo: el posicionamiento relativo de ítems exige que algunos de ellos deban ubicarse en una posición específica con respecto a otros ítems existentes. Esta preferencia permite introducir el ordenamiento de un conjunto de paquetes según sus posiciones respecto a los ejes. Por lo tanto, esta preferencia ayuda a realizar pedidos en muchos casos reales, tales como: entrega de paquetes (un artículo i que debe entregarse antes de que el artículo k se coloque preferiblemente más cerca de la puerta del maletero) o soporte de carga (ningún paquete pesado debe descansar sobre paquetes endebles). ), entre otros.

Respecto a esta preferencia, podemos definir dos perspectivas diferentes para tratar el posicionamiento relativo:

Posicionamiento a evitar (\(P_q^{-}\)): la lista de elementos (i, k) no debe estar en la posición relativa \(q\in Q\) especificada. Entonces, se espera \(b_{i,k,q}=0\), favoreciendo configuraciones donde el solucionador selecciona \(q'\in Q\) con \(q'\ne q\) para el posicionamiento relativo de los elementos. (yo, k).

Posicionamiento a favor (\(P_q^{+}\)): la lista de elementos (i, k) debe estar en una determinada posición relativa q. Activada esta preferencia, \(b_{i,k,q}=1\) debería mantenerse y en consecuencia, \(b_{i,k,q'}=0 \ \forall q'\ne q\).

Formalmente, estas preferencias se escriben como

Estas preferencias también podrían tratarse como preselecciones obligatorias. En tal caso, el número de variables necesarias se reduciría, al igual que el espacio de búsqueda. Si dejamos \(\smash [t]{p^{-}=\sum _{q\in Q}|P_q^{-}|}\) y \(\smash [t]{p^{+} =\sum _{q\in Q}|P_q^{+}|}\) con \(\smash [t]{P^{-}_q\cap P^{+}_{q'}=\varnothing }\), con base en (15), la cantidad de variables reducidas estaría dada por \(\smash [t]{p^{-}+6p^{+}}\). Además, \(\smash [t]{n(p^{-}+5p^{+})}\) restricciones no superpuestas (ver (9)–(14)) se satisfacen directamente y pueden ignorarse, por lo tanto simplificando el problema. En este artículo, en aras de la claridad, estas preferencias se han aplicado con fines de soporte de carga como restricciones duras (HC), como se explica en los próximos "Resultados experimentales".

Equilibrio de carga: para activar esta restricción se debe proporcionar un centro de masa objetivo. Las posiciones globales con respecto al contenedor en su conjunto (como se describe en el objetivo \(o_3\) en (3)), se fijan utilizando las siguientes restricciones

Esta característica está representada en la Fig. 3 para \(({\tilde{L}},{\tilde{W}})=(L/2,W/2)\), cuya línea roja muestra el \({ \tilde{x}}_i\) y \({\tilde{y}}_i\) valores (ver (4)).

Representación de los valores \({\tilde{x}}_i\) y \({\tilde{y}}_i\) disponibles garantizados por las restricciones dadas en (27) para \(({\tilde{L}}, {\tilde{W}}) = (L/2,W/2)\).

En cuanto a la complejidad de los 3 dBPP propuestos en esta investigación, la cantidad total de variables necesarias para abordar una instancia arbitraria se da en la Tabla 3, donde nuestra formulación escala como \({\mathscr {O}}[m^2+nm] \) en términos de variables. Además, la cantidad total de restricciones requeridas se proporciona en la Tabla 4, cuya cantidad crece cuadráticamente como \({\mathscr {O}}[m^2+nm]\).

En esta sección, llevamos a cabo una experimentación para demostrar la aplicabilidad de Q4RealBPP, donde el problema se modeló como CQM y luego se resolvió mediante LeapCQMHybrid proporcionado por D-Wave27. Inicialmente, debe quedar claro que CQM se refiere al modelo matemático que utiliza funciones objetivo cuadráticas y restricciones cuadráticas sobre variables binarias y enteras. Como este concepto fue introducido por D-Wave Systems, esta empresa desarrolló el solucionador híbrido LeapCQMHybrid, que también admite la definición de requisitos de igualdad y desigualdad. Esta característica aporta una ventaja en comparación con la optimización binaria cuadrática sin restricciones (QUBO), que es la formulación nativa de las QPU. El modelo CQM y LeapCQMHybrid introducen algunos atajos interesantes para un uso más amigable, permitiendo al usuario proporcionar un problema de una manera más intuitiva y descriptiva, evitando la traducción a una formulación matemática en forma de matriz QUBO.

Más específicamente, el flujo de trabajo LeapCQMHybrid es el siguiente: primero, una interfaz clásica recibe la formulación CQM del problema como entrada. Luego, ejecuta una serie de subprocesos de cálculo paralelos, donde cada uno de ellos se compone de dos partes: un módulo heurístico (HM) y un módulo cuántico (QM). Por un lado, HM intenta resolver el problema utilizando un solucionador heurístico de última generación. Por otro lado, QM ayuda a esta resolución formulando diferentes consultas cuánticas con el objetivo de guiar al HM hacia regiones prometedoras del espacio de búsqueda, o encontrar mejoras a soluciones ya existentes. Este QM realiza sus operaciones accediendo a la última computadora cuántica disponible de D-Wave. Al momento de escribir este artículo, la arquitectura más actualizada es Advantage_system, compuesta por 5616 qubits organizados en una topología de Pegasus. Los solucionadores híbridos de D-Wave Systems son propietarios, por lo que los detalles adicionales sobre las subrutinas cuánticas y la cantidad de qubits utilizados para resolver un problema no están disponibles públicamente. Los lectores interesados ​​pueden consultar el informe relacionado proporcionado por D-Wave para obtener más información32.

Dicho esto, para demostrar la aplicabilidad de Q4RealBPP, hemos creado un punto de referencia ad hoc compuesto por 12 instancias diferentes de 3 dBPP. Para analizar el impacto de cada restricción, cada instancia se dedica a evaluar una característica específica del problema. Además, hemos generado dos instancias específicas que reúnen todas las restricciones de nuestro modelado de 3 dBPP. Describimos en la Tabla 5 las principales características de las 12 instancias utilizadas.

Todo el conjunto de datos se generó empleando un script Python de desarrollo propio (acuñado como Q4RealBPP-DataGen). Para que este artículo sea lo más autónomo posible, explicamos brevemente cómo funciona Q4RealBPP-DataGen. Este script realiza dos pasos para generar instancias compatibles con Q4RealBPP: en primer lugar, Q4RealBPP-DataGen genera aleatoriamente un número definido de elementos, siguiendo la distribución del paquete y las dimensiones establecidas en la Ref.8. Luego, los atributos relacionados con la restricción de sobrepeso, las afinidades entre categorías de artículos, la capacidad de carga y el equilibrio de carga se completan mediante Q4RealBPP-DataGen. Estas restricciones son configuradas aleatoriamente por el generador, excepto las dos últimas (soporte de carga y equilibrio de carga). Estas últimas características, así como las dimensiones del contenedor, se han fijado empíricamente, en busca de un escenario realista. Debe aclararse que Q4RealBPP es un marco flexible que permite a los usuarios crear su propia configuración no solo configurando la instancia del problema sino también activando o desactivando las restricciones orientadas al mundo real. Para obtener más información, el benchmark completo de instancias y Q4RealBPP-DataGen están disponibles de forma abierta en33. Además, en 34 se proporciona una explicación detallada sobre cómo se generó el conjunto de datos y el formato de cada instancia.

En nuestro caso de uso específico, las preferencias en el posicionamiento relativo (consulte las restricciones de BPP del mundo real) se prueban como HC para soportar carga. Teniendo en cuenta los problemas de fragilidad, se podría aplicar la regla de elegir pares de paquetes para decidir a qué altura colocar cada uno de ellos en función de una relación de masa \(\eta\) (asumiendo que el peso está relacionado con la fragilidad). Por lo tanto, definiendo \(P_3^{-}=\{(i,k)\in I^2\text { }|\text { }i\eta \}\) (entonces \(b_{i,k,3}=0\text { }\forall (i,k)\in P_3^{-}\)) y \(P^{-}_6=\ {(i,k)\in I^2\text { }|\text { }i\eta \}\) (entonces \(b_{i ,k,6}=0\text { }\forall (i,k)\in P_6^{-}\)), esta instanciación evita configuraciones donde elementos cuya masa es más de \(\eta\) veces la masa de otros se colocan encima de ellos.

La Figura 4 representa los resultados proporcionados por Q4RealBPP para cada una de las instancias descritas en la Tabla 5. Con respecto al tiempo de ejecución, hemos determinado empíricamente que el tiempo que le toma a LeapCQMHybrid resolver estas instancias es \({30}\,{\textrm {s}}\), presentando un tiempo máximo de acceso a la Unidad de Procesamiento Cuántico (QPU) de \({0.032}\,{\textrm{s}}\) por ejecución. Por último, para los lectores interesados, todos los resultados obtenidos están disponibles gratuitamente33.

(a) Paleta de colores utilizada en los casos resueltos. (b)–(m) Breve descripción de los casos indicados en la Tabla 5 y las soluciones proporcionadas por Q4RealBPP. Las líneas rojas muestran los límites del contenedor. Las restricciones activadas funcionan como se esperaba.

Además de eso, hemos realizado experimentos adicionales con el objetivo de comprender mejor el rendimiento de Q4RealBPP. Para ello, hemos resuelto todos los casos descritos en la Tabla 5 bajo diferentes límites de tiempo. Así, se ejecutaron 10 copias de cada instancia de forma independiente con límites de tiempo establecidos en 5, 10, 30 y 60 s. En la parte superior de la Fig. 5, los resultados obtenidos se muestran usando la media \(\mu\) y la desviación estándar \(\sigma\) del valor de energía \(\{e_i\}_{i=1}^{ 10}\) (donde la energía representa la suma de los valores objetivos a optimizar), siendo \(e_i\) la i-ésima energía devuelta por el solucionador en el límite de tiempo asignado para cada instancia. Además, también se adjunta el tiempo medio de acceso a la QPU en nanosegundos. Como análisis complementario, en la parte inferior de la Fig. 5, dado que las energías devueltas varían considerablemente dependiendo de la naturaleza de la instancia, hemos calculado la desviación alrededor de las energías medias en términos de

para ilustrar más claramente la estabilidad de la solución. Este análisis adicional se muestra en la parte inferior de la Fig. 5.

Se pueden extraer tres conclusiones principales de la Fig. 5: (1) en general, cuanto mayor sea el límite de tiempo dado, menor será la energía devuelta (por lo tanto, mejor será la calidad de la solución); (2) la desviación alrededor de los valores medios de la función objetivo se mantiene estable frente a los diferentes límites de tiempo dados y no muestra una dependencia notable con la naturaleza del caso estudiado; y (3) aunque se le han dado diferentes límites de tiempo al solucionador, el tiempo de acceso a la QPU no varió significativamente para cada uno, lo que indica que el proceso de optimización en el flujo de trabajo LeapCQMHybrid se basa principalmente en el módulo heurístico del solucionador. A pesar del comportamiento claro mostrado por nuestros resultados, se debe trabajar más para tener una comprensión más profunda de cómo funciona el marco presentado.

Arriba: valores medios de energía con su correspondiente desviación estándar para las 10 corridas pertenecientes a cada instancia. De izquierda a derecha en cada instancia, los límites de tiempo dados al solucionador son \({5}\,{\textrm{s}}\), \({10}\,{\textrm{s}}\), \({30}\,{\textrm{s}}\) y \({60}\,{\textrm{s}}\). Los números colocados encima y debajo de las áreas sombreadas muestran el tiempo medio de acceso a la QPU para cada límite de tiempo dentro de cada instancia (en unidades de nanosegundos). Abajo: usando (28), desviación alrededor de la energía media de los resultados mostrados arriba. Para ambas gráficas, el área sombreada muestra la región donde cayeron los valores mínimo y máximo durante el estudio.

En este trabajo hemos presentado Q4RealBPP, un marco cuántico clásico para resolver instancias del mundo real de 3 dBPP. Este software puede ser utilizado fácilmente tanto por usuarios finales como por profesionales para tratar instancias de 3 dBPP considerando restricciones como el peso, la carga, las categorías de paquete y el equilibrio de carga.

Para demostrar la aplicabilidad de Q4RealBPP, lo hemos probado en 12 instancias de diferente naturaleza, con la intención principal de mostrar la capacidad del método para abarcar restricciones del mundo real. Como se muestra en la Fig. 4, Q4RealBPP ha abordado con éxito todas las instancias generadas, contemplando diferentes situaciones del mundo real. Particularmente dignos de mención son los dos últimos casos, 3dBPP_11 y 3dBPP_12 (Fig. 4l, m, respectivamente), donde todas las restricciones están activadas.

El trabajo futuro comprende los siguientes intereses: primero, hemos planeado desarrollar una versión más avanzada de Q4RealBPP para generalizar el marco a otras variantes de BPP y considerar características adicionales como la categorización de elementos en múltiples clases. Además, tenemos la intención de explotar este marco junto con algoritmos complementarios de Inteligencia Artificial para mejorar sus posibles aplicaciones en el mundo real. Finalmente, una comparación exhaustiva entre Q4RealBPP y cualquier método tradicional de inteligencia artificial contribuiría a un análisis más profundo de nuestro marco en términos de solidez de los resultados y tiempos de ejecución. De todos modos, esta valiosa comparación implicaría inevitablemente la implementación de una técnica clásica completamente adaptada al problema de 3 dBPP descrito en este artículo. Por este motivo, hemos fijado esta actuación como trabajo futuro. Como conclusión final, los autores consideran que es necesario seguir trabajando en este sentido, por lo que animamos a los investigadores en este campo a utilizar y adaptar nuestras instancias de evaluación comparativa33 para probar y comparar marcos novedosos y ya existentes.

El código está disponible del autor correspondiente (EO) previa solicitud razonable. Los datos utilizados, así como Q4RealBPP-DataGen y todos los resultados discutidos en este trabajo, están disponibles en http://dx.doi.org/10.17632/y258s6d939.1.

Garey, MR & Johnson, DS Algoritmos de aproximación para problemas de embalaje de contenedores: una encuesta. En Análisis y diseño de algoritmos en optimización combinatoria 147-172 (Springer, 1981).

Capítulo Google Scholar

Munien, C. & Ezugwu, AE Algoritmos metaheurísticos para problemas de embalaje de contenedores unidimensionales: un estudio de los avances y aplicaciones recientes. J. Intel. Sistema. 30, 636–663 (2021).

Google Académico

Delorme, M., Iori, M. & Martello, S. Problemas de embalaje y corte de contenedores: modelos matemáticos y algoritmos exactos. EUR. J. Ópera. Res. 255, 1-20 (2016).

Artículo MathSciNet MATEMÁTICAS Google Scholar

Martello, S., Pisinger, D. & Vigo, D. El problema del embalaje de contenedores tridimensionales. Ópera. Res. 48, 256–267 (2000).

Artículo MathSciNet MATEMÁTICAS Google Scholar

Lodi, A., Martello, S. & Vigo, D. Algoritmos heurísticos para el problema del embalaje de contenedores tridimensionales. EUR. J. Ópera. Res. 141, 410–420 (2002).

Artículo MathSciNet MATEMÁTICAS Google Scholar

Yang, H. & Shi, J. Un algoritmo híbrido de cd/vnd para embalaje de contenedores tridimensionales. En 2010, Segunda Conferencia Internacional sobre Modelado y Simulación por Computadora, vol. 3, 430–434 (IEEE, 2010).

Parreño, F., Alvarez-Valdés, R., Oliveira, J. F. & Tamarit, J. M. A hybrid grasp/vnd algorithm for two-and three-dimensional bin packing. Ann. Oper. Res. 179, 203–220 (2010).

Artículo MathSciNet MATEMÁTICAS Google Scholar

Elhedhli, S., Gzara, F. & Yildiz, B. Embalaje en contenedores tridimensionales y paletización de cajas mixtas. Informa J. Optim. 1, 323–352 (2019).

Artículo MathSciNet Google Scholar

Ramos, AG, Silva, E. & Oliveira, JF Una nueva metodología de equilibrio de carga para problemas de carga de contenedores en el transporte por carretera. EUR. J. Ópera. Res. 266, 1140-1152 (2018).

Artículo MathSciNet MATEMÁTICAS Google Scholar

Paquay, C., Schyns, M. & Limbourg, S. Una formulación de programación entera mixta para el problema de embalaje de contenedores tridimensionales derivado de una aplicación de carga aérea. En t. Trans. Ópera. Res. 23, 187–213 (2016).

Artículo MathSciNet MATEMÁTICAS Google Scholar

Paquay, C., Limbourg, S., Schyns, M. & Oliveira, JF Heurística constructiva basada en Mip para el problema de embalaje de contenedores tridimensionales con restricciones de transporte. En t. J. Prod. Res. 56, 1581-1592 (2018).

Artículo MATEMÁTICAS Google Scholar

Silva, EF, Machado Toffolo, TA & Wauters, T. Métodos exactos para corte y empaque tridimensional: un estudio comparativo sobre problemas de contenedores individuales. Computadora. Ópera. Res. 109, 12-27 (2019).

Artículo MathSciNet MATEMÁTICAS Google Scholar

Lucas, A. Ising formulaciones de muchos problemas de np. Frente. Física. 2, 25 (2014).

Artículo de Google Scholar

Gill, SS y cols. Computación cuántica: taxonomía, revisión sistemática y direcciones futuras. Software. Practica. Exp. 52, 66-114 (2022).

Artículo de Google Scholar

Chandarana, P. et al. Optimización cuántica contradiabática digitalizada y metaaprendizaje. arXiv:2206.09966 (preimpresión de arXiv) (2022).

Huang, T. y otros. Conducción cuántica en tiempo óptimo mediante aprendizaje de circuitos variacionales. arXiv:2211.00405 (preimpresión de arXiv) (2022).

Luckow, A., Klepsch, J. y Pichlmeier, J. Computación cuántica: hacia problemas de referencia de la industria. Digitale Welt 5, 38–45 (2021).

Artículo de Google Scholar

Osaba, E., Villar-Rodriguez, E. & Oregi, I. Una revisión sistemática de la literatura sobre computación cuántica para problemas de enrutamiento. Acceso IEEE 20, 20 (2022).

Google Académico

Orús, R., Mugel, S. & Lizaso, E. Computación cuántica para las finanzas: visión general y perspectivas. Rev. Phys. 4, 100028 (2019).

Artículo de Google Scholar

García-de Andoin, M., Osaba, E., Oregi, I., Villar-Rodríguez, E. & Sanz, M. Heurística híbrida cuántica-clásica para el problema del embalaje de contenedores. En Actas del Compañero de la Conferencia sobre Computación Genética y Evolutiva, 2214–2222 (Asociación de Maquinaria de Computación, 2022).

De Andoin, MG, Oregi, I., Villar-Rodriguez, E., Osaba, E. & Sanz, M. Punto de referencia comparativo de un algoritmo cuántico para el problema del embalaje de contenedores. En 2022, serie de simposios IEEE sobre inteligencia computacional (SSCI), 930–937 (2022).

Bozhedarov, A. et al. Optimización cuántica y de inspiración cuántica para resolver el problema del embalaje mínimo del contenedor. arXiv:2301.11265 (preimpresión de arXiv) (2023).

Layeb, A. & Boussalia, SR Un novedoso algoritmo de búsqueda de cuco de inspiración cuántica para el problema del embalaje de contenedores. En t. J.Inf. Tecnología. Computadora. Ciencia. 4, 58–67 (2012).

Google Académico

Zendaoui, Z. & Layeb, A. Algoritmo de búsqueda de cuco adaptativo para el problema del embalaje de contenedores. En Modelado e implementación de sistemas complejos 107–120 (Springer, 2016).

Capítulo Google Scholar

Layeb, A. & Boussalia, SR Un novedoso algoritmo de búsqueda de cuco inspirado en lo cuántico para el problema de embalaje de contenedores de tamaño variable. En t. J. Matemáticas. Ópera. Res. 6, 732–751 (2014).

Artículo MathSciNet Google Scholar

Zhang, G. Algoritmos evolutivos de inspiración cuántica: una encuesta y un estudio empírico. J. Heurista. 17, 303–351 (2011).

Artículo MATEMÁTICAS Google Scholar

Desarrolladores D-Wave. Medición del rendimiento del solucionador de modelos cuadráticos restringidos por saltos. Tecnología. Representante 14-1065A-A, D-Wave Systems Inc. (2022).

Equipo de desarrolladores de D-Wave Ocean. 3d-bin-packing (repositorio de GitHub) (2022). Consultado por última vez el 27/02/2023.

Preskill, J. Computación cuántica en la era NISQ y más allá. Cuántico 2, 79 (2018).

Artículo de Google Scholar

Dahmani, N. & Krichen, S. Resolución de un problema de equilibrio de carga con un enfoque de optimización de enjambre de partículas multiobjetivo: aplicación al transporte de carga aérea. En t. J. Ópera. Res. 27, 62–84 (2016).

Artículo MathSciNet MATEMÁTICAS Google Scholar

Zhu, R. & Wang, L. Investigación sobre optimización de canales de barcos en tiempo real basada en un algoritmo de equilibrio de carga. En la 29ª Conferencia Internacional de Ingeniería Polar y Oceánica (OnePetro, 2019).

Desarrolladores D-Wave. Solucionador híbrido para modelos cuadráticos restringidos. Tecnología. Representante 14-1055A-A, D-Wave Systems Inc. (2021).

Osaba, E., Villar, E. & V. Romero, S. Conjunto de datos de referencia y generador de instancias para 3dbpp del mundo real. https://doi.org/10.17632/y258s6d939.1 (2023). En línea en Mendeley Data.

Osaba, E., Villar-Rodriguez, E. & Romero, VS Conjunto de datos de referencia y generador de instancias para problemas de empaquetado de contenedores tridimensionales del mundo real. Resumen de datos 20, 109309 (2023).

Artículo de Google Scholar

Descargar referencias

Este trabajo contó con el apoyo del Gobierno Vasco a través del programa HAZITEK (proyecto Q4_Real, ZE-2022/00033), y del CDTI español a través del Programa de Proyectos de I+D Cerveza 2021 (proyecto QOptimiza, 095359) y el Programa Misiones Ciencia e Innovación (CUCO ) bajo la Subvención MIG-20211005.

TECNALIA, Alianza Vasca para la Investigación y la Tecnología (BRTA), 48160, Derio, España

Sebastián V. Rosemary, Eneko Osaba, Esther Villar-Rodríguez, Izaskun Oregi & Yue Ban

EUNEIZ, 01013, Vitoria-Gasteiz, España

Izaskun Oregi

También puedes buscar este autor en PubMed Google Scholar.

También puedes buscar este autor en PubMed Google Scholar.

También puedes buscar este autor en PubMed Google Scholar.

También puedes buscar este autor en PubMed Google Scholar.

También puedes buscar este autor en PubMed Google Scholar.

Todos los autores concibieron la investigación. SVR formuló el problema y desarrolló el código. EVR formuló y desarrolló el generador de instancias. SVR y EO concibieron y realizaron los experimentos. Todos los autores escribieron el manuscrito. Todos los autores revisaron el manuscrito.

Correspondencia a Eneko Osaba.

Los autores declaran no tener conflictos de intereses.

Springer Nature se mantiene neutral con respecto a reclamos jurisdiccionales en mapas publicados y afiliaciones institucionales.

Acceso Abierto Este artículo está bajo una Licencia Internacional Creative Commons Attribution 4.0, que permite el uso, compartir, adaptación, distribución y reproducción en cualquier medio o formato, siempre y cuando se dé el crédito apropiado al autor(es) original(es) y a la fuente. proporcione un enlace a la licencia Creative Commons e indique si se realizaron cambios. Las imágenes u otro material de terceros en este artículo están incluidos en la licencia Creative Commons del artículo, a menos que se indique lo contrario en una línea de crédito al material. Si el material no está incluido en la licencia Creative Commons del artículo y su uso previsto no está permitido por la normativa legal o excede el uso permitido, deberá obtener permiso directamente del titular de los derechos de autor. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by/4.0/.

Reimpresiones y permisos

V. Romero, S., Osaba, E., Villar-Rodríguez, E. et al. Enfoque híbrido para resolver casos de problemas de embalaje de contenedores del mundo real utilizando recocidos cuánticos. Representante científico 13, 11777 (2023). https://doi.org/10.1038/s41598-023-39013-9

Descargar cita

Recibido: 06 de marzo de 2023

Aceptado: 18 de julio de 2023

Publicado: 21 de julio de 2023

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

Cualquier persona con la que compartas el siguiente enlace podrá leer este contenido:

Lo sentimos, actualmente no hay un enlace para compartir disponible para este artículo.

Proporcionado por la iniciativa de intercambio de contenidos Springer Nature SharedIt

Al enviar un comentario, acepta cumplir con nuestros Términos y pautas de la comunidad. Si encuentra algo abusivo o que no cumple con nuestros términos o pautas, márquelo como inapropiado.