Approccio ibrido per la risoluzione di problemi reali

Rapporti scientifici volume 13, numero articolo: 11777 (2023) Citare questo articolo

418 accessi

2 Altmetrico

Dettagli sulle metriche

L'imballaggio efficiente degli articoli nei contenitori è un compito quotidiano comune. Conosciuto come Bin Packing Problem, è stato intensamente studiato nel campo dell’intelligenza artificiale, grazie al vasto interesse da parte dell’industria e della logistica. Da decenni sono state proposte molte varianti, tra cui il problema dell’imballaggio dei contenitori tridimensionale che è quello più vicino ai casi d’uso del mondo reale. Introduciamo un quadro ibrido quantistico-classico per risolvere problemi di imballaggio dei contenitori tridimensionali nel mondo reale (Q4RealBPP), considerando diverse caratteristiche realistiche, quali: (1) dimensioni del pacco e del contenitore, (2) restrizioni di sovrappeso, (3) affinità tra categorie di articoli e (4) preferenze per l'ordinazione degli articoli. Q4RealBPP consente la risoluzione di casi orientati al mondo reale di 3 dBPP, contemplando restrizioni ben apprezzate dai settori industriale e logistico.

L'ottimizzazione del confezionamento dei prodotti in un numero finito di contenitori è un compito quotidiano cruciale nel campo della produzione e della distribuzione. A seconda delle caratteristiche sia delle confezioni che dei contenitori, possono essere formulati molteplici problemi di imballaggio, generalmente noti come Bin Packing Problems (BPP)1. All'interno di questa categoria, il BPP unidimensionale (1 dBPP) è considerato il più semplice2, il cui obiettivo è imballare tutti gli articoli nel minor numero possibile di contenitori. Sono state proposte molte varianti con un numero variabile di vincoli per affrontare situazioni reali nella logistica e nell'industria3. Il BPP tridimensionale (3 dBPP)4, in cui ogni pacco ha tre dimensioni: altezza, larghezza e profondità, è la variante più conosciuta e più impegnativa. Evidenziato in diversi studi5,6,7, 3 dBPP ha un interesse pratico in molti contesti industriali. Negli ultimi anni, è stato formulato per possedere applicazioni diverse e pratiche come il caricamento di pallet8, il trasporto su strada9, il trasporto aereo di merci10, ecc. A causa della sua complessità, 3 dBPP viene utilizzato frequentemente anche come punto di riferimento per testare metodi e meccanismi di nuova concezione11,12 .

Su un altro fronte, l’informatica quantistica è ancora nella sua fase iniziale ma ha attirato molta attenzione da parte della comunità scientifica poiché offre a ricercatori e professionisti un paradigma rivoluzionario per affrontare diversi tipi di problemi pratici di ottimizzazione13,14,15,16. In particolare, i ricottori quantistici sono stati recentemente applicati a un'ampia varietà di problemi di ottimizzazione ispirati ai campi dell'industria17, della logistica18 e dell'economia19. Tuttavia, la ricerca sul BPP condotta nella comunità quantistica è ancora scarsa, anche se il BPP è stato ampiamente studiato classicamente come problema di ottimizzazione.

Il lavoro pionieristico sul BPP nel campo dell'informatica quantistica presenta un metodo ibrido quantistico-classico per risolvere 1 dBPP20, il cui solutore è composto da due moduli: (1) una subroutine quantistica con cui cercare un insieme di configurazioni ammissibili per riempire una contenitore singolo e (2) un'euristica computazionale classica che costruisce soluzioni complete utilizzando i sottoinsiemi forniti dalla subroutine quantistica. Per approfondire le prestazioni della subroutine quantistica sviluppata, sono stati condotti ulteriori test rispetto a un campionamento casuale e un'euristica basata sul cammino casuale21. Oltre a questi due articoli, un ulteriore studio formula un problema relativo all’industria dell’energia atomica come un problema di 1 dBPP, risolvendolo utilizzando il ricottura quantistica D-Wave22. Un altro lavoro mostra tecniche di calcolo evolutivo di ispirazione quantistica come alternativa per affrontare i problemi relativi al BPP23,24,25. Le tecniche di ispirazione quantistica sono una classe specifica di algoritmi evolutivi che fanno uso della fisica quantistica per definire le loro operazioni e sono progettati per essere eseguiti su un computer classico26. Pertanto, non possono essere eseguiti su nessuna macchina quantistica.

A differenza di 1 dBPP, affrontare 3 dBPP nel dominio quantistico è molto più impegnativo a causa di due motivi correlati: (1) la sua complessità, che aumenta man mano che vengono presi in considerazione i vincoli del mondo reale e (2) lo stato incipiente di sviluppo degli attuali computer quantistici commerciali con capacità ancora limitate da decoerenza ed errori, che potrebbero rappresentare un ostacolo alla risoluzione di problemi altamente vincolati. In questo articolo, presentiamo un framework ibrido di calcolo quantistico-classico per il 3 dBPP orientato al mondo reale, che è coniato come Quantum for Real Bin Packing Problem (Q4RealBPP). Il framework proposto fa ricorso al risolutore ibrido Leap Constrained Quadratic Model (CQM) (LeapCQMHybrid27) di D-Wave. Allo stesso tempo, Q4RealBPP si basa su un codice esistente28. Questo codice di riferimento è un ottimo punto di partenza, che ha aperto la strada a questi due principali contributi sviluppati in questo lavoro: