CASOS DE USO (2): Computación cuántica en industrias estratégicas

en Casos de usoen Publicado el

CUCO es el primer gran proyecto de computación cuántica a nivel nacional y empresarial. Este proyecto persigue avanzar el estado del arte de algoritmos cuánticos y aplicar ese conocimiento a una serie de pruebas de concepto en distintos sectores estratégicos de la economía española como Energía, Financiero, Espacio, Defensa y Logística. En este contexto, se investigarán casos de uso en observación de la Tierra, la lucha contra el cambio climático y el medioambiente, la trazabilidad de la información en toda la cadena de suministro, la optimización y simulación de cálculos financieros complejos, la inteligencia de señales, entre otros. El proyecto ha sido subvencionado por el CDTI y apoyado por el Ministerio de Ciencia e Innovación bajo el Plan de Recuperación, Transformación y Resiliencia.

Con el objetivo de dar a conocer los avances del proyecto, este artículo es la continuación de una serie de tres artículos dedicados a explicar varios de los casos de uso que han sido seleccionados por los socios del proyecto, y que serán investigados a lo largo de los próximos tres años.

Caso de uso: LOGÍSTICA

Las empresas de logística llevan años trabajando en la optimización de sus rutas de entrega para llegar a un mayor número de clientes en el menor tiempo posible, y con la máxima carga permitida en cada vehículo para reducir los gastos y no generar sobrecostes. Durante la pandemia del Covid-19 hubo un explosivo aumento del número de pedidos online que se encontró con servicios de distribución de mercancías que no dieron abasto para hacer efectivo ese aumento de entregas. La obligación de dar servicio a un mayor número de usuarios, junto con la presión de la reducción de costes, evidenciaron más que nunca la necesidad de tener una estrategia sólida de operaciones de enrutamiento y transporte.

Pero la planificación de rutas es un problema complejo, en el que entran en juego diversas variables con interdependencias entre ellas, y del que Amatech ha extraído dos casos de uso para ser estudiados en el proyecto CUCO: (1) Optimización de rutas indoor (almacenes) y outdoor (puntos de entrega) para mejorar la eficiencia de las flotas de reparto; y (2) Optimización de carga y descarga de camiones.

En el primer caso de uso, existe una necesidad de optimización en términos de sostenibilidad económica (reducción de costes y de tiempo) y medioambiental (reducción de la contaminación asociada) de un conjunto de rutas a realizar por una flota de vehículos localizados usualmente en un punto común (depósito o almacén), que conjuntamente deben dar servicio a un número de clientes geográficamente dispersos. Aquí entran en juego múltiples variables como la disponibilidad de vehículos, la capacidad, el número de puntos de reparto, los plazos y horarios de entrega, la frecuencia de los repartos, etc. 

Este problema pertenece al conjunto denominado Vehicle Routing Problem (VRP), dentro de la Optimización Combinatoria. Son problemas muy conocidos y, a pesar del esfuerzo investigador realizado en los últimos 20 años, incluso los problemas de rutas más básicos son todavía muy difíciles de resolver óptimamente. Además, el tiempo y esfuerzo computacional requerido para resolver este tipo de problemas aumenta exponencialmente respecto al tamaño del mismo (número de variables consideradas), por lo que se busca obtener soluciones aproximadas, aunque no sean las óptimas, para que puedan ser encontradas en un tiempo aceptable.

En el caso de la optimización de carga y descarga de camiones se busca hallar la distribución óptima de los paquetes para aprovechar al máximo el espacio de transporte y ahorrar en cada desplazamiento, mientras se planifica la situación de cada paquete en función de la ruta de entrega y se respetan las normas de apilamiento y seguridad de los paquetes y del vehículo. 

El problema de constituir los mosaicos de cajas en un contenedor tiene muchas soluciones factibles, incluso para los casos más sencillos, y ha sido estudiado desde los años 70 bajo la denominación Bin Packing Problem (BPP). Este problema se incluye dentro de la categoría de problemas NP-duros, cuya complejidad crece exponencialmente con el número de objetos a almacenar, lo que a efectos prácticos implica que no existe procedimiento conocido que permita obtener la solución óptima al problema en cuestión en un tiempo acotado, por lo que en las últimas décadas se ha apostado por los métodos heurísticos que se limitan a dar soluciones factibles cercanas a la óptima, que pueden no ser lo suficientemente buenas.

Mediante la computación cuántica, se espera poder reducir los tiempos de computación necesarios para obtener una solución óptima y, a su vez, modelar los problemas con mayor número de variables o restricciones, lo cual nos permitirá representar de una manera más fiel los casos reales.

Actualmente, existen herramientas o algoritmos puramente cuánticos que se ejecutan solamente en un ordenador cuántico; algoritmos quantum-inspired que se ejecutan en ordenadores clásicos pero que utilizan algunos conceptos de la mecánica cuántica, y algoritmos híbridos cuántico-clásicos que utilizan generalmente un sistema cuántico para resolver una parte del problema y un sistema clásico que va optimizando iterativamente algunos parámetros.

Uno de los algoritmos híbridos que se ha estado investigando es el Quantum Approximate Optimization Algorithm (QAOA), que pertenece al grupo de los algoritmos cuánticos variacionales (VQA). Estos algoritmos utilizan circuitos cuánticos parametrizados que se ejecutan en un ordenador cuántico y usan bucles de aprendizaje clásico para ir mejorando dichos parámetros. Este tipo de algoritmos han sido utilizados previamente en otros trabajos para resolver problemas de optimización, al igual que el problema VRP de nuestro primer caso de uso.

Por otro lado, se ha estado trabajando con el algoritmo puramente cuántico Quantum Annealing (QA). Este algoritmo está principalmente pensado para resolver problemas de optimización y permite encontrar el estado de mínima energía, lo cual sería el equivalente a encontrar el mínimo óptimo para nuestros problemas. En este proyecto se ha utilizado para poder resolver el problema BPP de una dimensión, problema que no había sido resuelto previamente mediante técnicas cuánticas.

Por lo tanto, la aplicación de la computación cuántica a este tipo de problemas puede ser una excelente alternativa para mejorar los parámetros de resolución alcanzados hasta la fecha, a la vez que se erige como un importante reto tecnológico debido a las pocas investigaciones existentes en la actualidad en este ámbito.

Reflexiones sobre las ventajas cuánticas

La computación cuántica tiene el potencial de abordar problemas complejos que son intratables mediante los sistemas de cómputo actuales. Este potencial se ha podido prever a nivel teórico con la propuesta de varios algoritmos cuánticos, como es el algoritmo de Shoro el algoritmo de Grover, entre otros. A estas propuestas teóricas le han seguido varias propuestas de implementaciones hardware, basados en sistemas superconductores, fotónicos o de trampas de iones, y sus correspondientes experimentos, que demuestran la ejecución de una tarea compleja en un dispositivo cuántico en un tiempo mucho menor que lo que tardaría en un sistema clásico o convencional.

Si bien es cierto que estos experimentos han servido como pruebas de concepto para probar lo que generalmente se conoce como ventaja cuántica, el tipo de tareas que atacan son muy artificiales y sin una utilidad práctica aparente. A pesar de los vertiginosos avances en el desarrollo de la ingeniería cuántica, por ahora no se ha logrado demostrar una ventaja cuántica en tareas que se puedan asociar a aplicaciones prácticas y de interés para la industria e investigación. Esto se debe principalmente a un estado inmaduro del hardware, incapaz aún de albergar el número necesario de qubits para codificar un problema lo suficientemente grande y complejo como para que no cuente ya con una solución clásica eficiente. Sin embargo, cada año presenciamos la introducción al mercado de nuevas generaciones de procesadores cuánticos que doblan el número de qubits del año anterior a la vez que mejoran su control y tolerancia a errores. La evolución de la tecnología es tal que estamos llegando a un punto de transición en el que se prevé que las primeras aplicaciones prácticas de esta tecnología estén al caer, llevando el campo a una fase de desarrollo que va más allá del ámbito académico y se preocupa más por la practicidad de la misma y de su comercialización.

Pero entonces, ¿qué es lo que entendemos como ventaja cuántica y cómo la cuantificamos? Dentro del marco de este proyecto de computación cuántica en industrias estratégicas (CUCO) buscamos identificar aquellos casos de uso que pueden llegar a convertirse en aplicaciones prácticas para los sistemas cuánticos. Para ello, el primer paso es definir con mayor precisión el concepto de ventaja cuántica, buscando identificar una métrica clara para evaluar el impacto tanto real como potencial que tienen las distintas propuestas de esta tecnología dentro de la industria para dichos casos de uso. Para ello es fundamental investigar herramientas de evaluación que nos permitan de manera precisa y objetiva comparar el rendimiento computacional de un sistema convencional con un sistema cuántico en la resolución de un problema de las mismas características.

El rendimiento de un ordenador consiste en la cantidad de trabajo útil que puede llevar a cabo el sistema para un conjunto definido de criterios de eficiencia o métricas. Sin embargo, definir medidas de rendimiento computacional con el fin de comparar dos paradigmas de computación tan dispares es una tarea compleja y aún poco desarrollada; por ejemplo, no tiene sentido cuantificar la cantidad de memoria RAM consumida por un proceso cuántico, del mismo modo que no tiene sentido hablar del número de qubits necesarios para la ejecución de un proceso en un ordenador personal. Para definir las métricas adecuadas debemos primero considerar cuáles pueden ser las métricas de mayor interés para las distintas industrias y sus usuarios a la hora de decidir adoptar una tecnología u otra. Uno de los criterios más establecidos dentro del marco económico-social es el análisis coste-eficacia, que evalúa los costes relativos y los resultados asociados a una acción que tiene como fin cumplir un objetivo concreto. Al extrapolar esta idea al contexto de computación podemos identificar tres criterios coste-eficacia principales de los sistemas de computación, clásicos y cuánticos, a la hora de dar solución a un problema de cómputo de interés: el tiempo de ejecución, la precisión del resultado final y el consumo energético. Con el tiempo de ejecución evaluamos el tiempo de disponibilidad del resultado y cuán rápido el usuario puede tomar una decisión o acción dependiendo del mismo. La precisión es un criterio muy relevante para problemas que requieren una gran exactitud en su resultado, evitando al máximo el número de aproximaciones en su resolución. Finalmente, el consumo energético es un criterio de eficiencia que cada vez adopta un papel más importante en una sociedad que busca ser cada vez más sostenible. Para demostrar una ventaja cuántica atractiva para su adopción, la computación cuántica debe superar la clásica en uno o varios de estos tres criterios, demostrando así un menor coste asociado a la resolución de un problema en concreto. Pese a que las predicciones teóricas auguren una ventaja cuántica para las tres métricas, en el proyecto CUCO se están desarrollando herramientas de medida y benchmarks que exploran y comparan las capacidades de varios sistemas, cuánticos y clásicos, con el fin de probar por primera vez de manera clara y objetiva la practicidad que presenta la computación cuántica y con ello su enorme potencial para la sociedad actual.

Autores del artículo:

  • María de la Cruz González López, Research & Development Consultant en AMATECH Group
  • Lander Echevarría Univaso, R&D Technician en AMATECH Group
  • Marta Pascual Estarellas, Senior Quantum Engineer en Qilimanjaro Quantum Tech

Referencias:

  • [1] Cordeau, J. F., Laporte, G., Potvin, J. Y., & Savelsbergh, M. W. (2007). Transportation on demand. Handbooks in operations research and management science, 14, 429-466.
  • [2]  Bräysy, O., & Gendreau, M. (2005). Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transportation science, 39(1), 104-118.
  • [3] Taillard, É., Badeau, P., Gendreau, M., Guertin, F., & Potvin, J. Y. (1997). A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation science, 31(2), 170-186.
  • [4] Yaman, H. (2006). Formulations and valid inequalities for the heterogeneous vehicle routing problem. Mathematical Programming, 106(2), 365-390.
  • [5] Toth, P., & Vigo, D. (2002). VRP with backhauls. In The vehicle routing problem (pp. 195-224). Society for Industrial and Applied Mathematics.
  • [6] Dethloff, J. (2001). Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR-Spektrum, 23(1), 79-96.
  • [7] Cordeau, J. F., Gendreau, M., & Laporte, G. (1997). A tabu search heuristic for periodic and multi‐depot vehicle routing problems. Networks: An International Journal, 30(2), 105-119.
  • [8] Bard, J. F., Huang, L., Jaillet, P., & Dror, M. (1998). A decomposition approach to the inventory routing problem with satellite facilities. Transportation science, 32(2), 189-203.
  • [9] Lawler, E. L. (1985). The traveling salesman problem: a guided tour of combinatorial optimization. Wiley-Interscience Series in Discrete Mathematics.
  • [10] Laporte, G., Toth, P., & Vigo, D. (2013). Vehicle routing: historical perspective and recent contributions. EURO Journal on Transportation and Logistics, 1(2), 1-4
  • [11] Bermeo Muñoz, Elver A. , & Calderón Sotero, Jaime Hernán  (2009). Diseño de un modelo de optimización de rutas de transporte. El Hombre y la Máquina,  (32), 52-67.
  • [12] Khosiawan, Y., Nielsen, I., Do, N. A. D., & Yahya, B. N. (2016). Concept of indoor 3d-route UAV scheduling system. In Information Systems Architecture and Technology: Proceedings of 36th International Conference on Information Systems Architecture and Technology–ISAT 2015–Part I (pp. 29-40). Springer, Cham.
  • [13] Lodi, A., Martello, S., & Vigo, D. (2002). Recent advances on two-dimensional bin packing problems. Discrete Applied Mathematics, 123(1-3), 379-396.
  • [14] Laabadi, S., Naimi, M., El Amri, H., & Achchab, B. (2019, September). A Crow Search-Based Genetic Algorithm for Solving Two-Dimensional Bin Packing Problem. In Joint German/Austrian Conference on Artificial Intelligence (Künstliche Intelligenz) (pp. 203-215). Springer, Cham.
  • [15] López, P. (2019). Introducing an approach based on an advanced hybrid model for the two-dimensional bin packing problem. Annals of Electrical and Electronic Engineering, 2(11), 7-13.
  • [16] Sbai, I., & Krichen, S. (2019, March). A Hybrid PSO-LS approach for solving the Two-Dimensional Bin Packing Problem with weight capacities constraint: A case study. In Proceedings of the 9th International Conference on Information Systems and Technologies (pp. 1-8).
  • [17] Bezerra, V. M., Leao, A. A., Oliveira, J. F., & Santos, M. O. (2019). Models for the two-dimensional level strip packing problem–a review and a computational evaluation. Journal of the Operational Research Society, 1-19.
  • [18] Martello, S., Pisinger, D., & Vigo, D. (2000). The three-dimensional bin packing problem. Operations research, 48(2), 256-267.
  • [19] Oliveira, Ó., Matos, T., & Gamboa, D. (2019, May). Adaptive Sequence-Based Heuristic for the Three-Dimensional Bin Packing Problem. In International Conference on Learning and Intelligent Optimization (pp. 69-76). Springer, Cham.
  • [20] Pugliese, L. D. P., Guerriero, F., & Calbi, R. (2019). Solving a Three-Dimensional Bin-Packing Problem Arising in the Groupage Process: Application to the Port of Gioia Tauro. In A View of Operations Research Applications in Italy, 2018 (pp. 29-40). Springer, Cham.
  • [21] Almeida, R. D., & Steiner, M. T. A. (2016). Resolution of one-dimensional bin packing problems using augmented neural networks and minimum bin slack. International Journal of Innovative Computing and Applications, 7(4), 214-224.
  • [22] Trivella, A., & Pisinger, D. (2016). The load-balanced multi-dimensional bin-packing problem. Computers & Operations Research, 74, 152-164.
  • [23] Polyakovskiy, S., & M’Hallah, R. (2018). A hybrid feasibility constraints-guided search to the two-dimensional bin packing problem with due dates. European Journal of Operational Research, 266(3), 819-839.
  • [24] Delgado, M.C., Cortés, P. Escudero, A., & Muñuzuri, J. (2007). Una búsqueda tabú para el Bin Packing Problem. International Conference on Industrial Engineering & Industrial Management – CIO 2007.
  • [25] Mauricio Sánchez, D., Rojas, A., & Calderón, G. (2008). Un Algoritmo GRASP con dos Parámetros de Relajación para el problema 3D-BIN Packing con Restricciones de Estabilidad. Revista De investigación De Sistemas E Informática, 5(1), 75–85
  • [26] E. Farhi, J. Goldstone, and S. Gutmann, (2014). A Quantum Approximate Optimization Algorithm,” arXiv e-prints, p. arXiv:1411.4028
  • [27] B. K. Behera, P. K. Panigrahi et al., “Solving vehicle routing problem using quantum approximate optimization algorithm,” arXiv preprint arXiv:2002.01351, 2020
  • [28] T. Kato, “On the adiabatic theorem of quantum mechanics,” Journal of the Physical Society of Japan, vol. 5, no. 6, pp. 435–439, 1950
  • [29] M. Garcia-de-Andoin, I. Oregi, E. Villar-Rodriguez, E. Osaba, M. Sanz, (2022) “Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem”, arXiv:2207.07460 [quant-ph]
  • [30] SIAM J.Sci.Statist.Comput. 26 (1997) 1484
  • [31] Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC), May 1996, pages 212-219
  • [32] Annual Review of Condensed Matter Physics 2020 11:1, 369-395
  • [33] Applied Physics Reviews 6, 041303 (2019)
  • [34] Applied Physics Reviews. 6, 021314 (2019)
  • [35] Nature, volume 574, 505–510 (2019), Nature 606, 75–81 (2022)