L'obiettivo dei problemi di packing è trovare il modo migliore per pacchettizzare un insieme di articoli di determinate dimensioni in container con packing fisse. Un'applicazione tipica consiste nel caricare le scatole sui furgoni in modo efficiente. Spesso non è possibile imballare tutti gli articoli a causa dei vincoli di capacità. In questo caso, il problema è trovare un sottoinsieme di elementi con dimensione totale massima che rientri nei container.
Esistono molti tipi di problemi di imballaggio. Due dei più importanti sono i problemi con lo zaino e il bin packing.
Problemi con lo zaino
Nel semplice problema dello zaino, c'è un solo container (uno zaino). Gli elementi hanno valori e dimensioni e l'obiettivo è pacchettizzare un sottoinsieme di elementi con un valore totale massimo.
Nel caso speciale in cui il valore sia uguale alla dimensione, l'obiettivo è massimizzare la dimensione totale degli articoli del pacchetto.
OR-Tools fornisce diversi risolutori per i problemi dello zaino nella sua libreria degli algoritmi.
Esistono anche versioni più generali del problema dello zaino. Ecco un paio di esempi:
Problemi multidimensionali sullo zaino, in cui gli articoli hanno più di una quantità fisica, come peso e volume, e lo zaino ha una capacità per ciascuna quantità. In questo caso, il termine dimensione non si riferisce necessariamente alle consuete dimensioni spaziali di altezza, lunghezza e larghezza. Tuttavia, alcuni problemi potrebbero riguardare le dimensioni spaziali, ad esempio l'individuazione del modo ottimale per impacchettare scatole rettangolari in un contenitore rettangolare.
Più problemi con lo zaino, che comprendono più zaini e l'obiettivo è massimizzare il valore totale degli oggetti confezionati in tutti gli zaini.
Tieni presente che puoi avere un problema multidimensionale con un singolo zaino o un problema multidimensionale con una sola dimensione.
Il problema del bin packing
Uno dei problemi di imballaggio più noti è il bin-packing, in cui sono presenti più container (chiamati bin-packing) di pari capacità. A differenza del problema degli zaini multipli, il numero di bin non è fisso. L'obiettivo è trovare il minor numero di fasce che possono contenere tutti gli elementi.
Ecco un semplice esempio per illustrare la differenza tra il problema dello zaino multiplo e il problema del bin packing. Supponiamo che un'azienda abbia dei furgoni per le consegne, ognuno dei quali ha una capacità di carico di 18.000 libbre e 130.000 kg di articoli da consegnare.
Zaino multiplo: hai cinque camion e vuoi caricare un sottoinsieme degli articoli con il peso massimo.
Imballaggio: hai 20 camion (più che sufficienti per contenere tutti gli oggetti) e vuoi usare il minor numero di furgoni che li possa contenere tutti.
Le seguenti sezioni mostrano come risolvere i vari tipi di problemi di imballaggio con OR-Tools, a partire dal problema dello zaino.