Abordagem híbrida para resolver problemas reais

Scientific Reports volume 13, Artigo número: 11777 (2023) Citar este artigo

418 Acessos

2 Altmétrico

Detalhes das métricas

A embalagem eficiente de itens em caixas é uma tarefa diária comum. Conhecido como Bin Packing Problem, tem sido intensamente estudado na área de inteligência artificial, graças ao amplo interesse da indústria e da logística. Durante décadas, muitas variantes foram propostas, sendo o problema tridimensional de empacotamento de caixas a mais próxima dos casos de uso do mundo real. Introduzimos uma estrutura híbrida quântica-clássica para resolver problemas tridimensionais de bin packing do mundo real (Q4RealBPP), considerando diferentes características realistas, tais como: (1) dimensões da embalagem e da caixa, (2) restrições de excesso de peso, (3) afinidades entre categorias de itens e (4) preferências para ordenação de itens. Q4RealBPP permite a resolução de instâncias de 3 dBPP orientadas para o mundo real, contemplando restrições bem apreciadas pelos setores industrial e logístico.

A otimização da embalagem de produtos em um número finito de embalagens é uma tarefa diária crucial na área de produção e distribuição. Dependendo das características das embalagens e dos recipientes, múltiplos problemas de embalagem podem ser formulados, geralmente conhecidos como Bin Packing Problems (BPP)1. Dentro desta categoria, o BPP unidimensional (1 dBPP) é considerado o mais simples2, cujo objetivo é acondicionar todos os itens no menor número possível de recipientes. Muitas variantes com um número variável de restrições foram propostas para lidar com situações reais na logística e na indústria3. O BPP tridimensional (3 dBPP)4, em que cada embalagem possui três dimensões: altura, largura e profundidade, é a variante mais conhecida e mais desafiadora. Destacado em diversos estudos5,6,7, 3 o dBPP tem interesse prático em muitos ambientes industriais. Nos últimos anos, foi formulado para possuir aplicações diversas e práticas, como carregamento de paletes8, transporte rodoviário9, carga aérea10, etc. Devido à sua complexidade, o 3 dBPP também é recorrentemente empregado como referência para testar métodos e mecanismos recentemente desenvolvidos11,12 .

Por outro lado, a computação quântica ainda está na sua fase inicial, mas tem atraído muita atenção da comunidade científica, pois oferece aos investigadores e profissionais um paradigma revolucionário para lidar com diferentes tipos de problemas práticos de otimização13,14,15,16. Em particular, os recozidores quânticos foram recentemente aplicados a uma ampla variedade de problemas de otimização inspirados nas áreas da indústria17, logística18 e economia19. No entanto, as pesquisas sobre BPP realizadas na comunidade quântica ainda são escassas, embora o BPP tenha sido amplamente estudado classicamente como um problema de otimização.

O trabalho pioneiro sobre BPP no campo da computação quântica apresenta um método híbrido quântico-clássico para resolver o 1 dBPP20, cujo solucionador é composto por dois módulos: (1) uma sub-rotina quântica com a qual se busca um conjunto de configurações viáveis ​​para preencher um single bin e (2) uma heurística computacional clássica que constrói soluções completas empregando os subconjuntos dados pela sub-rotina quântica. Para aprofundar o desempenho da sub-rotina quântica desenvolvida, novos testes foram realizados contra uma amostragem aleatória e uma heurística baseada em passeio aleatório21. Além desses dois artigos, um estudo adicional formula um problema relacionado à indústria de energia atômica como 1 dBPP, resolvendo-o usando o recozimento quântico D-Wave22. Outros trabalhos mostram técnicas de computação evolutiva de inspiração quântica como uma alternativa para resolver problemas relacionados ao BPP23,24,25. As técnicas de inspiração quântica são uma classe específica de algoritmos evolutivos que fazem uso da física quântica para definir suas operações e são projetadas para serem executadas em um computador clássico26. Assim, eles não podem ser executados em nenhuma máquina quântica.

Em contraste com 1 dBPP, lidar com 3 dBPP no domínio quântico é muito mais desafiador devido a dois motivos relacionados: (1) sua complexidade, que aumenta à medida que as restrições do mundo real são levadas em conta e (2) o estado incipiente de desenvolvimento dos atuais computadores quânticos comerciais com capacidades ainda limitadas por decoerência e erros, o que poderia ser um obstáculo para a resolução de problemas altamente restritos. Neste artigo, apresentamos uma estrutura híbrida de computação quântica clássica para o 3 dBPP orientado para o mundo real, que é cunhado como Quantum for Real Bin Packing Problem (Q4RealBPP). O framework proposto recorre ao Solver Híbrido Leap Constrained Quadratic Model (CQM) (LeapCQMHybrid27) da D-Wave. Ao mesmo tempo, o Q4RealBPP é construído sobre um código existente28. Este código de referência é um excelente ponto de partida, que abriu caminho para estas duas principais contribuições desenvolvidas neste trabalho: