Il problema di bin packing 3D (3D-BPP) consiste, dato un insieme di oggetti (item) rettangolari di diverse dimensioni, nel determinare il numero minimo di contenitori rettangolari (bin) identici tra loro necessari per contenere tutti gli oggetti dati. Si suppone che gli oggetti siano inseriti ortogonalmente rispetto ai contenitori e che non possano essere ruotati. Il problema e strettamente NP-hard, poiche e la generalizzazione del problema di bin packing monodimensionale (1D-BPP), che e un problema combinatorio NP-hard.

La diferenza principale tra il caso monodimensionale del problema di bin packing e le sue varianti pluridimensionali e la verica della feasibility (fattibilità, possibilità di realizzazione) del packing: dato un sottoinsieme di oggetti i 2 Iji 2 b; b 2 B, verificare che esista una combinazione tale per cui questi siano inseribili nel bin, senza eccedere le dimensioni dello stesso e senza che essi si sovrappongano o compenetrino. Nel caso del 1-BPP il

problema non si pone dal momento che la permutazione della posizione degli oggetti non influisce sulla misura finale della feasibility (cambiando l’ordine degli addendi, il risultato della somma non cambia). Mentre gia nel caso bidimensionale la combinazione degli oggetti influisce sulla feasibility del packing.

Quindi, in un problema di natura combinatoria, com’e quello di bin packing monodimensionale, si aggiunge un’altra variante di natura combinatoria: la disposizione degli item all’interno di ogni bin.

Un esempio di applicazione è la pianificazione del carico di un automezzo con differenti imballi terziari.